LatticeHacks

### Polynomials

``````    Zx.<x> = ZZ[]
``````

This creates a `Zx` class. A `Zx` object is a polynomial in `x` with integer coefficients. For example:

``````    sage: f = Zx([3,1,4])
sage: f
4*x^2 + x + 3
``````

This polynomial `f` is a sum of three terms: `4*x^2`, `x`, and `3`. Each term is an integer coefficient (4, 1, and 3 respectively) times a power of `x` (`x^2`, `x`, and `1` respectively).

Easier version of the same example to copy and paste into Sage:

``````    f = Zx([3,1,4])
f
# output: 4*x^2 + x + 3
``````

### Polynomial multiplication

The `Zx` class has a built-in multiplication method that multiplies each term and adds the results. For example, multiplying `f` by `x`, or any power of `x`, shifts the list of coefficients of `f`:

``````    f
# output: 4*x^2 + x + 3
f*x
# output: 4*x^3 + x^2 + 3*x
``````

Another example:

``````    g = Zx([2,7,1])
g
# output: x^2 + 7*x + 2
f*g
# output: 4*x^4 + 29*x^3 + 18*x^2 + 23*x + 6
``````

### Cyclic convolution

``````    def convolution(f,g):
return (f * g) % (x^n-1)
``````

This is the multiplication operation used in NTRU. It is the same as polynomial multiplication but reduces the output "modulo `x^n-1`": this means replacing `x^n` with 1, replacing `x^(n+1)` with `x`, replacing `x^(n+2)` with `x^2`, etc.

The inputs are two `n`-coefficient polynomials `f` and `g`, meaning polynomials with coefficients of `1`, `x`, and so on through `x^(n-1)`. The output is also an `n`-coefficient polynomial, since `x^n` etc. have been eliminated. It's possible for some or all of the `n` output coefficients to be `0` (and, similarly, input coefficients can be `0`). Saying `n`-coefficient doesn't mean that all of `1`, `x`, ..., `x^(n-1)` appear; it means that `x^n`, `x^(n+1)`, etc. don't appear.

Example:

``````    n = 3
f*g
# output: 4*x^4 + 29*x^3 + 18*x^2 + 23*x + 6
convolution(f,g)
# output: 18*x^2 + 27*x + 35
``````

As another example, convolution of `f` by powers of `x` rotates the list of `n` coefficients of `f`:

``````    n = 3
f
# output: 4*x^2 + x + 3
convolution(f,x)
# output: x^2 + 3*x + 4
convolution(f,x^2)
# output: 3*x^2 + 4*x + 1
``````

Beware that `n` is a global variable. Python exercise: Write a function `ring(n)` whose output is a class `R` that is similar to `Zx` but automatically reduces the results of addition, subtraction, and multiplication modulo `x^n-1`. Sage already knows how to do this (`R = Zx.quotient(x^n-1)`) but the exercise is to make your own class starting from `Zx`, defining `__mul__`, etc.

Math exercise: Can you figure out two input polynomials where the convolution is `0` (all output coefficients `0`)? This is automatic if one input is `0`, or if the other input is `0`, or both, but can you figure out any other examples?

The name "cyclic convolution" (or "circular convolution") comes from signal processing. Polynomial multiplication is called "acyclic convolution".

### Modular reduction

``````    def balancedmod(f,q):
g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
return Zx(g)
``````

There are two inputs to `balancedmod`: an `n`-coefficient integer polynomial `f`; and a positive integer `q`. The output is the same polynomial except that each coefficient is reduced modulo `q`. Mathematicians normally define reduction to produce outputs between `0` and `q-1`, but `balancedmod` instead produces outputs between `-q/2` and `q/2`: more precisely, between `-q/2` and `q/2-1` if `q` is even, or between `-(q-1)/2` and `(q-1)/2` if `q` is odd.

For example:

``````    u = Zx([3,1,4,1,5,9])
u
# output: 9*x^5 + 5*x^4 + x^3 + 4*x^2 + x + 3
n = 7
balancedmod(u,10)
# output: -x^5 - 5*x^4 + x^3 + 4*x^2 + x + 3
balancedmod(u,3)
# output: -x^4 + x^3 + x^2 + x
``````

Internally, `balancedmod` uses Sage's `% q` operation for integers, which always produces outputs between `0` and `q-1`. `balancedmod` adjusts the input and output by `q//2`, which means `q/2` rounded down.

Beware that negative inputs to `% q` typically produce negative results in lower-level languages, so the output of `% q` leaks the sign of the input (unless the input happens to be divisible by `q`, in which case the output is `0`). This leak can be a serious security problem. Sage also supports a `% q` operation for polynomials, and a similar leak is sometimes visible in the output:

``````    u = 314-159*x
u % 200
# output: -159*x + 114
(u - 400) % 200
# output: -159*x - 86
(u - 600) % 200
# output: -159*x + 114
balancedmod(u,200)
# output: 41*x - 86
``````

### Random polynomials with d nonzero coefficients

``````    def randomdpoly():
assert d <= n
result = n*
for j in range(d):
while True:
r = randrange(n)
if not result[r]: break
result[r] = 1-2*randrange(2)
return Zx(result)
``````

`randomdpoly` returns an `n`-coefficient polynomial where exactly `d` coefficients are nonzero (`d` are nonzero, the other `n-d` are all zero). Each nonzero coefficient is either `1` or `-1`. Beware that `d` and `n` are both global variables.

For example:

``````    n = 7
d = 5
f = randomdpoly()
f
# output: x^6 + x^5 - x^3 + x^2 - 1
f = randomdpoly()
f
# output: -x^4 + x^3 + x^2 - x + 1
``````

### Division modulo primes

``````    def invertmodprime(f,p):
T = Zx.change_ring(Integers(p)).quotient(x^n-1)
return Zx(lift(1 / T(f)))
``````

`invertmodprime` computes a reciprocal of a polynomial modulo `x^n-1` modulo `p`. There are two inputs: an `n`-coefficient polynomial `f`; and a prime number `p` (for example, `3`). The output is an `n`-coefficient polynomial `g` so that `convolution(f,g)` is `1+p*u` for some polynomial `u`. `invertmodprime` raises an exception if no such `g` exists.

For example:

``````    n = 7
f
# output: -x^4 + x^3 + x^2 - x + 1
f3 = invertmodprime(f,3)
f3
# output: x^6 + 2*x^4 + x
convolution(f,f3)
# output: 3*x^6 - 3*x^5 + 3*x^4 + 1
``````

This convolution is `1+3*u` where `u` is the polynomial `x^6 - x^5 + x^4`.

The concept of `invertmodprime` also makes sense for non-primes (see `invertmodpowerof2` below), but `invertmodprime` internally uses some Sage subroutines that aren't smart enough to handle non-primes.

### Division modulo powers of 2

``````    def invertmodpowerof2(f,q):
assert q.is_power_of(2)
g = invertmodprime(f,2)
while True:
r = balancedmod(convolution(g,f),q)
if r == 1: return g
g = balancedmod(convolution(g,2 - r),q)
``````

Just like `invertmodprime` above, except that the second input `q` is 2 or 4 or 8 or 16 or ... Example:

``````    n = 7
q = 256
f
# output: -x^4 + x^3 + x^2 - x + 1
fq = invertmodpowerof2(f,q)
convolution(f,fq)
# output: -256*x^6 + 256*x^4 - 256*x^2 + 257
``````

This convolution is `1+256*u` where `u` is the polynomial `-x^6 + x^4 - x^2 + 1`.

Math exercise: Watch what's happening internally in `invertmodpowerof2`, and explain why it works. Hint: How does `r` relate to the `r` in the previous loop?

### NTRU key generation

``````    def keypair():
while True:
try:
f = randomdpoly()
f3 = invertmodprime(f,3)
fq = invertmodpowerof2(f,q)
break
except:
pass
g = randomdpoly()
publickey = balancedmod(3 * convolution(fq,g),q)
secretkey = f,f3
return publickey,secretkey
``````

This returns an NTRU public key `h` and a corresponding secret key `f,f3`. The public key looks like a random `n`-coefficient polynomial modulo `q`. For example, if `n = 7` (much too small for security!) and `q = 256`, then the public key looks like 7 random bytes:

``````    n = 7
d = 5
q = 256
publickey,secretkey = keypair()
publickey
# output: 54*x^6 - 40*x^5 + 90*x^4 + 101*x^3 - 108*x^2 + 80*x + 76
``````

The `f` part of the secret key is a polynomial with small coefficients. Convolution of `f` with the public key modulo `q` produces another polynomial with small coefficients, namely 3 times the `g` that appeared in key generation:

``````    f,f3 = secretkey
f
# output: -x^6 + x^5 - x^4 + x^2 + 1
convolution(f,publickey)
# output: 256*x^6 + 3*x^5 - 3*x^3 - 3*x^2 + 253*x - 253
balancedmod(_,q)
# output: 3*x^5 - 3*x^3 - 3*x^2 - 3*x + 3
``````

### Messages for encryption

``````    def randommessage():
result = list(randrange(3) - 1 for j in range(n))
return Zx(result)
``````

`randommessage` returns an `n`-coefficient polynomial where each coefficient is either `1` or `0` or `-1`. For example:

``````    n = 7
randommessage()
# output: -x^6 - x^5 + x^4
randommessage()
# output: x^6 + x^5 - x^4 - 1
randommessage()
# output: -x^4 - x^3 - x + 1
randommessage()
# output: -x^6 + x^4 - x^2 + 1
``````

### Encryption

``````    def encrypt(message,publickey):
r = randomdpoly()
return balancedmod(convolution(publickey,r) + message,q)
``````

`encrypt` returns an NTRU ciphertext given a message and a public key `h`. The ciphertext is `h*r+m` modulo `x^n-1` modulo `q`, where `m` is the message and `r` is random.

Example:

``````    n = 7
d = 5
q = 256
h,secretkey = keypair()
h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
m = randommessage()
m
# output: -x^6 - x^4 + x^2 + 1
c = encrypt(m,h)
c
# output: -66*x^6 + 37*x^5 + 115*x^4 - 15*x^3 - 6*x^2 - 89*x + 27
``````

### Decryption

``````    def decrypt(ciphertext,secretkey):
f,f3 = secretkey
a = balancedmod(convolution(ciphertext,f),q)
return balancedmod(convolution(a,f3),3)
``````

`decrypt` returns a message given an NTRU ciphertext and a secret key.

Example of testing decryption for 10 ciphertexts using 10 different keys with reasonable NTRU parameters:

``````    n = 743
d = 495
q = 2048
for tests in range(10):
publickey,secretkey = keypair()
m = randommessage()
c = encrypt(m,publickey)
print m == decrypt(c,secretkey)

# output: True
# output: True
# output: True
# output: True
# output: True
# output: True
# output: True
# output: True
# output: True
# output: True
``````

Here is an example of the internal calculations in encryption and decryption to illustrate why decryption works:

``````    n = 7
d = 5
q = 256
h,secretkey = keypair()
h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
m = randommessage()
m
# output: x^6 + x^5 - x^4 - x^3 + x - 1
r = randomdpoly()
r
# output: -x^6 + x^5 + x^4 + x^3 - x^2
f = secretkey
f
# output: -x^6 - x^5 - x^4 - x^3 - x
g3 = balancedmod(convolution(f,h),q)
g3
# output: -3*x^6 - 3*x^3 + 3*x^2 - 3*x - 3
c = balancedmod(convolution(h,r) + m,q)
c
# output: -93*x^6 - 105*x^5 - 110*x^4 - 95*x^3 - 106*x^2 - 111*x - 95
a = balancedmod(convolution(f,c),q)
a
# output: 3*x^5 - 13*x^4 - 3*x^3 + 2*x^2 - x + 3
convolution(g3,r) + convolution(f,m)
# output: 3*x^5 - 13*x^4 - 3*x^3 + 2*x^2 - x + 3
balancedmod(a,3)
# output: -x^4 - x^2 - x
balancedmod(convolution(f,m),3)
# output: -x^4 - x^2 - x
``````

The idea is that `c = h*r+m` modulo q, and `f*h = 3*g` modulo q, so `a = f*c = f*h*r+f*m = 3*g*r+f*m` modulo `q`. The polynomials `g,r,f,m` have small coefficients, so there is a limit on how big the coefficients of `3*g*r+f*m` can be. If this limit is small enough compared to `q`, then `a` is exactly `3*g*r+f*m`, and reducing `a` modulo `3` is the same as reducing `f*m` modulo `3`. Multiplying by `f3` produces `m` modulo `3`.

Beware that decryption can fail. One can standardize `n`, `d`, and `q` that avoid all decryption failures for valid ciphertexts, but an attacker can still deliberately choose invalid ciphertexts to see whether decryption works. It is important for security to take extra steps to protect against these chosen-ciphertext attacks.

### An attack example with very small NTRU parameters

The following example uses `n = 7`, `d = 5`, and `q = 256`.

The attacker starts from the public key `h`, which is `3*g/f`. It's simpler to work with `g/f`, which is computed here as `h3`:

``````    h
# output: -82*x^6 + 118*x^5 - 94*x^4 + 108*x^3 + 70*x^2 - 122*x + 5
Integers(q)(1/3)
# output: 171
h3 = (171*h)%q
``````

Think of the secret `g` as the secret `f` times `h3`. Remember that the secret `f` is obtained from `1`, `x`, `x^2`, `x^3`, `x^4`, `x^5`, `x^6`. by some additions and subtractions. The secret `g` is correspondingly obtained from the polynomials `h3`, `h3*x`, `h3*x^2`, `h3*x^3`, `h3*x^4`, `h3*x^5`, `h3*x^6` by some additions and subtractions. Here are these polynomials:

``````    h3
# output: 58*x^6 + 210*x^5 + 54*x^4 + 36*x^3 + 194*x^2 + 130*x + 87
convolution(h3,x)
# output: 210*x^6 + 54*x^5 + 36*x^4 + 194*x^3 + 130*x^2 + 87*x + 58
convolution(h3,x^2)
# output: 54*x^6 + 36*x^5 + 194*x^4 + 130*x^3 + 87*x^2 + 58*x + 210
convolution(h3,x^3)
# output: 36*x^6 + 194*x^5 + 130*x^4 + 87*x^3 + 58*x^2 + 210*x + 54
convolution(h3,x^4)
# output: 194*x^6 + 130*x^5 + 87*x^4 + 58*x^3 + 210*x^2 + 54*x + 36
convolution(h3,x^5)
# output: 130*x^6 + 87*x^5 + 58*x^4 + 210*x^3 + 54*x^2 + 36*x + 194
convolution(h3,x^6)
# output: 87*x^6 + 58*x^5 + 210*x^4 + 54*x^3 + 36*x^2 + 194*x + 130
``````

Actually, `g` is `f*h3` modulo `q`: `q` can be added to or subtracted from any coefficient. This means that `g` is obtained as a combination of the polynomials `q`, `q*x`, `q*x^2`, `q*x^3`, `q*x^4`, `q*x^5`, `q*x^6`, `h3`, `h3*x`, `h3*x^2`, `h3*x^3`, `h3*x^4`, `h3*x^5`, `h3*x^6`.

Finally, concatenating the coefficients of `g` and `f` produces a combination of the rows of the following matrix:

``````    M = matrix(2*n)
for i in range(n): M[i,i] = q
for i in range(n,2*n): M[i,i] = 1
for i in range(n):
for j in range(n):
M[i+n,j] = convolution(h3,x^i)[j]

M
# output: [256   0   0   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0 256   0   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0 256   0   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0 256   0   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0 256   0   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0   0 256   0   0   0   0   0   0   0   0]
# output: [  0   0   0   0   0   0 256   0   0   0   0   0   0   0]
# output: [ 87 130 194  36  54 210  58   1   0   0   0   0   0   0]
# output: [ 58  87 130 194  36  54 210   0   1   0   0   0   0   0]
# output: [210  58  87 130 194  36  54   0   0   1   0   0   0   0]
# output: [ 54 210  58  87 130 194  36   0   0   0   1   0   0   0]
# output: [ 36  54 210  58  87 130 194   0   0   0   0   1   0   0]
# output: [194  36  54 210  58  87 130   0   0   0   0   0   1   0]
# output: [130 194  36  54 210  58  87   0   0   0   0   0   0   1]
``````

The LLL algorithm quickly finds short combinations of these rows:

``````    M.LLL()
# output: [ -1  -1   1  -1   1   0   0  -1   1  -1  -1   1   0   0]
# output: [  0  -1  -1   1  -1   1   0   0  -1   1  -1  -1   1   0]
# output: [  1  -1   1  -1   0   0   1  -1   1   1  -1   0   0   1]
# output: [ -1   1  -1   0   0   1   1   1   1  -1   0   0   1  -1]
# output: [  1  -1   0   0   1   1  -1   1  -1   0   0   1  -1   1]
# output: [  1   1   1   1   1   1   1   1   1   1   1   1   1   1]
# output: [  0   0   1   1  -1   1  -1   0   0   1  -1   1   1  -1]
# output: [ 39 -28  19  12  11 -48  -4  47   6 -31 -20 -19  36 -18]
# output: [ -5 -34 -14  -3   9 -39 -43  47  54  22   1 -17  19   1]
# output: [  4 -39  28 -19 -12 -11  48  18 -47  -6  31  20  19 -36]
# output: [  9 -40 -43  -5 -32 -13  -1 -17  20   1  47  54  23   3]
# output: [ -1   9 -40 -43  -5 -32 -13   3 -17  20   1  47  54  23]
# output: [ 14   3  -9  40  43   4  32 -22  -3  17 -18  -1 -48 -54]
# output: [ 28 -19 -12 -11  48   4 -39  -6  31  20  19 -36  18 -47]
``````

The first row is the secret `g` followed by the secret `f`. Actually, it turns out to be the negative of `g` followed by the negative of `f`:

``````    M.LLL()[n:]
# output: (-1, 1, -1, -1, 1, 0, 0)
Zx(list(_))
# output: x^4 - x^3 - x^2 + x - 1
f
# output: -x^4 + x^3 + x^2 - x + 1
``````

But the attacker can simply use the decryption algorithm without worrying about this negation. Similarly, LLL could have produced (for example) `x*g` and `x*f`, but this would again have worked for decryption. NTRU needs much larger `n` for security.

### Automating the attack

``````    def attack(publickey):
recip3 = lift(1/Integers(q)(3))
publickeyover3 = balancedmod(recip3 * publickey,q)
M = matrix(2 * n)
for i in range(n):
M[i,i] = q
for i in range(n):
M[i+n,i+n] = 1
c = convolution(x^i,publickeyover3)
for j in range(n):
M[i+n,j] = c[j]
M = M.LLL()
for j in range(2 * n):
try:
f = Zx(list(M[j][n:]))
f3 = invertmodprime(f,3)
return (f,f3)
except:
pass
return (f,f)

n = 120
q = 2^32
d = 81

publickey,secretkey = keypair()
donald = attack(publickey)
print donald
try:
m = randommessage()
c = encrypt(m,publickey)
assert decrypt(c,donald) == m
print 'attack successfully decrypts'
except:
print 'attack was unsuccessful'
``````

Version: This is version 2017.12.28 of the "NTRU" web page.