How to represent an ideal lattice using a matrix?

Question

In Craig Gentry's thesis on implementing a homomorphic encryption scheme, he defines an ideal lattice as an ideal in the quotient ring $\mathbb Z[x]/\langle f\rangle$, with $f$ a polynomial of degree $n$. I understand that such a quotient ring can be represented as a lattice of ideals with the bottom element $\langle f \rangle$ and the top element $\mathbb Z[x]$, with larger ideals containing $\langle f \rangle$ in between.

Gentry then says that each ideal in this ring can be "represented by a lattice generated by the columns of a lattice basis $\mathbf B_I$, an $n \times n$ matrix".

The principal ideal $\langle f \rangle$ and its larger ideals above it in the lattice are generated by polynomials of degree $\leq n$, but how does one determine the rest of the lattice's structure using such a matrix?

On second thought, I think it refers to this but I don't know or understand if the ideals of $\Bbb Z[x]$ are amenable to this analysis. — rschwieb, Dec 03 '15 at 21:27
This article appears to contain some more leads on how to do it in precisely this case. — rschwieb, Dec 03 '15 at 21:32

score 0 · Accepted Answer · answered Jan 14 '16 at 23:16

On page 66 of Gentry's thesis, he explains how to construct this ideal lattice. Paraphrased:

Let $R=\mathbb{Z}[x]/\langle f\rangle$ (the quotient ring described in the question), and $\mathbf{v}\in R$. $\mathbf{v}$ is represented by a coefficient vector $\in \mathbb{Z}^n$.

Then the ideal $\langle \mathbf{v}\rangle$ corresponds with a lattice $L=\{\mathbf{v}\times x^i \operatorname{mod} f(x):i\in [0,n-1]\}$.

It appears that in the context of Gentry's thesis, an "ideal lattice" is not a lattice consisting of ideals but a lattice that happens to have the necessary properties to also be an ideal. To represent this lattice one only needs the coefficient vector(s) of the polynomials that generate the corresponding ideal.

How to represent an ideal lattice using a matrix?

1 Answers1