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:
- $X^n+1$ factors into two irreducible factors modulo $q$, where each factor is of degree $n/2$ see Lemma 3 of here
- 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:
- 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.
- 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$.
- 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}}$.
- 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.
