Constant-Round Arguments from One-Way Functions

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.