In-person CryptoDay at Northeastern

Friday, April 29, 2022 - 9:00am to 4:00pm
Refreshments: 
Yes
Location: 
Northeastern University
Speaker: 
Zvika Brakerski, David Wu, Rahul IIango, Alexandra Henzinger

Speaker: Zvika Brakerski (Weizmann Institute)
Title: Constructive Post-Quantum Reductions

Abstract:

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.