# 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, -f)
f_norm = f^2 + f^2

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

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


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

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


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

pfq = (p * fq, p * fq)
h = (
QQ(pfq * g) - QQ(g * pfq),
QQ(pfq * g) + QQ(pfq * g),
)


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 * h - h * r,
r * h + r * h,
)

e = (
QQ(rh + m),
QQ(rh + m),
)


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

a = (
QQ(f) * e - e * QQ(f),
QQ(f) * e + QQ(f) * e,
)

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

b = (PP(a), PP(a))

c = (
fp * b - b * fp,
fp * b + fp * b,
)


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*g-r*g) + f*m-f*m , p*(r*g+r*g)+f*m+f*m)
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) * e - e * QQ(f), QQ(f) * e + QQ(f) * e)
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.lift()]), ZZ['x']([coeff.lift_centered() for coeff in aq.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.