Back to Events

Seminar Series

November 17

Quantum Key Leasing for PKE and FHE with a Classical Lessor

Jiahui Liu
University of Texas

Part Of

10:30A
- 12:00P

Location

G-882, Hewlett Room
Add to Calendar 2023-11-17 10:30:00 2023-11-17 12:00:00 America/New_York Quantum Key Leasing for PKE and FHE with a Classical Lessor In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et. al. Eurocrypt' 23, Ananth et. al. TCC' 23), as a strengthened security notion of its predecessor put forward in Ananth et. al. Eurocrypt' 21. This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and then the lessee will be completely deprived of the capability to evaluate. In this work, we construct a secure key leasing scheme to lease a decryption key of a (classical) public-key, homomorphic encryption scheme from standard lattice assumptions. We achieve strong form of security where:* The entire protocol uses only classical communication between a classical leaser (client) and a quantum lessee (server).* Assuming standard assumptions, our security definition ensures that every computationally bounded quantum adversary could not simultaneously provide a valid classical deletion certificate and yet distinguish ciphertexts.Our security relies on the hardness of learning with errors assumption. Our scheme is the first scheme to be based on a standard assumption and satisfying the two properties above.Joint work with Orestis Chardouvelis, Vipul Goyal, Aayush Jain G-882, Hewlett Room

November 03

Private Web Search with Tiptoe

Alexandra Henzinger
CSAIL MIT

Part Of

10:30A
- 12:00P

Location

G882, Hewlett Room
Add to Calendar 2023-11-03 10:30:00 2023-11-03 12:00:00 America/New_York Private Web Search with Tiptoe 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 uses semantic embeddings to reduce the problem of private full-text search to private nearest-neighbor search. 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 on 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). Finally, Tiptoe is extensible: it also supports private text-to-image search and, with minor modifications, it can support private search over audio, code, and more.This talk is based on joint work with Emma Dauterman, Henry Corrigan-Gibbs, and Nickolai Zeldovich.Join Zoom Meetinghttps://mit.zoom.us/j/96066296819 G882, Hewlett Room

October 27

Universal Amplification of KDM Security: From 1-Key to Multi-Key

Daniel Wichs

Part Of

10:30A
- 12:00P

Location

G-882, Hewlett Room
Add to Calendar 2023-10-27 10:30:00 2023-10-27 12:00:00 America/New_York Universal Amplification of KDM Security: From 1-Key to Multi-Key An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the 1-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify 1-key circular to 1-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from 1-key to n-key security for arbitrary n. As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same "galactic inefficiency". Joint work with Brent Waters G-882, Hewlett Room

October 13

Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Assumptions

Alexis Korb
UCLA

Part Of

10:30A
- 12:00P

Location

G-882, Hewlett Room
Add to Calendar 2023-10-13 10:30:00 2023-10-13 12:00:00 America/New_York Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Assumptions The existence of “unstructured” hard languages in NP ∩ coNP is anintriguing open question. Bennett and Gill (SICOMP, 1981) askedwhether P is separated from NP ∩ coNP relative to a random oracle,a question that remained open ever since. While a hard languagein NP ∩ coNP can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist,Bitansky et al. (SICOMP, 2021) ruled out such a construction basedon an injective one-way function, an unstructured primitive that iseasy to instantiate heuristically. In fact, the latter holds even with ablack-box use of indistinguishability obfuscation.We give the first evidence for the existence of unstructured hardlanguages in NP ∩ coNP by showing that if UP ⊈ RP, which followsfrom the existence of injective one-way functions, the answer toBennett and Gill’s question is affirmative: with probability 1 overa random oracle O, we have that PO ≠ NPO ∩ coNPO . Our proofgives a constructive non-black-box approach for obtaining candidatehard languages in NP ∩ coNP from cryptographic hash functions.The above conditional separation builds on a new constructionof non-interactive zero-knowledge (NIZK) proofs, with a computa-tionally unbounded prover, to convert a hard promise problem intoa hard language. We obtain such NIZK proofs for NP, with a uni-formly random reference string, from a special kind of hash functionwhich is implied by (an unstructured) random oracle. This shouldbe contrasted with previous constructions of such NIZK proofs thatare based on one-way permutations or other structured primitives,as well as with (computationally sound) NIZK arguments in therandom oracle model.Join Zoom Meetinghttps://mit.zoom.us/j/99316064630 G-882, Hewlett Room