Timeline for What kind of operations are involved in NTRU?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 15, 2015 at 14:07 | comment | added | mephisto | So, actually you can only speed up matrix-vector products using the FFT if your lattice is structured. It does not work for random lattices. I think it should be possible to use it for NTRU as NTRU (implicitly) uses a cyclic lattice described by polynomials (if I remember correctly). Btw., Ring-LWE or LWE in general does not refer to the encryption scheme that dylan7 mentions but rather to the underlying hard problem (think of it like something similar to the discrete logarithm problem). | |
| Aug 14, 2015 at 16:43 | comment | added | dylan7 | @Dingo13 I realized I left some out due to not making the comment too long. I explained it in an answer. | |
| Aug 14, 2015 at 14:55 | comment | added | Dingo13 | @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? | |
| Aug 14, 2015 at 14:43 | comment | added | dylan7 | @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. | |
| Aug 14, 2015 at 14:39 | comment | added | dylan7 | @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. | |
| Aug 14, 2015 at 13:39 | comment | added | Dingo13 | 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 ? | |
| Aug 14, 2015 at 13:21 | history | answered | mephisto | CC BY-SA 3.0 |