Join Log in
Score:1
max avatar Crypto

NTRUEncrypt fails on complex algebra

dm flag
max

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the system works just as expected.

I have noticed an interesting publication regarding expanding NTRU to higher order algebras. This one is about quaternions but in the following example I will try complex numbers first, baby steps.

So, I have implemented the code to define cryptosystem's parameters, encrypt and decrypt, but in the end I cannot recover the initial polynomial. I do not know if this is just a bug or is there a conceptual error in my steps; need some help loooking through this.

Define parameters and respective polynomial rings:

N = 11
p = 3
q = 37

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)

Select polynomials $f$ and $g$

f_1 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
f_2 = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])

g_1 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])
g_2 = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

f = (f_1, f_2)
g = (g_1, g_2)

Calculate a multiplicative inverse of $f$ over respective rings $PP$ and $QQ$.
Remember that: $f^{-1}_{XX} = [\frac{1}{||f||^2}]_{XX}\times \bar{f}$
Also: $||f||^2 = f_0^2 + f_1^2$ and $\bar{f} = (f_0, -f_1)$

f_ = (f[0], -f[1])
f_norm = f[0]^2 + f[1]^2

f_norm_inv_p = PP(f_norm) ^ -1
fp = (
    PP(f_[0] * f_norm_inv_p),
    PP(f_[1] * f_norm_inv_p),
)

f_norm_inv_q = QQ(f_norm) ^ -1
fq = (
    QQ(f_[0] * f_norm_inv_q),
    QQ(f_[1] * f_norm_inv_q),
)

Check the inverses under complex multiplication $a \times b = (ac-bd, ad+bc)$

assert PP(f[0] * fp[0]) - PP(fp[1] * f[1]) == 1
assert PP(f[0] * fp[1]) + PP(f[1] * fp[0]) == 0
assert QQ(f[0] * fq[0]) - QQ(fq[1] * f[1]) == 1
assert QQ(f[0] * fq[1]) + QQ(f[1] * fq[0]) == 0

Generate public key $h = pf_q \times g$

pfq = (p * fq[0], p * fq[1])
h = (
    QQ(pfq[0] * g[0]) - QQ(g[1] * pfq[1]),
    QQ(pfq[0] * g[1]) + QQ(pfq[1] * g[0]),
)

Encryption $e = r \times h + m$

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

r = (
    RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]),
    RR([0, 1, 1, 1, 1, 1, 1, 0, -1, 1, 1]),
)

rh = (
    r[0] * h[0] - h[1] * r[1],
    r[0] * h[1] + r[1] * h[0],
)

e = (
    QQ(rh[0] + m[0]),
    QQ(rh[1] + m[1]),
)

Decryption:
$a = f \times e$ (remember to center lift the coefficients)
$b = PP[a]$
$c = f_p \times b$

a = (
    QQ(f[0]) * e[0] - e[1] * QQ(f[1]),
    QQ(f[0]) * e[1] + QQ(f[1]) * e[0],
)

a = (
    ZZ['x']([coeff.lift_centered() for coeff in a[0].lift()]),
    ZZ['x']([coeff.lift_centered() for coeff in a[1].lift()]),
)

b = (PP(a[0]), PP(a[1]))

c = (
    fp[0] * b[0] - b[1] * fp[1],
    fp[0] * b[1] + fp[1] * b[0],
)

In the end $c \neq m$... I am a little troubled, why(?)

P.S. To quickly check Sage piece of code you may use this site: https://sagecell.sagemath.org/

132
1 + 0
Score:2
Daniel S avatar Crypto
ru flag
Daniel S

Again, there's nothing wrong with the code: the rounding process is noisier in this case and has again caused a reduction to be lifted in correctly.

Essentially here we are using NTRU with the Gaussian integers as base ring $\mathbb Z[i][x]$ instead of the more usual $\mathbb Z[x]$. However, we're still in a nice Euclidean setting and so this should not concern us. There's a slight gotcha in that 37 does not generate a prime ideal over the Gaussians because e.g. $37=(6+i)(6-i)$. This may cause more choices of $g(x)$ to be unsuitable for not having an inverse, but is unlikely to impinge in practice. Also note that you don't have to set $f_1=f_2$ nor otherwise for other polynomials if you do not wish. By choosing this limitation, you restrict to the residue choices $0,1+i,-1-i\pmod p$ when you could be using 9 residue choices for $p=3$.

Anyway, recall that the goal of the decryption process is to recover the (Gaussian) integer polynomial $$a(x)=r(x)g(x)p+f(x)m(x)$$ which we can compute as

sage: inta = ( p*(r[0]*g[0]-r[1]*g[1]) + f[0]*m[0]-f[1]*m[1] , p*(r[0]*g[1]+r[1]*g[0])+f[0]*m[1]+f[1]*m[0])
sage: inta
(0, -10*xbar^10 - 8*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 - 2*xbar^3 - 20*xbar^2 - 6*xbar)

notice that as integers the coefficients of the real and imaginary parts of $a(x)$ are the sums of four pairs of products rather than the two pairs of products in non-Gaussian NTRU. This leads to larger coefficient growth and a greater chance of error. If we now compare the $a(x)$ that we wish to recover to its reduction mod $q$ that is obtained during the decryption process, we see

sage: aq = ( QQ(f[0]) * e[0] - e[1] * QQ(f[1]), QQ(f[0]) * e[1] + QQ(f[1]) * e[0])
sage: aq
(0, 27*xbar^10 + 29*xbar^9 + 16*xbar^8 + 20*xbar^7 + 10*xbar^6 + 4*xbar^5 + 8*xbar^4 + 35*xbar^3 + 17*xbar^2 + 31*xbar)

and all of the coefficients agree mod $q$ as we would hope. However, when we try to lift, we see that there are coefficients of $a(X)$ that lie outside the interval $(-q/2,q/2)$: specifically the imaginary parts of the coefficients of $x^7$ and $x^2$. Thus, when we lift we recover an incorrect integer polynomial:

sage: a = ( ZZ['x']([coeff.lift_centered() for coeff in aq[0].lift()]), ZZ['x']([coeff.lift_centered() for coeff in aq[1].lift()]))
sage: a
(0, -10*x^10 - 8*x^9 + 16*x^8 - 17*x^7 + 10*x^6 + 4*x^5 + 8*x^4 - 2*x^3 + 17*x^2 - 6*x)

This leads to the failure to recover the plaintext. Had you selected a prime $q$ with $20<q/2$ such as $q=43$ then the process would have worked fine.

+ 0
ธงชาติไทย
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.