为什么NTRUEncrypt在不同的大模量值上失效？

Question

我试图密切跟踪算法这里 (保持相同的变量名)，并在Sage引擎中重构密码系统。它似乎适用于参数(N, p, q) = (11, 3, 31)，但在(N, p, q) = (11, 3, 29)的末尾会引发断言错误。请参阅以下代码：

N = 11
p = 3
q = 31 # fails for 29

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)

f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

fp = PP(f) ^ -1
fq = QQ(f) ^ -1
assert fp * f == 1
assert fq * f == 1

h = QQ( (p * fq) * g )
m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1])
r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0])
e = QQ(r * h + m)
a = QQ(f) * e
a = ZZ['x']([coeff.lift_centered() for coeff in a.lift()])
b = PP(a)
c = fp * b
assert c == m

我在这里做错什么了吗？

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

Answer 1

没有什么不正确的，基于格的密码术有一个解密失败的机会，这个机会随着程度和噪声相对模数的增加而增加。我认为，看这里的实际数字是很有启发意义的，这样才能感受到基于格的密码学中固有的不确定性。如果我们扩展sage代码来同时生成这两种情况

N = 11
p = 3
q1 = 31
q2 = 29

R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q1.<x> = PolynomialRing(Zmod(q1))
QQ1 = Q1.quotient(x^N - 1)
Q2.<x> = PolynomialRing(Zmod(q2))
QQ2 = Q2.quotient(x^N - 1)


f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

fp = PP(f) ^ -1
fq1 = QQ1(f) ^ -1
fq2 = QQ2(f) ^ -1
assert fp * f == 1
assert fq1 * f == 1
assert fq2 * f == 1

h1 = QQ1( (p * fq1) * g )
h2 = QQ2( (p * fq2) * g )
m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1])
r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0])
e1 = QQ1(r * h1 + m)
e2 = QQ2(r * h2 + m)
a1 = QQ1(f) * e1
al1 = ZZ['x']([coeff.lift_centered() for coeff in a1.lift()])
a2 = QQ2(f) * e2
al2 = ZZ['x']([coeff.lift_centered() for coeff in a2.lift()])
b1 = PP(al1)
b2 = PP(al2)
c1 = fp * b1
c2 = fp * b2

请注意，我还为a(x)\mod q及其对\mathbb Z[x]的提升使用了单独的变量。如果我们比较a1和a2，我们可以看到

sage: a1
27*xbar^10 + 3*xbar^9 + 30*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 20*xbar^3 + 27*xbar^2 + 24*xbar
sage: a2
25*xbar^10 + 3*xbar^9 + 28*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 18*xbar^3 + 25*xbar^2 + 22*xbar

这些是相同多项式a(x)=r(x)g(x)p+f(x)m(x)的约简。

=-4x^{10}+3x^9-x^8+4x^7+15x^6+10x^5+4x^4-11x^3-4x^2-7x

对于整数和解密，我们希望将这个多项式的每一个缩减提升到原来的整数版本。整数多项式的系数是小整数乘积的和，所以我们希望它们不会增长到大。特别是，如果所有的系数都在(-q/2,q/2)的范围内，那么这个约简可以被解释为这个区间中的剩余，并且被提升回原始的多项式而没有错误。然而，如果我们看x^6 t的系数是15，虽然它在区间(-31/2,31/2)中，但它不存在于区间(-29/2,29/2)中，所以我们的缩减不是平凡的，我们的升力也不起作用。具体来说，如果我们看看al1和al2

sage: al1
-4*x^10 + 3*x^9 - x^8 + 4*x^7 + 15*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x
sage: al2
-4*x^10 + 3*x^9 - x^8 + 4*x^7 - 14*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x

在第二种情况下，我们在整数上恢复了错误的多项式，导致以后的步骤失败。q越大，整数多项式系数超出可恢复范围的可能性就越小，因此解密失败就会减少。然而，增加q可以使攻击者的生活变得更容易，并且必须进行权衡。

在解密失败的情况下，可以通过扫描提升多项式中接近q/2的系数，然后通过\pm q调整这些可疑系数来纠正这些错误。然而，这会导致非恒定的解密时间，并造成各种类型的侧机制、欺骗和故障注入漏洞。