Problemă SIS vs LWE

Funcția unidirecțională Ajtai este definită de

$$f_A(x)= Ax \; mod\; q $$ unde x $\în \{0,1\}^m$ și A $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ este o funcție unidirecțională ( Ajtai 96)

În timp ce funcția Regev One way (Regev 05) este definită peste x $\în \mathbb{Z_q}^k$ și $e \in \mathscr{E}^m$ și A $\in \mathbb{Z_q}^{m \times k}$ .Funcția unidirecțională este definită ca

$$g_A(x,e) =Ax +e \; mod\; q \; (LWE) $$

$g_A(x,e)$ este o funcție unidirecțională.Întrebarea mea este: funcția One way a lui Regev oferă avantaj față de funcția Ajtai One way în ceea ce privește proiectarea de noi scheme de criptare sau sunt echivalente în ceea ce privește cazurile lor de utilizare? De asemenea, sunt echivalente în ceea ce privește duritatea?

Există constrângeri importante în parametrii funcției lui Ajtai, ceea ce o face foarte surjectivă (fiecare imagine are multe preimagini). Nu știm cum să obținem o schemă de criptare din asta.

Dimpotrivă, cea a lui Regev este folosită de obicei într-un regim injectiv. Și știm cum să construim și o schemă de criptare din ea.

In ceea ce priveste Duritatea, rezolvarea SIS terminata $A^t$ destul de direct permite rezolvarea LWE peste $A$. În cealaltă direcție există și o reducere care este cuantică. Deci, cel puțin pentru computerele cuantice, problemele sunt echivalente.

Acest lucru ar trebui luat cu un sâmbure de sare: există pierderi uriașe în această reducere. În special, LWE este cu niste parametri uriași probabil mai greu decât SIS cu un anumit parametru mai rezonabil.