1
$\begingroup$

Let $\mathcal R$ be the ring of integers of a power of two cyclotomic field. That is, $\mathcal R = \mathbb Z[x] /\langle x^{2^k}+1\rangle $ for some integer $k$. We denote $\mathcal R / q \mathcal R$ by $\mathcal R_q$. This is a well known setup for ring-LWE.

I think that for randomly chosen element $a \in \mathcal R_q$, as I know, the algebraic norm $N(a)$ is approximate to $q^n$. (But I do not also have any reference for this.) Thus, I additionally guess that the determinant of the anti-circulant matrix generated by $\phi(a)$, where $\phi(a)$ is a coefficient embedding from $\mathcal R$ to $\mathbb Z^n$, is also close to $q^n$ with non-negligible probability.

However, I cannot find any reference for the closeness. Could you give me any reference or the answer that the statement is true or not?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Fair warning that

  1. my algebraic number theory is a bit rusty, and
  2. this solely reduces your problem to a (standard) problem, namely showing a lower bound on the shortest vector of a random ideal lattice.

Recall that an ideal lattice in some number field $K$ is a lattice that takes the form $L = I\mathcal{O}_K$, i.e. is an ideal $I$ in the ring of integers of $K$. Ideal lattices, as lattices, satisfy Minkowski's first bound, namely that (in dimension $n$) $\lambda_1(L) \leq \sqrt{n} \sqrt[n]{\det L}$.

Now, given an ideal lattice $I\mathcal{O}_K$, noting that $|N(I)| = |\mathcal{O}_K / I| = \left|\frac{\det I}{\det \mathcal{O}_K}\right|$, we get that $$\lambda_1(I\mathcal{O}_K) \leq \sqrt{n}\sqrt[n]{\det I}\implies \frac{\lambda_1(I\mathcal{O}_K)}{\sqrt{n}\sqrt[n]{\det \mathcal{O}_K}} \leq \sqrt[n]{N(I)}.$$

This reduces your problem to showing that, for average ideals $I$ (or perhaps principle ideals $(a)$), $\lambda_1(I\mathcal{O}_K)$ is large. I know of good references for showing that there exists $I$ such that $\lambda_1(I\mathcal{O}_K)$ is large (namely section 4 of this). A typical reference for discussion that on average integer lattices have $\lambda_1(\mathcal{L}(A))$ large is this or this. I will also briefly give a (directly) proof that $\lambda_1(\mathcal{L}(A))$ is large on average (for uniform $A$). The ones in the references use fairly high-powered tools, namely things like Siegal's integration formula. The direct proof hopefully will show where things break down in the ideal case.

Let $\mathcal{B}_n(c)$ be a (zero-centered) ball of integer vectors of radius at most $c$. Let $\mathcal{L}(A)$ be the lattice generated by a matrix $A$, which we will assume is uniformly random. Then, we have that \begin{align*} \Pr_A[\lambda_1(\mathcal{L}(A)) > c] &= 1 - \Pr_A[\lambda_1(\mathcal{L}(A)) \leq c]\\ & 1 - \Pr_A[\mathcal{L}(A) \cap \mathcal{B}(c) = \{0\}]\\ &\geq 1 - |\mathcal{B}(c)\setminus\{0\}| \max_{z\in\mathcal{B}(c)\setminus\{0\}}\Pr_A[z \in\mathcal{L}(A)]. \end{align*} All that we have done now is rearrange things, and apply the union bound. All that remains is to

  1. estimate $|\mathcal{B}(c)\setminus\{0\}|$, and
  2. compute $\Pr_A[z \in\mathcal{L}(A)]$.

The first is a standard (mathematical) computation, see claim 8.2. The second is also standard (at least for integer lattices) --- one has that $$\max_{z\neq 0}\Pr_A[z \in\mathcal{L}(A)] = \frac{|\mathcal{L}(A)\setminus \{0\}|}{|\mathbb{Z}^n/q\mathbb{Z}^n\setminus\{0\}|} = \frac{q^n-1}{\det \mathcal{L}(A) - 1}.$$ For integer lattices, it is straightforward to compute $\det \mathcal{L}(A)$ (see for example this). But this is (roughly) what we are trying to lower bound in the ideal case, i.e. we reduced lower bounding $N(a)$ to lower bounding $\lambda_1(a\mathcal{O}_K)$ to lower bounding $\det a\mathcal{O}_K \approx N(a)\dots$

$\endgroup$
1
  • $\begingroup$ Thank you for your kind answer. I will find the references! $\endgroup$
    – Ring-LWE
    Oct 22, 2022 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.