More Web Proxy on the site http://driver.im/

research-article

Open access

The SPHINCS⁺ Signature Framework

Authors:

Daniel J. Bernstein,

Andreas Hülsing,

Ruben Niederhagen,

Joost Rijneveld,

Peter SchwabeAuthors Info & Claims

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Pages 2129 - 2146

https://doi.org/10.1145/3319535.3363229

Published: 06 November 2019 Publication History

Abstract

We introduce SPHINCS+, a stateless hash-based signature framework. SPHINCS+ has significant advantages over the state of the art in terms of speed, signature size, and security, and is among the nine remaining signature schemes in the second round of the NIST PQC standardization project. One of our main contributions in this context is a new few-time signature scheme that we call FORS. Our second main contribution is the introduction of tweakable hash functions and a demonstration how they allow for a unified security analysis of hash-based signature schemes. We give a security reduction for SPHINCS+ using this abstraction and derive secure parameters in accordance with the resulting bound. Finally, we present speed results for our optimized implementation of SPHINCS+ and compare to SPHINCS-256, Gravity-SPHINCS, and Picnic.

Supplementary Material

WEBM File (p2129-hulsing.webm)

Download
127.70 MB

References

[1]

Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Perlner, Angela Robinson, and Daniel Smith-Tone. 2019. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process. NISTIR 8240. available online at https://doi.org/10.6028/NIST.IR.8240.

[2]

Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. 2015. Ciphers for MPC and FHE. In Advances in Cryptology -- EUROCRYPT 2015 (LNCS), Elisabeth Oswald and Marc Fischlin (Eds.), Vol. 9056. Springer, 430--454. https://eprint.iacr.org/2016/687.

[3]

Erdem Alkim, Paulo S. L. M. Barreto, Nina Bindel, Patrick Longa, and Jefferson E. Ricardini. 2019. The Lattice-Based Digital Signature Scheme qTESLA. Cryptology ePrint Archive, Report 2019/085. https://eprint.iacr.org/2019/085.

[4]

Jean-Philippe Aumasson, Daniel J. Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hülsing, Panos Kampanakis, Stefan Kölbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, and Peter Schwabe. 2019. SPHINCS+. Submission to NIST's post-quantum crypto standardization project. http://sphincs.org/data/sphincs+-round2-specification.pdf.

[5]

Jean-Philippe Aumasson and Guillaume Endignoux. 2017a. Clarifying the subset-resilience problem. Cryptology ePrint Archive, Report 2017/909. https://eprint.iacr.org/2017/909.

[6]

Jean-Philippe Aumasson and Guillaume Endignoux. 2017b. Gravity-SPHINCS. Submission to the NIST PQC project. https://github.com/gravity-postquantum/gravity-sphincs/blob/master/Supporting_Documentation/submission.pdf.

[7]

Jean-Philippe Aumasson and Guillaume Endignoux. 2018. Improving stateless hash-based signatures. In Topics in Cryptology -- CT-RSA 2018 (LNCS), Nigel P. Smart (Ed.), Vol. 10808. Springer, 219--242. https://eprint.iacr.org/2017/933.

[8]

Daniel J. Bernstein. 2008. ChaCha, a variant of Salsa20. SASC 2008: The State of the Art of Stream Ciphers.

[9]

Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O'Hearn. 2015. SPHINCS: Practical Stateless Hash-Based Signatures. In Advances in Cryptology -- EUROCRYPT 2015, Elisabeth Oswald and Marc Fischlin (Eds.). LNCS, Vol. 9056. Springer, 368--397. https://eprint.iacr.org/2014/795.

[10]

Daniel J. Bernstein and Andreas Hülsing. 2018. Decisional second-preimage resistance: When does SPR imply PRE? https://eprint.iacr.org/2019/492.pdf.

[11]

Daniel J. Bernstein and Tanja Lange. accessed 2019-05--10. eBACS: ECRYPT Benchmarking of Cryptographic Systems. http://bench.cr.yp.to .

[12]

Nina Bindel, Sedat Akleylek, Erdem Alkim, Paulo S. L. M. Barreto, Johannes Buchmann, Edward Eaton, Gus Gutoski, Juliane Kr"amer, Patrick Longa, Harun Polat, Jefferson E. Ricardini, and Gustavo Zanon. 2019. Submission to NIST's post-quantum project (2nd round): lattice-based digital signature scheme qTESLA. Round-2 submission to the NIST PQC project. https://qtesla.org/wp-content/uploads/2019/04/qTESLA_round2_04.26.2019.pdf.

[13]

Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. 2011. Random Oracles in a Quantum World. In ASIACRYPT 2011, DongHoon Lee and Xiaoyun Wang (Eds.). LNCS, Vol. 7073. Springer, 41--69.

Digital Library

[14]

Leon Groot Bruinderink and Andreas Hülsing. 2017. “Oops, I did it again” -- Security of One-Time Signatures under Two-Message Attacks. In International Conference on Selected Areas in Cryptography -- SAC 2017 (LNCS), Carlisle Adams and Jan Camenisch (Eds.). Springer, 299--322. https://eprint.iacr.org/2016/1042.

[15]

Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, and Markus Rückert. 2011b. On the Security of the Winternitz One-Time Signature Scheme. In Africacrypt 2011, A. Nitaj and D. Pointcheval (Eds.). LNCS, Vol. 6737. Springer, 363--378.

[16]

Johannes Buchmann, Erik Dahmen, and Andreas Hülsing. 2011a. XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions. In Post-Quantum Cryptography, Bo-Yin Yang (Ed.). LNCS, Vol. 7071. Springer, 117--129. https://eprint.iacr.org/2011/484.

Digital Library

[17]

Melissa Chase, David Derler, Steven Goldfeder, Jonathan Katz, Vladimir Kolesnikov, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Xiao Wang, and Greg Zaverucha. 2019. The Picnic Signature Scheme -- Design Document. Round-2 submission to the NIST PQC project. version 2.0, https://github.com/microsoft/Picnic/blob/master/spec/design-v2.0.pdf.

[18]

Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. 2017. Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS'17. ACM, 1825--1842. https://eprint.iacr.org/2017/279.

Digital Library

[19]

Erik Dahmen, Katsuyuki Okeya, Tsuyoshi Takagi, and Camille Vuillaume. 2008. Digital Signatures Out of Second-Preimage Resistant Hash Functions. In Post-Quantum Cryptography, Johannes Buchmann and Jintai Ding (Eds.). LNCS, Vol. 5299. Springer, 109--123.

[20]

Itai Dinur, Yunwen Liu, Willi Meier, and Qingju Wang. 2015. Optimized Interpolation Attacks on LowMC. In Advances in Cryptology -- ASIACRYPT 2015 (LNCS), Tetsu Iwata and Jung Hee Cheon (Eds.), Vol. 9558. Springer, 535--560. https://eprint.iacr.org/2015/418.

Digital Library

[21]

Christoph Dobraunig, Maria Eichlseder, and Florian Mendel. 2015. Higher-Order Cryptanalysis of LowMC. In Information Security and Cryptology -- ICISC 2015 (LNCS), Soonhak Kwon and Aaram Yun (Eds.), Vol. 9558. Springer, 87--101. https://eprint.iacr.org/2015/407.

[22]

Láo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2019. CRYSTALS--Dilithium: Algorithm Specification and Supporting Documentation. Round-2 submission to the NIST PQC project. https://pq-crystals.org/dilithium/data/dilithium-specification-round2.pdf.

[23]

Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. 2018. CRYSTALS -- Dilithium: Digital Signatures from Module Lattices. Transactions on Cryptographic Hardware and Embedded Systems 1 (2018), 238--268. Issue 2018.

[24]

Amos Fiat and Adi Shamir. 1986. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. In Advances in Cryptology -- CRYPTO '86 (LNCS), Andrew M. Odlyzko (Ed.), Vol. 263. Springer, 186--194.

[25]

Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. 2019. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU -- Specifications v1.1. Round-2 submission to the NIST PQC project. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-2/submissions/Falcon-Round2.zip.

[26]

Oded Goldreich. 1987. Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme. In Advances in Cryptology - CRYPTO '86, Andrew M. Odlyzko (Ed.). LNCS, Vol. 263. Springer, 104--110.

[27]

Oded Goldreich. 2004. Foundations of Cryptography: Volume 2, Basic Applications .Cambridge University Press, Cambridge, UK.

Digital Library

[28]

Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. 1988. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., Vol. 17, 2 (1988), 281--308.

Digital Library

[29]

Andreas Hülsing. 2013a. Practical Forward Secure Signatures using Minimal Security Assumptions. Ph.D. Dissertation. TU Darmstadt. http://tuprints.ulb.tu-darmstadt.de/3651.

[30]

Andreas Hülsing. 2013b. W-OTS+-- Shorter Signatures for Hash-Based Signature Schemes. In Progress in Cryptology -- AFRICACRYPT 2013 (LNCS), Amr Youssef, Abderrahmane Nitaj, and Aboul-Ella Hassanien (Eds.), Vol. 7918. Springer, 173--188. https://eprint.iacr.org/2017/965.

[31]

Andreas Hülsing, Denis Butin, Stefan-Lukas Gazdag, Joost Rijneveld, and Aziz Mohaisen. 2018. XMSS: eXtended Merkle Signature Scheme. RFC 8391. https://doi.org/10.17487/RFC8391 https://rfc-editor.org/rfc/rfc8391.txt.

[32]

Andreas Hülsing, Lea Rausch, and Johannes Buchmann. 2013. Optimal Parameters for XMSS MT. In Security Engineering and Intelligence Informatics, Alfredo Cuzzocrea, Christian Kittl, Dimitris E. Simos, Edgar Weippl, and Lida Xu (Eds.). LNCS, Vol. 8128. Springer, 194--208. https://eprint.iacr.org/2017/966.

[33]

Andreas Hülsing, Joost Rijneveld, and Fang Song. 2016. Mitigating Multi-target Attacks in Hash-Based Signatures. In PKC 2016 (LNCS), Chen-Mou Cheng, Kai-Min Chung, Guiseppe Persiano, and Bo-Yin Yang (Eds.), Vol. 9614. Springer, 387--416. https://eprint.iacr.org/2015/1256.

[34]

Stefan Kölbl, Martin Lauridsen, Florian Mendel, and Christian Rechberger. 2017. Haraka v2 -- Efficient Short-Input Hashing for Post-Quantum Applications. IACR Transactions on Symmetric Cryptology, Vol. 2016, 2 (2017), 1--29. https://doi.org/10.13154/tosc.v2016.i2.1--29 https://eprint.iacr.org/2016/098.

[35]

Leslie Lamport. 1979. Constructing digital signatures from a one way function. Technical Report SRI-CSL-98. SRI International Computer Science Laboratory.

[36]

David McGrew, Michael Curcio, and Scott Fluhrer. 2019. Leighton-Micali Hash-Based Signatures. RFC 8554. https://doi.org/10.17487/RFC8554

[37]

Ralph Merkle. 1990. A Certified Digital Signature. In Advances in Cryptology -- CRYPTO '89 (LNCS), Gilles Brassard (Ed.), Vol. 435. Springer, 218--238.

[38]

NIST. 2016. Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.

[39]

Christian Rechberger, Hadi Soleimany, and Tyge Tiessen. 2018. Cryptanalysis of Low-Data Instances of Full LowMCv2. IACR Transactions on Symmetric Cryptology, Vol. 2018, 3 (2018), 163--181. https://doi.org/10.13154/tosc.v2018.i3.163--181.

[40]

Leonid Reyzin and Natan Reyzin. 2002. Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying. In Information Security and Privacy 2002, Lynn Batten and Jennifer Seberry (Eds.). LNCS, Vol. 2384. Springer, 1--47.

[41]

Dominique Unruh. 2012. Quantum Proofs of Knowledge. In Advances in Cryptology -- EUROCRYPT 2012 (LNCS), David Pointcheval and Thomas Johansson (Eds.), Vol. 7237. Springer, 135--152. https://eprint.iacr.org/2010/212.

[42]

Dominique Unruh. 2015. Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model. In Advances in Cryptology -- EUROCRYPT 2015 (LNCS), Elisabeth Oswald and Marc Fischlin (Eds.), Vol. 9056. Springer, 755--784. http://eprint.iacr.org/2014/587.

[43]

Dominique Unruh. 2016. Computationally binding quantum commitments. In Advances in Cryptology -- EUROCRYPT 2016 (LNCS), Marc Fischlin and Jean-Sébastien Coron (Eds.), Vol. 9666. Springer, 497--527. https://eprint.iacr.org/2015/361.

Cited By

Bicakci KUlker KUzunay YŞahin HGündoğan M(2024)Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?IACR Communications in Cryptology10.62056/an59qgxqOnline publication date: 8-Jul-2024
https://doi.org/10.62056/an59qgxq
Chakraborty DNandi M(2024)Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving HashIACR Communications in Cryptology10.62056/akgy11zn4Online publication date: 7-Oct-2024
https://doi.org/10.62056/akgy11zn4
Zafar AIqbal S(2024)Code-Based Cryptography and Its Place in Quantum-Safe StrategiesHarnessing Quantum Cryptography for Next-Generation Security Solutions10.4018/979-8-3693-9220-1.ch004(89-124)Online publication date: 27-Sep-2024
https://doi.org/10.4018/979-8-3693-9220-1.ch004
Show More Cited By

Index Terms

The SPHINCS⁺ Signature Framework
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Digital signatures

Recommendations

RFC 8391: XMSS: eXtended Merkle Signature Scheme
Quantum-Access Security of Hash-Based Signature Schemes
Information Security and Privacy
Abstract
In post-quantum cryptography, hash-based signature schemes are attractive choices because of the weak assumptions. Most existing hash-based signature schemes are proven secure against post-quantum chosen message attacks (CMAs), where the ...
Recovering the Tight Security Proof of SPHINCS $^{+}$
Advances in Cryptology – ASIACRYPT 2022
Abstract
In 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the SPHINCS $^{+}$ construction. This work gives a new tight security proof for SPHINCS $^{+}$ . The flaw can be traced back to the security proof for the Winternitz one-... $^{}$ $^{}$ $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

November 2019

2755 pages

ISBN:9781450367479

DOI:10.1145/3319535

General Chairs:
Lorenzo Cavallaro
King's College London, UK
,
Johannes Kinder
Bundeswehr University Munich, Germany
,
Program Chairs:
XiaoFeng Wang
Indiana University, USA
,
Jonathan Katz
George Mason University, USA

Copyright © 2019 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2019

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11 - 15, 2019

London, United Kingdom

Acceptance Rates

CCS '19 Paper Acceptance Rate 149 of 934 submissions, 16%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

115
Total Citations
View Citations
3,141
Total Downloads

Downloads (Last 12 months)1,123
Downloads (Last 6 weeks)221

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bicakci KUlker KUzunay YŞahin HGündoğan M(2024)Quantum-Resistance Meets White-Box Cryptography: How to Implement Hash-Based Signatures against White-Box Attackers?IACR Communications in Cryptology10.62056/an59qgxqOnline publication date: 8-Jul-2024
https://doi.org/10.62056/an59qgxq
Chakraborty DNandi M(2024)Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving HashIACR Communications in Cryptology10.62056/akgy11zn4Online publication date: 7-Oct-2024
https://doi.org/10.62056/akgy11zn4
Zafar AIqbal S(2024)Code-Based Cryptography and Its Place in Quantum-Safe StrategiesHarnessing Quantum Cryptography for Next-Generation Security Solutions10.4018/979-8-3693-9220-1.ch004(89-124)Online publication date: 27-Sep-2024
https://doi.org/10.4018/979-8-3693-9220-1.ch004
Shadaksharappa BRamkumar P(2024)Analysis of Drop-In-Replaceability Applying Post-Quantum Cryptography TechniquesHarnessing Quantum Cryptography for Next-Generation Security Solutions10.4018/979-8-3693-9220-1.ch003(75-88)Online publication date: 27-Sep-2024
https://doi.org/10.4018/979-8-3693-9220-1.ch003
Das SKar NDeb S(2024)Moving Towards a Quantum AgeAdvancing Cyber Security Through Quantum Cryptography10.4018/979-8-3693-5961-7.ch002(31-58)Online publication date: 4-Oct-2024
https://doi.org/10.4018/979-8-3693-5961-7.ch002
Carril XKardaris CRibes-GonzáLez JFarràs OHernandez CKostalabros VGonzález-Jiménez JMoretó M(2024)Hardware Acceleration for High-Volume Operations of CRYSTALS-Kyber and CRYSTALS-DilithiumACM Transactions on Reconfigurable Technology and Systems10.1145/367517217:3(1-26)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1145/3675172
Ricci SShapoval VDzurenda PRoenne POupicky JMalina L(2024)Lattice-based Multisignature Optimization for RAM Constrained DevicesProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3670461(1-10)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3670461
Wood TThomas KDean MKannan SLearney R(2024)Towards Post-Quantum Verifiable CredentialsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3669932(1-10)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3669932
Wang ZDong XKang YChen HWang Q(2024)An Example of Parallel Merkle Tree Traversal: Post-Quantum Leighton-Micali Signature on the GPUACM Transactions on Architecture and Code Optimization10.1145/365920921:3(1-25)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1145/3659209
Lopez-Valdivieso JCumplido R(2024)Design and Implementation of Hardware-Software Architecture Based on Hashes for SPHINCS+ACM Transactions on Reconfigurable Technology and Systems10.1145/365345917:4(1-22)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1145/3653459
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents