# 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?

-

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.

-
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$.