Talk:Short integer solution problem

Some problems in this article

General problems

1. Parameter constraints on m in section 3.1 are given as inequalities, but constraints on m in section 3.3 are given as approximations. Again, the cited works use different notation and present bounds in a different form than the article, which is fine, except that it is difficult what the author of the article means by this approximation symbol. It would be better to use asymptotic notation like big oh, big omega, big theta, etc notation than to use the approximation notation, and even better to use inequalities as in section 3.1.
2. Section 3.3 mentions how the constraints on m change, but no comment is made about beta. Even if they are unchanged, a comment should be made about beta.
3. It seems like the latter part of 3.3 (beginning with the definition of the nega-circulant matrix and including the rest of the section) belongs in section 3.2. If so, the citation "SWIFFT: A modest proposal for FFT hashing" provides no security analysis on the general R-SIS problem, but does describe the nega-circulant matrix stuff, and so should also be moved out of section 3.3 and into section 3.2. If the latter part of 3.3 is not moved, then it seems to me like the current placement of the citation within the article suggests that this citation has something to say about the parameter constraints required for solutions to exist.
4. The constraints presented in "Generalized Compact Knapsacks" are worse than the constraints presented in section 3.3, no works are cited that improved them, and it's not clear to me where they come from without a citation. I think these bounds were improved in "Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors" by Chris Peikert and Alon Rosen, but I believe this is not the only improvement in this area. This issue is made difficult because the cited works use different notation and present bounds in a different form than this wikipedia article, so it is not immediately clear from reading the citations whether the bounds in this article are accurate.

Bad citation

1. The citation "Generalized Compact Knapsacks" was written by Lyubashevsky and Micciancio, not just Micciancio.

Suggested changes

1. Replace the approximation constraint on m in section 3.3 with something more precise (if not sharp inequalities, at least asymptotics)
2. Include constraints on beta in section 3.3 (even if they are the same constraint from section 3.1).
3. Move the definition of the nega-circulant matrix and the last two paragraphs of section 3.3 to section 3.2.
4. Move citation "SWIFFT" in section 3.3 to section 3.2.
5. Find correct citations for the constraints presented in section 3.3 and, if possible, document a sequence of citations improving those constraints.
6. Correct the citation "Generalized Compact Knapsacks" to include both authors.
7. A section describing estimating the hardness of a Ring-SIS instance would be a welcome addition. Two good citations for this include "A Framework to Select Parametersfor Lattice-Based Cryptography" by Alkadri, Buchmann, Bansarkhani, and Kramer (see here) and "Parameter selection in lattice-based cryptography" by Player (see here.)

Bggoode (talk) 18:35, 22 April 2021 (UTC)