You are looking at a specific version 20121218:130656 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
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.
Keywords
non-malleabilityNIZKsimulation soundnessrandom oracle modelFiat-Shamir
Contact author(s)
giorgia marson @ cased de
History
2012-12-18: received
Short URL
https://ia.cr/2012/704
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.