Skip to main content
Cryptography

Return to Answer

Forgot to multiply B by C.inverse
Source Link
LeoDucas
LeoDucas
  • 1.4k
  • 6
  • 12

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A$$A' = C^{-1} A = [B' | I]$. Then $C^{-1} u = A' x = B x_1 + x_2$$C^{-1} u = A' x = B' x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A$. Then $C^{-1} u = A' x = B x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A = [B' | I]$. Then $C^{-1} u = A' x = B' x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.

Source Link
LeoDucas
LeoDucas
  • 1.4k
  • 6
  • 12

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A$. Then $C^{-1} u = A' x = B x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.