复代数上的NTRUEncrypt失败

Question

我遵循的是NTRUEncrypt密码体制，如维基百科所描述的。我已经在Sage Math engine中实现了它(在此过程中使用了小问题，但最终得到了成功的解决)，并且系统的工作方式与预期的一样。

我注意到了关于将NTRU扩展为高阶代数的一个有趣的出版物。这个是关于四元数的，但是在下面的例子中，我将首先尝试复数，步骤。

因此，我已经实现了定义密码系统参数的代码，加密和解密，但最终无法恢复初始多项式。我不知道这是否只是一个bug，或者在我的步骤中是否有一个概念错误；需要一些帮助来查看这个问题。

定义参数和相应的多项式环：

N = 11
p = 3
q = 37

R. = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P. = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q. = PolynomialRing(Zmod(q))
QQ = Q.quotient(x^N - 1)

选择多项式f和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)

计算f在各自环PP和QQ上的乘积逆。记住：f^{-1}_{XX} = [\frac{1}{||f||^2}]_{XX}\times \bar{f}也是：||f||^2 = f_0^2 + f_1^2和\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),
)

检查复乘法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

生成公钥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]),
)

加密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]),
)

解密：a = f \times e (记得把系数集中起来) 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],
)

最后c \neq m..。我有点麻烦，为什么(？)

要快速检查Sage代码，您可以使用以下站点：https://sagecell.sagemath.org/

Answer 1

同样，代码没有什么问题:在这种情况下，舍入过程更吵，并且再次导致正确地取消了减少。

从本质上讲，我们使用的是带高斯整数的NTRU作为基环\mathbb Z[i][x]，而不是更常见的\mathbb Z[x]。然而，我们仍然处于一个很好的欧几里得环境中，所以这不应该与我们有关。这里有一个小问题，就是37不能在高斯上产生一个质数理想，因为例如37=(6+i)(6-i)。这可能会导致更多的g(x)选择不适合于没有相反的选择，但在实践中不太可能产生冲击。还请注意，如果您不愿意的话，您不必为其他多项式设置f_1=f_2或其他多项式。通过选择此限制，当您可以为0,1+i,-1-i\pmod p使用9个剩余选项时，您将限制为p=3的剩余选择。

无论如何，回想一下解密过程的目标是恢复(高斯)整数多项式a(x)=r(x)g(x)p+f(x)m(x)，我们可以将其计算为

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)

注意，作为整数，a(x)的实部和虚部的系数是四对乘积的和，而不是非高斯NTRU中的两对乘积的和。这将导致更大的系数增长和更大的错误机会。如果我们现在将希望恢复的a(x)与在解密过程中获得的简化的mod q进行比较，我们将看到

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)

正如我们所希望的那样，所有系数都符合mod q。然而，当我们试图提升时，我们看到a(X)的系数位于区间(-q/2,q/2)之外:特别是x^7和x^2系数的虚部。因此，当我们提起时，我们恢复了一个不正确的整数多项式：

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)    

这导致无法恢复明文。如果您选择了一个带有20 (例如q=43 )的素数D21，那么这个过程就会运行得很好。