Join Log in
Score:3
max avatar Crypto

NTRUEncrypt fails on sedonion algebra

dm flag
max

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?

266
1 + 2
fgrieu avatar
ng flag
fgrieu
Related [question](https://crypto.stackexchange.com/q/103511/555).
0
Reply
Daniel S avatar
ru flag
Daniel S
I've set up a chat to discuss your edit: https://chat.stackexchange.com/rooms/141744/sedonion-ntru
0
Reply
Score:3
Daniel S avatar Crypto
ru flag
Daniel S

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.

+ 5
max avatar
dm flag
max
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?
0
Reply
Daniel S avatar
ru flag
Daniel S
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.
0
Reply
max avatar
dm flag
max
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?
0
Reply
max avatar
dm flag
max
Daniel: You should now that your explanations helped me finalise my research paper: https://joss.theoj.org/papers/10.21105/joss.05272 you are in the 'acknowledgments' ;)
0
Reply
Daniel S avatar
ru flag
Daniel S
@max Congratulations on your paper; I am glad that I was able to help.
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.