The One-More-ISIS Problem

In “Practical, Round-Optimal Lattice-Based Blind Signatures” by Shweta Agrawal, Elena Kirshanova, Damien Stehle and Anshu Yadav, the authors introduce a new candidate hard lattice problem. They introduce this problem to build blind signatures but in this blog post, I’ll ignore the application and only talk about the cryptanalytic target: One-more-ISIS.

A challenger selects a matrix and sends it to the adversary. The adversary can perform two types of queries:

1. Syndrome queries The adversary can request a challenge vector which the challenger selects at random, i.e. , adds to some set and returns to the adversary.
2. Preimage queries. The adversary submits any vector . The challenger will return a short vector such that . Denote for the number of preimage queries.

In the end the adversary is asked to output pairs satisfying:

• ,
• and
• .

The hardness of the problem depends on the parameters, critically and . To see this consider the following two attacks, given in the above mentioned paper.

Combinatorial Attack. The adversary requests preimages for all , here is the -th unit vector. Then, adding up such preimages allows to construct any image. Since the norm of the preimages returned by the challenger is , this allows to solve the One-more-ISIS problem when . Of course, smaller and larger sets of preimages are possible, increasing and decreasing the output norm respectively.

Lattice Attack. The adversary requests preimages of zero and uses that to produce a short basis for the kernel of , i.e. . This constitutes a trapdoor for and thus permits to return short preimages for any target. The key point here is that this trapdoor is of degraded quality relative to the trapdoor used by the challenger. The key computational challenge then is to fix-up or improve this degraded trapdoor in order to be able to sample sufficiently short vectors.

I’d say that last computational problem is of more general interest. That is, given some polynomial number of short vectors in a lattice, how hard is it to produce a slightly shorter basis for this lattice? Okay, technically, there might be a way of sampling short preimages without finding such a high-quality basis, but finding such a high-quality basis would certainly solve the problem.

Finally, it’s worth noting that this problem is not only relevant for building blind signatures. It would also arise in some side-channel attacks on GPV-style signature schemes such as Falcon. That is, in these signature schemes, signing the same twice would produce a preimage of zero, i.e. implies . Sampling many such preimages of zero would constitute a trapdoor as discussed above. Falcon defends against this by signing for some fresh random . Now, in a setting where only poor randomness is available (think attacks on Schnorr-like signatures with poor randomness) this might collapse down to again. Studying lattice attacks on One-more-ISIS would help us to understand how devastating this would be.