# Are hash trees an alternative, quantum-resistant signature scheme which can replace RSA?

Can hash trees can provide quantum resistant signatures to replace RSA for signing securely? What is the key size and how many times can we use same key?

-

Hash trees alone wont do that. But hash trees in combination with one time signatures (this is called the Merkle signature scheme).

If you use hash based one time signatures such as Lamport-Diffie, then yes.

Basically, the hash tree is used to "aggregate" $k$ public keys by representing the hash values of the public keys as leaves of the hash tree and recursively computing the hash values of inner nodes of the tree as hash of the concatenation of its children till you obtain the "root public key hash". Then every leave public key can be used for a single time with a one time signature scheme and allows you to produce $k$ signatures in total.

Therefore, you compute a signature with public key $i$ and you have to add the "root public key hash" and the authentication path of public key $i$, i.e. the hash values of all siblings of public key $i$ on the unique path to the root of the tree (this is required to check if public key $i$ is "contained" in the tree by recomputing the root). Latter contains $\log n$ hash values for a tree of height $n$.

The key and signature sizes depend on the used one time signature scheme and in turn on the hash function.

-
Yes for example the Merkle tree hash will be able to replace signature based on RSA. Remember that the best quantum algorithm to finding collisions is the Groover algorithm, but that require $2^{n/3}$ evaluations of hash function.