Document Open Access Logo

Quantum-Access Security of the Winternitz One-Time Signature Scheme

Authors Christian Majenz , Chanelle Matadah Manfouo , Maris Ozols

PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.21.pdf
  • Filesize: 0.86 MB
  • 22 pages

Document Identifiers

Author Details

Christian Majenz
  • Centrum Wiskunde & Informatica and QuSoft, Amsterdam, The Netherlands
Chanelle Matadah Manfouo
  • African Institute for Mathematical Science & Quantum Leap Africa, Kigali, Rwanda
Maris Ozols
  • Institute for Logic, Language, and Computation, Korteweg-de Vries Institute for Mathematics, and Institute for Theoretical Physics, University of Amsterdam and QuSoft, Amsterdam, The Netherlands

Funding

  • Majenz, Christian: NWO Veni grant (Project No. VI.Veni.192.159).
  • Manfouo, Chanelle Matadah: NWO Gravitation grant QSC (Project No. 024.003.037) and AIMS-NEI.
  • Ozols, Maris: NWO Vidi grant (Project No. VI.Vidi.192.109).

Acknowledgements

The authors thank anonymous reviewers for insightful comments and Stacey Jeffery for helpful discussions. CMM deeply thanks the African Institute for Mathematical Sciences, Quantum Leap Africa Rwanda, and QuSoft Amsterdam for their support.

Cite AsGet BibTex

Christian Majenz, Chanelle Matadah Manfouo, and Maris Ozols. Quantum-Access Security of the Winternitz One-Time Signature Scheme. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITC.2021.21

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum information theory
  • Security and privacy → Digital signatures
  • Security and privacy → Information-theoretic techniques
Keywords
  • quantum cryptography
  • one-time signature schemes
  • quantum random oracle model
  • post-quantum cryptography
  • quantum world
  • hash-based signatures
  • information-theoretic security

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, et al. Status report on the second round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST, 2020. URL: https://doi.org/10.6028/NIST.IR.8309.
  2. Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-access-secure message authentication via blind-unforgeability. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 788-817. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_27.
  3. Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM conference on Computer and communications security, pages 62-73. ACM, 1993. URL: https://doi.org/10.1145/168588.168596.
  4. Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS+ signature framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS'19, pages 2129-2146, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3319535.3363229.
  5. Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. On the security of proofs of sequential work in a post-quantum world, 2020. URL: http://arxiv.org/abs/2006.10972.
  6. Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In International Conference on the Theory and Application of Cryptology and Information Security, pages 41-69. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_3.
  7. Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013, pages 361-379, Berlin, Heidelberg, 2013. Springer. URL: https://doi.org/10.1007/978-3-642-40084-1_21.
  8. Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher. Quantum attacks without superposition queries: The offline Simon’s algorithm. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019, pages 552-583, Cham, 2019. Springer. URL: https://doi.org/10.1007/978-3-030-34578-5_20.
  9. Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. In Cláudio L. Lucchesi and Arnaldo V. Moura, editors, LATIN'98: Theoretical Informatics, pages 163-169, Berlin, Heidelberg, 1998. Springer. URL: https://doi.org/10.1007/BFb0054319.
  10. Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. XMSS - a practical forward secure signature scheme based on minimal security assumptions. In Bo-Yin Yang, editor, Post-Quantum Cryptography, pages 117-129, Berlin, Heidelberg, 2011. Springer. URL: https://doi.org/10.1007/978-3-642-25405-5_8.
  11. Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work, 2020. URL: http://arxiv.org/abs/2010.11658.
  12. Shimon Even, Oded Goldreich, and Silvio Micali. On-line/off-line digital signatures. Journal of Cryptology, 9(1):35-67, 1996. URL: https://doi.org/10.1007/0-387-34805-0_24.
  13. Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner. Semantic security and indistinguishability in the quantum world. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, pages 60-89, Berlin, Heidelberg, 2016. Springer. URL: https://doi.org/10.1007/978-3-662-53015-3_3.
  14. Tommaso Gagliardoni, Juliane Krämer, and Patrick Struck. Quantum indistinguishability for public key encryption, 2020. URL: http://arxiv.org/abs/2003.00578.
  15. Sumegha Garg, Henry Yuen, and Mark Zhandry. New security notions and feasibility results for authentication of quantum data. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017, pages 342-371, Cham, 2017. Springer. URL: https://doi.org/10.1007/978-3-319-63715-0_12.
  16. Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on computing, 17(2):281-308, 1988. URL: https://doi.org/10.1137/0217017.
  17. Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Tight adaptive reprogramming in the QROM, 2020. URL: http://arxiv.org/abs/2010.15103.
  18. Masahito Hayashi. Optimal sequence of quantum measurements in the sense of Stein’s lemma in quantum hypothesis testing. Journal of Physics A: Mathematical and General, 35(50):10759, 2002. URL: https://doi.org/10.1088/0305-4470/35/50/307.
  19. Andreas Hülsing, Denise Butin, Stefan-Lukas Gazdag, Joost Rijneveld, and Aziz Mohaisen. XMSS: Extended hash-based signatures. RFC 8391, 2018. URL: https://doi.org/10.17487/RFC8391.
  20. Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016, pages 207-237, Berlin, Heidelberg, 2016. Springer. URL: https://doi.org/10.1007/978-3-662-53008-5_8.
  21. Leslie Lamport. Constructing digital signatures from a one way function. Technical Report SRI-CSL-98, SRI International Computer Science Laboratory, 1979. URL: http://lamport.azurewebsites.net/pubs/dig-sig.pdf.
  22. Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2019, pages 189-218, Cham, 2019. Springer. URL: https://doi.org/10.1007/978-3-030-17659-4_7.
  23. Christian Majenz, Chanelle Matadah Manfouo, and Maris Ozols. Quantum-access security of the Winternitz one-time signature scheme, 2021. URL: http://arxiv.org/abs/2103.12448.
  24. Ralph C. Merkle. A certified digital signature. In Conference on the Theory and Application of Cryptology, pages 218-238. Springer, 1989. URL: https://doi.org/10.1007/0-387-34805-0_21.
  25. Michael A. Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. URL: https://doi.org/10.1023/A:1012603118140.
  26. Thomas Santoli and Christian Schaffner. Using Simon’s algorithm to attack symmetric-key cryptographic primitives. Quantum Info. Comput., 17(1–2):65-78, 2017. URL: https://doi.org/10.26421/QIC17.1-2-4.
  27. Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124-134. IEEE, 1994. URL: https://doi.org/10.1109/SFCS.1994.365700.
  28. Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019, pages 239-268, Cham, 2019. Springer. URL: https://doi.org/10.1007/978-3-030-26951-7_9.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact