Paper 2017/398

Post-Quantum Security of Fiat-Shamir

Dominique Unruh

Abstract

The Fiat-Shamir construction (Crypto 1986) is an efficient transformation in the random oracle model for creating non-interactive proof systems and signatures from sigma-protocols. In classical cryptography, Fiat-Shamir is a zero-knowledge proof of knowledge assuming that the underlying sigma-protocol has the zero-knowledge and special soundness properties. Unfortunately, Ambainis, Rosmanis, and Unruh (FOCS 2014) ruled out non-relativizing proofs under those conditions in the quantum setting. In this paper, we show under which strengthened conditions the Fiat-Shamir proof system is still post-quantum secure. Namely, we show that if we require the sigma-protocol to have computational zero-knowledge and statistical soundness, then Fiat-Shamir is a zero-knowledge simulation-sound proof system (but not a proof of knowledge!). Furthermore, we show that Fiat-Shamir leads to a post-quantum secure unforgeable signature scheme when additionally assuming a "dual-mode hard instance generator" for generating key pairs. Finally, we study the extractability (proof of knowledge) property of Fiat-Shamir. While we have no proof of the extractability itself, we show that if we can prove extractability, then other desired properties such as simulation-sound extractability (i.e., non-malleability), and unforgeable signatures follow.

Note: Added an analysis of the concrete security. Various minor changes.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2017
Keywords
quantum cryptographyzero knowledgedigital signatures
Contact author(s)
unruh @ ut ee
History
2018-05-16: last of 3 revisions
2017-05-09: received
See all versions
Short URL
https://ia.cr/2017/398
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/398,
      author = {Dominique Unruh},
      title = {Post-Quantum Security of Fiat-Shamir},
      howpublished = {Cryptology ePrint Archive, Paper 2017/398},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/398}},
      url = {https://eprint.iacr.org/2017/398}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.