Paper 2012/704
On the Non-malleability of the Fiat-Shamir Transform
Sebastian Faust, Markulf Kohlweiss, 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
-
CC BY
BibTeX
@misc{cryptoeprint:2012/704,
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},
url = {https://eprint.iacr.org/2012/704}
}