# Is my proof about uniqueness of ring-LWE secret correct?

Suppose that $$n$$ is a power of two, $$q=3\pmod 8$$, prime and $$R=\mathbb{Z}[X]/(X^n+1)$$. Denote $$\Vert\cdot\Vert$$ as the infinity norm in $$R_q=R/qR$$ on the coefficients of elements in $$R_q$$. The coefficients are assumed to be in $$[-\frac{q-1}{2},\frac{q-1}{2}]$$. I'll just cite some facts that I will use in my proof:

1. $$X^n+1$$ factors into two irreducible factors modulo $$q$$, where each factor is of degree $$n/2$$ see Lemma 3 of here
2. As a consequence of the above fact, given a fixed $$s\in R_q$$, $$s\neq 0$$, the number of distinct $$a\cdot s\in R_q$$, over all $$a\in R_q$$ is at least $$q^{n/2}$$, as claimed but without rigorous proof from page 7.

Now my claim is that given a uniformly random $$a\in R_q$$, an RLWE sample $$b=as+e$$ (where $$s,e$$ are chosen from a discrete Gaussian distribution on $$\mathbb{Z}^n$$ so that with overwhelming probability, $$\Vert s\Vert, \Vert e\Vert\leq \beta$$, for some $$\beta$$) has a unique secret $$s$$. So the proof goes by contradiction:

1. Suppose that given a uniformly random $$a\in R_q$$, assume that $$b=as+e=as^\prime+e^\prime$$, where $$s\neq s^\prime$$ and $$s,s^\prime,e,e^\prime$$ are chosen from the above discrete Gaussian distribution so that all their norms are $$\leq \beta$$ with overwhelming probability.
2. Thus, we can rewrite the above equation as $$a(s-s^\prime)=(e^\prime-e)$$ and we claim that this only happens with negligible probability over all such $$a,s,s^\prime,e,e^\prime$$.
3. We proceed in several steps: First, fix $$e,e^\prime,s,s^\prime$$ and ask the probability that the above equation holds over all $$a\in R_q$$, that is, what is the probability that $$a(s-s^\prime)=(e^\prime-e)$$ for a uniformly random $$a\in R_q$$? My answer to this question is that since $$a(s-s^\prime)$$ takes at least $$q^{n/2}$$ different values over all $$a\in R_q$$, then the above equation holds with probability $$\leq \dfrac{1}{q^{n/2}}$$.
4. Finally, we take the union bound over all $$s,s^\prime,e,e^\prime$$ taken from the discrete Gaussian distribution so that all of them have norms $$\leq \beta$$ with overwhelming probability, then the overall probability that $$a(s-s^\prime)=(e^\prime-e)$$ is $$\leq \dfrac{(2\beta+1)^{4n}}{q^{n/2}}$$, since the number of elements in $$R_q$$ that has infinity norm less than $$\beta$$ is $$(2\beta+1)^n$$ and by the triangle inequality.

I showed this proof to my professor but it does not make sense to him and said that I am making a dumb mistake specially on step 3 of my proof.

Right now, I don't see why my proof is incorrect and he did not mention why my proof is wrong. I tried to explain to him my proof but was shut down since for him, I did a terrible mistake.

So anybody who can help and shed light to this matter is greatly appreciated.

• I can see the following issue --- you are (implicitly) analyzing the function $T_a(s) = as$. Your statement about the number of values $as$ can take is just that $\mathsf{im}(T_a) \geq q^{n/2}$. In this language, what happens to your argument when $e\in R_q\setminus \mathsf{im}(T_a)$? Should we expect such points to exist? (hint --- yes. Why?)
– Mark
Jul 9 at 6:03
• It is very likely possible that there $R_q\setminus \mathsf{im}(T_a)$ is nonempty and in fact, has cardinality $\leq q^n-q^{n/2}$. So it seems to me now that when I take the union bound, it should be under the condition that $e^\prime-e\in \mathsf{im} (T_a)$, is this correct? Jul 9 at 21:59
• What do you do if e'-e is not in this set though? This is the crux of the issue with your argument.
– Mark
Jul 10 at 5:24