The Lamport-Diffie signature scheme is said to be quantum-resistant. Why is that? What would a quantum attempt to attack this signature scheme look like, and how does it fail?
$\begingroup$
$\endgroup$
11
-
2$\begingroup$ Security of lamport signatures reduces to the pre-image resistance of the underlying hash function. The best generic quantum algorithm to find pre-images is grover's algorithm with cost $2^{n/2}$. $\endgroup$– CodesInChaosJun 29, 2013 at 15:52
-
$\begingroup$ @CodesInChaos Where I will be able to find this reduction? $\endgroup$– juaninfJun 30, 2013 at 2:30
-
$\begingroup$ @CodesInChaos I read that the minimal requeriment to build a secure scheme signature is to use a one way function. In this context Why the Lamport-Diffie is quantum resistance? $\endgroup$– juaninfJun 30, 2013 at 3:01
-
$\begingroup$ There are two ways to capture the quantum attack. One allows you to query a classical signing oracle. The other allows you to query a quantum signing oracle. Which one do you consider? $\endgroup$– xagawaJul 2, 2013 at 14:57
-
1$\begingroup$ Returning to the original question, the direct answer is 1) the original reduction is applicable to quantum setting (if the signing oracle is classical) and 2) there might be a family of quantum-resilience one-way functions. If you consider the case that the signing oracle is quantum, then the answer is in Boneh and Zhandry (CRYPTO 2013). $\endgroup$– xagawaJul 6, 2013 at 15:17
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
The security of the LD scheme can be reduced to the one-wayness (aka preimage resistance) of the used hash function. The reduction is quite easy:
Assume you want to invert the one-way function $f$ for image $y=f(x)$, given a forger for LD-OTS. Then you generate a valid LD key pair using $f$, sample a random position i in the key pair and a bit b and replace $pk_{i,b}$ by $y$ and run the adversary on the modified $pk$. If the adversaries query has bit $b$ in position $i$ you abort and restart the proceedure. Otherwise, you can answer the query. Now you hope that the adversaries forgery hash bit $b$ at position $i$. If this is the case, the $i$th element of the signature is a preimage of $y$ under $f$.
The reduction works with only a slight loss in success probability, i.e. you loose something as you abort in some cases. However, this loss can be bounded by $1/2m$ for $m$ bit messages. You can find the details in the post-quantum cryptography book by Bernstein et al..
Now, the argument for the LD scheme to be quantum secure follows from the fact that the best known generic attack against the one-wayness of a hash function using a quantum computer is Grovers algorithm that has exponential runtime. Moreover, there exist several hash functions that are conjectured to be one-way, even in the presence of a quantum computer.
Something else was recently shown by Boneh and Zhandry in their Crypto2013 paper. There they show that the scheme remains secure even if the adversary is given the ability to make super position queries. This models the case that the scheme itself is run on a quantum computer, not only the adversary.
