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.
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 Θ(√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.