Paper 2015/770

A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles

Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, and Ivan Visconti


The Fiat-Shamir (FS) transform uses a hash function to generate, without any further overhead, non-interactive zero-knowledge (NIZK) argument systems from constant-round public-coin honest-verifier zero-knowledge (public-coin HVZK) proof systems. In the proof of zero knowledge, the hash function is modeled as a programmable random oracle (PRO). In TCC 2015, Lindell embarked on the challenging task of obtaining a similar transform with improved heuristic security. Lindell showed that, for several interesting and practical languages, there exists an efficient transform in the non-programmable random oracle (NPRO) model that also uses a common reference string (CRS). A major contribution of Lindell's transform is that zero knowledge is proved without random oracles and this is an important step towards achieving efficient NIZK arguments in the CRS model without random oracles. In this work, we analyze the efficiency and generality of Lindell's transform and notice a significant gap when compared with the FS transform. We then propose a new transform that aims at filling this gap. Indeed our transform is almost as efficient as the FS transform and can be applied to a broad class of public-coin HVZK proof systems. Our transform requires a CRS and an NPRO in the proof of soundness, similarly to Lindell's transform.

Note: This paper will appear in TCC 2016-A.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2016
NIZKFiat-Shamir TransformNPROSigma Protocols
Contact author(s)
ivan visconti @ gmail com
2016-04-20: last of 2 revisions
2015-08-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Giuseppe Persiano and Luisa Siniscalchi and Ivan Visconti},
      title = {A Transform for NIZK Almost as Efficient and General as the Fiat-Shamir Transform Without Programmable Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2015/770},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.