Join Log in
Score:4
Chito Miranda avatar Crypto

Prove that a small Ring-LWE secret is unique

us flag
Chito Miranda

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.

169
1 + 0
lwe
Score:2
LeoDucas avatar Crypto
gd flag
LeoDucas

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.

0 + 6
Chito Miranda avatar
us flag
Chito Miranda
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?
0
Reply
Chris Peikert avatar
in flag
Chris Peikert
No, because the columns of your $\mathbf{A}$ are correlated, not independent.
1
Reply
Chito Miranda avatar
us flag
Chito Miranda
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$.
0
Reply
Chito Miranda avatar
us flag
Chito Miranda
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?
0
Reply
LeoDucas avatar
gd flag
LeoDucas
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.
0
Reply
Chito Miranda avatar
us flag
Chito Miranda
Yes, I missed to count the number of invertible elements of $R_q$. Thanks for pointing that out! Now, I wonder what will happen to the first probability if $x_1$ is non invertible.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.