Are quantum preimage attacks on hash-based random oracles serious for lattice signatures?

Question

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?

Answer 1

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.