### Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model

Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner

##### Abstract

The famous Fiat-Shamir transformation turns any public-coin three-round interactive proof, i.e., any so-called sigma-protocol, into a non-interactive proof in the random-oracle model. We study this transformation in the setting of a quantum adversary that in particular may query the random oracle in quantum superposition. Our main result is a generic reduction that transforms any quantum dishonest prover attacking the Fiat-Shamir transformation in the quantum random-oracle model into a similarly successful quantum dishonest prover attacking the underlying sigma-protocol (in the standard model). Applied to the standard soundness and proof-of-knowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the Fiat-Shamir transformation even when allowing quantum attacks. Our result improves and completes the partial results that have been known so far, but it also proves wrong certain claims made in the literature. In the context of post-quantum secure signature schemes, our results imply that for any sigma-protocol that is a proof-of-knowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding Fiat-Shamir signature scheme is secure in the quantum random-oracle model. For example, we can conclude that the non-optimized version of Fish, which is the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.

Available format(s)
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
Fiat-Shamirpost-quantumdigital signaturesNIZKQROMproof of knowledge
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
c majenz @ uva nl
c schaffner @ uva nl
History
2020-07-27: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/190

CC BY

BibTeX

@misc{cryptoeprint:2019/190,
author = {Jelle Don and Serge Fehr and Christian Majenz and Christian Schaffner},
title = {Security of the Fiat-Shamir Transformation in the Quantum Random-Oracle Model},
howpublished = {Cryptology ePrint Archive, Paper 2019/190},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/190}},
url = {https://eprint.iacr.org/2019/190}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.