Where: 17th floor seminar room at BU’s new Center for Computing and Data Sciences, 665 Commonwealth Ave, Boston MA 02215.
Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs
Program:
9:30 – 10:00
Welcome and Breakfast
10:00 – 11:00
Eran Tromer (Columbia) Oblivious Message Retrieval
11:30 – 12:30
Noga Amit (Weizmann)
Constant-round Arguments from One-way Functions
12:30 – 2:00
Lunch (provided)
2:00 – 3:00
Jiahui Liu (UT Austin) Collusion-Resistant Copy-Protection for Watermarkable Functionalities
3:30 – 4:30
James Bartusek (UC Berkeley) Obfuscation of Pseudo-Deterministic Quantum Circuits
Speaker: Eran Tromer (Columbia)
Title: Oblivious Message Retrieval
Abstract:
Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale.
We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding.
Furthermore, the model and constructions generalize to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.
Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers’ cost is ~$1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.
Title: Constant-round Arguments from One-way Functions
Abstract: We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of P, such as depth-bounded computations. Kilian’s celebrated work [STOC 1992] provides such 4-message arguments for P (actually, for NP) using collision-resistant hash functions. We show that one-way functions suffice for obtaining constant-round arguments of almost-linear verification time for languages in P that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian’s) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time. Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear communication (or verification) complexity are not known even for NC (indeed, even for AC^1).
Based on joint work with Guy Rothblum.
Speaker: Jiahui Liu (UT Austin)
Title: Collusion-Resistant Copy-Protection for Watermarkable Functionalities
Abstract: Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under “1 -> 2 attacks”: the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model. Our results are twofold:
(*) The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO’ 21). In the literature, watermarking decryption, digital signature schemes and PRFs have been extensively studied. For the first time, we show that digital signature schemes can be copy-protected. Together with the previous work on copy-protection of decryption and PRFs by Coladangelo et al. (CRYPTO’ 21), it suggests that many watermarkable functionalities can be copy-protected, partially answering the above open question by Aaronson et al.
(*) We make all the above schemes (copy-protection of decryption, digital signatures, and PRFs) k bounded collusion resistant for any polynomial k, giving the first bounded collusion resistant copy-protection for various functionalities in the plain model.
Speaker: James Bartusek (UC Berkeley)
Title: Obfuscation of Pseudo-Deterministic Quantum Circuits
Abstract: We will show how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, assuming the quantum hardness of learning with errors. Instantiating the classical oracle with a candidate post-quantum indistinguishability obfuscator, we obtain the first candidate construction of indistinguishability obfuscation for a class of circuits that is powerful enough to implement Shor’s algorithm.
Along the way, we construct a publicly-verifiable classical verification of quantum computation scheme for quantum “partitioning” circuits, which can be used to verify the evaluation procedure of Mahadev’s quantum fully-homomorphic encryption scheme. We achieve this by constructing a type of publicly-decodable “Pauli functional commitment” scheme, which must satisfy a notion of binding against committers that have access to both of the receiver’s standard and Hadamard basis decoding functionalities.
Based on joint work with Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.
Where: 17th floor seminar room at BU’s new CDS building (665 Commonwealth Ave)
Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs
Program:
9:00 – 9:30
Welcome and Breakfast
9:30 – 10:30
Prabhanjan Ananth (UCSB) Cloning Games: A General Framework for Unclonable Primitives
11:00 – 12:00
Fermi Ma (Simons/Berkeley) Commitments to Quantum States
12 – 1:30
Lunch (provided)
1:30 – 2:30
Zhengzhong Jin (MIT) Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
3:00 – 4:00
Sam Hopkins (MIT) Differential Privacy versus Robustness: Black-Box Reductions and Efficient Algorithms
Speaker: Prabhanjan Ananth (UCSB) Title: Cloning Games: A General Framework for Unclonable Primitives
Abstract:
The powerful no-cloning principle of quantum mechanics can be leveraged to achieve interesting primitives, referred to as unclonable primitives, that are impossible to achieve classically. In the past few years, we have witnessed a surge of new unclonable primitives. Understanding the relationship between the different unclonable primitives is still in its nascent stages and moving forward, we need a more systematic study of unclonable primitives.
We introduce a new framework called cloning games. We show that this framework captures many fundamental unclonable primitives such as quantum money, copy-protection, unclonable encryption, single-decryptor encryption and many more. By reasoning about different types of cloning games, we obtain many interesting implications to unclonable cryptography, including the following:
– We obtain the first construction of information-theoretically secure single-decryptor encryption in the one-time setting. – We construct unclonable encryption in the quantum random oracle model based on BB84 states, improving upon the previous work which used coset states. Our work also provides a simpler security proof for the previous work. – We construct copy-protection for single-bit point functions in the quantum random oracle model based on BB84 states, also improving upon the previous work which used coset states, and also achieving a simpler proof. – We obtain an equivalence of copy-protection schemes with respect to different challenge distributions. Similarly, we also obtain an equivalence of single-decryptor encryption schemes with respect to different ciphertext distributions.
En route, we present a new toolkit that enables us to generically use classical techniques to build unclonable primitives.
(Joint work with Fatih Kaleoglu and Qipeng Liu)
Speaker: Fermi Ma (Simons/Berkeley) Title: Commitments to Quantum States
Abstract:
What does it mean to commit to a quantum state? In this talk, I will present a simple, but perhaps counterintuitive answer: a quantum state commitment (QSC) is binding if sending the commitment erases the committed message from the sender’s view. Using this new definition, I will show how to construct the first succinct QSCs, which can be seen as an analog of collision-resistant hashing for quantum messages.
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application is a quantum-communication version of Kilian’s succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
Speaker: Zhengzhong Jin (MIT) Title: Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
Abstract:
Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This “input-length barrier” to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier.
We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits and Turing machines to avoid the brute-force input-by-input check employed in prior works.
– We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length.
– Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook’s Theory PV.
– Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications.
To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.
Joint work with Abhishek Jain.
Speaker: Sam Hopkins (MIT) Title: Differential Privacy versus Robustness: Black-Box Reductions and Efficient Algorithms
Abstract:
I’ll discuss connections between robustness to adversarial corruption and differential privacy in high-dimensional statistical estimation problems; highlights include (1) a black-box reduction from privacy to robustness and (2) the first computationally-efficient algorithms for learning high-dimensional Gaussians privately with nearly-optimal sample complexity (and robustness).
Based on joint works with Kristian Georgiev, Gautam Kamath, Mahbod Majid, and Shyam Narayanan
Organizers: Ran Canetti, Henry Corrigan-Gibbs, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs
Program:
9:00 – 9:30
Welcome and Breakfast
9:30 – 10:30
Benny Applebaum (Tel Aviv University) – video Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
11:00 – 12:00
Rafael Pass (Cornell Tech) – video Leakage-Resilient Hardness v.s. Randomness
12 – 1:30
Lunch (provided)
1:30 – 2:30
Dakshita Khurana (UIUC) – video SNARGs for P from sub-exponential DDH and QR
3:00 – 4:00
Wei-Kai Lin (Northeastern) – video Optimal Single-Server Private Information Retrieval
Speaker: Benny Applebaum (Tel Aviv University) Title: Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
Abstract:
Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality f to the task of securely computing a simpler functionality g. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as {\em privacy}. The special case of a degree-2 encoding g (2MPRE) has recently found several applications to secure multiparty computation (MPC) with either information-theoretic security or making black-box access to cryptographic primitives. Unfortunately, as all known constructions are based on information-theoretic MPC protocols in the plain model, they can only be private with an honest majority.
In this work, we break the honest-majority barrier and present the first construction of general 2MPRE that remains secure in the presence of a dishonest majority. Our construction encodes every n-party functionality f by a 2MPRE that tolerates at most t=2n/3 passive corruptions.
We derive several applications including (1) The first non-interactive client-server MPC protocol with perfect privacy against any coalition of a minority of the servers and up to t of the n clients; (2) Completeness of 3-party functionalities under non-interactive t-private reductions; and (3) A single-round t-private reduction from general-MPC to an ideal oblivious transfer (OT). These positive results partially resolve open questions that were posed in several previous works. We also show that t-private 2MPREs are necessary for solving (2) and (3), thus establishing new equivalence theorems between these three notions. Finally, we present a new approach for constructing fully-private 2MPREs based on multi-round protocols in the OT-hybrid model that achieve *perfect privacy* against *active* attacks. Moreover, by slightly restricting the power of the active adversary, we derive an equivalence between these notions. This forms a surprising and quite unique connection between a non-interactive passively-private primitive to an interactive actively-private primitive.
Based on joint work with Yuval Ishai, Or Karni, and Arpita Patra.
Speaker: Rafael Pass (Cornell Tech) Title: Leakage-Resilient Hardness v.s. Randomness
Abstract:
A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated “hardness v.s. randomness” paradigm pioneered by Blum-Micali (SIAM JoC’84), Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness assumptions under which prBPP = prP, but these hardness assumptions are not known to also be necessary for such derandomization.
In this work, following the recent work by Chen and Tell (STOC’20) that considers “almost-all-input” hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider “almost-all-input” *leakage-resilient hardness* of a function f—that is, hardness of computing f(x) even given, say, sqrt(|x|) bits of leakage of f(x). We show that leakage-resilient hardness characterizes derandomization of prBPP (i.e., gives a both *necessary* and *sufficient* condition for derandomization). In more detail, we show that there exists a constant c such that the following are equivalent:
prBPP = P;
Existence of a poly-time computable function f : {0, 1}^n -> {0,1}^n that is almost-all-input leakage-resilient hard with respect to n^c-time probabilistic algorithms.
Our characterization naturally extends also to the low-end derandomization regime, to derandomization of MA, and also to average-case derandomization, by appropriately weakening the requirements on the function f.
Joint work with Yanyi Liu
Speaker: Dakshita Khurana (UIUC) Title: SNARGs for P from sub-exponential DDH and QR
Abstract:
Abstract: We will describe a construction of publicly-verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computations from group-based assumptions, without relying on pairings. In particular, assuming the sub-exponential hardness of both the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the size of the instance: 1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime (n+S).T^{o(1)} 2. A SNARG for any language that can be decided in deterministic time T with communication complexity and verifier runtime n.T^{o(1)}.
Speaker: Wei-Kai Lin (Northeastern) Title: Optimal Single-Server Private Information Retrieval
Abstract:
In this talk, we present a single-server Private Information Retrieval (PIR) scheme, which allows a client to privately query the database from the server. Our construction achieves optimal bandwidth and server computation (up to poly-logarithmic factors), assuming the hardness of the Learning With Errors (LWE) problem.
In the setting of single-server PIR, the server stores an n-bit database, and the client wants to query some bits in the database privately and adaptively so that the server learns nothing about the indices of the queried bits. Our scheme uses ~O(√n) client storage, but it achieves amortized ~O(√n) server and client computation and ~O(1) bandwidth per query, and completes in a single roundtrip, where the ~O notation hides a security parameter and poly-logarithmic factor. In particular, we achieve a significant reduction in bandwidth over the state-of-the-art scheme by Corrigan-Gibbs, Henzinger, and Kogan (Eurocrypt’22): their scheme requires as much as ~O(√n) bandwidth per query, with comparable computational and storage cost as ours. Since they proved that their scheme is nearly optimal in terms of server computation and client storage, our scheme is additionally optimal in bandwidth.
This is a joint work with Mingxun Zhou, Yiannis Tselekounis, and Elaine Shi.
Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage.
We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted.
Along the way, we make several additional contributions:
1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting.
2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically “restored” post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.
Joint work with Nir Bitansky and Yael Kalai.
Speaker: David Wu, UT Austin Title: Batch Arguments for NP and More from Standard Bilinear Group Assumptions
Abstract:
Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a prover to convince a verifier of multiple NP statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance.
In this talk, we introduce a direct approach for constructing batch arguments from standard bilinear map assumptions (e.g., subgroup decision or k-Lin) which avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches. In turn, we obtain the first construction of batch arguments for NP from standard bilinear map assumptions.
As corollaries to our main construction, we also obtain a delegation scheme for RAM programs (i.e., a SNARG for P) as well as an aggregate signature scheme supporting bounded aggregation from standard bilinear map assumptions in the plain model.
Joint work with Brent Waters
Speaker: Rahul Ilango Title: The Minimum Circuit Size Problem: What is it, what’s new, and where might things go?
Title: The Minimum Circuit Size Problem: What is it, what’s new, and where might things go?
Abstract:
In this talk, I will give a broad introduction to the Minimum Circuit Size Problem (and, more generally, the area of “meta-complexity”) and then survey some exciting recent developments. These new developments include: a) equivalences between the existence of one-way functions and average-case hardness of the Minimum Circuit Size Problem, b) worst-case to average-case reductions for NP via meta-complexity, and c) a framework building towards reducing SAT to the Minimum Circuit Size Problem. No prior background on this topic is required!
This survey is based on many works by many authors, including (non-exhaustively): Eric Allender, Lijie Chen, Mahdi Cheraghchi, Shuichi Hirahara, Yanyi Liu, Bruno Loff, Dimitrios Myrisiotis, Igor Oliveira, Rafael Pass, Hanlin Ren, Rahul Santhanam, Harsha Tirumala, Neekon Vafa, and Ilya Volkovich.
Speaker: Alexandra Henzinger, MIT Single-Server Private Information Retrieval with Sublinear Amortized Time
Abstract:
This talk will present new private-information-retrieval protocols in the single-server setting. These schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size.
Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small “hint” about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time—yielding sublinear amortized cost.
Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.
This talk is based on joint work with Henry Corrigan-Gibbs and Dmitry Kogan.
One of the ultimate goals of symmetric-key cryptography is to find a rigorous theoretical framework for building complex cryptographic primitives from small components, such as cryptographic S-boxes. Unfortunately, a fundamental obstacle towards reaching this goal comes from the fact that traditional security proofs cannot get security beyond 1/2^n, where n is the size of the corresponding small component. As a result, prior provably secure approaches — which we call “big-box cryptography” — always made n larger than the security parameter, which led to several problems. Most notably, the design was too coarse to really explain practical constructions, as (arguably) the most interesting design choices happening when instantiating such “big-boxes” were completely abstracted out.
In this work, we introduce a novel paradigm (or heuristic?) for building big objects from small objects, which we call small-box cryptography.
As an illustration, we apply our framework to the analysis of SPN ciphers (e.g, generalizations of AES), getting quite reasonable concrete hardness estimates for the resulting ciphers. We also apply our framework to the design of stream ciphers. Here, however, we focus on the simplicity of the resulting construction, for which we also managed to find a direct “big-box”-style security justification, under a well-studied and widely believed eXact Linear Parity with Noise (XLPN) assumption.
Overall, we hope that our work might initiate new follow-up results in the area of small-box cryptography.
Joint work with Harish Karthikeyan and Daniel Wichs.
Speaker: Guy Bresler Title: Average-Case Reductions Amongst Statistical Problems
Abstract:
In this talk I will describe a few simple average-case reduction techniques and use these techniques to show how the computational phase transitions in a variety of statistical problems with widely varying structures all follow from a slight generalization of the planted clique conjecture. Some of these problems are robust sparse linear regression, tensor PCA, and certain dense stochastic block models. The talk is based on joint work with Matthew Brennan (https://arxiv.org/abs/2005.08099).
Speaker: David Heath Title: EpiGRAM: Practical Garbled RAM
Yao’s Garbled Circuit (GC) is a foundational technique for achieving secure multiparty computation (MPC). GC allows two parties to securely compute any Boolean circuit. However, many computations are naturally expressed as RAM programs, not as Boolean circuits. While any RAM program can be polynomially reduced to a circuit, in practice the reduction is often prohibitively expensive.
Garbled RAM (GRAM) is a GC improvement that directly supports random access arrays without adding extra rounds to the GC protocol. Hence, GRAM allows us to securely and directly compute RAM programs. The first non-trivial GRAM (Lu and Ostrovsky, Eurocrypt 2013) required repeated evaluation of a PRF inside GC. Unfortunately, this non-black-box use of a cryptographic primitive is staggeringly expensive. While several subsequent works improved various important aspects of GRAM, no works addressed the central issue: GRAM remained expensive.
In this talk, I will present EpiGRAM, a new construction that dramatically improves GRAM’s efficiency. EpiGRAM improves over prior work by three to four orders of magnitude and opens the door to using GRAM in implementations. Our key insight is a new garbled data structure that we call a lazy permutation network. This data structure allows the garbled circuit to efficiently (and without extra rounds) outsource RAM accesses to the GC evaluator. In this talk, I will present the technical issues inherent to GRAM, and I will show how the lazy permutation network efficiently solves these problems.
EpiGRAM is joint work with Vladimir Kolesnikov (Georgia Tech) and Rafail Ostrovsky (UCLA) and will appear at Eurocrypt 2022.
Speaker: Gabe Kaptchuk Title: Weaving Social Accountability into Cryptographic Protocols
When deployed, cryptographic systems transform from purely technical system into sociotechnical constructs. As a result, cryptographers must take special care that it is possible to keep those who use these cryptographic systems maliciously can be help accountable, by making misuse difficult and detectable. I investigate this problem in the setting of end-to-end encrypted systems. First, I will discuss Abuse Resistant Law Enforcement Access Systems [Eurocrypt21], which studies the problem of constructing law enforcement access systems (ie. government backdoors) that ensure accountability mechanisms in the case of unauthorized surveillance. Second, I will discuss Apple’s recent CSAM scanning proposal, analyzing the system through the lens of accountability.
We are very excited to bring the Boston-area crypto community back together for another in-person crypto day with exciting talks by our own students.
When: *IN-PERSON* Crypto Day on Friday, November 19 at MIT.
Where: MIT Stata Center, Star Auditorium (D-463).
Logistics: Masks are mandatory. Non-MIT visitors: please sign up at this link for a Tim ticket which you need to enter the Stata building. Once you sign up, you will receive a QR code which you can use to activate the elevators and open the doors. If there are any access issues, please contact Debbie Lehto (dlehto@csail.mit.edu). We look forward to seeing you all.
Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.
Program:
9:15-9:30
Welcome and Breakfast
9:30 – 10:30
Alex Lombardi, MIT
10:45 – 11:45
Luowen Qian, Boston University
11:45 – 1:30
Lunch (provided)
1:30 – 2:30
Ari Karchmer, Boston University
2:45 – 3:45
Meghal Gupta, Microsoft Research
4:00 – 5:00
Willy Quach, Northeastern University
Speaker: Alex Lombardi Title: Post-Quantum Zero Knowledge, Revisited
Abstract:
A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary’s state is essential. In this work, we develop new techniques for quantum rewinding in the context of extraction and zero-knowledge simulation:
1) We show how to extract information from a quantum adversary by rewinding it without disturbing its internal state. We use this technique to prove that important interactive protocols, such as the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are zero-knowledge against quantum adversaries.
2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator.
Our results achieve (constant-round) black-box zero-knowledge with negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution:
3) We introduce coherent-runtime expected quantum polynomial time, a computational model that (1) captures all of our zero-knowledge simulators, (2) cannot break any polynomial hardness assumptions, and (3) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the right quantum analogue of classical expected polynomial-time simulation.
Joint work with Fermi Ma and Nicholas Spooner.
Speaker: Luowen Qian Title: Beating Classical Impossibility of Position Verification
Abstract:
We introduce the notion of position verification protocols with classical verifiers, and instantiate such a protocol via adapting the proof of quantumness protocol by Brakerski et al (FOCS’18). As a result, we achieve classically verifiable position verification assuming quantum hardness of Learning with Errors.
Towards establishing the security, we prove that a natural non-local game for noisy trapdoor claw-free functions (NTCFs) are computationally hard assuming the adaptive hardcore bit property, which could be of independent interest.
Joint work with Jiahui Liu and Qipeng Liu.
Speaker: Ari Karchmer Title: Covert Verifiable Learning: How to Learn with an Untrusted Intermediary
Abstract:
In this talk, we introduce and motivate the Covert Verifiable Learning (CVL) framework and survey several results. The CVL framework considers the task of learning a function via oracle queries, where the queries and responses are monitored (and perhaps also modified) by an untrusted intermediary. The goal is twofold: First, to prevent the intermediary from gaining any information about either the function or the learner’s intentions (e.g. the particular hypothesis class the learner is considering). Second, to curb the intermediary’s ability to meaningfully interfere with the learning process, even when it can modify the oracles’ responses.
Among the results described in this talk are the following:
A Covert Learning algorithm in the agnostic setting for decision trees, where a polynomial time eavesdropping adversary that observes all queries and responses learns nothing about either the function, or the learned hypothesis.
A Covert Verifiable Learning algorithm that provides similar learning and privacy guarantees, even in the presence of a polynomial-time adversarial intermediary that can modify all oracle responses. Here the learner is granted additional random examples and is allowed to abort whenever the oracles responses are modified.
Aside theoretical interest, the study of Covert Verifiable Learning is motivated by applications — outlined in this talk — to the outsourcing of automated scientific discovery in molecular biology as well as model extraction attacks.
Joint work with Ran Canetti.
Speaker: Meghal Gupta Title: Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to >1/2 Adversarial Corruption
Abstract:
An important question in coding theory is how to communicate over a noisy channel while being resilient to a maximum fraction of errors. One way this has been studied is via error correcting codes (ECC); in this talk we focus on two interactive generalizations of ECC’s that also address communication over a noisy channel.
In the first setting, only Alice (the sender) has a message she wants to send to Bob (the receiver). Though this can be solved with ECC’s, is there a better solution where Alice and Bob engage in an interactive protocol? We define this new concept as an interactive error correcting code (iECC), and show that for adversarial erasures over a binary channel, iECC’s can be better than ECC’s! The maximal error-resilience of an ECC is 1/2 of the communicated bits; in this talk, we construct an iECC that is resilient to adversarial erasure of 6/11 (>1/2) of the total communicated bits.
In the second setting, both Alice and Bob wish to compute some function f of their private inputs x and y by engaging in a protocol to jointly compute f(x,y). This problem introduced the field of interactive coding in the 90’s, which asks the question: how resilient to adversarial error can we make their protocol? In this talk, we resolve a long-standing problem about binary interactive protocols: what is the best possible error resilience one can achieve? We construct a binary protocol resilient to 1/6 errors, for which a matching impossibility result is known. Before our result, the best construction was resilient to 5/39 errors.
This is based on joint work with Yael Tauman Kalai and Rachel Zhang.
Speaker: Willy Quach Title: Succinct LWE Sampling, Random Polynomials, and Obfuscation
Abstract:
We present a construction of indistinguishability obfuscation (iO) that relies on the learning with errors (LWE) assumption together with a new notion of succinctly sampling pseudorandom LWE samples. We then present a candidate LWE sampler whose security is related to the hardness of solving systems of polynomial equations. Our construction improves on the recent iO candidate of Wee and Wichs (Eurocrypt 2021) in two ways: first, we show that a much weaker and simpler notion of LWE sampling suffices for iO; and secondly, our candidate LWE sampler is secure based on a compactly specified and falsifiable assumption about random polynomials, with a simple error distribution that facilitates cryptanalysis.
Based on joint work with Lalita Devadas, Vinod Vaikuntanathan, Hoeteck Wee and Daniel Wichs.
What: A special *IN-PERSON* crypto day on Friday, July 23 at Northeastern.
We’re very excited to bring the Boston-area crypto community back together for a special in-person crypto day. We can’t wait to see all of you in person again!
Logistics: Masks are optional for fully vaccinated participants and required for everyone else. The talks will be in a large auditorium to give participants plenty of room to socially distance if desired. No food or drinks are allowed in the auditorium. Lunch will be served on the 6th floor in room 655.
Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.
Program:
9:15-9:30
Welcome
9:30 – 10:30
Jon Ullman, Northeastern University The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation (video)
11:00 – 12:00
Hoeteck Wee, NTT Research Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption (video)
12:00 – 1:30
Lunch (provided – in ISEC 655)
1:30 – 2:30
Zhengzhong Jin, Johns Hopkins University SNARGs for P from LWE (video)
3 – 4
Yael Tauman Kalai, MSR and MIT Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs (video)
4:30 – 5:30
Rishab Goyal, MIT Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption (video)
Abstracts:
Speaker: Jon Ullman, Northeastern University Title: The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
Abstract: There has been a recent wave of interest in intermediate trust models for
differential privacy that eliminate the need for a fully trusted central data
collector, but overcome the limitations of local differential privacy. This
interest has led to the introduction of the shuffle model (Cheu et al.,
EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private
model (Dwork et al., ITCS 2010). The message of this line of work is that, for
a variety of low-dimensional problems — such as counts, means, and histograms
— these intermediate models offer nearly as much power as central differential
privacy. However, there has been considerably less success using these models
for high-dimensional learning and estimation problems. In this work, we show
that, for a variety of high-dimensional learning and estimation problems, both
the shuffle model and the pan-private model inherently incur an exponential
price in sample complexity relative to the central model. For example, we show
that, private agnostic learning of parity functions over $d$ bits requires
$Ω(2^{d/2})$ samples in these models, and privately selecting the most
common attribute from a set of $d$ choices requires $Ω(d^{1/2})$ samples,
both of which are exponential separations from the central model. Our work
gives the first non-trivial lower bounds for these problems for both the
pan-private model and the general multi-message shuffle model.
Joint work with Albert Cheu
Speaker: Hoeteck Wee, NTT Research Title: Breaking the sqrt(N) Barrier in Pairing-Based Broadcast Encryption
Abstract: We present the first pairing-based ciphertext-policy attribute-based encryption (CP-ABE) scheme for the class of degree 3 polynomials with compact parameters: the public key, ciphertext and secret keys comprise O(n) group elements, where n is input length for the function. As an immediate corollary, we obtain a pairing-based broadcast encryption scheme for N users with O(N^{1/3})-sized parameters, breaking the long-standing sqrt{N} barrier for pairing-based broadcast encryption. All of our constructions achieve adaptive security against unbounded collusions, and rely on the (bilateral) $k$-Lin assumption in prime-order bilinear groups.
Speaker: Zhengzhong Jin, Johns Hopkins University Title: SNARGs for P from LWE
Abstract: We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For T steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in T. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC’21].
Along the way, we also provide the first construction of non-interactive batch arguments for NP based solely on the LWE assumption.
Based on the joint work with Arka Rai Choudhuri and Abhishek Jain.
Speaker: Yael Tauman Kalai, MSR and MIT Title: Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs
Abstract:
We introduce the notion of a somewhere statistically sound (SSS) interactive argument, which is a hybrid between a statistically sound proof and a computationally sound proof.We show that Kilian’s protocol, instantiated with a computationally non-signaling PCP (Brakerski, Holmgren, and Kalai, STOC 2017) and a somewhere statistically binding hash family (Hubacek and Wichs, ITCS 2015), is an SSS argument. We observe that the first two messages of Kilian, instantiated with these primitives, is a sound instantiation of the BMW heuristic (Kalai, Raz, Rothblum, STOC 2013). Armed with this observation, we show how to efficiently convert any succinct non-interactive argument (SNARG) for BatchNP into a SNARG for any language that has a non-signaling PCP, including any deterministic language and any language in NTISP, using a somewhere statistically binding hash family.
Secondly, we show that the soundness of SSS arguments can be proved in a straight-line manner, implying that they are also post-quantum sound if the underlying assumption is post-quantum secure. This provides a straightforward proof that Kilian’s protocol, instantiated this way, is post-quantum sound under the post-quantum hardness of LWE (though we emphasize that a computationally non-signaling PCP exists only for deterministic languages and for specific subclasses of non-deterministic languages such as NTISP, but not for all of NP). We put forward a natural conjecture that constant-round SSS arguments can be soundly converted into non-interactive arguments via the Fiat-Shamir transformation. We argue that SSS arguments evade the current Fiat-Shamir counterexamples, including the one for Kilian’s protocol (Bartusek, Bronfman, Holmgren, Ma and Rothblum, TCC 2019) by requiring additional properties from both the hash family and the PCP.
This is joint work with Vinod Vaikuntanathan and Rachel Zhang.
Speaker: Rishab Goyal, MIT Title: Dynamic Collusion Bounded Functional Encryption from Identity-Based Encryption
Abstract: Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such \emph{statically} bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system. We initiate the study of \emph{dynamically} bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as:
1) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience. 2) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc. 3) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$.
We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.
joint work with Rachit Garg, George Lu and Brent Waters
Alex Bredariol Grilo (CNRS/Sorbonne) and James Bartusek (UC Berkeley) (double feature with 15 min break in the middle) Secure Computation is in MiniQCrypt
Speaker: Nick Spooner, BU Title: Proof-Carrying Data without Succinct Arguments
Abstract: Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Prior approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this talk I will describe how to obtain PCD without relying on SNARKs. In particular, we construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce.
We then exploit this new framework to achieve a more efficient PCD construction, by giving an accumulation scheme for a non-interactive argument of knowledge for R1CS with constant verification time. Our results are supported by a modular and efficient implementation.
Speaker: Dima Kogan (Stanford) Title: Private Information Retrieval with Sublinear Online Time
Speaker: Alex Bredariol Grilo (CNRS/Sorbonne) and James Bartusek (UC Berkeley) Title: Secure Computation is in MiniQCrypt
Abstract: MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. This talk will show that simulation-secure oblivious transfer is in MiniQCrypt, and thus that secure multi-party computation of any quantum functionality is in MiniQCrypt. The main technical contribution is a construction of extractable and equivocal bit commitment from quantum-secure one-way functions, which is used to instantiate the Bennet-Brassard-Crépeau-Skubiszewska (CRYPTO 91) framework to yield simulation-secure OT.
Abstract: Most types of messages we transmit (e.g., video, audio, images, text)
are not fully compressed, since efficient compression algorithms
can fail to reach the information-theoretic limit. In this
work, we study the transmission of partially compressed messages
over a noisy channel, noting that these messages may have additional
structure that is unused by standard error correcting codes.
We introduce a model in which “well-formed” messages comprise a
small fraction of all strings, and are recognizable. In this model,
we construct a (probabilistic) encoding procedure that achieves
better tradeoffs between data rates and error-resilience (compared to
just applying a standard error correcting code).
Surprisingly, our techniques also yield better tradeoffs in the standard setting
where all binary strings are valid messages.
When: Thursday and Friday, July 30-31. How: A Zoom link was sent to the e-mail list. If you did not receive it, e-mail the organizers to ask for one. Organizers: Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.
Abstract: In this talk, I will present a construction of chosen ciphertext secure public-key encryption from (injective) trapdoor functions. This construction is black box and assumes no special properties (e.g. “lossy”, “correlated product secure”) of the trapdoor function.
Joint work with Susan Hohenberger and Brent Waters [ paper ]
Abstract: The Fiat-Shamir transform is a methodology for compiling a (public-coin) interactive proof system for a language L into a non-interactive argument system for L. In this work, we consider the problem of compiling Pietrzak’s succinct interactive proof system (ITCS 2019) for the iterated squaring problem. We construct a hash function family (with evaluation time roughly 2^{\lambda^\epsilon}) that guarantees the soundness of Fiat-Shamir for this protocol assuming the sub-exponential (2^{-n^{1-\epsilon}})-hardness of the n-dimensional learning with errors problem. (The latter follows from the worst-case 2^{n^{1-\epsilon}} hardness of lattice problems.) More generally, we extend the “bad-challenge function” methodology of Canetti et al. for proving the soundness of Fiat-Shamir to a class of protocols whose bad-challenge functions are not efficiently computable.
As a corollary (following Choudhuri et al., ePrint 2019 and Ephraim et al., EUROCRYPT 2020), we construct hard-on-average problems in the complexity class CLS \subset PPAD under the 2^{\lambda^\epsilon}-hardness of the repeated squaring problem and the 2^{-n^{1-\epsilon}}-hardness of the learning with errors problem. Under the additional assumption that the repeated squaring problem is “inherently sequential”, we also obtain a Verifiable Delay Function (Boneh et al., EUROCRYPT 2018) in the standard model. Finally, we give additional PPAD-hardness and VDF instantiations demonstrating a broader tradeoff between the strength of the repeated squaring assumption and the strength of the lattice assumption.
Abstract: In this work, we show the hardness of finding a Nash equilibrium, a PPAD-complete problem, based on the quasi-polynomial hardness of the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019].Towards this goal, we construct an unambiguous and updatable delegation scheme that is of independent interest.
This delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is unambiguous meaning that it is hard to find two different proofs for the same statement. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, one can efficiently update it into a proof for the statement that the machine reaches the next configuration C’ in T+1 steps.
Abstract: Differential privacy enables rich statistical analyses on data while provably protecting individual-level privacy. The last decade of research has shown that, at least in principle, a number of fundamental statistical tasks are compatible with differential privacy. However, privacy-preserving analyses often require additional complexity over their non-private counterparts, for instance, in terms of the number of data samples one needs to collect in order to get accurate results. In fact, some infinite concept classes that are “easy” to learn in standard computational learning theory become impossible to learn under differential privacy using any finite number of samples.
In this talk, we will describe these impossibility results for private learning and place them in context. We will present a recent characterization of the privately learnable concept classes as exactly those that are learnable in Littlestone’s mistake-bound model of online learning. This equivalence opens new connections between privacy, combinatorics, and stability in learning theory.
Based primarily on work with contributions from Noga Alon, Roi Livni, Maryanthe Malliaris, Shay Moran, Kobbi Nissim, Uri Stemmer, and Salil Vadhan.
Abstract: This talk will address the following question: Assume an untrusted party claims to have used machine learning to learn a classifier for a certain task. In what cases is it cheaper to verify that the proposed classifier is good (in the PAC sense), compared to independently learning a new classifier from scratch?
If verification is significantly cheaper than learning, that could have important practical implications for delegation of machine learning tasks in commercial settings, and might also have consequences for verification of scientific publications, and for AI safety. Two results will be discussed: (1) There exists a learning problem where verification requires quadratically less random samples than are required for learning. (2) The broad class of Fourier-sparse functions (which includes decision trees, for example) can be efficiently verified using random samples only, even though it is widely believed to be impossible to efficiently learn this class from random samples alone.
Jonathan is a PhD student at UC Berkeley. This talk covers joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (Weizmann Institute of Science), and Amir Yehudayoff (Technion-IIT).
Abstract: “Quantum cryptography” uses a quantum communication channel to achieve new functionalities. For example, the unclonability of quantum messages means an attacker cannot both record quantum communication and also pass it along to the recipient. This leads to a form of eavesdropping detection that is central to quantum key distribution.
In this talk, I will discuss some recent work in an emerging area that I call “local quantum cryptography.” Here, all communication channels remain classical, but the various parties leverage local quantum computing to achieve never-before-possible functionalities. Functionalities we achieve include unclonable cryptographic keys, quantum money with classical communication, rate-limited signatures, and more. The central challenge in this area is to take advantage of features of quantum mechanics such as unclonability, even though all “quantumness” is happening locally on the adversary’s device and therefore is entirely under the adversary’s control.
Based on joint works with Ryan Amos, Marios Georgiou, and Aggelos Kiayias
Charles River Crypto Day 
You must be logged in to post a comment.