What kind of operations are involved in NTRU?

Question

I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm?

When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where are the matrix-vector products?

Answer 1

Almost all lattice-based schemes that have somewhat practical performance use lattices from a subset of all lattices. Those lattices have additional structure and can be described using polynomials. The big advantage of doing this is that on the one hand the size of a description of the lattice is much smaller than for arbitrary lattices and on the other hand that one can use the fast Fourier transform (FFT) to do multiplication. If you want to learn more about this google for Ideal lattices or "the Ring setting" / Ring-LWE.

A different point one should note is that these advances in terms of performance are caused by additional structure that these lattices provide. Currently, we do not know any attacks that can exploit this additional structure to actually break the schemes (at least for the classes of lattices proposed). However, this is a topic of ongoing research and it is already known that for some spacial cases (if one selects these subsets in a bad way) schemes get insecure (see e.g. https://eprint.iacr.org/2015/176.pdf).

Answer 2

The way some of the Lattice-based Crypto works is by creating a private basis, with short orthogonal vectors that allows for easy computation. The public basis consists of an HNF, coined "Bad-basis", with non-orthogonal vectors that makes breaking the system difficult:

NTRU-encrypt(one version of it) works as follows:

Private-key: Given parameter $q$ two short vectors $(f,g)$ are chosen to create the private key with a cyclic Transformation $T$. Together they create the private q-ary lattice with basis $(T\cdot f,T\cdot g)$. The lattice is a convolutional modular lattices which are q-ary lattices closed under $T: <x,y> \mapsto <Tx,Ty>$

Public-key: $T$ and $f,g$ must satisfy $T\cdot f$ is congruent to $I$ mod p where p is another system parameter(described in the link I posted at the bottom; $f,g$ must satisfy some requirements) and $T\cdot g$ is congruent to $O$ zero matrix. The public key is fully described by $h=[T\cdot f]^{-1} g$ (mod q) and the public matrix $H$ is $[(I,T\cdot f)^t;(O,q.I)^t]$ where $;$ denotes column separation.The plaintext is $(-r,m)$ where $r$ is a random vector:

Encryption: $[(-r,m)^t]$ mod H $=$ (reduces to) $(m+[T\cdot h]r)$ (mod q). The top part of the matrix result is just $O$, again explained in the link.

Decryption: is $[T\cdot f]c$ mod q =$[T\cdot f]m+[T\cdot g]r$ mod p $= I.m+O.r=m$

All of this is from a great book on Post-quantum crypto, under the NTRU encrypt section. The SVP is the trap-door because finding short vectors reveals the private short basis. The FFT is also used in some Lattice-based compresion functions that use the FFT to speed up matrix multiplication (one of them is the link below does it in a very clever way)

As mephisto mentioned Learning-with Errors is another Lattice-based system with the benefit of providing an actual security proof, which I believe NTRU encrypt doesn't have. In addition, certain structured lattices (Ideal-lattices), as mephisto mentioned, are used to also speed up computation and memory. As you can see the public basis is really only determined by $h$. LWE is based on distinguishing uniform chosen lattice vectors with a lattice vector chosen by a matrix multiplication and perturbation. There are improved NTRUencrypt version which I believe the link explains. Since the lattices are based on polynomial-ideals, polynomial multiplication goes hand-in-hand with the matrix-vector products. Out of the post-quantum proposals it seems to create simple cryptosystems, but not necessarily the most secure.