### 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*[0]
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[0]
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()[0][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[0]
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.