# Friday, Nov 1 at MSR

**When:** Friday, Nov 1, 2019.

**Where:** Microsoft New England Research and Development Center

Abigail Adams room on floor M.

1 Memorial Drive, Cambridge MA 02142.

**Organizers:** Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.

**Thanks:** NSF MACS Project for their generous support.

### Program:

9:30 – 10:00. | Coffee/Breakfast |

10:00 – 11:00. | Fermi Ma, Princeton University On the (In)security of Kilian-Based SNARGs |

11:15 – 12:15. | Giulio Malavolta, Carnegie Mellon University Homomorphic Time-Lock Puzzles |

12:15 – 1:30. | Lunch |

1:30 – 2:30. | Shai Halevi, Algorand Foundation Compressible FHE with Applications to PIR |

2:45 – 3:45. | Noah Stephens-Davidowitz, MITWill lattice-based cryptography be broken in practice? |

4 – 5 | Prashant Vasudevan, UC BerkeleyFormalizing Data Deletion in the Context of the Right to be Forgotten |

### Abstracts:

**Speaker:** Fermi Ma, Princeton University**Title:** On the (In)security of Kilian-Based SNARGs

Abstract: The Fiat-Shamir transform applied to Kilian’s protocol (and its extension to interactive oracle proofs) is at the heart of both theoretical results as well as practical implementations of highly efficient non-interactive proof systems (e.g., SNARKs and STARKs). In this work, we demonstrate significant obstacles to establishing the soundness of this approach. We exhibit a particular (contrived) interactive oracle proof (IOP) for NP for which Fiat-Shamir is unsound for any concrete hash function and any Merkle tree commitment. We also show that if Kilian’s original protocol for PCPs is instantiated with a particular (contrived) Merkle tree commitment and any “natural” PCP, then the Fiat-Shamir transform cannot be soundly applied using any concrete hash function. Put together, our results suggest that provably-secure PCP/IOP-based SNARGs will require a synergistic choice of the PCP/IOP, the Merkle tree commitment, and Fiat-Shamir hash function.

Joint work with James Bartusek, Liron Bronfman, Justin Holmgren, and

Ron D. Rothblum.

**Speaker:** Giulio Malavolta, Carnegie Mellon University **Title:** Homomorphic Time-Lock Puzzles

Abstract: Time-lock puzzles allow one to encrypt messages for the future, by efficiently generating a puzzle with a solution s that remains hidden until time T has elapsed. The solution is required to be concealed from the eyes of any algorithm running in (parallel) time less than T. We put forth the notion of homomorphic time-lock puzzles, where one can evaluate functions over puzzles without solving them, i.e., one can manipulate a set of puzzles with solutions (s1,…,sn) to obtain a puzzle that solves to f(s1,…,sn), for any function f. We give a construction of homomorphic time-lock puzzle for any polynomially-computable function based on standard cryptographic assumptions. Then we discuss how homomorphic time-lock puzzles overcome the limitations of classical time-lock puzzles by proposing new protocols for applications of interest, such as e-voting, multi-party coin flipping, and fair contract signing.

Based on a joint work with Sri Aravinda Krishnan Thyagarajan.

**Speaker:** Shai Halevi, Algorand Foundation**Title:** Compressible FHE with Applications to PIR

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate (1-\epsilon for any \epsilon>0). Moreover, we describe how to compress many Gentry-Sahai-Waters (GSW) ciphertexts (e.g., ciphertexts that may have come from a homomorphic evaluation) into (fewer) high-rate ciphertexts.

Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably less than whole-database AES encryption — specifically about 2.3 mod-q multiplication per database byte, where q is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $\tilde{O}(\log\log k + \log\log\log N)$, where $k$ is the security parameter and $N$ is the number of database files, which are assumed to be sufficiently large.

joint work with Craig Gentry

**Speaker:** Noah Stephens-Davidowitz, MIT**Title**: Will lattice-based cryptography be broken in practice?

Lattice-based cryptography is currently being standardized for widespread use, in anticipation of the development of quantum computers. I.e., we’re going to use this to secure the internet. So, how secure is it really?

I’ll discuss the intimate relationship between lattice-based cryptography and worst-case lattice problems and present both new lower bounds and new algorithmic progress for these problems.

Based on joint works with Divesh Aggarwal, Zvika Brakerski, Huck Bennett, Sasha Golovnev, and Vinod Vaikuntanathan.

**Speaker:** Prashant Vasudevan, UC Berkeley **Title**: Formalizing Data Deletion in the Context of the Right to be Forgotten

The right of an individual to request the deletion of their personal data by an entity that might be storing it — referred to as “the right to be forgotten” — has been explicitly recognized, legislated, and exercised in several jurisdictions across the world, including the European Union, Argentina, and California. However, much of the discussion surrounding this right offers only an intuitive notion of what it means for it to be fulfilled — of what it means for such personal data to be deleted.

In this work, we provide a formal definitional framework for the right to be forgotten using tools and paradigms from cryptography. In particular, we provide a precise definition of what could be (or should be) expected from an entity that collects individuals’ data when a request is made of it to delete some of this data. While it cannot be viewed as expressing the statements of current laws (since these are rather vague in this respect), our work offers technically precise definitions that represent possibilities for what the law could reasonably expect, and alternatives for what future versions of the law could explicitly require.

Finally, with the goal of demonstrating the applicability of our framework and definitions, we consider various natural and simple scenarios where the right to be forgotten comes up. For each of these scenarios, we highlight the pitfalls that arise even in genuine attempts at implementing systems offering deletion guarantees, and also describe technological solutions that provably satisfy our definitions. These solutions bring together techniques built by various communities.

Joint work with Sanjam Garg and Shafi Goldwasser