Merkle signature scheme: Difference between revisions

In [[hash-based cryptography]], the '''Merkle signature scheme''' is a [[Digital signature|digital signature scheme]] based on [[Merkle tree|Merkle trees]] (also called hash trees) and one-time signatures such as the [[Lamport signature|Lamport signature scheme]]. It was developed by [[Ralph Merkle]] in the late 1970s and is an alternative to traditional digital signatures such as the [[Digital Signature Algorithm]] or [[RSA (algorithm)|RSA]].

An advantage of the Merkle signature scheme is that it is believed to be resistant against attacks by [[quantum computer|quantum computers]]. The traditional [[Public-key cryptography|public key]] algorithms, such as RSA and [[ElGamal signature scheme|ElGamal]] would become insecure if an effective quantum computer could be built (due to [[Shor's algorithm]]). The Merkle signature scheme, however, only depends on the existence of secure [[hash function]]s. This makes the Merkle signature scheme very adjustable and resistant to quantum computer-based attacks. The Merkle signature is a ''one time signature'' with finite signing potential. The work of [[Moni Naor]] and [[Moti Yung]] on signature based [[One-way permutation|one-way permutations]] and functions (and the invention of [[universal one-way hash function|universal one-way hash functions]]) gives a way to extend a Merkle-like signature to a complete signature scheme.{{Citation needed|date=January 2017}}