4
$\begingroup$

I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact:

Fact 1: $\Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\\\$} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$, where $R_q=\mathbb{Z}_q[X]/(X^n+1)$, where $n$ is a power of two, $q$ is a prime and $\beta$ is some positive real number.

Now, let $D_\sigma$ be the discrete Gaussian distribution on $R=\mathbb{Z}[X]/(X^n+1)$ (which can also be viewed as the discrete Gaussian on $\mathbb{Z}^n$ via the coefficient embedding from $R$ to $\mathbb{Z}^n$. Another fact:

Fact 2: $\Pr[\Vert z\Vert_\infty \leq \mathcal{O}(\sigma\sqrt{n}): z\leftarrow D_\sigma]>1-2^{-n}$ for appropriate choice of $\sigma$.

Now suppose that $a\xleftarrow{\\\$}R_q$ and $s,e\leftarrow D_\sigma$ so that $b=as+e$, hence $(a,b)$ is an RLWE sample for secret $s$. Thus, $\Vert s\Vert_\infty,\Vert e\Vert_\infty$ are both less than $\beta=\mathcal{O}(\sigma\sqrt{n})$ with overwhelming probability by Fact 2.

Now I want to prove that it is impossible to find another $s^\prime, s^\prime\neq s$, $\Vert s^\prime\Vert_\infty\leq \beta$ such that $b=as^\prime+e^\prime$, $\Vert e^\prime \Vert_\infty\leq \beta$ with overwhelming probability. Here is my argument:

Proceed by contradiction. Suppose $b=as^\prime+e^\prime$. (Assume that $a$ is an invertible element of $R_q$, this is the case with overwhelming probability for the case $q=3\pmod{8}$). Then $s^\prime=a^{-1}(b-e^\prime)=a^{-1}(e-e^\prime)+s$. Thus, $(a^{-1},s^\prime)$ is an RLWE sample for secret $e^\prime-e$ since $a^{-1}$ is uniformly random by the fact that $a$ is uniformly random. Hence, such $s^\prime$ is indistinguishable from a uniformly random element in $R_q$ by the decisional-RLWE assumption. But by Fact 1, for $q>4\beta +2$, the probability that $\Vert s^\prime \Vert_\infty \leq \beta$ is $<2^{-n}$. Hence, such small $s$ is unique with overwhelming probability. (This also tells that if we don't put any restriction on the norm of $s$, the RLWE secret for $b$ is not unique since we can simply construct such $s^\prime$).

So, I would like to know if my argument is correct or not, and would appreciate any helpful feedback from anyone.

$\endgroup$
2
+150
$\begingroup$

The statement you are trying to make is information-theoretic (existence of something), not computational (easiness of finding something), so the fact that you invoke the RLWE hardness assumption is concerning.

One thing you do have right is to indeed consider the difference of two solutions $[\mathbf A; \mathbf I] \cdot (s-s', e-e') = 0$. In fact, the set of such differences form the SIS-lattice, so you essentially are trying to prove that there are no SIS solutions for a shortness of $2\beta$ in the $\ell_\infty$ norm. In other words, one wants to prove that the minimal distance of the RSIS lattice is above $2\beta$.

The standard proof strategy goes as follows:

  • consider each non-zero $z$
  • For a random $\mathbf A$, Note that $\mathbf Az$ is uniform
  • Bound the probability that $\mathbf Az$ falls in a ball of radius $2\beta$ (using your first fact)
  • Apply a union bound over all the $z$ of norm less than $2\beta$
  • Conclude.

You'll find the details of such a proof in various lecture notes, (e.g., Lemma 5 of https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf). This is typically given for general lattice (without ring structure), but, apart from non-invertibility issue (which you already figured out how to handle with $q \cong 3 \mod 8$) the proof can be adapted to the ring setting.

$\endgroup$
6
  • $\begingroup$ Thanks for the feedback. In my case, the polynomial $a$ corresponds to matrix $\mathbf{A}$ consisting of columns who are anti-cyclic shifts of the coefficients of $a$. So given that $a$ is uniformly random chosen in $R_q$, can we still regard its corresponding matrix $\mathbf{A}$ as uniformly random? $\endgroup$ Aug 8 at 17:08
  • 1
    $\begingroup$ No, because the columns of your $\mathbf{A}$ are correlated, not independent. $\endgroup$ Aug 8 at 18:59
  • $\begingroup$ Taking the idea from Lemma 5 of lecture-9.pdf, here is my argument: Fix $x_1,x_2\in R_q,$ both nonzero. Define the map $f_{x_1,x_2}: R_q\to R_q$ given by $a \mapsto ax_1+x_2$. It is immediate that $f_{x_1,x_2}$ is a 1-1 map for invertible $x_1$. Thus, $R_q= x_1 R_q + x_2$ for invertible $x_1$. $\endgroup$ Aug 9 at 4:47
  • $\begingroup$ Thus, $\Pr \{(ax_1+x_2 = 0 \pmod{q}: a\leftarrow R_q\}=q^{-n}$ for invertible $x_1$. Taking the union bound over all $(x_1,x_2)\in R_q^2$, $x_1$ is invertible, where $\Vert x_i\Vert_\infty\leq 2\beta$, then $\Pr \{ \exists (x_1,x_2): (ax_1+x_2 = 0 \pmod{q} \cap \Vert x_i \Vert_\infty\leq 2\beta \} \leq (4\beta+1)^{2n}\cdot q^{-n}$ over the choice of uniform $a\in R_q$. Is this right? $\endgroup$ Aug 9 at 5:13
  • $\begingroup$ Yes, this looks essentially ok. Indeed, you do not need the columns of $A$ to be independent; the fact that $Ax$ is uniform is sufficient. A minor adjustment is need at the conclusion to also count for the non-invertible a's. $\endgroup$
    – LeoDucas
    Aug 10 at 9:17

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.