# 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}$. – CodesInChaos Jun 29 '13 at 15:52
@CodesInChaos Where I will be able to find this reduction? – juaninf Jun 30 '13 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? – juaninf Jun 30 '13 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? – xagawa Jul 2 '13 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). – xagawa Jul 6 '13 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..