Cancelled
Security Seminar
This event has been cancelled
November 01
September 27
Seyoon Ragavan: Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
Seyoon Ragavan (MIT)
Add to Calendar
2024-09-27 10:30:00
2024-09-27 12:00:00
America/New_York
Seyoon Ragavan: Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$. As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024). Joint work with Neekon Vafa (MIT) and Vinod Vaikuntanathan (MIT).
32-G882 Hewlett
September 20
Cancelled
Lali Devadas, Batching Adaptively-Sound SNARGs for NP
This event has been cancelled
Cancelled
Seyoon Ragavan: Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
This event has been cancelled
Lali Devadas, Batching Adaptively-Sound SNARGs for NP
Lali Devadas, MIT
Add to Calendar
2024-09-20 10:30:00
2024-09-20 12:00:00
America/New_York
Lali Devadas, Batching Adaptively-Sound SNARGs for NP
A succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement is true with a proof whose size is sublinear in the length of its NP witness. Moreover, a SNARG is adaptively sound if the adversary can choose the statement it wants to prove after seeing the scheme's public parameters. Recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-exponentially secure indistinguishability obfuscation, sub-exponentially secure one-way functions, and polynomial hardness of the discrete log assumption).We consider the batch setting where the prover wants to certify a collection of statements and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of statements. All existing adaptively-sound constructions either require the size of the public parameters to scale linearly with the number of statements or have proof size that scales linearly with the size of a single NP witness. In this work, we show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we can obtain an adaptively-sound SNARG for batch-NP where the size of the proof is poly(k) and the size of the public parameters is poly(k+|C|), where k is a security parameter and |C| is the size of the circuit that computes the associated NP relation.We give two approaches for batching adaptively-sound SNARGs for NP. Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) and avoids relying on a structure like homomorphism.Joint work with Brent Waters (UT Austin and NTT Research) and David J. Wu (UT Austin).
32-G882 Hewlett
September 13
Charles River Crypto Day @ MIT
David Wu, Ran Canetti, Brent Waters and Julia Len
UT Austin, BU, NTT Research, and MIT
Add to Calendar
2024-09-13 9:15:00
2024-09-13 15:00:00
America/New_York
Charles River Crypto Day @ MIT
Program:9:15am–9:30am: Coffee/Welcome 9:30am - 10:30am: David Wu (UT Austin)"Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation"10:45am - 11:45am: Ran Canetti (BU) "Towards general-purpose program obfuscation via local mixing"11:45am - 12:45pm: Lunch (provided)12:45pm - 1:45pm: Brent Waters (NTT Research & UT Austin)"A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors"2:00pm - 3:00pm: Julia Len (MIT)"Recent Developments in Authenticated Encryption"
D463 (Star)
August 16
Yevgeniy Dodis: Perpetual Encryption
Yevgeniy Dodis (New York University)
Add to Calendar
2024-08-16 10:30:00
2024-08-16 12:00:00
America/New_York
Yevgeniy Dodis: Perpetual Encryption
We consider the problem of building a private blockchain (BC) on top of a public one. This has the advantage that users of the private BC do not need to build expensive consensus protocol, while still maintaining privacy. When building this object, we realize the need for a novel encryption scheme we call perpetual encryption (PE), which is a new primitive of independent interest. Very roughly, PE schemes support dynamically changing keys sk_1, sk_2, ... in a way that ciphertext c_n for epoch n:(1) can be efficiently decrypted using any future key sk_n, sk_{n+1},...(2) looks random even given all past keys sk_1,..,sk_{n-1}. We also show how to build an efficient PE from any public-key encryption, hashing and other standard symmetric primitives.
32-G882 Hewlett Room
July 19
Maria Corte Real Santos: Post-quantum secure signature schemes from isogenies
Maria Corte Real Santos (University College London)
Add to Calendar
2024-07-19 10:30:00
2024-07-19 12:00:00
America/New_York
Maria Corte Real Santos: Post-quantum secure signature schemes from isogenies
Most public-key cryptography that is deployed in today’s systems is susceptible to attacks by quantum computers. With increasing investment in the development of large-scale quantum computers, it is important to develop cryptography that is secure against both classical and quantum attacks. Considering this, in 2016, NIST began an effort to standardise post-quantum secure key exchange mechanisms and signature schemes. In this talk, we will focus on signature schemes, and introduce SQIsign, the only isogeny-based signature scheme that was submitted to NISTs recent alternate call for signatures and boasts the smallest combined signature and public key sizes. We will discuss the benefits and drawbacks of SQIsign compared to other post-quantum secure signatures, and present joint work (with Jonathan Komada Eriksen, Michael Meyer and Krijn Reijnders) to obtain faster verification for SQIsign.
32-G882 Hewlett Room
May 31
Cancelled
SEMINAR TRAINING
This event has been cancelled
Alessandro Chiesa: On Succinct Arguments from Ideal Hash Functions
Alessandro Chiesa (EPFL)
Add to Calendar
2024-05-31 10:30:00
2024-05-31 12:00:00
America/New_York
Alessandro Chiesa: On Succinct Arguments from Ideal Hash Functions
Note: Non-standard location (Patil/Kiva G-449)In this talk I will overview recent progress in the theory of succinct arguments in the random oracle model (ROM). Then I will focus on a result showing that well-known constructions of zkSNARKs in the ROM, including constructions used in practice, are secure in the universal composability (UC) framework.
32-G449 STAR/KIVA
May 10
Pseudorandom Error-Correcting Codes
Miranda Christ (Columbia University)
Add to Calendar
2024-05-10 10:30:00
2024-05-10 12:00:00
America/New_York
Pseudorandom Error-Correcting Codes
We construct pseudorandom error-correcting codes (or simply pseudorandom codes), which are error-correcting codes with the property that any polynomial number of codewords are pseudorandom to any computationally-bounded adversary. Efficient decoding of corrupted codewords is possible with the help of a decoding key.We build pseudorandom codes that are robust to substitution and deletion errors, where pseudorandomness rests on standard cryptographic assumptions. Specifically, pseudorandomness is based on either 2^{O(\sqrt{n})}-hardness of LPN, or polynomial hardness of LPN and the planted XOR problem at low density.As our primary application of pseudorandom codes, we present an undetectable watermarking scheme for outputs of language models that is robust to cropping and a constant rate of random substitutions and deletions. The watermark is undetectable in the sense that any number of samples of watermarked text are computationally indistinguishable from text output by the original model. This is the first undetectable watermarking scheme that can tolerate a constant rate of errors.Our second application is to steganography, where a secret message is hidden in innocent-looking content. We present a constant-rate stateless steganography scheme with robustness to a constant rate of substitutions. Ours is the first stateless steganography scheme with provable steganographic security and any robustness to errors.This is based on joint work with Sam Gunn: https://eprint.iacr.org/2024/235
32-G882 Hewlett Room
May 03
Aparna Gupte: How to Construct Quantum FHE, Generically
Aparna Gupte (MIT)
Add to Calendar
2024-05-03 10:30:00
2024-05-03 12:00:00
America/New_York
Aparna Gupte: How to Construct Quantum FHE, Generically
We construct a (compact) quantum fully homomorphic encryption (QFHE) scheme starting from any (classical) fully homomorphic encryption scheme (with decryption in NC^1) together with a dual-mode trapdoor claw-free function family. Compared to previous constructions (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) which made non-black-box use of similar underlying primitives, our construction provides a pathway to instantiations from different assumptions. Our construction uses the techniques of Dulek, Schaffner and Speelman (CRYPTO 2016) and shows how to make the client in their QFHE scheme classical using dual-mode trapdoor claw-free functions. As an additional contribution, we show a new instantiation of dual-mode trapdoor claw-free functions from group actions. This is based on joint work with Vinod Vaikuntanathan.
32-G882 (Hewlett)
April 05
Valerio Cini:: Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
Valerio Cini (NTT Research)
Add to Calendar
2024-04-05 10:30:00
2024-04-05 12:00:00
America/New_York
Valerio Cini:: Lattice-Based SNARKs: Publicly Verifiable, Preprocessing, and Recursively Composable
A succinct non-interactive argument of knowledge (SNARK) allows a prover to produce a short proof that certifies the veracity of a certain NP-statement. In the last decade, a large body of work has studied candidate constructions that are secure against quantum attackers. Unfortunately, no known candidate matches the efficiency and desirable features of (pre-quantum) constructions based on bilinear pairings.In this work, we make progress on this question. We propose the first lattice-based SNARK that simultaneously satisfies many desirable properties: It (i) is tentatively post-quantum secure, (ii) is publicly-verifiable, (iii) has a logarithmic-time verifier and (iv) has a purely algebraic structure making it amenable to efficient recursive composition. Our construction stems from a general technical toolkit that we develop to translate pairing-based schemes to lattice-based ones. At the heart of our SNARK is a new lattice-based vector commitment (VC) scheme supporting openings to constant-degree multivariate polynomial maps, which is a candidate solution for the open problem of constructing VC schemes with openings to beyond linear functions. However, the security of our constructions is based on a new family of lattice-based computational assumptions which naturally generalises the standard Short Integer Solution (SIS) assumption.
32-G882 (Hewlett)
March 22
Learning from Nisan's natural proofs
Ari Karchmer (Boston University)
Add to Calendar
2024-03-22 10:30:00
2024-03-22 12:00:00
America/New_York
Learning from Nisan's natural proofs
In this talk, we will discuss the concept of Natural Proofs of circuit lower bounds (Razborov and Rudich, 1994), and their general relationship to cryptography and computational learning theory. Then, we will dive into some recent progress in the area by highlighting a new technique for extracting efficient distribution-independent learning algorithms or fully-agnostic learning algorithms from a restricted class of Natural Proofs due to Nisan (1993). The new results presented in this talk are based in part on two papers:- Ari Karchmer. Distributional pac-learning from nisan’s natural proofs. In 15th Innovations in Theoretical Computer ScienceConference (ITCS 2024). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2024.- Ari Karchmer. Agnostic membership query learning with nontrivial savings: New results, techniques. In 35th InternationalConference on Algorithmic Learning Theory (ALT 2024). PMLR, 2024.
32-G882 Hewlett Room
March 15
Adaptively Sound Zero-Knowledge SNARKs for UP
Surya Mathialagan, MIT EECS
Add to Calendar
2024-03-15 10:30:00
2024-03-15 12:00:00
America/New_York
Adaptively Sound Zero-Knowledge SNARKs for UP
Abstract:We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class UP in the reusable designated verifier model. UP is an expressive subclass of NP consisting of all NP languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm. Our main results are as follows.1. A reusably and adaptively sound zero-knowledge (zk) dvSNARG for UP, from subexponential LWE and evasive LWE (a relatively new but popular variant of LWE). Our SNARGs achieve very short proofs of length (1 + o(1))λ bits for 2^{-λ} soundness error.2. A generic transformation that lifts any ``Sahai-Waters-like'' (zk) SNARG to an adaptively sound (zk) SNARG, in the designated-verifier setting. In particular, this shows that the Sahai-Waters SNARG for NP is adaptively sound in the designated verifier setting, assuming subexponential hardness of the underlying assumptions. The resulting SNARG proofs have length (1 + o(1))λ bits for 2^{-λ} soundness error. Our result sidesteps the Gentry-Wichs barrier for adaptive soundness by employing an exponential-time security reduction.3. A generic transformation that lifts any adaptively sound (zk) SNARG for UP to an adaptively sound (zk) SNARK for UP, while preserving zero-knowledge. The resulting SNARK achieves the strong notion of black-box extraction. There are barriers to achieving such SNARKs for all of NP from falsifiable assumptions, so our restriction to UP is, in a sense, necessary.Applying (3) to our SNARG for UP from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for UP from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size poly(λ). These are the first SNARK constructions (even in the designated-verifier setting) for a non-trivial subset of NP from (sub-exponentially) falsifiable assumptions.
32-G882 Hewlett Room
February 23
POSTPONED: Adaptively Sound Zero-Knowledge SNARKs for UP
Surya Mathialagan, MIT EECS
Add to Calendar
2024-02-23 10:30:00
2024-02-23 12:00:00
America/New_York
POSTPONED: Adaptively Sound Zero-Knowledge SNARKs for UP
Abstract:We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class UP in the reusable designated verifier model. UP is an expressive subclass of NP consisting of all NP languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm. Our main results are as follows. 1. A reusably and adaptively sound zero-knowledge (zk) dvSNARG for UP, from subexponential LWE and evasive LWE (a relatively new but popular variant of LWE). Our SNARGs achieve very short proofs of length (1 + o(1))λ bits for 2^{-λ} soundness error.2. A generic transformation that lifts any ``Sahai-Waters-like'' (zk) SNARG to an adaptively sound (zk) SNARG, in the designated-verifier setting. In particular, this shows that the Sahai-Waters SNARG for NP is adaptively sound in the designated verifier setting, assuming subexponential hardness of the underlying assumptions. The resulting SNARG proofs have length (1 + o(1))λ bits for 2^{-λ} soundness error. Our result sidesteps the Gentry-Wichs barrier for adaptive soundness by employing an exponential-time security reduction.3. A generic transformation that lifts any adaptively sound (zk) SNARG for UP to an adaptively sound (zk) SNARK for UP, while preserving zero-knowledge. The resulting SNARK achieves the strong notion of black-box extraction. There are barriers to achieving such SNARKs for all of NP from falsifiable assumptions, so our restriction to UP is, in a sense, necessary. Applying (3) to our SNARG for UP from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for UP from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size poly(λ). These are the first SNARK constructions (even in the designated-verifier setting) for a non-trivial subset of NP from (sub-exponentially) falsifiable assumptions.
32-G882 Hewlett Room
February 16
Add to Calendar
2024-02-16 10:30:00
2024-02-16 12:00:00
America/New_York
Unconditionally secure quantum commitments with preprocessing
We demonstrate how to build computationally secure commitment schemes with the aid of quantum auxiliary inputs without unproven complexity assumptions. Furthermore, the quantum auxiliary input can be prepared either (1) efficiently through a trusted setup similar to the classical common random string model, or (2) strictly between the two involved parties in uniform exponential time. Classically this remains impossible without first proving P \neq NP. Based on: https://arxiv.org/abs/2311.18171
32-G882 Hewlett Room
December 15
Add to Calendar
2023-12-15 10:30:00
2023-12-15 12:00:00
America/New_York
Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions
Guruswami and Smith (J. ACM 2016) considered codes for channels that are computationally bounded which modify at most a p-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon’s binary symmetric channel which flips each bit independently with probability p, but weaker than Hamming’s channels which may flip any p-fraction of bits and are computationally unbounded.Recently, there has been a growing body of work that aims to construct codes against channels that are computationally bounded (e.g., bounded memory channels, channels that are poly-size circuits). In this work, we consider bounded size channels and construct codes that:- Achieve an optimal rate of 1-H(p) (matching the rate of binary symmetric channels, and beating the rate of Hamming channels).- Are explicit, assuming E does not have a size 2^Ω(n) nondeterministic circuits.Achieving these codes implies circuit lower bounds (and therefore explicit constructions need to be based on hardness assumptions). This result builds on the recent result by Shaltiel and Silbak (FOCS 2022) that gave a randomized Monte-Carlo construction, rather than explicit codes.A key component in our codes (that we believe to be of independent interest) is a new complexity theoretic notion of hard to sample functions (HTS).Loosely speaking, a function f is HTS for circuits of size n^c, if for every randomized circuit A of size n^c that samples a distribution (X,Y) such that X has sufficiently large min-entropy, it holds that Pr[Y=f(X)] is small.This notion is inspired by a related notion introduced by Viola (SICOMP 2012) in which X is the uniform distribution and is similar in flavor to the definition of multi-collision-resistant hash functions. Building on classical works on “hardness amplification” (and using many additional tools and ideas from pseudorandomness) we construct HTS functions under hardness assumptions.This is a joint work with Ronen Shaltiel.
G-882, Hewlett Room
December 08
Add to Calendar
2023-12-08 10:30:00
2023-12-08 12:00:00
America/New_York
SNARGs, Propositional Proofs, and Local Unsatisfiability
Abstract:We construct a succinct non-interactive argument system for every NP language L that has a propositional proof of non-membership, i.e. that a string x is not in L, and prove it is non-adaptively sound under the LWE assumption. The common reference string in our construction grows with the space required to verify the propositional proof, and the size of the proof grows poly-logarithmically in the length of the propositional proof.Unlike most of the literature on SNARGs, our result implies SNARGs with proof length shorter than logarithmic in the deterministic time complexity of the language. As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption. Our argument system achieves several properties unachievable by related prior work [Sahai-Waters, STOC '14, and Jain-Jin, FOCS '22] such as transparent setup and reliance on a polynomial-time falsifiable assumption. Moreover, our approach departs dramatically from these prior works: we show how to design SNARGs for hard languages without publishing a program (in the CRS) that has the power to verify NP witnesses. At a technical level, we make use of a new notion that we call a ``locally unsatisfiable extension'' of an NP verification circuit C, which is an instance-dependent extension of the circuit C that is ``locally unsatisfiable'' (in the sense of a local assignment generator) for any false statement x.
December 01
Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance
Cody Freitag
Add to Calendar
2023-12-01 10:30:00
2023-12-01 12:00:00
America/New_York
Public-Coin, Complexity-Preserving, Succinct Arguments of Knowledge for NP from Collision-Resistance
Succinct arguments allow a powerful (yet polynomial-time) prover to convince a weak verifier the validity of some mathematical statement using very little communication. A major barrier to the deployment of such proofs is the unwieldy overhead of the prover relative to the complexity of the statement to be proved. Despite over 30 years of progress aiming to minimize the prover's time complexity, the prover's space complexity still remains prohibitively large for existing protocols. In this work, we focus on complexity-preserving arguments where a verifier can be convinced the validity of a non-deterministic time $T$ and space $S$ RAM computation by a RAM prover running in time $\tilde O(T)$ and space $\tilde O(S)$---ignoring polynomial factors in the security parameter.Bitansky and Chiesa (CRYPTO '12) first constructed complexity-preserving succinct arguments of knowledge for NP based on fully homomorphic encryption. However, their protocols require the verifier to maintain private state, so they are not publicly verifiable. Public verifiability is a key property needed for applications of proofs in the distributed, multi-party setting, which have been the driving force behind the modern resurgence of interest into cryptographic proofs. For this reason, Bitansky and Chiesa asked whether public-coin complexity preserving succinct arguments for NP exist from standard cryptographic assumptions. In this work, we resolve this open question positively and provide a construction based solely on the existence of collision-resistant hash functions. This talk is based on joint work with Omer Paneth and Rafael Pass.
G-882 Hewlett Room