Luați în considerare următoarea modificare a problemei Short Integer Solution (SIS):
Lăsa $n$ fie un număr întreg și $\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$ fie funcţii ale $n$. Eșantionați o uniformă $A\gets[-\alpha,\alpha]^{n\times m}$. Sarcina este de a calcula vectorul „scurt”. $e\in\mathbb{Z}^m$ în nucleul de $A$. Acesta este:
- $|e| < \beta$.
- $A.e=0^n$. Aici, egalitatea este valabilă pentru numerele întregi
Versiunea obișnuită a SIS este aceeași ca mai sus, cu excepția cazului în care $A.e=0^n$ deține mod $q$, și $q=2\alpha+1$ (astfel încât $A$ este uniformă în $\mathbb{Z}_q^{n\ori m}$). Această variantă elimină modulul.
Întrebare: Există rezultate non-triviale de duritate/ușurință pentru această versiune de SIS? Ce setări ale parametrilor sunt ușoare și care (dacă există) pot fi dovedite grele pe baza unor probleme mai grave ale rețelei, ca în versiunea obișnuită a SIS?
Atacul banal: Există un algoritm banal în cazul în care $\beta$ este mare. Puteți calcula un vector nucleu peste numerele întregi luând minore ale matricei $A$. Acești minori și, prin urmare, vectorul nucleului, pot fi delimitați cu ușurință de către $(\alpha n)^{O(n)}$. Deci in regim $\beta= (\alpha n)^{O(n)}$, există un atac banal.
Ceea ce sunt cel mai curios este cazul în care $\alpha,\beta$ sunt polinomiale în $n$. Există atacuri aici sau poate fi arătată vreo duritate?
Am ales distribuția pentru $A$ mai sus pentru a da o problemă concretă. Dar m-ar interesa și alte distribuții pe $A$. De exemplu, ce se întâmplă dacă intrările de $A$ sunt gaussieni discreti, etc?
Se poate lua în considerare și o versiune neomogenă a acestei variante SIS, unde $A.e=u$, pentru un vector $u$ (din nou, fără un modul). Trebuie să fim atenți, deși la mare $u$ nu va fi o solutie. Poate ne limităm la întâmplare $u\in\{0,1\}$, sau în $[-\gamma,\gamma]^n$. De asemenea, m-ar interesa dacă se poate spune ceva și despre această problemă, în afară de adaptarea simplă a banalului atac de sus.
