Cryptology ePrint Archive: Report 2012/704

On the Non-malleability of the Fiat-Shamir Transform

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

Abstract: 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.

Category / Keywords: cryptographic protocols / non-malleability, NIZK, simulation soundness, random oracle model, Fiat-Shamir

Publication Info: 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.

Date: received 16 Dec 2012

Contact author: giorgia marson at cased de

Available formats: PDF | BibTeX Citation

Version: 20121218:130656 (All versions of this report)

Discussion forum: Show discussion | Start new discussion