2
$\begingroup$

Let $K$ be a number field of degree $n$ and $\Lambda^q_h=\{(f,g)\in\mathcal{O}_K\text{ : }fh-g = 0\bmod q\mathcal{O}_K\}$, where $h$ is an NTRU public key. Then $\{(1,h),(0,q)\}$ generates a lattice. I've found it stated in the literature that $Vol(\Lambda^q_h) = Vol(\mathcal{O}_K)^2q^n$ (e.g. here), but how does the proof of this statement run? Or where can I find a proof?

$\endgroup$
2
$\begingroup$

This is a standard computation in number theory. The idea behind it is that the matrix you have written down is a basis of the lattice as an $\mathcal{O}_K$-module, but to find the volume you first find a $\mathbb{Z}$-basis for the lattice, and then do "standard" computations with this. If $B$ is a $\mathbb{Z}$-basis of $\mathcal{O}_K$, then one has that:

$$B' = \begin{pmatrix}B & hB\\ 0 & qB\end{pmatrix} = \begin{pmatrix}1 & h\\ 0 & q\end{pmatrix}\otimes B$$

is a $\mathbb{Z}$-basis for your lattice. You can then compute the volume of this in the "standard" way, e.g. taking determinants, to get that:

$$\det B' = q^{\deg \mathcal{O}_K}(\det B)^2$$

which is precisely the expression you have written.

You can probably find this in many (if not all) textbooks on algebraic number theory. For example, I believe this is a corollary of lemma 2.23 of Milne's notes, but there are a number of abstractions one would have to unwind to verify this.

$\endgroup$

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.