Abstract
In this talk, we will discuss recent progress on instantiating the Fiat-Shamir heuristic using explicit hash functions. We obtain positive results by either making strong (but simple and meaningful) assumptions or by focusing on round-compressing restricted classes of public-coin interactive proofs.
Our approach yields the following concrete results:
1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under an "optimal security" assumption on a circular-secure variant of LWE.
2) A non-interactive zero-knowledge argument system for NP in the common reference string model, under either of the following two assumptions: (i) optimal hardness of search-LWE against polynomial-time adversaries, or (ii) the existence of a circular-secure FHE scheme with a standard (polynomial time, negligible advantage) level of security.
We will discuss some of the techniques behind these (and related) results as well as challenges and open problems.
This talk is based on joint works with Ran Canetti, Yilei Chen, Justin Holmgren, Guy Rothblum, Ron Rothblum, and Daniel Wichs.