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.

  • $\begingroup$ 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?) $\endgroup$
    – Mark
    Jul 9 at 6:03
  • $\begingroup$ 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? $\endgroup$ Jul 9 at 21:59
  • $\begingroup$ What do you do if e'-e is not in this set though? This is the crux of the issue with your argument. $\endgroup$
    – Mark
    Jul 10 at 5:24

Your Answer

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

Browse other questions tagged or ask your own question.