# Quantum resistance of Lamport signatures

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?

• 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}$. Jun 29, 2013 at 15:52
• @CodesInChaos Where I will be able to find this reduction? Jun 30, 2013 at 2:30
• @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? Jun 30, 2013 at 3:01
• 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? Jul 2, 2013 at 14:57
• 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). Jul 6, 2013 at 15:17

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