NTRUEncrypt fails on quaternion algebra

Question

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])

def Quaternion_add_Quaternion(Q1, Q2):
    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)
        Qb = Quaternion_add_Quaternion(Q2b1a, Q1b2a)
        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_rhm = Quaternion_add_Quaternion(Q_fhRR, Q_m)
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?

Answer 1

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.