Score:1

Literature on (concrete) hardness of Short Integer Solution (SIS)

ng flag

I am interested in what the state of the art results on the hardness of the Short Integer Solution (SIS) instances are. The one I am the most familiar with (and the most discussed) is to use lattice reduction, which can be ignored. I have also found the Blum-Kalai-Wasserman (BKW) algorithm, which seems to be applicable to SIS, though I have not looked too deeply into it. Apart from these, are there other attacks specifically for SIS, or that can be adapted to it, e.g., from attacks on LWE?

It seems that hardness of LWE is widely discussed, hence this question.


Related

Mark avatar
ng flag
One particular tool used to estimate the hardness of LWE instances is Albrecht's [Lattice Esitimator](https://github.com/malb/lattice-estimator). You can view the readme to notice that it does not currently work for SIS instances, but that this is planned. Often, when non-experts (including myself) cite concrete discussions of the hardness of LWE, they are really just citing some output of Albrecht's estimator, which estimates the complexity of various attacks on LWE.
Gareth Ma avatar
ng flag
@Mark Thanks for your comment. I am actually planning to implement SIS into the lattice-estimator, hence the question. For the second comment, note that Albrecht's estimator includes citations of many prior researches in its documentations and source codes, and I am interested in finding those "primary resources" for SIS hardness.
Mark avatar
ng flag
There is a description of several attacks on SIS in "SoK: On the Security of Cryptographic Problems from Linear Algebra". You might find this to be a useful preliminary resource to use for further searching.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.