Abstract
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.