[FKMV12] On the Non-malleability of the Fiat-Shamir Transform

Authors: Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, Daniele Venturi | Venue: INDOCRYPT 2012 | Source

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.

BibTeX

Copy

@Inproceedings{INDOCRYPT:FKMV12,
  author = {Sebastian Faust and Markulf Kohlweiss and Giorgia Azzurra Marson and Daniele Venturi},
  title = {On the Non-malleability of the {Fiat}-{Shamir} Transform},
  pages = {60--79},
  editor = {Steven D. Galbraith and Mridul Nandi},
  booktitle = {Progress in Cryptology - INDOCRYPT~2012: 13th International Conference in Cryptology in India},
  volume = {7668},
  series = {Lecture Notes in Computer Science},
  address = {Kolkata, India},
  month = {dec~9--12},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2012},
  doi = {10.1007/978-3-642-34931-7_5},
}