Hashbased Signatures
Today's challenge
Digital signatures are massively used online, notably for authentication, integrity checking and nonrepudiation. The digital signature algorithms most commonly used in practice — RSA, DSA and ECDSA — rely on hardness assumptions about number theoretic problems, namely composite integer factorisation and the computation of discrete logarithms. In 1994, Peter Shor [Sho94] showed that these number theoretic problems would become breakable in the presence of quantum computing. Quantum computers could solve them in polynomial time, compromising the security of the digital signature schemes used today. While quantum computers are not yet available, their development is occurring at a swift pace and therefore constitute a real threat over the next decades. Fortunately, postquantum cryptography provides a variety of quantumresistant alternatives to classical digital signature schemes [BBD09]. Hashbased signatures or Merkle signatures as they are also known, are one of the most promising of these alternatives.
Why go hashbased?
There are many reasons to use hashbased signature schemes and to prefer those over other alternatives. While the very early Merkle Signature Scheme lacks of practical performance and space requirements, today's hashbased schemes like XMSS are reasonably fast and yield small signatures. Also the security requirements are compelling. While the security of other postquantum cryptographic schemes like latticebased ones is still object to further research, hashbased signatures are well understood. Using a signature scheme always requires a hash function to reduce a message to a small representation of characters that can be signed easily. While other signature schemes rely on additional intractability assumptions to generate a signature, a hashbased solution only needs a secure hash function for the same procedure. Therefore the security of the scheme holds with the hash function used. If the latter one gets compromised, it can be replaced. The underlying Merkle scheme is not affected. Some hashbased schemes even reduce the need for a collisionresistant hash function to one that only needs to withstand attacks on the secondpreimage. That given you will get to know about security issues early as attacks in general aim on the stronger security assumption. As an example practical attacks in means of the collisionresistance of the MD5 function are known, but we still do not know about virtual attacks on the secondpreimage. With some schemes, other desirable features like forward security are available as well. A scheme being forward secure means that an attacker will not be able to get information about formerly used signature keys by getting hold of the current private key.
OneTime Signatures
Hashbased signatures are based on socalled onetime signatures (OTS). As the term implies, a single key pair must only be used once. Otherwise, an attacker is able to reveal more parts of the private key and spoof signatures. A popular example is the scheme proposed by Leslie Lamport and Whitfield Diffie in 1979 [Lam79]. As one can imagine, this is not very practical. Many key pairs are needed to sign lots of messages, and therefore some kind of key management is required. A solution to cope with this situation was proposed by Ralph Merkle in 1979 [Mer79]. He suggested the use of (binary) hash trees, which are now called Merkle trees. But first, more about onetime signatures: For this kind of signature one generates random data for each case of having a '0' or a '1' representing a single bit of the message. This is the private key. The public key represents the hashed version for each of the random data blocks. To sign a message, the private key data for each bit is revealed, depending on the single message bit being '0' or '1'. A verifier can calculate the hashes and compare them to the public key. Here one notices that generating a second signature would tell more about the private key and allow an attacker to forge further signatures. Therefore a single key pair must only be used once. To improve performance and reduce space requirements, Merkle proposed the Winternitz OTS, named after Robert Winternitz. The basic idea of the Winternitz OTS is to sign several bits at once.
Here you can see the LamportDiffie scheme (example message 001) following McGrew's visualisation (link to NIST):
Hashbased Signatures
To overcome the key management problem of onetime signature key pairs, Merkle proposed the use of hash trees. In the Merkel signature scheme (MSS), verification keys are hashed and build the leaves of the tree. Neighbouring children are concatenated and then hashed to build the parent node. The root of the tree represents the public key of the scheme. A signature is generated by applying the private key of an OTS scheme. The corresponding verification key is handed on to the receiver of the message along with the signature. The verifier also has to be told about neighbouring nodes on the path to the root of the MSS tree, which is referred to as the authentication path. Using that information, the receiver can verify the signature and use the verification key to build the leave and reach the root of the tree using the authentication path. The root is already known to the verifier as the public key, which he obtained earlier, for example via a certificate. For each new signature generated the next key pair must be used. As one can see, this scheme is stateful. For example, the index of the used key pair — respectively leaf — of the MSS tree must be stored. This is a whole new situation in the use of cryptographic schemes. Due to slow runtimes, as well as large key and signature sizes, this scheme was not used in practice since other schemes like RSA were known and easier to implement. But as the need for postquantum cryptography has arisen, the interest in hashbased signatures led to renewed interest in those schemes and significant improvements occurred over the last years. Signature generation is much faster thanks to the use of pseudorandom number generators, the construction of large is trees is easier thanks to multitree proposals and many more contributions have been made. In 2011, Andreas Hülsing introduced XMSS [BH11], a hashbased signatures scheme based on minimal security assumptions [Hül13]. This scheme and its multitree variant XMSS^{MT} are the most advanced approaches for practical hashbased signatures.
A list of literature on hashbased signatures can be found on Andreas Hülsing's Website.
A summer school lecture on hashbased signatures by Johannes Buchmann and Andreas Hülsing can be found on Youtube provided by the Institute for Quantum Computing, University of Waterloo.
Here you can see an XMSS tree following Andreas Hülsing [Hül13]:
New Challenges
To introduce hashbased signature schemes to today's cryptographic infrastructure, a few drawbacks must be overcome. This does not mean there are barriers one cannot manage, but issues that just have not arose so far and have to be dealt with and thought about now. Particularly statefulness has to be handled. Private keys of e.g. RSA are stateless. They can easily be used. It's possible to have several copies, no matter whether you allow access for several process for example talking about a TLSserver handling hundreds of connections or whether you want to make backups of your key. Due to the statefulness of hashbased schemes, private keys become a critical resource. Also any kind of copy is a security threat as an attacker could get hold of an old key state and forge signatures. Another aspect are interfaces to cryptographic software like TLS libraries. Those are sometimes not prepared to deal with changing keys. Furthermore, issues emerging from the integration with a public key infrastructure (PKI) such as key distribution and revocation must be addressed.
[BBD09] 
Bernstein, Daniel J. and Buchmann, Johannes and Dahmen, Erik (Editors): PostQuantum Cryptography. Springer (2009) 

[BH11] 
Buchmann, Johannes and Hülsing, Andreas: XMSS — A Practical Forward Secure Signature Scheme based on Minimal Security Assumptions. In: Yang, BoYin (Editor): PostQuantum Cryptography, Vol. 7071, Springer (2011) 

[Hül13] 
Hülsing, Andreas: Practical Forward Secure Signatures using Minimal Security Assumptions. Ph.D. thesis, Technische Universität Darmstadt (2013) 

[Lam79] 
Lamport, Leslie: Constructing Digital Signatures from a One Way Function. In: SRI International Technical Report CSL98, SRI International Computer Science Laboratory (1979) 

[Mer79] 
Merkle, Ralph C.: Secrecy, Authentication, And Public Key Systems. Ph.D. thesis, Stanford University (1979) 

[Sho94] 
Shor, Peter W.: PolynomialTime Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1484–1509 (1997) 