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!

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.

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.

Hope that clears things up!

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!