# NTRUEncrypt fails on quaternion algebra

This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is described here.

I am trying to implement NTRUEncrypt system but working on a Quaternion algebra. I think the code is correct since it works fine for a very simple blinding value $$r$$. The problem is - it works only for selected very simple cases. Please see below Sage code with the correct scheme:

#### 1. Quaternion class implementation

Simple implementation for quaternions over polynomial rings.
Basic functions necessary for operations of the cryptosystem.
Most importantly: $$Q_1 \times Q_2$$ multiplication is implemented recursively (i.e. quaternion is composed of two complex numbers, etc).

def QuotientRingPolynomialInverse(p, ring):
return ring(p) ^ -1

class Quaternion():
def __init__(self, arglist):
self.coordinates = tuple(arglist)

def QuaternionCojnugate(Q):
templist = list(Q.coordinates)
templist = [
templist[i] if i==0 else -templist[i] for i in range(len(templist))
]
return Quaternion(templist)

def QuaternionNormSquared(Q):
return sum([c*c for c in Q.coordinates])

def Quaternion_mul_const(Q, a):
return Quaternion([c*a for c in Q.coordinates])

dim = len(Q1.coordinates)
return Quaternion([
Q1.coordinates[i] + Q2.coordinates[i] for i in range(dim)
])

def Quaternion_sub_Quaternion(Q1, Q2):
dim = len(Q1.coordinates)
return Quaternion([
Q1.coordinates[i] - Q2.coordinates[i] for i in range(dim)
])

def Quaternion_mul_Quaternion(Q1, Q2):
dim = len(Q1.coordinates)
# recursion base
if dim == 1:
return Quaternion([Q1.coordinates[0] * Q2.coordinates[0]])
# recursion step
else:
# helper objects
halfd = int(dim / 2)
Q1a = Quaternion(Q1.coordinates[:halfd])
Q1b = Quaternion(Q1.coordinates[halfd:])
Q2a = Quaternion(Q2.coordinates[:halfd])
Q2b = Quaternion(Q2.coordinates[halfd:])
# multiply recursively
Q1a2a = Quaternion_mul_Quaternion(
Q1a,
Q2a
)
Q2b1b = Quaternion_mul_Quaternion(
QuaternionCojnugate(Q2b),
Q1b
)
Q2b1a = Quaternion_mul_Quaternion(
Q2b,
Q1a
)
Q1b2a = Quaternion_mul_Quaternion(
Q1b,
QuaternionCojnugate(Q2a)
)
# construct the final object
Qa = Quaternion_sub_Quaternion(Q1a2a, Q2b1b)
return Quaternion(Qa.coordinates + Qb.coordinates)


#### 2. Parameters of the cryptosystem

Set $$(N,p,q)$$ parameters and construct polynomial (quotient) rings.

N = 11
p = 3
q = 127

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)


#### 3. Public key generation

Define quaternions $$f = (f_1, f_2, f_3, f_4)$$ and $$g = (g_1, g_2, g_3, g_4)$$. Cast $$f$$ to quotient rings and calculate its inverses. Generate public key $$h = pf_q^{-1} \times g$$

f_1 = RR([1, 0, 0, 1, -1, 1, 0, 0, 0, 0, -1])
f_2 = RR([0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0])
f_3 = RR([-1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0])
f_4 = RR([0, 1, 0, 0, 0, 0, 0, -1, -1, -1, -1])
Q_f = Quaternion([f_1, f_2, f_3, f_4])
Q_fPP = Quaternion([PP(_) for _ in Q_f.coordinates])
Q_fQQ = Quaternion([QQ(_) for _ in Q_f.coordinates])

g_1 = RR([0, -1, 0, 0, 0, 0, 1, 0, 0, 1, 0])
g_2 = RR([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1])
g_3 = RR([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
g_4 = RR([-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1])
Q_g = Quaternion([g_1, g_2, g_3, g_4])

Q_f_ = QuaternionCojnugate(Q_f)
f_norm = QuaternionNormSquared(Q_f)
f_norm_inv_p = PP(f_norm) ^ -1
Q_fp = Quaternion([
PP(_) * f_norm_inv_p for _ in Q_f_.coordinates
])
f_norm_inv_q = QQ(f_norm) ^ -1
Q_fq = Quaternion([
QQ(_) * f_norm_inv_q for _ in Q_f_.coordinates
])

Q_pfq = Quaternion_mul_const(Q_fq, p)
Q_pfqg = Quaternion_mul_Quaternion(Q_pfq, Q_g)
Q_h = Quaternion([QQ(_) for _ in Q_pfqg.coordinates])


#### 4. Encryption

Define quaternions $$m$$ and $$r$$ (blinding value). Encrypt the message $$e = r \times h + m$$.

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

r = (
QQ([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
)
Q_r = Quaternion(r)

Q_rh = Quaternion_mul_Quaternion(Q_r, Q_h)
Q_fhRR = Quaternion([RR(_) for _ in Q_rh.coordinates])

Q_e = Quaternion([QQ(_) for _ in Q_rhm.coordinates])


#### 5. Decryption

$$a = f \times e$$ (remember to center lift the coefficients)
$$b = PP[a]$$
$$c = f_p^{-1} \times b$$

Q_a = Quaternion_mul_Quaternion(Q_fQQ, Q_e)

Q_a = Quaternion([
ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[0].lift()]),
ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[1].lift()]),
ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[2].lift()]),
ZZ['x']([coeff.lift_centered() for coeff in Q_a.coordinates[3].lift()]),
])

Q_b = Quaternion([PP(_) for _ in Q_a.coordinates])

Q_c = Quaternion_mul_Quaternion(Q_fp, Q_b)

assert Q_m.coordinates[0] == Q_c.coordinates[0]
assert Q_m.coordinates[1] == Q_c.coordinates[1]
assert Q_m.coordinates[2] == Q_c.coordinates[2]
assert Q_m.coordinates[3] == Q_c.coordinates[3]


In the example above everything checks out, therefore I believe my error is conceptual, not in the code... With the following $$r$$ below the cryptosystem fails:

r = (
QQ([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
QQ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]),
)


What am I doing wrong?

• I suspect you are more likely to get an answer if you present the computations as pseudocode or mathematical formulas. (By the way, SageMath has a QuaternionAlgebra class that you've been reinventing partially!) Dec 30, 2022 at 3:42
• @yyyyyyy : thanks, I have added a few formulas for clarification. I believe it is important to keep the exact Sage code inside for anyone who would like to check things out by themselves.
– max
Dec 30, 2022 at 14:06
• Related question.
– fgrieu
Jan 1 at 20:21

It's a little hard to unpick, but I suspect that the issue is in failing to account for the non-commutativity of quaternions. The r in the example code is a purely real element and so commutes, but the r mentioned at the end has a $$k$$ component and so does not necessarily commute with other quaternions.
Ignoring the modulo $$p$$ stuff for the time being, the goal of the NTRU systems is to try and have the receiver recover characteristic zero polynomial $$pg(x)r(x)+f(x)m(x).$$ However, receiver does all of their recovery in characteristic $$q$$ and so recovery in previous circumstances failed if any coefficients fall outside the interval $$(-q/2,q/2)$$. With quaternions there is the additional gotcha of making sure that we do the correct right and left multiplies when recovering the polynomial.
Here receiver has formed the characteristic $$q$$ polynomial $$h$$ according to $$h(x)\equiv pf^{-1}(x)g(x)\pmod{\langle q,x^n-1\rangle}.$$ Sender then forms the characteristic $$q$$ polynomial $$e(x)\equiv r(x)h(x)+m(x)=pr(x)f^{-1}(x)g(x)+m(x)\pmod{\langle q,x^n-1\rangle}.$$ Receiver then computes the characteristic $$q$$ polynomial $$f(x)e(x)\equiv pf(x)r(x)f^{-1}(x)g(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}.$$ If we were in a commutative setting, this would be fine as things would resolve to $$pr(x)g(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}$$ as required. However quaternions do not commute and so we cannot perform this simplification.
If however we change the computation of e(x) so that we multiply with $$r(x)$$ on the right we have $$e(x)\equiv h(x)r(x)+m(x)=pf^{-1}(x)g(x)r(x)+m(x)\pmod{\langle q,x^n-1\rangle}$$ and $$f(x)e(x)\equiv pf(x)f^{-1}(x)g(x)r(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}$$ which would resolve to $$pg(x)r(x)+f(x)m(x)\pmod{\langle q,x^n-1\rangle}$$ and decryption could proceed correctly. I think that this just entails changing Q_rh = Quaternion_mul_Quaternion(Q_r, Q_h) to Q_rh = Quaternion_mul_Quaternion(Q_h, Q_r), but have not experimented.