1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ One particular tool used to estimate the hardness of LWE instances is Albrecht's Lattice Esitimator. 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. $\endgroup$
    – Mark Schultz-Wu
    Jul 30, 2023 at 3:52
  • $\begingroup$ @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. $\endgroup$
    – Gareth Ma
    Jul 30, 2023 at 15:27
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Jul 31, 2023 at 19:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.