**When**: **Crypto Day** on **Friday, April 29**.

**Where: ** Northeastern University, ISEC building (805 Columbus Ave), Room 655 (6th floor)

**Logistics:** Masks are optional for fully vaccinated attendees.

**Organizers:** Ran Canetti, Yael Kalai, Vinod Vaikuntanathan and Daniel Wichs.

### Program:

9:00 – 9:30 | Welcome and Breakfast |

9:30 – 10:30 | Zvika Brakerski, Weizmann Institute, Constructive Post-Quantum Reductions(video) |

11:00 – 12:00 | David Wu, UT Austin Batch Arguments for NP and More from Standard Bilinear Group Assumptions (video) |

12 – 1:30 | Lunch (provided) |

1:30 – 2:30 | Rahul Ilango, MITThe Minimum Circuit Size Problem: What is it, what’s new, and where might things go?(video) |

3:00 – 4:00 | Alexandra Henzinger, MITSingle-Server Private Information Retrieval with Sublinear Amortized Time(video) |

**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 AustinTitle: 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.

You must be logged in to post a comment.