# Minimum distance between polynomials in ring-LWE

Let $$R_q=\mathbb{Z}_q[x]/\langle f(x)\rangle$$ where $$f(x)=x^n+1$$, as in the ring-LWE problem.

Let $$a(x)$$ be chosen uniformly at random from $$R_q$$.

Question: Is there any theorem that lower bounds the distance between any two polynomials of the form $$a(x)s_1(s)$$ and $$a(x)s_2(x)$$?

In other words, what is the value of $$d$$ such that $$||a(x)s_1(x)-a(x)s_2(x)||\geq d$$ except with negligible probability, for any two polynomials $$s_1(x),s_2(x)\in R_q$$ and where $$||\cdot||$$ is the usual $$L_2$$ norm?

• Hello. It is a good question, but the $L_2$ norm is defined over vectors and it is not clear how you are embedding the polynomials in a vector space. Are you just representing the polynomials as vectors with their coefficients? (So, for instance, $2x^3 -1$ becomes the vector $(2, 0, 0, -1)$). – Hilder Vitor Lima Pereira Nov 24 '18 at 17:19
• Yes, I am thinking of the canonical embedding – P.B. Nov 24 '18 at 17:26
• Well, the canonical embedding is the one that uses isomorphisms to embed the polynomials. The one I've described is the coefficient embedding... – Hilder Vitor Lima Pereira Nov 24 '18 at 17:31
• Sorry. I mean the coefficient embedding then – P.B. Nov 24 '18 at 17:46
• How do you define "negligible probability" in this case? – kodlu Nov 24 '18 at 21:19

I'm assuming $$n$$ is a power of $$2$$ and that $$q$$ is an odd prime larger than $$n$$. I'm discarding the trivial case $$s_1 = s_2$$.
If you consider everything $$\mod q$$, then it is most likely over the choice of $$a$$ that there exists $$s_1 \neq s_2$$ such that $$\|a s_1 - a s_2\| = \sqrt{n}$$. Indeed, $$a$$ is invertible in $$R_q$$ with probability about $$1 - n/q$$. Take $$s_2 = s_1 - a^{-1}$$, then you have $$a s_1 - a s_2 = 1 \mod q$$ and the embedding norm of $$1$$ is $$\sqrt{n}$$.
If you do not consider this $$\mod q$$, i.e. you work in $$R=\mathbb Z[x]/⟨f(x)⟩$$, then you are precisely asking for the minimal distance $$\lambda_1(\mathfrak I)$$ of the ideal lattice $$\mathfrak I$$ generated by $$a$$. For such an ideal lattice, we can estimate rather precisely this minimal distance. A simple lower bound is $$\lambda_1(\mathfrak I) \geq \Delta_K^{1/2n} \cdot N(a)^{1/n}$$, where $$N$$ denotes the algebraic norm of $$a$$ (that is, the product of all its embeddings), and $$\Delta_K$$ is the discriminant of field $$K = \mathbb Q(x)/(x^n+1)$$. The reason is that the minimal vector $$x$$ must generate a subideal of $$\mathfrak I$$, so $$N(x) \geq N(a)$$, and $$\|x\|^n \geq \Delta_K^{1/2} N(x)$$. An upper bound is also given by Minkowski's theorem.
• So this is the canonical embedding we are talking about right? In this case, we have that $||as_1-as_2||\geq \sqrt{n}$? Or are you just saying that there are $s_1,s_2$ such that $||as_1-as_2||= \sqrt{n}$ but there could be others $r_1,r_2$ for which the differente between $ar_1$ and $ar_2$ is even lower? – P.B. Nov 25 '18 at 13:36
• There could be $0$ as well ;). BBut nothing in between indeed, at least for that particular ring. – LeoDucas Nov 25 '18 at 16:26