Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1902.07556 · Lecture notes in computer science

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

Jelle Don, Serge Fehr, Christian Majenz, Christian Schaffner

Published Jan 1, 2019• 161 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-26951-7_13

Related papers

A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model

Eike Kiltz, Vadim Lyubashevsky, Christian Schaffner

Lecture notes in computer science•Jan 1, 2018•181 citations

Quantum Security and Fiat-Shamir for Cryptographic Protocols

Fermi Ma

•Jan 1, 2021•0 citations

Post-quantum Security of Fiat-Shamir

Dominique Unruh

Lecture notes in computer science•Jan 1, 2017•78 citations

On Security of Fiat-Shamir Signatures over Lattice in the Presence of Randomness Leakage.

Yuejun Liu, Yongbin Zhou, Shuo Sun +2 more

•Jan 1, 2019•2 citations

QCCA Security of Fujisaki-Okamoto Transformation in the Quantum Random Oracle Model

Xu Liu, Mingqiang Wang

Lecture notes in computer science•Jan 1, 2024•1 citation

On Removing Interaction from Quantum Proofs

Nicholas Spooner, Max Tromanhauser

An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) $Σ$-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $Σ$-protocol (which they call a $Ξ$-protocol) in which the prover's first message is quantum, and show that HVZK $Ξ$-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat-Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.

quant-pharXiv:2609.38387•Oct 1, 2026•0 citations
An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) ΣΣΣ-protocol for NP using the Fiat-Shamir transformation. Broadbent and Grilo introduced a quantum analog of a ΣΣΣ-protocol (which they call a ΞΞΞ-protocol) in which the prover's first message is quantum, and show that HVZK ΞΞΞ-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat-Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat-Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.