Paper 2012/704

On the Non-malleability of the Fiat-Shamir Transform

Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi


The Fiat-Shamir transform is a well studied paradigm for removing interaction from public-coin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions. A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. An extended abstract of this paper is published in the proceedings of the 13th International Conference on Cryptology in India, Indocrypt 2012. This is the full version.
non-malleabilityNIZKsimulation soundnessrandom oracle modelFiat-Shamir
Contact author(s)
giorgia marson @ cased de
2012-12-18: received
Short URL
Creative Commons Attribution


      author = {Sebastian Faust and Markulf Kohlweiss and Giorgia Azzurra Marson and Daniele Venturi},
      title = {On the Non-malleability of the Fiat-Shamir Transform},
      howpublished = {Cryptology ePrint Archive, Paper 2012/704},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.