### The Fiat-Shamir Transformation in a Quantum World

Özgür Dagdelen, Marc Fischlin, and Tommaso Gagliardoni

##### Abstract

The Fiat-Shamir transformation is a famous technique to turn identification schemes into signature schemes. The derived scheme is provably secure in the random-oracle model against classical adversaries. Still, the technique has also been suggested to be used in connection with quantum-immune identification schemes, in order to get quantum-immune signature schemes. However, a recent paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the random-oracle model may not be immediately applicable to quantum adversaries, because such adversaries should be allowed to query the random oracle in superposition. It has been unclear if the Fiat-Shamir technique is still secure in this quantum oracle model (QROM). Here, we discuss that giving proofs for the Fiat-Shamir transformation in the QROM is presumably hard. We show that there cannot be black-box extractors, as long as the underlying quantum-immune identification scheme is secure against active adversaries and the first message of the prover is independent of its witness. Most schemes are of this type. We then discuss that for some schemes one may be able to resurrect the Fiat-Shamir result in the QROM by modifying the underlying protocol first. We discuss in particular a version of the Lyubashevsky scheme which is provably secure in the QROM.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Fiat-Shamirsignaturequantum random oracle model
Contact author(s)
marc fischlin @ gmail com
History
2013-06-21: last of 3 revisions
See all versions
Short URL
https://ia.cr/2013/245

CC BY

BibTeX

@misc{cryptoeprint:2013/245,
author = {Özgür Dagdelen and Marc Fischlin and Tommaso Gagliardoni},
title = {The Fiat-Shamir Transformation in a Quantum World},
howpublished = {Cryptology ePrint Archive, Paper 2013/245},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/245}},
url = {https://eprint.iacr.org/2013/245}
}

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