关于NTRUEncrypt的一个新问题:小r(x)和最近向量问题

Question

在具有系统参数NTRUEncrypt的(N, p, q)中，将Bob的公钥设为h(x).

要加密系数较小的明文m(x)，Alice需要生成一个随机r(x),，其系数也要小，并计算密文c(x) = r(x) \times h(x) + m(x) \bmod q.。

人们认为很难从m(x)中找到c(x)，这种困难大概是基于最接近的向量问题。

我的问题是:为什么r(x)必须在加密中有很小的系数？看起来，即使r(x)有很大的系数，从c(x)中找到m(x)仍然与CVP问题有关；这是真的吗？

Answer 1

使r(x)系数变小的意图并不是使攻击者的生活变得困难，而是使目标收件人的生活成为可能。

回想一下，h(X)被选中为表单

h(X)\equiv \frac{g(X)p}{f(X)}\pmod q

当f(X)和g(X)的系数小且秘密时，p是q的素小，q是相对于所有小量的大的。

现在考虑解密，它以c(X)的乘积f(X)开始给出

c(X)f(X)\equiv r(X)g(X)p+m(X)f(X)\pmod q

如果f，g，m和r的系数都很小，那么我们可以用很高的概率来写。

c(X)f(X)= r(X)g(X)p+m(X)f(X)

在没有约简模q的整数上，将系数舍入到0(即强制进入区间[-q/2,q/2])。另一方面，如果r(X)有任何较大的(相对于q)系数，那么我们几乎肯定无法做到这一点。

如果我们的舍入过程是成功的，那么我们可以删除r(X)的贡献，减少模p，然后恢复m(X)。

请注意，随着度的增长，舍入过程并不一定会成功，因此NTRUEncrypt的失败概率取决于系数、大小和程度，我们必须尽量保持在较低的水平。还请注意，故障可能取决于m(X)的选择，这使得攻击者能够主动获取有关私钥的信息(同样，我们试图保持较小的概率)。

您是正确的，r(X)\pmod q可以通过求解CVP来恢复，而不管其系数的大小(假设m(X)的系数很小)。