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?