CryptoDay @ NYU, Friday, Oct 20, 2023

Important: Registration is free but mandatory. Registration deadline: October 19, 2023, 11:59 PM.

Oct 20, 2023 (Friday) at NYU, WWH 109, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.

Program

09:30 – 10:00.	Introduction/Coffee
10:00 – 10:50.	Ethan Mook (Northeastern) Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
11:00 – 11:50.	Zeyu Liu (Yale) Amortized Functional Bootstrapping in less than 7ms, with ~O(1) polynomial multiplications
12:00 – 02:00.	Lunch
02:00 – 02:50.	Emma Dauterman (University of California, Berkeley) Private web search with Tiptoe
03:00 – 03:50.	Hugo Krawczyk (AWS Cryptography) The Joy of Cryptography: A Personal Journey.

Registration Very important: Link

Registration is free but mandatory.
Registration deadline: Oct. 19, 2023, 23:59 (ET).
Only registered participants will be allowed to enter.

Venue

Address: NYU, WWH 109, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.

[Directions] [Google Maps]

Organizers

Fabrice Benhamouda (AWS Cryptography)
Nicholas Genise (Duality Technologies)
Tal Rabin (AWS Cryptography)
with the help and support of Marshall Ball and Yevgeniy Dodis (NYU).

Support

NY CryptoDay is sponsored by Google.

Abstracts

• Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE / Ethan Mook (Northeastern)
  
  Can we design a private variant of “Google search” that would enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a solution to this problem, where users would send their search queries to Google encrypted in a way that allows Google to compute the encrypted search results, without learning anything about the query itself. However, this solution would require Google to run a huge computation that touches the entire content of the Internet to answer each encrypted search query, making it realistically infeasible! Is there a way for Google to preprocess the Internet content into a special data structure that would allow it to answer any encrypted query efficiently by only accessing some small number of locations in the data structure? We give a solution to this problem as a special case of our work.
  
  Concretely, we construct the first schemes for “doubly efficient private information retrieval” and “fully homomorphic encryption in the RAM model” under standard cryptographic hardness assumptions (Ring Learning with Errors). Previously we only had heuristic candidate constructions that only satisfied relaxed variants of these primitives. Our new solutions combine tools from cryptography together with data structures for fast polynomial evaluation (Kedlaya and Umans ’08).
  
  
  
• Amortized Functional Bootstrapping in less than 7ms, with ~O(1) polynomial multiplications / Zeyu Liu (Yale)
  
  Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap n LWE ciphertexts simultaneously, reducing the total cost from ~O(n^2) to ~O(3^ε n^{1+1/ε}) for arbitrary ε > 0. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping.
  
  In this work, we propose a construction that is not only asymptotically efficient (requiring only ~O(n) polynomial multiplications for bootstrapping n LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes about 5 ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes about 6.7ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space. This talk is based on joint work with Yunhao Wang and will be appearing at Asiacrypt’23.
  
  
  
• Private web search with Tiptoe / Emma Dauterman (University of California, Berkeley)
  
  Tiptoe is a private web search engine that allows clients to search over hundreds of millions of documents, while revealing no information about their search query to the search engine’s servers. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require hardware enclaves or non-colluding servers. Tiptoe relies on a co-design of neural information-retrieval algorithms with fast cryptographic protocols: first, Tiptoe uses modern machine-learning techniques to reduce the problem of private full-text search to private nearest-neighbor search, and then Tiptoe implements private nearest-neighbor search with a new, high-throughput protocol based on linearly homomorphic encryption. Running on a 45-server cluster, Tiptoe can privately search over 360 million web pages with 145 core-seconds of server compute, 56.9 MiB of client-server communication (74% of which can occur before the client enters its search query), and 2.7 seconds of end-to-end latency. Tiptoe’s search works best on conceptual queries (“knee pain”) and less well for exact string matches (“123 Main Street, New York”). On the standard MS MARCO search-quality benchmark, Tiptoe ranks the best-matching result in position 7.7 on average. This is worse than a state-of-the-art, non-private neural search algorithm (average rank: 2.3), but is close to the classical tf-idf search algorithm (average rank: 6.7). This talk is based on joint work with Alexandra Henzinger, Henry Corrigan-Gibbs, and Nickolai Zeldovich and will be appearing at SOSP’23.
  
  
  
• The Joy of Cryptography: A Personal Journey. / Hugo Krawczyk (AWS Cryptography)
  
  This is the IACR Distinguished Lecture delivered from Crypto’23.