Hash-based cryptography: Difference between revisions

Revision as of 22:15, 10 July 2022

Revision as of 22:32, 10 July 2022

Line 3:

So far, hash-based cryptography is used to construct [[digital signature]]s schemes such as the [[Merkle signature scheme]], zero knowledge and computationally integrity proofs, such as the zk-STARK<ref name=bensasson2018> Scalable, transparent, and post-quantum secure computational integrity, Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018

</ref> proof system and range proofs over issued credentials via the HashWires <ref name=kchalkias2021>{{cite journal|last1=Chalkias|first1=Konstantinos|last2=Cohen|first2=Shir|last3=Lewi|first3=Kevin|last4=Moezinia|first4=Fredric|last5=Romailler|first5=Yolan|title=HashWires: Hyperefficient Credential-Based Range Proofs|journal=Privacy Enhancing Technologies Symposium (PETS) 2021|year=2021}}</ref> protocol. Hash-based signature schemes combine a one-time signature scheme, such as a [[Lamport signature]], with a [[Merkle tree]] structure. Since a one-time signature scheme key can only sign a single message securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure is used to this end. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes.

An important limitation of hash-based signature schemes is that they can only sign a fixed number of messages securely, because of their use of one-time signature schemes.

In 2022, the US [[National Institute of Standards and Technology]] announced [[SPHINCS+]] as one of three algorithms to be standardized for digital signatures.<ref>{{Cite web |date=2022-07-05 |title=NIST announces four quantum-resistant algorithms |url=https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |access-date=2022-07-10 |website=VentureBeat |language=en-US}}</ref> NIST standardized stateful hash-based cryptography based on the [[eXtended Merkle Signature Scheme]] (XMSS) and [[Leighton-Micali Signatures]] (LMS), which are applicable in different circumstances, in 2020, but noted that the requirement to maintain state when using them makes them more difficult to implement in a way that avoids misuse.<ref>{{Cite web|url=https://csrc.nist.gov/news/2019/stateful-hbs-request-for-public-comments|title=Request for Public Comments on Stateful HBS {{!}} CSRC|last=Computer Security Division|first=Information Technology Laboratory|date=2019-02-01|website=CSRC {{!}} NIST|language=EN-US|access-date=2019-02-04}}</ref><ref>{{Cite journal |last=Alagic |first=Gorjan |last2=Apon |first2=Daniel |last3=Cooper |first3=David |last4=Dang |first4=Quynh |last5=Dang |first5=Thinh |last6=Kelsey |first6=John |last7=Lichtinger |first7=Jacob |last8=Miller |first8=Carl |last9=Moody |first9=Dustin |last10=Peralta |first10=Rene |last11=Perlner |first11=Ray |date=2022-07-05 |title=Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process |url=https://csrc.nist.gov/publications/detail/nistir/8413/final |language=en}}</ref><ref>{{Cite journal |last=Cooper |first=David |last2=Apon |first2=Daniel |last3=Dang |first3=Quynh |last4=Davidson |first4=Michael |last5=Dworkin |first5=Morris |last6=Miller |first6=Carl |date=2020-10-29 |title=Recommendation for Stateful Hash-Based Signature Schemes |url=https://csrc.nist.gov/publications/detail/sp/800-208/final |language=en}}</ref>

Line 35 ⟶ 37:

==Examples of hash-based signature schemes==

Since Merkle's initial scheme, numerous hash-based signature schemes with performance improvements have been introduced. Recent ones include the XMSS, the Leighton-Micali (LMS), the SPHINCS and the BPQS schemes. Most hash-based signature schemes are [[State (computer science)|stateful]], meaning that signing requires updating the secret key, unlike conventional digital signature schemes. For stateful hash-based signature schemes, signing requires keeping state of the used one-time keys and making sure they are never reused. The XMSS, LMS and BPQS<ref>{{cite journal |last1=Chalkias|first1=Konstantinos|last2=Brown|first2=James|last3=Hearn|first3=Mike|last4=Lillehagen|first4=Tommy|last5=Nitto|first5=Igor|last6=Schroeter|first6=Thomas|title=Blockchained Post-Quantum Signatures|journal=Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018) |pages=1196–1203|year=2018|url=https://eprint.iacr.org/2018/658.pdf}}</ref> schemes are stateful, while the SPHINCS scheme is stateless. SPHINCS signatures are larger than XMSS, and LMS signatures, while. BPQS has been designed specifically for blockchain systems. Additionally to the WOTS⁺ one-time signature scheme,<ref name="wotsplus"/> SPHINCS also uses a few-time (hash-based) signature scheme called HORST. HORST is an improvement of an older few-time signature scheme, HORS (Hash to Obtain Random Subset).<ref>{{cite book|last1=Reyzin|first1=Leonid|last2=Reyzin|first2=Natan|title=Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying|journal=Lecture Notes in Computer Science|date=2002|volume=2384|issue=Information Security and Privacy|pages=144–153|doi=10.1007/3-540-45450-0_11|language=en|isbn=978-3-540-43861-8|citeseerx=10.1.1.24.7320}}</ref>

The stateful hash-based schemes XMSS and XMSS^''MT'' are specified in [[Request for Comments|RFC]] 8391 (XMSS: eXtended Merkle Signature Scheme)