Unlocking Cryptography: Minimal Assumptions for Constant-Round Arguments 🔐

Guy Rothblum (Apple)
https://simons.berkeley.edu/talks/guy-rothblum-apple-2023-05-01
Minimal Complexity Assumptions for Cryptography

We show that, assuming only the existence of one-way functions, there is a constant-round doubly-efficient argument system with almost-linear verification time for languages that have log-space uniform circuits of linear depth and polynomial size.



Comparing this new result with prior work: known 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]. Kilian's protocol [STOC 1992] works for a richer class of computations (all of P or even all of NP, assuming the prover is given a witness for the input's membership in the language), but it assumes the existence of collision-resistant hash functions.



Joint work with Noga Amit.