Join Log in
Score:2
max avatar Crypto

NTRUEncrypt fails on quaternion algebra

dm flag
max

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?

113
1 + 3
yyyyyyy avatar
in flag
yyyyyyy
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!)
0
Reply
max avatar
dm flag
max
@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.
0
Reply
fgrieu avatar
ng flag
fgrieu
Related [question](https://crypto.stackexchange.com/q/103544/555).
0
Reply
Score:3
Daniel S avatar Crypto
ru flag
Daniel S

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.

+ 1
max avatar
dm flag
max
Daniel: I have one more follow-up to this, hopefully the last one as that is my ultimate goal: https://crypto.stackexchange.com/questions/103544/ntruencrypt-fails-on-sedonion-algebra
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.