Paper 2024/590

Revisiting the Security of Fiat-Shamir Signature Schemes under Superposition Attacks

Quan Yuan, The University of Tokyo
Chao Sun, Southeast University
Tsuyoshi Takagi, The University of Tokyo

The Fiat-Shamir transformation is a widely employed technique in constructing signature schemes, known as Fiat-Shamir signature schemes (FS-SIG), derived from secure identification (ID) schemes. However, the existing security proof only takes into account classical signing queries and does not consider superposition attacks, where the signing oracle is quantum-accessible to the adversaries. Alagic et al. proposed a security model called blind unforgeability (BUF, Eurocrypt'20), regarded as a preferable notion under superposition attacks. In this paper, we conduct a thorough security analysis of FS-SIGs in the BUF model. First, we propose a special property for ID schemes called quantum special honest-verifier zero-knowledge (qsHVZK), which is stronger than classical HVZK. We prove that qsHVZK is a sufficient property for BUF (with implicit rejection) of the resulting FS-SIG in the quantum random oracle model (QROM). Next, we give an efficient construction of (a weaker variant) of qsHVZK ID scheme based on the quantum hardness of LWE problems. To avoid enhancing the requirement of HVZK, we then progress to the deterministic FS-SIG (DFS) for more efficient constructions. We show that if the pseudorandom function is quantum-access-secure (QPRF), then we can prove the BUF security of the resulting DFS only with the requirement of the standard (multi-)HVZK in the QROM. A similar result can be extended to the hedged version of FS-SIG.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACISP 2024
Fiat-Shamir transformdigital signaturesidentification schemessuperposition attacksquantum random oracle
Contact author(s)
yuanquan @ g ecc u-tokyo ac jp
2024-04-16: approved
2024-04-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Quan Yuan and Chao Sun and Tsuyoshi Takagi},
      title = {Revisiting the Security of Fiat-Shamir Signature Schemes under Superposition Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2024/590},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.