2
$\begingroup$

I am trying to argue about the hardness of LWE, but in a setting that is different from the standard one.

Consider the task of learning the LWE secret $s$ from noisy samples. The specifications of the problem are an $m \times n$ matrix $A$, a $n \times 1$ vector $s$, and a Gaussian noise vector $e$. By a noisy sample, I mean a vector that evaluates to $As + e$. The Gaussian noise is sampled independently at random from an appropriately chosen Gaussian distribution every time a noisy sample is asked for. $m$ is chosen to be sufficiently large.

The process works as follows:

  1. The learner receives a noisy sample.
  2. The learner processes the sample and guesses what the secret is.
  3. There is a ”judge” who tells the learner how close or far they are, in $L_1$ norm, from the actual secret.
  4. The process repeats.

Is it known that the learner will not converge well to the secret in polynomial time?

$\endgroup$

1 Answer 1

3
$\begingroup$

This would be very bad. Assuming that you're calculating $\mod q$ for some $q$, the learner can recover $s$ with at most $3n$ queries even while ignoring the samples.

I'll assume that $q$ is even, but the odd case is not much harder.

For a first guess the learner could try $s=(0,0,\ldots,0)^T$ and for a second try $(q/2,0,\ldots,0)^T$. Let $a$ be the $L_1$ distance of the first component from 0 and $b$ be the $L_1$ distance of the first component from $q/2$.

I know that $a+b=q/2$ and I known that $a-b$ is the difference of the two pieces of advice which I received in Step 3. I can now compute $a$ and $b$ and narrow the first component down to 2 possible values. A third query will disambiguate.

I can obviously repeat the process for other components.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.