# Proof that (ring-)LWE secret is unique

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?

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)$$.
• 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. Commented Jul 9, 2021 at 1:46
• @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$. Commented Jul 9, 2021 at 2:53
• 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. Commented Jul 9, 2021 at 2:57
• @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". Commented Jul 9, 2021 at 3:46