# NTRUEncrypt fails on complex algebra

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the system works just as expected.

I have noticed an interesting publication regarding expanding NTRU to higher order algebras. This one is about quaternions but in the following example I will try complex numbers first, baby steps.

So, I have implemented the code to define cryptosystem's parameters, encrypt and decrypt, but in the end I cannot recover the initial polynomial. I do not know if this is just a bug or is there a conceptual error in my steps; need some help loooking through this.

Define parameters and respective polynomial rings:

N = 11
p = 3
q = 37

R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q.<x> = PolynomialRing(Zmod(q))
QQ = Q.quotient(x^N - 1)


Select polynomials $$f$$ and $$g$$

f_1 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
f_2 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])

g_1 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])
g_2 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

f = (f_1, f_2)
g = (g_1, g_2)


Calculate a multiplicative inverse of $$f$$ over respective rings $$PP$$ and $$QQ$$.
Remember that: $$f^{-1}_{XX} = [\frac{1}{||f||^2}]_{XX}\times \bar{f}$$
Also: $$||f||^2 = f_0^2 + f_1^2$$ and $$\bar{f} = (f_0, -f_1)$$

f_ = (f[0], -f[1])
f_norm = f[0]^2 + f[1]^2

f_norm_inv_p = PP(f_norm) ^ -1
fp = (
PP(f_[0] * f_norm_inv_p),
PP(f_[1] * f_norm_inv_p),
)

f_norm_inv_q = QQ(f_norm) ^ -1
fq = (
QQ(f_[0] * f_norm_inv_q),
QQ(f_[1] * f_norm_inv_q),
)


Check the inverses under complex multiplication $$a \times b = (ac-bd, ad+bc)$$

assert PP(f[0] * fp[0]) - PP(fp[1] * f[1]) == 1
assert PP(f[0] * fp[1]) + PP(f[1] * fp[0]) == 0
assert QQ(f[0] * fq[0]) - QQ(fq[1] * f[1]) == 1
assert QQ(f[0] * fq[1]) + QQ(f[1] * fq[0]) == 0


Generate public key $$h = pf_q \times g$$

pfq = (p * fq[0], p * fq[1])
h = (
QQ(pfq[0] * g[0]) - QQ(g[1] * pfq[1]),
QQ(pfq[0] * g[1]) + QQ(pfq[1] * g[0]),
)


Encryption $$e = r \times h + m$$

m = (
PP([0, 0, 0, 0, 0, 1, 1, 0, -1, 1, 1]),
PP([0, 0, 0, 0, 0, 1, 1, 0, -1, 1, 1]),
)

r = (
RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]),
RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]),
)

rh = (
r[0] * h[0] - h[1] * r[1],
r[0] * h[1] + r[1] * h[0],
)

e = (
QQ(rh[0] + m[0]),
QQ(rh[1] + m[1]),
)


Decryption:
$$a = f \times e$$ (remember to center lift the coefficients)
$$b = PP[a]$$
$$c = f_p \times b$$

a = (
QQ(f[0]) * e[0] - e[1] * QQ(f[1]),
QQ(f[0]) * e[1] + QQ(f[1]) * e[0],
)

a = (
ZZ['x']([coeff.lift_centered() for coeff in a[0].lift()]),
ZZ['x']([coeff.lift_centered() for coeff in a[1].lift()]),
)

b = (PP(a[0]), PP(a[1]))

c = (
fp[0] * b[0] - b[1] * fp[1],
fp[0] * b[1] + fp[1] * b[0],
)


In the end $$c \neq m$$... I am a little troubled, why(?)

P.S. To quickly check Sage piece of code you may use this site: https://sagecell.sagemath.org/

Again, there's nothing wrong with the code: the rounding process is noisier in this case and has again caused a reduction to be lifted in correctly.

Essentially here we are using NTRU with the Gaussian integers as base ring $$\mathbb Z[i][x]$$ instead of the more usual $$\mathbb Z[x]$$. However, we're still in a nice Euclidean setting and so this should not concern us. There's a slight gotcha in that 37 does not generate a prime ideal over the Gaussians because e.g. $$37=(6+i)(6-i)$$. This may cause more choices of $$g(x)$$ to be unsuitable for not having an inverse, but is unlikely to impinge in practice. Also note that you don't have to set $$f_1=f_2$$ nor otherwise for other polynomials if you do not wish. By choosing this limitation, you restrict to the residue choices $$0,1+i,-1-i\pmod p$$ when you could be using 9 residue choices for $$p=3$$.

Anyway, recall that the goal of the decryption process is to recover the (Gaussian) integer polynomial $$a(x)=r(x)g(x)p+f(x)m(x)$$ which we can compute as

sage: inta = ( p*(r[0]*g[0]-r[1]*g[1]) + f[0]*m[0]-f[1]*m[1] , p*(r[0]*g[1]+r[1]*g[0])+f[0]*m[1]+f[1]*m[0])
sage: inta
(0, -10*xbar^10 - 8*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 - 2*xbar^3 - 20*xbar^2 - 6*xbar)


notice that as integers the coefficients of the real and imaginary parts of $$a(x)$$ are the sums of four pairs of products rather than the two pairs of products in non-Gaussian NTRU. This leads to larger coefficient growth and a greater chance of error. If we now compare the $$a(x)$$ that we wish to recover to its reduction mod $$q$$ that is obtained during the decryption process, we see

sage: aq = ( QQ(f[0]) * e[0] - e[1] * QQ(f[1]), QQ(f[0]) * e[1] + QQ(f[1]) * e[0])
sage: aq
(0, 27*xbar^10 + 29*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 + 35*xbar^3 + 17*xbar^2 + 31*xbar)


and all of the coefficients agree mod $$q$$ as we would hope. However, when we try to lift, we see that there are coefficients of $$a(X)$$ that lie outside the interval $$(-q/2,q/2)$$: specifically the imaginary parts of the coefficients of $$x^7$$ and $$x^2$$. Thus, when we lift we recover an incorrect integer polynomial:

sage: a = ( ZZ['x']([coeff.lift_centered() for coeff in aq[0].lift()]), ZZ['x']([coeff.lift_centered() for coeff in aq[1].lift()]))
sage: a
(0, -10*x^10 - 8*x^9 + 16*x^8 - 17*x^7 + 10*x^6 + 4*x^5 + 8*x^4 - 2*x^3 + 17*x^2 - 6*x)


This leads to the failure to recover the plaintext. Had you selected a prime $$q$$ with $$20 such as $$q=43$$ then the process would have worked fine.