3
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Grover's Algorithm is a search algorithm with time $O(n^{1/2})$. You're probably thinking of the Brassard-Hoyer-Tapp algorithm instead (which uses Grover's algorithm internally). $\endgroup$
    – Reid
    Dec 29, 2013 at 22:25
  • $\begingroup$ @Reid If I recall correctly Daniel Bernstein analyzed the two algorithms and concluded that no attack will ever be cheaper using Brassard-Hoyer-Tapp then Grover's due to the memory requirements, therefore only $2^{n/2}$ should be taken account for in terms of security levels. $\endgroup$
    – orlp
    Dec 29, 2013 at 22:44
  • $\begingroup$ @nightcracker: That's an interesting bit of research! I was only able to find these slides, though... do you happen to know if there's a paper floating around? (I did some searching on DJB's website and Google Scholar but found nothing.) Anyway, the OP said Grover's algorithm was "the best quantum algorithm to [find] collisions" and took $2^{n/3}$ queries, but that's a description of BHT, not Grover's, AFAIK. $\endgroup$
    – Reid
    Dec 30, 2013 at 0:58
  • 1
    $\begingroup$ @Reid I did some searching and found the paper. It's exactly what I remembered. Bernstein argues that BHT will never be superior to Grover's in price/performance thanks to the largely inferior memory usage. Running parallel instances of Grover is more cost effective, making BHT obsolete. $\endgroup$
    – orlp
    Dec 30, 2013 at 1:15
  • $\begingroup$ @nightcracker: Thanks for the reference! The paper title does not include 'brassard' in its title or keywords, it seems ... At any rate, that'll take some time to digest, but the premise certainly makes sense -- BHT takes $\Theta(n^{1/3})$ space, which really is a fair bit. $\endgroup$
    – Reid
    Dec 30, 2013 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.