Hi weve been given the following question in one of our classes but have not been taught anything about it and is worded strangely. It is to show how the LWE problem works by showing how small errors can have a big impact on the result using the two equations below.

$$ \begin{bmatrix}100 & 99 \\101 & 100 \end{bmatrix}\begin{bmatrix}S_1 \\S_2 \end{bmatrix} = \begin{bmatrix}199 \\201 \end{bmatrix} mod 500 \rightarrow \begin{bmatrix}S_1 \\S_2 \end{bmatrix} = \begin{bmatrix}1 \\1 \end{bmatrix} $$

$$ \begin{bmatrix}100 & 99 \\101 & 100 \end{bmatrix} \begin{bmatrix}S_1 \\S_2 \end{bmatrix} + \begin{bmatrix}0 \\1 \end{bmatrix} = \begin{bmatrix}199 \\201 \end{bmatrix} mod 500 \rightarrow \begin{bmatrix}S_1 \\S_2 \end{bmatrix} = \begin{bmatrix}100 \\-99 \end{bmatrix} $$

Ive been trying to read about it on some papers but am having trouble understanding what they mean. Can anyone explain how to do this in a simple way.

  • $\begingroup$ You have two many equality signs, and the second (0,1) should probably be (S1,S2). And the idea was probably to have two slightly different vectors on the right (now they are both equal to (199,201)) leading to very different solution vectors (S1,S2). $\endgroup$ – TMM Jul 11 '17 at 2:18
  • $\begingroup$ yeah sorry I don't know how i copied it down so wrong. fixed $\endgroup$ – dmnte Jul 11 '17 at 5:45
  • 1
    $\begingroup$ The basic intuition here is that if you simply "solve" for S (with Gaussian elimination), then the results will be very different based on the chosen noise/error vector - the noise hides the secret coefficient vector (S1,S2), and without knowing the error vector it will therefore be hard (or so we think) to recover this secret vector. $\endgroup$ – TMM Jul 11 '17 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.