2
$\begingroup$

For most of the lattice-based signature schemes in the hash-based random oracle model (like BLISS), quantum preimage attacks (e.g., Grover's alg) against the random oracle component of the signature are not considered in security estimates and this seems to be reasonable, because a preimage attack does not necessarily violate the unforgeability of the signature. But recently, some papers like Tesla, Tesla# and this, take this kind of attack into consideration.

My question: is this attack really serious and should we look attentively at them in security estimates?

$\endgroup$
2
$\begingroup$

Yes, it is important. In a lattice-based Fiat-Shamir signature scheme, the signature is (z,c) where z is a low-norm vector and c is a low-norm challenge.

The verification equation then satisfies c=H(Az-tc,m) where A and t are the public key (A is a matrix and t is a vector) and m is the message. If the Adversary is able to find an m' such that c=H(Az-tc,m'), then (z,c) is also a signature for m'. Thus having 128-bit classical pre-image resistance is not enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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