# What kind of operations are involved in NTRU?

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?

• @Dingo13 NTRUencrypt work in the setting of a convolutional modular lattice. The private key is vectors $f,g$ such that there exists a cyclic transformation $T$ such that $T*<f,g>=<identity,0>$. The public key is fully described by $h=[T*f]^-1 *g$. The message and a random vector $-r$ become the plaintext. The public matrix is $h$ with the identity and zero vectors on top. Due to this structure of the matrix ($HNF$ structure ) the resulting matrix multiplication(it's actually $[-r;m] mod PUBK$) results in an expression just with vectors and $T$ for the ciphertext. $c=(m+[T*h]r)mod q. – dylan7 Aug 14 '15 at 14:39 • @Dingo13 Learning with errors(which mephisto mentioned) is a proposed better PKC because it actually has a security proof behind it. This is based on the problem of distiguishing a vector created by a random transformation and perturbation vs being chosen unifirm randomly. – dylan7 Aug 14 '15 at 14:43 • @dylan Thanks for the details. if$*$is a multiplication, how we obtain a matrix for$h$? The multiplication of two polynoms does not give a polynom? – Dingo13 Aug 14 '15 at 14:55 • @Dingo13 I realized I left some out due to not making the comment too long. I explained it in an answer. – dylan7 Aug 14 '15 at 16:43 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*f,T*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*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*g$is congruent to$O$zero matrix. The public key is fully described by$h=[T*f]^{-1} g$(mod q) and the public matrix$H$is$[(I,T*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*h]r)$(mod q). The top part of the matrix result is just$O$, again explained in the link. Decryption: is$[T*f]c$mod q =$[T*f]m+[T*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.