Paper 2018/1004

Fiat-Shamir From Simpler Assumptions

Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, and Ron D. Rothblum


We present two new protocols: (1) A succinct publicly verifiable non-interactive argument system for log-space uniform NC computations, under the assumption that any one of a broad class of fully homomorphic encryption (FHE) schemes has almost optimal security against polynomial-time adversaries. The class includes all FHE schemes in the literature that are based on the learning with errors (LWE) problem. (2) A non-interactive zero-knowledge argument system for NP in the common random string model, assuming almost optimal hardness of search-LWE against polynomial-time adversaries. Both results are obtained by applying the Fiat-Shamir transform with explicit, efficiently computable functions (specifically, correlation intractable functions) to certain classes of interactive proofs. We improve over prior work by reducing the security of these protocols to qualitatively weaker computational hardness assumptions. Along the way, we also show that the Fiat-Shamir transform can be soundly applied (in the plain model) to a richer class of protocols than was previously known.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
alexjl @ mit edu
2018-10-23: last of 2 revisions
2018-10-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Canetti and Yilei Chen and Justin Holmgren and Alex Lombardi and Guy N.  Rothblum and Ron D.  Rothblum},
      title = {Fiat-Shamir From Simpler Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1004},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.