Literature | Andreas Hülsing

I try to keep an up-to-date commented list of literature about hash-based signature schemes. The list is based on the list from http://pqcrypto.org/hash.html by Daniel J. Bernstein. The list is sorted by topics. Hence, some papers appear in more than one category. I try to cover all publications on the topic, however, if you find one that I forgot please contact me.

Surveys

2009. Johannes Buchmann, Erik Dahmen, Michael Szydlo. “Hash-based digital signature schemes.” Pages 35–93 in: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (editors). Post-quantum cryptography. Springer, Berlin. ISBN 978-3-540-88701-0.

Covers… OTS: Lamport’s scheme, Winternitz-OTS; Tree: Basic Merkle tree; Tree traversal: Merkle’s, fractal-, log-, and improved log-traversal algorithm; Techniques: Tree chaining (CMSS), distributed signature generation (GMSS), pseudorandom key generation; Security: Reduction for basic Merkle tree + Lamport’s scheme requiring collision resistant hash function and a one-way function.

One-time signatures (OTS)

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

Introduces Lamport’s scheme, i.e. the first hash-based OTS.

1979. Ralph C. Merkle. “A certified digital signature.” Pages 218–238 in: Gilles Brassard (editor). Advances in Cryptology—Crypto ’89, 9th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 1989, proceedings. Lecture Notes in Computer Science 435. Springer. ISBN 3-540-97317-6.

Re-introduces Lamport’s scheme as Lamport-Diffie OTS. Introduces the Improved Lamport-Diffie OTS (“Create a coding scheme in which accidental or intentional conversion of 1’s to 0’s will produce an illegal codeword”) and the Winternitz-OTS (Combine the coding scheme idea with hash chains).

1989. Shimon Even, Oded Goldreich, Silvio Micali. “On-line/off-line digital signatures.” Pages 263-275 in: Advances in Cryptology—Crypto ’89, 9th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 1989, proceedings. Lecture Notes in Computer Science 435. Springer. ISBN 3-540-97317-6.
Full version: 1996. Shimon Even, Oded Goldreich, Silvio Micali. “On-line/off-line digital signatures.” Pages 35-67 in: Journal of Cryptology, Volume 9, Issue 1. Springer.

Proposes several variants of the basic Winternitz-OTS idea. The paper discusses several possible coding schemes. Also, the first paper that analyses the requirements on the used hash function to get a secure scheme.

1992. Jurjen N. Bos, David Chaum. “Provably unforgeable signatures.” Pages 1–14 in: Ernest F. Brickell (editor). Advances in cryptology—CRYPTO ’92. 12th annual international cryptology conference, Santa Barbara, California, USA, August 16–20, 1992, proceedings. Lecture Notes in Computer Science 740. Springer. ISBN 978-3-540-65069-0.

Introduces another optimization of Lamport’s scheme that further improves the Improved Lamport-Diffie OTS by Merkle.

1994. Daniel Bleichenbacher, Ueli M. Maurer. “Directed acyclic graphs, one-way functions and digital signatures.” Pages 75–82 in: Yvo Desmedt (editor). Advances in cryptology—CRYPTO ’94. 14th annual international cryptology conference, Santa Barbara, California, USA, August 21–25, 1994, proceedings. Lecture Notes in Computer Science 839. Springer. ISBN 3-540-58333-5.

Initiates an abstract treatment of all the previous OTS proposals as acyclic graph-based signature schemes. This is used to reason about optimal schemes.

1996. Daniel Bleichenbacher, Ueli M. Maurer. “On the efficiency of one-time digital signatures.” Pages 145–158 in: Kwangjo Kim, Tsutomu Matsumoto (editors). Advances in cryptology—ASIACRYPT ’96: international conference on the theory and applications of cryptology and information security, Kyongju, Korea, November 3–7, 1996, proceedings. Lecture Notes in Computer Science 1163. Springer. ISBN 3-540-61872-4. MR 98g:94001.

Proposes one specific “graph-based” OTS that is optimal in terms of the ratio of message length and hash function calls for key generation.

1996. Daniel Bleichenbacher, Ueli M. Maurer. “Optimal tree-based one-time digital signature schemes.” Pages 363–374 in: Claude Puech, Rüdiger Reischuk (editors). STACS 96, 13th annual symposium on theoretical aspects of computer science, Grenoble, France, February 22–24, 1996, proceedings. Lecture Notes in Computer Science 1046. Springer. ISBN 3-540-60922-9.

Several theoretical results regarding optimal graphs for OTS.

2001. Adrian Perrig. “The BiBa one-time signature and broadcast authentication protocol.” Pages 28–37 in: CCS 2001, proceedings of the 8th ACM conference on computer and communications security, November 6–8, 2001, Philadelphia, Pennsylvania, USA. ACM Press.

Introduces the BiBa-OTS. BiBa has small signatures and fast verification but signing is slow and public keys are large.

2002. Michael Mitzenmacher, Adrian Perrig. “Bounds and improvements for BiBa signature schemes.” Harvard Computer Science Technical Report TR-02-02. http://www.eecs.harvard.edu/~michaelm/NEWWORK/papers.html.

Optimizes the BiBa-OTS and finally proposes Powerball-OTS.

2002. Leonid Reyzin, Natan Reyzin. “Better than BiBa: short one-time signatures with fast signing and verifying.” Pages 144–153 in: Lynn Margaret Batten, Jennifer Seberry (editors). Information security and privacy, 7th Australian conference, ACISP 2002, Melbourne, Australia, July 3–5, 2002, proceedings. Lecture Notes in Computer Science 2834. Springer. ISBN 3-540-43861-0.

Introduces HORS, actually not a one- but a few-time signature scheme. Security degrades with each signature made. Hence, it can be used for more then one signature. For how many more depends on the used parameters. Security is based on one-wayness and subset-resilience (a notion introduced in the paper). Moreover, it is shown how to implement the Bos / Chaum ’92 OTS more efficiently.

2002. Alejandro Hevia, Daniele Micciancio. “The Provable Security of Graph-Based One-Time Signatures and Extensions to Algebraic Signature Schemes.” Pages 191-196 in: Yuliang Zheng (editor). Advances in Cryptology — ASIACRYPT ’02, 8th International Conference on the Theory and Application of Cryptology and Information Security Queenstown, New Zealand, December 1–5, 2002, proceedings. Lecture Notes in Computer Science 2501. Springer. ISBN 978-3-540-00171-3.

Standard model security reduction for graph-based OTS (this subsumes all previous proposals excluding BiBa and HORS and some special cases of the graph-based schemes, see Dods et al. 2005) using a regular collision resistant hash function and a one-to-one pseudorandom generator. Both of which can be constructed from any one-way permutation.

2003. Kemal Bicakci, Gene Tsudik, Brian Tung. “How to construct optimal one-time signatures.” Pages 339–349 in: Computer Networks, Volume 43, Issue 3. Elsevier.

Discusses how to construct optimal OTS with a restriction to Improved Lamport-Diffie OTS style schemes, i.e. no chains. However, the results are already improved by Reyzin and Reyzin 2002.

2004. Josef Pieprzyk, Huaxiong Wang, Chaoping Xing. “Multiple-time signature schemes against adaptive chosen message attacks.” Pages 88–100 in: Mitsuru Matsui, Robert J. Zuccherato (editors). Selected areas in cryptography, 10th annual international workshop, SAC 2003, Ottawa, Canada, August 14–15, 2003, revised papers. Lecture Notes in Computer Science 3006. Springer. ISBN 3-540-21370-8.

Introduces HORS++. The improvement is to implement subset-resilient functions using r-cover-free sets. Be careful, the independet improvement proposed in this paper of using HORS(++) with hash chains is insecure (still planing to write a short note on this soon).

2005. C. Dods, Nigel P. Smart, Martijn Stam. “Hash based digital signature schemes.” Pages 96–115 in: Nigel P. Smart (editor). Cryptography and coding, 10th IMA international conference, Cirencester, UK, December 19–21, 2005, proceedings. Lecture Notes in Computer Science 3796. Springer. ISBN 3-540-30276-X.

Standard model security reduction for Winternitz-OTS using one of the checksum constructions from Even et al.. The required security properties of the used hash function are collision resistance, one-wayness and undetectability (introduced in the paper, states that output can not be distinguished from a random bit string). Also give a security reduction for the best graph-based scheme by Bleichenbacher and Maurer in the random oracle model. This scheme was not covered by the security reduction of Hevia and Micciancio. This is the first paper that provides a constructive description of the Bleichenbacher and Maurer scheme. Moreover, the paper discusses implications of the security reductions for the required hash function output sizes.

2008. Rainer Steinwandt, Viktória I. Villányi. “A one-time signature using run-length encoding.” Pages 179–185 in: Information Processing Letters, Volume 108, Issue 4. Elsevier.

Proposes an OTS similar to the Winternitz-OTS that reduces signature verification time at the cost of more expensive signature generation time. Roughly, the messages are hashed together with a counter until the hash value has a certain structure that allows to generate signatures where verification is faster. Security reduction is in the random oracle model.

2011. Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, Markus Rückert. “On the security of the Winternitz one-time signature scheme.” Pages 363-378 in: Abderrahmane Nitaj, David Pointcheval (editors). Progress in Cryptology – AFRICACRYPT 2011, 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011, proceedings. Lecture Notes in Computer Science 6737. Springer. ISBN: 978-3-642-21968-9.
Full version: Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, Markus Rückert. “On the security of the Winternitz one-time signature scheme.” Pages 84-96 in: International Journal of Applied Cryptography, Volume 3, Issue 1. Inderscience Publishers.

Several standard model security reductions for a slightly changed variant of the Winternitz-OTS by Even et al. requiring a pseudorandom function family instead of a hash function. This allows to use function families with half the output size compared to previous constructions as collision resistance is not required. Shows that minicrypt constructions of WOTS exist. Gives further security reductions using key-based security notions of function families.

2013. Andreas Hülsing. “W-OTS+-Shorter Signatures for Hash-Based Signature Schemes.” Pages 173-188 in: Amr Youssef, Abderrahmane Nitaj, Aboul Ella Hassanien (editors). Progress in Cryptology – AFRICACRYPT 2013,
6th International Conference on Cryptology in Africa, Cairo, Egypt, June 22-24, 2013, proceedings. Lecture Notes in Computer Science 7918. Springer. ISBN: 978-3-642-38552-0.

Introduces WOTS+, a variant of the Winternitz-OTS. Presents a standard model security reduction requiring a second-preimage resistant, undetectable one-way function. The new proof reduces the security requirements by Dods et al. and the proof is tighter than that of Buchmann et al. which allows for better practical performance.

2015. Daniel J. Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Peter Schwabe, Zooko Wilcox-O’Hearn. “SPHINCS: practical stateless hash-based signatures.” Pages 368-397 in: Elisabeth Oswald, Marc Fischlin (editors). Advances in Cryptology – EUROCRYPT 2015, 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Lecture Notes in Computer Science 9056. Springer. ISBN: 978-3-662-46799-2.

Introduces HORST, an extension of the few-time signature scheme HORS. The idea can be summarized as adding a Merkle tree to HORS to reduce the public key size and add several optimizations.

Many-time Signatures

1982. Ralph C. Merkle. “Secrecy, authentication, and public key systems.” UMI Research Press. Previous version: 1979. Ph.D. thesis, Stanford University.

Introduces Merkle trees and Merkle’s binary hash tree scheme.

1987. Ralph C. Merkle. “A digital signature based on a conventional encryption function.” Pages 369–378 in: Carl Pomerance (editor). Advances in cryptology—CRYPTO ’87. Proceedings of the Conference on the Theory and Applications of Cryptographic Techniques held at the University of California, Santa Barbara, California, August 16–20, 1987. Lecture Notes in Computer Science 293. Springer. ISBN 3-540-18796-0. MR 89b:68005.

Describes a binary certification tree scheme where every node in the tree consists of three OTS keys: One to sign the left child node, one to sign the right child node and one to sign a message.

1989. Moni Naor, Moti Yung. “Universal one-way hash functions and their cryptographic applications.” Pages 33–43 in: Proceedings of the 21st annual ACM symposium on theory of computing, May 14–17, 1989, Seattle, Washington, USA. ACM Press.

Introduces a chain based many-time signature scheme. Every node contains two OTS key pairs: One to sign a message and one to sign the hash of the public keys of the next node.

Proposes to split signature generation into an offline and an online phase. The offline phase can be “prepared” without knowing the message during less busy times. The online phase then does the message dependent part.

1990. Ralph C. Merkle. “A certified digital signature.” Pages 218–238 in: Gilles Brassard (editor). Advances in Cryptology—Crypto ’89, 9th annual international cryptology conference, Santa Barbara, California, USA, August 20–24, 1989, proceedings. Lecture Notes in Computer Science 435. Springer. ISBN 3-540-97317-6.

The paper that introduces Merkle trees and the corresponding binary hash tree signature scheme (MSS).

1999. Pankaj Rohatgi. “A compact and fast hybrid signature scheme for multicast packet authentication.” Pages 93–100 in: CCS ’99, proceedings of the 6th ACM conference on computer and communications security, November 1–4, 1999, Singapore. ACM Press.

Proposes several improvements that reduce the signature size of a MSS. First it proposes to use a TCR hash function (aka UOWHF) to sign the messages. Instead of also signing the TCR keys it is proposed to add a commitment to a key to each OTS public key. Second this paper already proposes the use of the XOR tree technique by Bellare and Rogaway to reduce the security requirements for the tree to second-preimage resistance of the hash function.

2002. Tal Malkin, Daniele Micciancio, Sara K. Miner. “Efficient generic forward-secure signatures with an unbounded number of time periods.” Pages 400–417 in: Lars R. Knudsen (editor). Advances in cryptology—EUROCRYPT 2002, international conference on the theory and applications of cryptographic techniques, Amsterdam, the Netherlands, April 28–May 2, 2002, proceedings. Lecture Notes in Computer Science 2332. Springer. ISBN 3-540-43553-0.

Presents a generic construction for a forward secure signature scheme. The described construction can be viewed as one Merkle signautre scheme (MSS) key pair used to sign the root nodes of other MSS key pairs which are used for signing messages. One of the key ideas is to use MSS key pairs with different heights on the lower layer. The first one has height 1 and then height grows by one for each new MSS key pair. This allows to sign an virtually unlimited number of messages with one key pair.

2005. Dalit Naor, Amir Shenhav, Avishai Wool. “One-time signatures revisited: have they become practical?” http://eprint.iacr.org/2005/442.

Discusses the usability of B-trees for hash-based signature schemes.

2005. Carlos Coronado. “On the security and efficiency of the Merkle signature scheme.” http://eprint.iacr.org/2005/192.

Presents a standard model reduction for MSS with Lamport. The used assumptions are a one-way function and a collision resistant hash function. Moreover, pseudorandom key generation is introduced and proven secure. Also, a forward secure variant is presented, but the proof is not in the standard model for forward secure signatures (it is assumed that an adversary learns only parts of the secret key on a key exposure).

2006. Johannes Buchmann, Luis Carlos Coronado Garcia, Erik Dahmen, Martin Döring, Elena Klintsevich. “CMSS—an improved Merkle signature scheme.” Pages 349–363 in: Rana Barua, Tanja Lange (editors). Progress in Cryptology—INDOCRYPT 2006, 7th international conference on cryptology in India, Kolkata, India, December 11–13, 2006, proceedings. Lecture Notes in Computer Science 4329. Springer. ISBN 3-540-49767-6.

Introduces the tree chaining concept and CMSS as the corresponding signature scheme. Tree chaining means using many layers of MSS key pairs. Those on the higher layers are used to sign the roots of those on the lower layers. On the lowest layer, the key pairs are used to sign the messages.

2007. Johannes Buchmann, Erik Dahmen, Elena Klintsevich, Katsuyuki Okeya, Camille Vuillaume. “Merkle signatures with virtually unlimited signature capacity.” Pages 31–45 in: Jonathan Katz, Moti Yung (editors). Applied Cryptography and Network Security, 5th international conference, ACNS 2007, Zhuhai, China, June 5–8, 2007, proceedings. Lecture Notes in Computer Science 4521. Springer. ISBN 978-3-540-72737-8.

Introduces distributed signature generation and the corresponding signature scheme GMSS. Distributed signature generation is an algorithmic approach that reduces the worst case runtime of the signature generation algorithm when using many layers of trees.

2008. Erik Dahmen, Katsuyuki Okeya, Tsuyoshi Takagi, Camille Vuillaume. “Digital signatures out of second-preimage resistant hash functions.” Pages 109–123 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Presents a MSS variant with a security reduction that needs only a second-preimage resistant hash function and a one-way function. The idea is roughly similar to the one by Rohatgi above. However, the description here is explicitly for hash-based signatures and contains a full security proof.

2011. Johannes Buchmann, Erik Dahmen, Andreas Hülsing. “XMSS – A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions.” Pages 117-129 in: Bo-Yin Yang (editor). Post-Quantum Cryptography 4th International Workshop, PQCrypto 2011, Taipei, Taiwan, November 29 – December 2, 2011, proceedings. Lecture Notes in Computer Science 7071. Springer. ISBN 978-3-642-25404-8.

Introduces XMSS, includes standard model security reductions for forward and standard security. Requirements on function families is one second-preimage resistant hash function and one pseudorandom fucntion family. Improves efficiency compared to previous schemes.

2013. Andreas Hülsing, Lea Rausch, Johannes Buchmann. “Optimal Parameters for XMSS^MT.” Pages 194-208 in: Alfredo Cuzzocrea, Christian Kittl, Dimitris E. Simos, Edgar Weippl, Lida Xu (editors). Security Engineering and Intelligence Informatics, CD-ARES 2013 Workshops: MoCrySEn and SeCIHD, Regensburg, Germany, September 2-6, 2013, proceedings. Lecture Notes in Computer Science 8128. Springer. ISBN 978-3-642-40587-7.

Introduces XMSS^MT, a multi-tree variant of XMSS similar to CMSS and GMSS. Improves worst case signing time introducing a new distributed signature generation algorithm. Adds a security reduction for the scheme being forward secure to second-preimage resistance of the used hash function and pseudorandomness of the used function family.

Introduces Sphincs, a stateless hash-based signature scheme. Builds upon ideas taken from XMSS and its predecessors. Also introduces HORST, an extension of the few-time signature scheme HORS. The construction is basically a multi-layer XMSS tree used to sign HORST public keys. Instead of using the HORST key pairs in order, starting with the “left most”, an index is chosen pseudorandomly. The paper also introduces a different approach to construct efficient fixed input size hash-functions (compared to the block cipher / hash function approaches chosen so far). In addition, the complexity of generic quantum attacks against the used hash function properties is analysed. Finally, one specific instantiation (SPHINCS-256) is given together with an optimized implementation.

2016. Andreas Hülsing, Joost Rijneveld, Fang Song. “Mitigating Multi-Target Attacks in Hash-based Signatures.” Pages 387-416 in: Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang (editors). Public-Key Cryptography – PKC 2016, 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. Lecture Notes in Computer Science 9614. Springer. ISBN 978-3-662-49383-0.

Introduces XMSS-T, roughly a formal treatment of the modified XMSS proposed in the XMSS Internet-Draft. Main difference between XMSS and XMSS-T is the use of different bitmasks and has function keys for every hash function call in the scheme. Bitmasks and function keys are pseudorandomly generated and the used seed is part of the public key to reduce public key size (requires ROM). In addition, the paper takes a formal look at so called multi-target attacks, defines security notions for hash functions capturing these and analyses query complexity of generic attacks against these properties.

Traversal Algorithms

Introduces the basic tree traversal algorithm. Introduces tree hash algorithm.

2002. Don Coppersmith, Markus Jakobsson. “Almost optimal hash sequence traversal.” Pages 102–119 in: Matt Blaze (editor). Financial Cryptography, 6th international conference, FC 2002, Southampton, Bermuda, March 11–14, 2002, revised papers. Lecture Notes in Computer Science 2357. Springer. ISBN 978-3-540-00646-6.

Introduces a pebbling algorithm to traverse a hash chain backwards in with $O(log²n)$ time-space-complexity.

2002. Helger Lipmaa. “On optimal hash tree traversal for interval time-stamping.” Pages 357–371 in: Agnes Hui Chan, Virgil Gligor (editors). Information security, 5th international conference, ISC 2002, Sao Paulo, Brazil, September 30–October 2, 2002, proceedings. Lecture Notes in Computer Science 2433. Springer. ISBN 978-3-540-44270-7.

Introduces a tree traversal algorithm for recursively built trees.

2003. Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, Michael Szydlo. “Fractal Merkle tree representation and traversal.” Pages 314–326 in: Marc Joye (editor). Topics in cryptology—CT-RSA 2003, the cryptographers’ track at the RSA conference 2003, San Francisco, CA, USA, April 13–17, 2003, proceedings. Lecture Notes in Computer Science 2612. Springer. ISBN 3-540-00847-0.

Introduces the fractal tree traversal algorithm. Roughly separates the tree into many layers of smaller trees. Always stores one tree per layer and computes the next one. Turns out to be the optimal algorithm, if leaf computations are treated as expensive as node computations.

2004. Michael Szydlo. “Merkle tree traversal in log space and time.” Pages 541–554 in: Christian Cachin, Jan Camenisch (editors). Advances in cryptology—EUROCRYPT 2004, international conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2–6, 2004, proceedings. Lecture Notes in Computer Science 3027. Springer. ISBN 3-540-21935-8.

Introduces the log traversal algorithm which improves the performance of the fractal traversal for certain metrics. As claimed in the title, the algorithm can do tree traversal in log space and time. Main contribuition: A scheduling for the tree hash instances that can run with a single stack.

2007. Piotr Berman, Marek Karpinski, Yakov Nekrich. “Optimal trade-off for Merkle tree traversal.” Theoretical Computer Science 372, 26–36.

Proves the fractal tree traversal to be asymptotically optimal. Proposes as a extension that left nodes can be computed almost for free.

2008. J. Buchmann, Erik Dahmen, M. Schneider. “Merkle tree traversal revisited.” Pages 63–77 in: Johannes Buchmann, Jintai Ding (editors). Post-quantum cryptography, second international workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17–19, 2008, proceedings. Lecture Notes in Computer Science 5299, Springer.

Improves the log traversal algorithm. Main improvement: The paper suggests to measure computation in terms of computed leaves. This better captures the case of hash-based signature schemes as a OTS key generation is much more costly than a single hash computation. Also shows how to deal with stateful pseudorandom generators for key generation.

2014. Berry Schoenmakers. “Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal.” https://eprint.iacr.org/2014/329

Introduces a new pebbling algorithm and proves it optimal under certain conditions.

2014. Markus Knecht, Willi Meier, Carlo U. Nicola. “A space- and time-efficient Implementation of the Merkle Tree Traversal Algorithm.” http://arxiv.org/abs/1409.4081

Improves the fractal tree traversal algorithm, adapting several improvements used for the log traversal algorithm before. Uses the number of leaf computations to measure performance, which is the important factor when using it for MSS. Also considers the case of pseudorandom key generation using stateful pseudorandom generators. Seems like the best solution at the moment if one is willing to spend slightly more storage than for the log algorithm. C implementation wanted…

Special Implementations

2008. Sebastian Rohde, Thomas Eisenbarth, Erik Dahmen, Johannes Buchmann, Christof Paar. “Fast Hash-Based Signatures on Constrained Devices.” Pages 104-117 in: Gilles Grimaud, François-Xavier Standaert (editors). Smart Card Research and Advanced Applications, 8th IFIP WG 8.8/11.2 International Conference, CARDIS 2008, London, UK, September 8-11, 2008, proceedings. Lecture Notes in Computer Science 5189. Springer. ISBN 978-3-540-85892-8.

Implementation of a Merkle tree signature scheme with Winternitz-OTS on a 8-bit smart card microprocessor.

2013. Andreas Hülsing, Christoph Busold, Johannes Buchmann. “Forward secure signatures on smart cards.” Pages 66-80 in: Lars R. Knudsen, Huapeng Wu (editors). Selected Areas in Cryptography, 19th International Conference, SAC 2012, Windsor, ON, Canada, August 15-16, 2012, Revised Selected Papers. Lecture Notes in Computer Science 7707. Springer. ISBN 978-3-642-35998-9.

Implementation of a two-tree-layer XMSS variant on a 16-bit smart card.

2013. Thomas Eisenbarth, Ingo von Maurich, Xin Ye. “Faster Hash-Based Signatures with Bounded Leakage.” Pages 223-243 in: Tanja Lange, Kristin Lauter, Petr Lisoněk (editors). Selected Areas in Cryptography – SAC 2013, 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers. Lecture Notes in Computer Science 8282. Springer. ISBN 978-3-662-43413-0.

Implementation on an AVR ATxmega micro controller. Proposes a changed tree traversal algorithm to achieve better leakage resilience.

2016. Andreas Hülsing, Joost Rijneveld, Peter Schwabe. “ARMed SPHINCS — Computing a 41KB signature in 16KB of RAM.” Pages 446-470 in: Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang (editors). Public-Key Cryptography – PKC 2016, 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I. Lecture Notes in Computer Science 9614. Springer. ISBN 978-3-662-49383-0.

Implementation of SPHINCS on an ARM Cortex M3 micro controller.

Theoretical Background

Presents a (chain-based) signature scheme construction from any universal one-way hash function (UOWHF).

1990. John Rompel. “One-way functions are necessary and sufficient for secure signatures.” Pages 387–394 in: Proceedings of the 22nd annual ACM symposium on theory of computing, May 13–17, 1990, Baltimore, Maryland, USA. ACM Press.

Proves the statement of the title by giving a construction for UOWHF from any one-way function. This fills the last gap left open by Naor and Yung. The paper sketches all required steps and gives a good intuition what is done but omits many details.

1997. Mihir Bellare, Phillip Rogaway. “Collision-Resistant hashing: Towards making UOWHFs practical.” Pages 470-484 in: Burton S. Kaliski Jr. (editor). Advances in Cryptology — CRYPTO ’97, 17th Annual International Cryptology Conference Santa Barbara, California, USA August 17–21, 1997, proceedings. Lecture Notes in Computer Science, 1294. Springer. ISBN 978-3-540-63384-6.

Introduces the XOR-tree technique later used to reduce the security requirements for Merkle trees to second-preimage resistance of the used hash function.

2005. Jonathan Katz, Chiu-Yuen Koo. “On constructing universal one-way hash functions from arbitrary one-way functions.” http://eprint.iacr.org/2005/328.

Gives the complete detailed formal proof for Rompel’s construction.

2013. Dan Boneh, Mark Zhandry. “Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World.” Pages 361-379 in: Ran Canetti,
Juan A. Garay (editors). Advances in Cryptology – CRYPTO 2013, 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013, proceedings, Part II. Lecture Notes in Computer Science, 8043. Springer. ISBN 978-3-642-40083-4. http://eprint.iacr.org/2013/088.

Introduce a quantum security model for signature schemes where the adversary is allowed to ask quantum superposition queries. Proof that Lamport’s scheme is secure in their model assuming one-wayness of the function used. Hence, all constructions that use Lamport to actually sign the message are secure in this quantum security model (at least for schemes that sign fixed size messages and hence use no hash function to first compress messages). If a hash function is used for message compression, Boneh and Zhandry get a reduction if this function is collision resistant. They extend the result on Lamport to show that one can build a fixed-length signature scheme, achieving their security notion, from any OWF.

2014. Fang Song. “A Note on Quantum Security for Post-Quantum Cryptography.” Pages 246-265 in: Michele Mosca (editor). Post-Quantum Cryptography, 6th International Workshop, PQCrypto 2014, Waterloo, ON, Canada, October 1-3, 2014. Proceedings. Lecture Notes in Computer Science, 8772. Springer. ISBN 978-3-319-11658-7. http://eprint.iacr.org/2014/709.

Gives conditions for security reductions to be preserved if the attacker is quantum. Proofs that the security reduction for XMSS holds in the presence of quantum adversaries (all the way from the OWF).

Standards / Drafts

2014. David McGrew, Michael Curcio. “Hash-Based Signatures”. Internet-Draft, Crypto Forum Research Group, IETF. https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/

Draft for an RFC. Version 2 from July 4, 2014, covers Merkle’s basic hash tree scheme with Winternitz-OTS.

2015. Andreas Hülsing, Denis Butin, Stefan-Lukas Gazdag, Aziz Mohaisen. “XMSS: Extended Hash-Based Signatures”. Internet-Draft, Crypto Forum Research Group, IETF. https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatures/

Draft for an RFC. Version 2 (01) from July 3, 2015, covers a variant of XMSS with WOTS+ as well as a multi-tree version. It deviates from the original XMSS quite a bit as it applies a new technique to prevent multi-target attacks. Therefore the hashing is done bit differently. It also describes how to do the message hash in a collision resilient way.

Patents

1979. Ralph C. Merkle. “Method of providing digital signatures.” U.S. Patent 4309569 A. (expired 1999) http://www.google.com/patents/US4309569

The Merkle tree scheme.

1987. Ralph C. Merkle. “Digital signature system and method based on a conventional encryption function.” U.S. Patent 4881264 A. (expired 1998) http://www.google.com/patents/US4881264

Defines a certification tree scheme where every node in the tree consists of three OTS keys: One to sign the left child node, one to sign the right child node and one to sign a message.

1993. Frank T. Leighton, Silvio Micali. “Large Provably Fast And Secure Digital Signature Schemes Based On Secure Hash Functions.” U.S. Patent 5432852. (expired 2013) http://www.google.com/patents/US5432852

Proposes several improvements for hash-based signatures. Especially, it proposes to append a a bit string to each message to be hashed within the tree or the OTS. This bitstring is different for each node within the tree or OTS and also for all users. They propose something like (UserID || uniqueAddress) to be used. This allows to give a random oracle model reduction to second-preimage resistance instead of collision resistance. (The paper actually reads more like a research paper than like a patent.)

2000. Pankaj Rohatgi. “Commitments in signatures.” U.S. Patent 6826687. (should expire 2020) [link]

Roughly captures his 1999 CCS paper.