NTRUEncrypt fails on sedonion algebra

Question

This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. Following these two papers: resource1 and resource2 I am trying to implement the method for sedonions over polynomial quotient rings in Sage.

Sedonion class is implemented in a similar manner as Quaternion in my previous question. One important difference is that multiplication $S_1 \times S_2$ is defined exactly as in resource1, page 1454. Despite strictly following the text of both publications, increasing $q$, modifying the decryption process, I cannot recover the original message $m$. I don't know if I have a bug in my code (unlikely) or am I overlooking some algebraic properties (non-alternativity?), again.

1. Parameters of the cryptosystem

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

N = 11
p = 3
q = 1000003

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)

2. Public key generation

Define sedonions $f$ and $g$.
Cast $f$ to quotient rings and calculate its inverses $\mod p$ and $\mod q$.
Generate public key $h = pf_q^{-1} \times g$.

f_1 = RR([0, 1, 0, 0, -1, 0, 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, 0, 0, 1, 0])
f_4 = RR([0, 0, 0, 0, 0, 0, 0, 1, 1, 1, -1])
f_5 = RR([1, 0, 0, -1, 1, 1, 1, 1, 1, 0, -1])
f_6 = RR([1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0])
f_7 = RR([-1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0])
f_8 = RR([0, 1, 0, 0, 0, 0, 1, 1, 1, -1, -1])
f_9 = RR([1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0])
f_10 = RR([0, 0, 0, 0, 1, 1, -1, 0, 0, -1, 0])
f_11 = RR([-1, 1, 0, 1, 0, 0, 0, 0, 1, -1, 0])
f_12 = RR([0, 1, 1, 1, 1, 0, 0, 1, 1, 1, -1])
f_13 = RR([1, 1, 1, 1, 1, 1, 1, 1, 1, 0, -1])
f_14 = RR([1, 0, 1, 0, 1, 0, -1, 0, 0, 1, 0])
f_15 = RR([-1, 1, 1, 0, 0, 0, -1, -1, 0, 1, 0])
f_16 = RR([0, 1, 1, 0, -1, 0, -1, 1, 0, -1, -1])
S_f = Sedonion([
    f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8,
    f_9, f_10, f_11, f_12, f_13, f_14, f_15, f_16
])
S_fPP = Sedonion([PP(_) for _ in S_f.coordinates])
S_fQQ = Sedonion([QQ(_) for _ in S_f.coordinates])

g_1 = RR([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0])
g_2 = RR([0, 0, 1, 0, 0, 1, 1, 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, 1, 0, 0, 0, 0, -1])
g_5 = RR([0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0])
g_6 = RR([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1])
g_7 = RR([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
g_8 = RR([-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
g_9 = RR([0, 0, -1, -1, 0, 0, 0, 1, 0, 1, 0])
g_10 = RR([0, 0, 1, 0, 0, -1, -1, 0, 0, 0, -1])
g_11 = RR([1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0])
g_12 = RR([-1, 0, 0, 1, 1, -1, 0, 0, 0, 0, -1])
g_13 = RR([0, 1, 1, -1, 0, 0, 0, 1, 0, 0, 0])
g_14 = RR([0, 0, 0, 0, 1, 0, 0, -1, 0, 0, -1])
g_15 = RR([0, 0, -1, 0, 1, 0, 1, 1, 0, 0, 1])
g_16 = RR([-1, 0, 0, 0, 0, 0, 0, 1, -1, -1, 0])
S_g = Sedonion([
    g_1, g_2, g_3, g_4, g_5, g_6, g_7, g_8,
    g_9, g_10, g_11, g_12, g_13, g_14, g_15, g_16
])

S_f_ = SedonionCojnugate(S_f)
f_norm = SedonionNormSquared(S_f)
f_norm_inv_p = PP(f_norm) ^ -1
S_fp = Sedonion([
    PP(_) * f_norm_inv_p for _ in S_f_.coordinates
])
f_norm_inv_q = QQ(f_norm) ^ -1
S_fq = Sedonion([
    QQ(_) * f_norm_inv_q for _ in S_f_.coordinates
])

S_pfq = Sedonion_mul_const(S_fq, p)
S_pfqg = Sedonion_mul_Sedonion(S_pfq, S_g)
S_h = Sedonion([QQ(_) for _ in S_pfqg.coordinates])

I have validated inverses (and the multiplication function alongside) with:

assert Sedonion_mul_Sedonion(S_fPP, S_fp).coordinates == \
    (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
assert Sedonion_mul_Sedonion(S_fQQ, S_fq).coordinates == \
    (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

4. Encryption

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

m = (
    PP([1, 0, 0, 0, 0, -1, 0, 0, 0, 1, 1]),
    PP([0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0]),
    PP([0, -1, 0, -1, 0, 0, 0, 0, 0, 1, 1]),
    PP([0, 0, 0, -1, -1, 0, 0, 0, -1, 0, 0]),
    PP([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]),
    PP([1, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0]),
    PP([1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1]),
    PP([0, 0, 1, -1, 1, 0, 0, 1, 1, 0, 0]),
    PP([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]),
    PP([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    PP([0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]),
    PP([0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0]),
    PP([0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1]),
    PP([1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0]),
    PP([1, 1, 1, -1, 1, 1, 1, -1, 0, 1, 1]),
    PP([0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0]),
)
S_m = Sedonion(m)

r = (
    QQ([0, 1, 1, 1, 0, 0, 0, 0, 0, 0, -1]),
    QQ([0, -1, -1, 0, 0, 0, 1, 0, 0, 0, 0]),
    QQ([1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1]),
    QQ([1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]),
    QQ([0, -1, -1, 1, 0, 1, 1, 0, 0, 0, 0]),
    QQ([1, 1, 1, 0, -1, 0, -1, 0, 0, 0, 0]),
    QQ([0, 0, -1, 0, 0, 0, -1, -1, 0, 1, 1]),
    QQ([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1]),
    QQ([0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0]),
    QQ([1, 1, 1, 1, -1, 0, 0, 0, 0, 0, 0]),
    QQ([0, 0, -1, 0, 1, 1, 1, 0, 0, 0, 1]),
    QQ([1, 1, 1, 1, 0, 0, -1, 0, 0, 0, 0]),
    QQ([0, -1, -1, 1, 1, -1, 1, 1, 1, 0, 0]),
    QQ([1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0]),
    QQ([0, 0, -1, 1, 0, 0, 1, -1, 0, -1, 1]),
)
S_r = Sedonion(r)

S_rh = Sedonion_mul_Sedonion(S_h, S_r)
S_fhRR = Sedonion([RR(_) for _ in S_rh.coordinates])

S_rhm = Sedonion_add_Sedonion(S_fhRR, S_m)
S_e = Sedonion([QQ(_) for _ in S_rhm.coordinates])

5. Decryption

$x = f \times e$ (center lift coefficients)
$y = PP[x]$
$z = f_p^{-1} \times y$ (center lift coefficients)

S_x = Sedonion_mul_Sedonion(S_fQQ, S_e)
S_x = Sedonion([
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[0].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[1].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[2].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[3].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[4].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[5].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[6].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[7].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[8].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[9].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[10].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[11].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[12].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[13].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[14].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_x.coordinates[15].lift()]),
])

S_y = Sedonion([PP(_) for _ in S_x.coordinates])

S_z = Sedonion_mul_Sedonion(S_fp, S_y)
S_z = Sedonion([
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[0].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[1].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[2].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[3].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[4].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[5].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[6].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[7].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[8].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[9].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[10].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[11].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[12].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[13].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[14].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in S_z.coordinates[15].lift()]),
])

And after these operations $S_m \neq S_z$, not even close...

Importantly: I have also tried the decryption process presented here, page 86, but it failed too.

EDIT

Upon closer inspection I see that Singh et al also state that the mechanism provided by Thakur-Tripathi is flawed. And so we confirm that. However it seems to me they provide the exact same scheme, just mention additional properties: IAP-A and IAP-D. I would like to zoom into section 4 of their paper a little.
The authors clearly state that these two properties hold for the basis elements in sedonions. The formulas look contradictory at first but I have verified them computationally and they hold, indeed. Multiplication $f \times (( g \times f) \times h)$ will result either in $(g \times h)$ or $(h \times g)$ for various elements, depending on whether the multiplication of base elements yields $+1$ or $-1$ coefficient (then the operands might be flipped). Up to this point the paper seems correct.
I have narrowed down the problem to the next subsection: "Extending the Property to Polynomials". At this specific point the authors seem to speak of a polynomial with $16$-dimensional vectors as coefficients, rather than $16$ polynomials with integer coefficients. I am a little confused if these may be used interchangeably... Moreover, they state that "...In this way all elements of $A$ will follow either of the two properties." I have verified this statement to be false by multiplication of distinct $(F,G,H)$ sedonions as they propose for the base elements. But maybe it has to do with that different polynomial representation which I have mentioned earlier? Maybe I misunderstood how this is supposed to work?

Answer 1

Flipping through these papers (or at least the Thakur-Tripathi and Malekian-Zakerolhosseini papers; I didn't bother with the paywall around the other), I'm not yet convinced that they are correct. On page 1456 of the Thakur-Tripathi paper, the key generation process is specified* as $$H(x)\equiv F^{-1}(x)\star G(x)\pmod q$$ encryption is specified as $$E(x)\equiv p\cdot H(x)\star\phi(x)+M(x)\pmod q$$ and the first step of decryption is specified as $$F(x)\star E(x).$$

They argue correctness by the following sequence of equations $$F(x)\star E(x)=F(x)\star (p\cdot H(x)\star \phi(x)+M(x))\pmod q$$ (this one is correct). Then $$F(x)\star E(x)\equiv p\cdot F(x)\star H(x)\star\phi(x)+ F(x)\star M(x)\pmod q$$ which combines a usage of both the distributive (true for octonions and sedonions) and associative (not true in general for octonions and sedonions). A correct expression is $$F(x)\star E(x)\equiv p\cdot F(x)\star (H(x)\star\phi(x))+ F(x)\star M(x)\pmod q.$$ Anyway, working from their expression they then proceed to argue that $$F(x)\star E(x)\equiv p\cdot F(x)\star F^{-1}(x)\star G(x)\star\phi(x)+F(x)\star M(x)\pmod q$$ which again uses the associative property when a correct expression is $$F(x)\star E(x)\equiv p\cdot F(x)\star ((F^{-1}(x)\star G(x))\star\phi(x))+F(x)\star M(x)\pmod q.$$ Whereas their final expression does allow them to deduce that $$F(x)\star E(x)\equiv p\cdot G(x)\star\phi(x)+F(x)\star M(x)\pmod q,$$ I don't see how to reach this conclusion using the octonion/sedonion rules of algebra applied to the correct expression (DISCLAIMER: I do not claim to be an expert in such algebras).

The Malekian-Zakerolhosseini paper seems to be a bit better informed their decryption process on page 86 attempts to use the Moufang identities to achieve correctness. Note that the Moufang identities apply to octonions, but I don't think that they work for sedonions in general (q.v. earlier disclaimer). In any event, their decryption process is to define $$B(x)\equiv(F\circ E)\circ F\pmod q$$ which by use of the Moufang identities they correctly deduce satisfies $$B(x)\equiv p\cdot(F\circ (F^{-1}(x)\circ G(x)))\circ(\Phi(x)\circ F(x))+(F(x)\circ M(x))\circ F(x)\pmod q.$$ They then claim that this can be simplified to $$B(x)\equiv p\cdot G(x)\circ(\Phi(x)\circ F(x))+(F(x)\circ M(x))\circ F(x)\pmod q,$$ and again I do not see how to deduce this without associativity.

In short,

• I don't see why the system in the Thakur-Tripathi paper would work at all.
• It might be worth dropping a line to Malekian-Zakerolhosseini to ask why they think that their final simplification holds, but even then the use of Moufang identities means that this works for the octonions but not the sedonions.
• There may or may not be something in the "inverse associative property" used by Singh, Padhya and Pal (they do at least claim to have verified the property computationally), but I don't propose to spend money investigating this.

---

(*) - Actually they botch this statement.