On the Non-malleability of the Fiat-Shamir Transform

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

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


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.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2012, 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings
Number of pages20
ISBN (Electronic)978-3-642-34931-7
ISBN (Print)978-3-642-34930-0
Publication statusPublished - 2012
Event13th International Conference on Cryptology in India - Indian Statistical Institute, Kolkata, India
Duration: 9 Dec 201212 Dec 2012


Conference13th International Conference on Cryptology in India
Abbreviated titleIndocrypt 2012
Internet address


Dive into the research topics of 'On the Non-malleability of the Fiat-Shamir Transform'. Together they form a unique fingerprint.

Cite this