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?


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).

  • $\begingroup$ Thanks for your answer. If I've well understood, matrix-vector products are due to the use of the FFT algorithm. Can this also be used in the NTRU system ? $\endgroup$ – Dingo13 Aug 14 '15 at 13:39
  • 1
    $\begingroup$ @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. $\endgroup$ – dylan7 Aug 14 '15 at 14:39
  • $\begingroup$ @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. $\endgroup$ – dylan7 Aug 14 '15 at 14:43
  • $\begingroup$ @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? $\endgroup$ – Dingo13 Aug 14 '15 at 14:55
  • $\begingroup$ @Dingo13 I realized I left some out due to not making the comment too long. I explained it in an answer. $\endgroup$ – 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.

Hope that clears things up!

  • $\begingroup$ Thanks very much for this detailed answer. I've read it and I certainly need to re-read it. Are lattice based crytographic algorithms more difficult to understand than number theory based ones ? $\endgroup$ – Dingo13 Aug 14 '15 at 17:29
  • $\begingroup$ @Dingo13 I would say,yes, since Number theory crypto is mostly just finite-field theory and mod math it can be taught right after an intro-abstract algebra class. I found the reason behind operations in number-theory crypto to explain itself very well. i.e. RSA is short-and-sweet, obvious why you need factoring to break it. The security behind these systems is not obvious from just understanding the cryptosystem operations. Code-based and especially the multivariate crypto are harder. Although the general gist of security is that bad/good-lattice situation which the link explains really well. $\endgroup$ – dylan7 Aug 14 '15 at 17:47
  • $\begingroup$ It's easy for someone new to crypto to jump right into number-theory crypto(mostly modular math at the beginning); lattices not so much. And again, it has no security proof(NTRU), so that must make the security somewhat difficult to grasp :). $\endgroup$ – dylan7 Aug 14 '15 at 17:47

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.