2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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!) $\endgroup$
    – yyyyyyy
    Commented Dec 30, 2022 at 3:42
  • $\begingroup$ @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. $\endgroup$
    – max
    Commented Dec 30, 2022 at 14:06
  • $\begingroup$ Related question. $\endgroup$
    – fgrieu
    Commented Jan 1, 2023 at 20:21

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.