The Cryptography and Security Seminar regularly hosts talks on theoretical and applied cryptography as well as systems security.
Mailing list: For announcements regarding upcoming seminars, please subscribe to the crypto-security-seminar mailing list.
September 28, 2026, 11am, GDC 6.516
Ertem Nusret Tas
Batch Threshold Encryption: Practical, Weighted, and Post-Quantum
Abstract: Batch threshold encryption enables a committee to publish succinct decryption keys for a set of ciphertexts such that, once a threshold number of these keys is available, exactly that set can be decrypted while all other ciphertexts remain secret. This problem arises in the context of an encrypted mempool, where the goal is to publish a short pre-decryption key that can decrypt all ciphertexts in a block. Existing constructions either rely on epochs or, when epochless, are vulnerable to censorship. They also incur communication proportional to validators’ stakes, require complex MPC protocols for distributed setup, and lack post-quantum security.
In this talk, we address these limitations. First, we present an epochless, censorship-resistant batch threshold encryption scheme with linear-sized public parameters, constant-size pre-decryption keys and ciphertexts, and efficient batch decryption. We then present a weighted batch threshold encryption scheme with an efficient distributed key-generation protocol that avoids the complex MPC setup required by prior constructions. Finally, we construct a new lattice-based threshold batch IBE scheme that is plausibly post-quantum secure.
The talk is based on Efficient Batch Threshold Encryption Using Partial Fraction Techniques (joint work with Dan Boneh, Rohit Nema, and Arnab Roy), Weighted Batch Threshold Encryption with Efficient DKG (joint work with Sasha Frolov, Aditi Partap, and Max Resnick), and Threshold Batch Identity-Based Encryption without Epochs (joint work with Dan Boneh and Evan Laufer).
Bio: Ertem Nusret Tas is a post-doc research associate at a16z Crypto Research. He completed his PhD at Stanford University, advised by Dan Boneh and David Tse. His research interests include blockchains, applied cryptography, and distributed computing.
April 10, 2026, 11am, POB 2.402
Abhishek Jain
Succinct Cryptography via Mathematical Proofs
Abstract: In this talk, I will discuss a recent line of work that leverages mathematical proofs for building advanced cryptographic primitives with low communication. The talk will focus on program obfuscation and succinct non-interactive arguments.
March 23, 2026, 11am, GDC 6.516
Shota Yamada
Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial Abort
Abstract: One of the most popular techniques to prove adaptive security of identity-based encryptions (IBE) and verifiable random functions (VRF) is the partitioning technique. Currently, there are only two methods to relate the adversary's advantage and runtime \( (\varepsilon, \mathsf{T}) \) to those of the reduction's (\( \varepsilon_\mathsf{proof}, \mathsf{T}_\mathsf{proof} \)) using this technique: One originates to Waters (Eurocrypt 2005) who introduced the famous artificial abort step to prove his IBE, achieving \( (\varepsilon_\mathsf{proof}, \mathsf{T}_\mathsf{proof}) = (O(\varepsilon/Q), \mathsf{T} + O(Q^2/\varepsilon^2)) \), where \( Q \) is the number of key queries. Bellare and Ristenpart (Eurocrypt 2009) provide an alternative analysis for the same scheme removing the artificial abort step, resulting in \( (\varepsilon_\mathsf{proof}, \mathsf{T}_\mathsf{proof}) = (O(\varepsilon^2/Q), \mathsf{T} + O(Q)) \). Importantly, the current reductions all loose quadratically in \( \varepsilon \).
In this paper, we revisit this two decade old problem and analyze proofs based on the partitioning technique through a new lens. For instance, the Waters IBE can now be proven secure with \( (\varepsilon_\mathsf{proof}, \mathsf{T}_\mathsf{proof}) = (O(\varepsilon^{3/2}/Q), \mathsf{T} + O(Q)) \), breaking the quadratic dependence on \( \varepsilon \). At the core of our improvement is a finer estimation of the failing probability of the reduction in Waters' original proof relying on artificial abort. We use Bonferroni's inequality, a tunable inequality obtained by cutting off higher order terms from the equality derived by the inclusion-exclusion principle.
Our analysis not only improves the reduction of known constructions but also opens the door for new constructions. While a similar improvement to Waters IBE is possible for the lattice-based IBE by Agrawal, Boneh, and Boyen (Eurocrypt 2010), we can slightly tweak the so-called partitioning function in their construction, achieving \( (\varepsilon_\mathsf{proof}, \mathsf{T}_\mathsf{proof}) = (O(\varepsilon/Q), \mathsf{T} + O(Q)) \). This is a much better reduction than the previously known \( (O(\varepsilon^3/Q^2), \mathsf{T} + O(Q)) \). We also propose the first VRF with proof and verification key sizes sublinear in the security parameter under the standard \( d \)-LIN assumption, while simultaneously improving the reduction cost compared to all prior constructions.
February 17, 2026, 1:30pm, GDC 6.516
Justin Raizes
How to Classically Verify a Quantum Cat Without Killing It
Abstract: Existing protocols for classical verification of quantum computation (CVQC) consume the prover's witness state, requiring a new witness state for each invocation. Because QMA witnesses are not generally clonable, destroying the input witness means that amplifying soundness and completeness via repetition requires many copies of the witness. Building CVQC with low soundness error that uses only one copy of the witness has remained an open problem so far.
We resolve this problem by constructing a CVQC that uses a single copy of the QMA witness, has negligible completeness and soundness errors, and does not destroy its witness. The soundness of our CVQC is based on the post-quantum Learning With Errors (LWE) assumption.
To obtain this result, we define and construct two primitives (under the post-quantum LWE assumption) for non-destructively handling superpositions of classical data, which we believe are of independent interest:
November 18, 2025, 10:00am, GDC 6.302
Daniel Wichs
Detecting and Correcting Computationally Bounded Errors using Cryptography
Abstract: We study the classical problems of error detection and correction under the additional restriction that the channel is computationally bounded. To take advantage of this restriction, we consider seeded codes, where the polynomial-time encoding and decoding procedures share a public random seed. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels. We give results for both large alphabets and the binary alphabet under standard cryptographic assumptions.
Based on joint works with Jad Silbak and George Lu
October 31, 2025, 11:00am, GDC 6.302
Rachel Lin
Succinct Garbling Schemes via Homomorphic Secret Sharing
Abstract: A major challenge in cryptography is the construction of succinct garbling schemes that have asymptotically smaller size than Yao’s garbled circuits, which contain \( \Omega(\lambda) \) bits per gate where \( \lambda \) is the security parameter. We present a new framework for succinct garbling that replaces the heavy machinery of most previous constructions by lighter-weight homomorphic secret sharing techniques.
Concretely, we achieve 1-bit-per-gate (amortized) garbling size for Boolean circuits under circular variants of standard assumptions in composite-order or prime-order groups, as well as a lattice-based instantiation. We further achieve fully succinct garbling schemes where the garbling size is independent of the description size of the programs, for certain simple programs or for circuits but providing only authenticity guarantees.
Our framework opens new avenues toward practical succinct garbling. It features significantly smaller garbling size than Yao's garbled circuits, while being practically efficient, in contrast to previous fully succinct garbling schemes that rely on expensive tools such as iO or a non-black-box combination of FHE and ABE. These features make our framework appealing when a garbled circuit is used as a functional ciphertext that is broadcast or stored in multiple locations (e.g., on a blockchain), in which case communication and storage may dominate computational cost.
Joint work with Yuval Ishai and Hanjun Li.
October 21, 2025, 11:00am, GDC 5.516
Rasoul Mahdavi
InsPIRe: Communication-Efficient PIR with Silent Preprocessing
Abstract: We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication). Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]).
In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query. Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication. Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput. We show that InsPIRe enables improvements across a wide range of applications and database shapes including the InterPlanetary File System and private device enrollment.
At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts. InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices. We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small. To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.
Bio: Rasoul is a fourth-year PhD candidate at the University of Waterloo, advised by Florian Kerschbaum, and a member of the CrySP lab. His research focuses on the design and implementation of secure and private computation protocols tailored for real-world applications. In particular, he works on applications of Homomorphic Encryption and Secure Multi-Party Computation, with a focus on Private Information Retrieval. He has also contributed to projects on Private Set Intersection and Differential Privacy. His work has been published in top-tier venues such as IEEE S&P, USENIX Security, ACM CCS, and NDSS. He has also interned at the Private Computing group at Google where he worked on the next generation of PIR protocols.
October 10, 2025, 11:00am, GDC 6.302
Rahul Ilango
Gödel in Cryptography: Zero-Knowledge Proofs With No Interaction, No Setup, and Perfect Soundness
Abstract: Gödel showed that there are true but unprovable statements. This was bad news for Hilbert, who hoped that every true statement was provable. In this talk, I’ll describe why Gödel’s result is, in fact, good news for cryptography. Specifically, Gödel’s result allows for the following strange scenario: a cryptographic system S is insecure, but it is impossible to prove that S is insecure. As I will explain, in this scenario (defined carefully), S is secure for nearly all practical purposes.
Leveraging this idea, we effectively construct — under longstanding assumptions — a classically-impossible cryptographic dream object: "zero-knowledge proofs for NP with no interaction, no setup, and perfect soundness" (I won’t assume you know what this means!). As an application, our result lets one give an ordinary mathematical proof that a Sudoku puzzle is solvable without revealing how to solve it. Previously, it was not known how to do this.
Paper Link: https://eccc.weizmann.ac.il/report/2025/095/
November 22, 2024, 11:00am, GDC 1.304
Yael Kalai
Classical Commitments to Quantum States
Abstract: We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption. Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was known assuming post-quantum indistinguishability obfuscation.
This is based on joint work with Sam Gunn, Anand Natarajan and Agi Villanyi.
Bio: Rasoul is a fourth-year PhD candidate at the University of Waterloo, advised by Florian Kerschbaum, and a member of the CrySP lab. His research focuses on the design and implementation of secure and private computation protocols tailored for real-world applications. In particular, he works on applications of Homomorphic Encryption and Secure Multi-Party Computation, with a focus on Private Information Retrieval. He has also contributed to projects on Private Set Intersection and Differential Privacy. His work has been published in top-tier venues such as IEEE S&P, USENIX Security, ACM CCS, and NDSS. He has also interned at the Private Computing group at Google where he worked on the next generation of PIR protocols.
November 7, 2024, 11:00am, GDC 7.808
Roy Stracovsky
Enhancing Anamorphic Cryptography
Abstract: Anamorphic cryptography (Persiano, Phan, and Yung, Eurocrypt 2022) allows users who share a “double key” to hide encrypted messages in ciphertexts and signatures to allow covert communication under a hypothetical “dictator” who can monitor all communication or force parties to give up their cryptographic keys in order to check for compliance.
In this talk, I will present joint work with Joseph Jaeger which enhances the security and functionality of anamorphic cryptography. We first enhance the security of anamorphic signatures by proposing two parallel notions of unforgeability (against the aforementioned dictator or instead a recipient) which close gaps in existing definitions termed robustness (Banfi, Gegier, Hirt, Maurer, and Rito, Eurocrypt 2024) and private anamorphism (Kutylowski, Persiano, Phan, Yung, and Zawada, Crypto 2023). Previously proposed anamorphic schemes do not necessarily achieve our new definitions but can sometimes be made to do so by modifying the scheme or by leveraging stronger assumptions on the underlying building blocks.
For our second enhancement, we introduce techniques to stealthily exchange keys via anamorphic cryptosystems, allowing covert communication between users that do not a priori share a double key. We propose and analyze multiple protocols in a four-quadrant security model capturing passive versus active adversaries who may or may not perform key compromise.
October 10, 2024, 2:00pm, GDC 4.516
Surya Mathialagan
Universal SNARGs for NP via Proofs of Completeness
Abstract: In this work, we give new constructions of succinct non-interactive arguments SNARGs for NP in the settings of both non-adaptive and adaptive soundness.
First, we construct a succinct non-interactive argument system (SNARG) for any NP language L, and prove the non-adaptive soundness assuming the security of an FHE scheme, a batch argument (BARG) scheme, as well as the existence of any two-message argument system for L where the prover’s message is succinct, and the completeness property has a polynomial-size Extended Frege proof. Our SNARG is universal in the sense that the construction does not depend on the two-message argument system. The set-up of our SNARG scheme is transparent (i.e. no private randomness). Beyond universality, we note that weaker primitives such as designated verifier SNARGs, and witness encryption both imply such 2-message arguments. Such an amplification of these primitives was not known before.
In the adaptive setting, we also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness.
Our framework yields several corollaries, including:
We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a “best possible SNARG''.
Based on the joint work with Zhengzhong Jin, Yael Tauman Kalai, and Alex Lombardi.
August 6, 2024, 2:00pm, GDC 6.816
Yao-Ching Hsieh
Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices
Abstract: Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC '09; Brakerski–Vaikuntanathan, FOCS '11], there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee, STOC '13; Boneh et al., Eurocrypt '14], only accommodate circuits up to a predetermined depth, akin to leveled homomorphic encryption. In addition, their components (master public key, secret keys, and ciphertexts) have sizes polynomial in the maximum circuit depth. Even in the simpler setting where a single key is published (or a single circuit is involved), the depth dependency persists, showing up in constructions of 1-key ABE and related primitives, including laconic function evaluation (LFE), 1-key functional encryption (FE), and reusable garbling schemes. So far, the only approach of eliminating depth dependency relies on indistinguishability obfuscation. An interesting question that has remained open for over a decade is whether the circular security assumptions enabling FHE can similarly benefit ABE.
In a recent work with Rachel Lin and Ji Luo, we introduce new lattice-based techniques to overcome the depth-dependency limitations. We construct LFE, 1-key FE, 1-key ABE, and reusable garbling schemes capable of evaluating circuits of unbounded depth and size from a standard circular security assumption. We also construct a full-fledged ABE scheme for circuits of unbounded depth and size by additionally relying on the recently proposed evasive LWE assumption.
In this talk, I will detail our technique toward supporting unbounded depth. I will focus on the core gadget of our construction, which is an unbounded depth homomorphic evaluation procedure over attribute-based encodings.
May 2, 2024, 1:30pm, GDC 6.302
Binyi Chen
LatticeFold: A Lattice-Based Folding Scheme and its Applications to Succinct Proof Systems
Abstract: Folding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Our evaluation of the final proof system suggests that it is highly performant while providing post-quantum security. This is a joint work with Dan Boneh.
Bio: Binyi Chen is a postdoc researcher at Stanford University. Previously, he was the Chief Cryptographer at Espresso Systems. He received his PhD from UC Santa Barbara in 2019. From 2018-2019, he was a visiting PhD student at University of Washington. He is broadly interested in post-quantum cryptography and blockchain technology. His recent research has focused on building concretely efficient succinct proof systems for large computation statements. He is the recipient of the Best Paper Award at Eurocrypt 2017 and the co-inventor of many succinct proof systems with broad industry impact, including Hyperplonk and Protostar.
April 12, 2024, 2:00pm, GDC 4.304
Amit Sahai
The Mathematics of Hiding Secrets in Software
Abstract: At least since the initial public proposal of public-key cryptography based on computational hardness conjectures (Diffie and Hellman, 1976), cryptographers have contemplated the possibility of a "one-way compiler" that translates computer programs into "incomprehensible" but equivalent forms. And yet, the search for such a "one-way compiler" remained elusive for decades. In this talk, we look back at our community's attempts to formalize the notion of such a compiler, culminating in our 2001 work with Barak, Goldreich, Impagliazzo, Rudich, Vadhan, and Yang, which proposed the notion of indistinguishability obfuscation (iO). Roughly speaking, iO requires that the compiled versions of any two equivalent programs (with the same size and running time) be indistinguishable to any efficient adversary. The notion of punctured programming, introduced in our work with Waters in 2013, spawned an area of research dedicated to exploring the remarkable power of iO. We'll then discuss the intense effort that recently culminated in our 2021 work with Jain and Lin, finally showing how to construct iO in such a way that, for the first time, we can prove the security of our iO scheme based on well-studied computational hardness conjectures in cryptography.
Bio: Amit Sahai is a Professor of Computer Science and (by courtesy) Mathematics at UCLA, and the incumbent of the Symantec Endowed Chair in Computer Science. He also serves as an Advisor to the Prison Mathematics Project. His primary research interests are in cryptography, coding theory, complexity theory, and security. He is the co-inventor of attribute-based encryption, functional encryption, and indistinguishability obfuscation. He was an invited lecturer at the 2022 International Congress of Mathematicians (ICM 2022, Special Sectional Lecture), and received the 2022 National Academy of Sciences Held Prize for his role in the development of indistinguishability obfuscation. His research works have been recognized by four Test of Time Awards (FOCS 2023, Eurocrypt 2023, Eurocrypt 2020, ACM CCS 2016) and a STOC 2021 Best Paper Award. For his teaching, he was given the 2016 Lockheed Martin Excellence in Teaching Award from the Samueli School of Engineering at UCLA. Many years ago, he was a member of the 1996 World Champion ACM ICPC Team from UC Berkeley. He is also a Simons Investigator (2021), Fellow of the ACM (2018), Fellow of the IACR (2019), and Fellow of the AMS (2024).
February 21, 2024, 2:00pm, GDC 6.302
Lalita Devadas
Rate-1 BARGs via Fully-Local SSB Hash Families
Abstract: In a somewhere statistically binding (SSB) hash family, the hash key is sampled to be statistically binding on some computationally hidden indices. We define and construct a fully-local SSB hash family, in which local openings are succinct and, crucially, can be verified against a succinct digest of the hash value, regardless of how many indices are statistically bound by the hash key. We use this hash family to boost the succinctness of any nontrivial non-interactive batch argument (BARG) scheme to the best possible, given the extractability property we need. This immediately gives us two applications: multi-hop aggregate signatures and incrementally verifiable computation, which prior to this work were only known from non-standard knowledge assumptions or in the random oracle model.
October 27, 2023, 2:15pm, GDC 4.302
Daniel Genkin
Side Channel Attacks: Lessons Learned or Troubles Ahead?
Abstract: The security and architecture communities will remember the past five years as the era of side channels. Starting from Spectre and Meltdown, time and again we have seen how basic performance-improving features can be exploited to violate fundamental security guarantees. Making things worse, the rise of side channels points to a much larger problem, namely the presence of large gaps in the hardware-software execution contract on modern hardware.
In this talk, I will give an overview of this gap, in terms of both security and performance. First, I will give a high-level survey on speculative execution attacks such as Spectre and Meltdown. I will then talk about how speculative attacks are still a threat to both kernel and browser isolation primitives, highlighting new issues on emerging architectures. Next, from the performance perspective, I will discuss new techniques for microarchitectural code optimizations, with an emphasis on cryptographic protocols and other compute-heavy workloads. Here I will show how seemingly simple, functionally equivalent, code modifications can lead to significant changes in the underlying microarchitectural behavior, resulting in dramatic performance improvements.
The talk will be interactive and include attack demonstrations.
Bio: Daniel Genkin is an Alan and Anne Taetle Early Career Associate Professor at the School of Cybersecurity and Privacy at Georgia Tech. Daniel's research interests are in hardware and system security, with particular focus on side channel attacks and defenses. Daniel's work has won the Distinguished Paper Award at IEEE Security and Privacy, an IEEE Micro Top Pick, the Black Hat Pwnie Awards, as well as top-3 paper awards in multiple conferences. Most recently, Daniel has been part of the team performing the first analysis of speculative and transient execution, resulting in the discovery of Spectre, Meltdown and follow ups. Daniel has a PhD in Computer Science from the Technion Israel's Institute of Technology and was a Postdoctoral fellow at the University of Pennsylvania and University of Maryland.
October 18, 2023, 10:30am, GDC 6.302
Srini Devadas
PAC Privacy: Automatic Privacy Measurement and Control of Data Processing
Abstract: We propose and study a new privacy definition, termed Probably Approximately Correct (PAC) Privacy. PAC Privacy characterizes the information-theoretic hardness to recover sensitive data given arbitrary information disclosure/leakage during/after any processing. Unlike the classic cryptographic definition and Differential Privacy (DP), which consider the adversarial (input-independent) worst case, PAC Privacy is a simulatable metric that quantifies the instance-based impossibility of inference. A fully automatic analysis and proof generation framework is proposed: security parameters can be produced with arbitrarily high confidence via Monte-Carlo simulation for any black-box data processing oracle. On the utility side, the magnitude of (necessary) perturbation required in PAC Privacy is not lower bounded by \( \Theta(\sqrt{d}) \) for a \( d \)-dimensional release but could be \( O(1) \) for many practical data processing tasks, which is in contrast to the input-independent worst-case information-theoretic lower bound. We discuss applications of PAC Privacy to statistical data processing tasks.
Joint work with Hanshen Xiao.
Bio: Srini Devadas is the Webster Professor of EECS at the Massachusetts Institute of Technology, where he has been on the faculty since 1988. Devadas's current research interests are in computer architecture, computer security, and applied cryptography. In 2021, he received the IEEE Cybersecurity Award for Practice, and the ACM SIGSAC Award for Outstanding Innovation for his work on secure hardware. Devadas is a MacVicar Faculty Fellow and an Everett Moore Baker teaching award recipient, considered MIT's two highest undergraduate teaching honors.
October 13, 2023, 2:15pm, GDC 4.302
Henry Corrigan-Gibbs
Private Web Search with Tiptoe
Abstract: This talk will present Tiptoe, a new privacy-preserving search engine. A Tiptoe client can perform a full-text search over hundreds of millions of web pages while revealing no information about its search query to the search engine's servers. Tiptoe's privacy guarantee is based on cryptography alone; it does not require any trusted hardware or non-colluding servers. Tiptoe first uses modern machine-learning techniques to reduce the problem of private full-text search to private nearest-neighbor search, and then it implements private nearest-neighbor search using a new high-throughput cryptographic protocol.
On a 45-server cluster, Tiptoe can privately search over 360 million web pages with 29 core-seconds of server computation, 14.7 MiB of client-server communication, and 2.8 seconds of end-to-end latency. Performing private searches over this data set requires the client to store a 1.19 GiB data structure. Tiptoe's search works best on conceptual queries ("chocolate cake recipe") and less well on exact-string-match queries ("123 Main Street, New York"). On the standard MS MARCO search-quality benchmark, Tiptoe ranks the best-matching result in position 6 on average. This is worse than a state-of-the-art non-private search algorithm (average rank: 2.3), and is comparable to the classical tf-idf search algorithm (average rank: 6). Finally, unlike existing systems for private search, Tiptoe is extensible: beyond private text search, it also supports image search and, with only minor modifications, it can support private search over audio, code, and more.
This talk is based on an SOSP 2023 paper (to appear) that is joint work with Alexandra Henzinger (MIT), Emma Dauterman (UC Berkeley), and Nickolai Zeldovich (MIT).
Bio: Henry Corrigan-Gibbs (he/him) is an assistant professor at MIT in the Department of Electrical Engineering and Computer Science. Henry builds computer systems that provide strong security and privacy properties using ideas from cryptography, computer security, and computer systems. Henry completed his PhD in the Applied Cryptography Group at Stanford, where he was advised by Dan Boneh. After that, he was a postdoc with Bryan Ford at EPFL.
Henry holds the Douglas Ross Career Development Professorship of Software Technology. He has received the MIT EECS Jerome Saltzer Award for Excellence in Teaching Recitation Sections (2023), an Honorable Mention for the ACM Doctoral Dissertation Award (2020), three IACR Best Young Researcher Paper Awards, the Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies (2016), and an IEEE Security and Privacy Distinguished Paper Award (2015). Henry's work has influenced IETF and NIST standards, and his Prio system for privacy-preserving telemetry data collection is used in Apple's iOS and Google's Android operating systems.