# NTRUEncrypt fails on sedonion algebra

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_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?

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.

• Can the cryptosystem be correct in at least some cases? i.e. the sender choosing very specific $F, G, \Phi$ (non-trivial: sedonions, not octonions) can force the properties needed for successful decryption?
– max
Commented Jan 1, 2023 at 21:04
• It’s not clear to me (I repeat my disclaimer). Obviously, if we restrict to the quaternion subalgebra, things will work, but I can’t think of any other construction. Commented Jan 1, 2023 at 21:21
• Daniel: Thank you for all your help. I have added an "EDIT" section to my question with more information. I would like to narrow this down before considering this closed, not leaving loose ends. Could you please take a look and let me know what do you think?
– max
Commented Jan 3, 2023 at 11:38
• Daniel: You should now that your explanations helped me finalise my research paper: joss.theoj.org/papers/10.21105/joss.05272 you are in the 'acknowledgments' ;)
– max
Commented May 16, 2023 at 8:27
• @max Congratulations on your paper; I am glad that I was able to help. Commented May 16, 2023 at 8:34