2
$\begingroup$

I read Regev's paper in 2005 about Learning with Errors and he mentioned that the secret of a LWE sample is unique but I have not seen a proof of this claim. Can someone point me to a paper proving this claim? Also, for the ring-LWE case, in particular for power of two cyclotomics, is the secret always unique?

$\endgroup$
3
$\begingroup$

Regev's LWE Survey contains a sketch of the proof.

Algorithms. One naive way to solve LWE is through a maximum likelihood algorithm. Assume for simplicity that $q$ is polynomial and that the error distribution is normal, as above. Then, it is not difficult to prove that after about $O(n)$ equations, the only assignment to $s$ that "approximately satisfies" the equations is the correct one. This can be shown by a standard argument based on Chernoff’s bound and a union bound over all $s\in\mathbb{Z}_q^n$. This leads to an algorithm that uses only $O(n)$ samples, and runs in time $2^{O(n \log n)}$. As a corollary we obtain that LWE is "well-defined" in the sense that with high probability the solution $s$ is unique, assuming the number of equations is $\Omega(n)$.

It may also be useful to view LWE from a different perspective --- namely as a parameter range for SIS where it is a priori unclear whether a solution should exist or not, so one "plants" one. See these notes for some perspective along these lines. Note that for standard SIS many solutions exist with high probability, so "LWE = Decisional SIS (in some parameter range)" is easy to get confused by if one is not careful, see for example this question.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer but I still don't see how the claimed algorithm above goes. Is there any available reference where this was explicitly proved? I am not exactly sure but my idea is suppose $b=A^Ts+e=A^Ts^\prime=e^\prime$, $e,e^\prime$ short. Then $A^T(s-s^\prime)=(e^\prime-e)$, then I don't know what comes next. $\endgroup$ Jul 9 at 1:46
  • $\begingroup$ @ChitoMiranda I don't know of it being written down anywhere. The argument (as I interpret it) is somewhat simple. Look at the probability (over uniformly random choice of $A$) of $\lVert A(s - s')\rVert$ being small. You can choose your favorite norm here, but the $\ell_\infty$ norm seems like a particularly good choice, as then you can reduce the problem to $\Pr[\forall i\in [m] \langle a_i, s_i - s_i'\rangle\text{ is small}] = 1 - (1 - \Pr[\langle a_i, s_i - s_i'\rangle \text{ is small})^m$. $\endgroup$
    – Mark
    Jul 9 at 2:53
  • $\begingroup$ Then union bound over all choices of $s'$, e.g. show $\Pr[\forall s' : \lVert A(s -s ')\rVert\text{ is big}] = 1-\Pr[\exists s'\neq s : \lVert A(s -s ')\rVert\text{ is small}] \geq 1 - q^n \Pr[\lVert A(s-s')\rVert\text{ is small}] = 1 - q^n (1 - \Pr[\langle a_i, s_i-s_i'\rangle\text{ is small}])^m$. That being said, working out the details seems fairly annoying, so I'll leave it to you (or someone else) to do so. $\endgroup$
    – Mark
    Jul 9 at 2:57
  • $\begingroup$ thanks for the help. I will definitely try your ideas and see if I come up with a rigorous proof. I struggle reading LWE-related papers since they leave out a lot of details that seem trivial to them but not for a novice like me. Thanks again and will probably post a proof if I succeed. $\endgroup$ Jul 9 at 3:02
  • $\begingroup$ @ChitoMiranda There exist indirect ways of proving this as well. Specifically it suffices to show that $\lambda_1(\Lambda_q(A))$/2 is larger than $\lVert e\Rvert$ with high probability. This should be a consequence of lemma 7.9.2 of Zamir's Lattice Coding for Signals and Networks, where it is shown that for random $q$-ary codes $A$, the number of points of $\Lambda_q(A)$ in $S$ approaches the density of $\Lambdaa_q(A)$ times $\mathsf{Vol}(S)$, e.g. what one would expect if the lattice points were "independent". $\endgroup$
    – Mark
    Jul 9 at 3:46

Your Answer

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

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