Paper 2021/387

Quantum-access security of the Winternitz one-time signature scheme

Christian Majenz, Chanelle Matadah Manfouo, and Maris Ozols


Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
quantumquantum access modelunforgeabilityone-time signatureshash-based signatureLamportWinternitz
Contact author(s)
christian majenz @ gmail com
cmatadah @ quantumleapafrica org
marozols @ gmail com
2021-06-24: revised
2021-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Majenz and Chanelle Matadah Manfouo and Maris Ozols},
      title = {Quantum-access security of the Winternitz one-time signature scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2021/387},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.