Charles Rive Crypto Day, Friday 12/2 @ BU
Daniel Wichs
When: Friday, Dec 2.
Where: BU’s Barrister Hall (located at the ground floor of the law school tower [map]).
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:
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
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.
Joint work with Sam Gunn, Nathan Ju, and Mark Zhandry.
https://eprint.iacr.org/2022/1358.pdf
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