Fiat-Shamir: From practice to theory

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

88 Scopus citations


We give new instantiations of the Fiat-Shamir transform using explicit, efficiently computable hash functions. We improve over prior work by reducing the security of these protocols to qualitatively simpler and weaker computational hardness assumptions. As a consequence of our framework, we obtain the following concrete results. 1) There exists 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) There exists a non-interactive zero-knowledge argument system for NP in the common reference string model, under either of the following two assumptions: (i) Almost 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. 3) The classic quadratic residuosity protocol of [Goldwasser, Micali, and Rackoff, SICOMP’89] is not zero knowledge when repeated in parallel, under any of the hardness assumptions above.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)9781450367059
StatePublished - Jun 23 2019
Externally publishedYes
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Cryptographic protocols
  • Delegation of computation
  • Fiat-Shamir heuristic
  • Zero-knowledge protocols


Dive into the research topics of 'Fiat-Shamir: From practice to theory'. Together they form a unique fingerprint.

Cite this