Paillier复杂剩余问题？

Question

Paillier密码系统既依赖于n = p.q所在的因式分解，也依赖于原论文中定义为：

决定n-残差的问题，即区分n-残和非n-残的问题，将用CRN来表示。与确定二次或高次残差问题一样，CRN是一个随机自约问题，即它的所有实例都是多项式等价的。因此，每一种情况都是平均情况，问题要么是一致棘手的，要么是一致多项式的。对于素数残差，决定n的残差被认为是计算困难的.因此，我们将假定：

猜想2. n-剩余模n2不存在多项式-时间分辨器，即CR-N是难以解决的.

因此，根据这个注解在\mathbb{Z}_{n^2}^*中给出的数字，我无法确定这个数字是否在剩余集上。

我的问题是：

1. 如果z=y^n\ mod\ n^2这么难的话
2. 更重要的是知道残余物中的一个数字是如此危险的。它怎么能帮我破解密码？

Answer 1

1. 如果z=y^n\ mod\ n^2这么难的话

我们不知道有什么有效的办法解决这个问题。从本质上讲，密码学中的任何难题都可以这样说。

我们也不知道将问题简化为一个研究得更好的问题(例如，分解问题)；因此，它被称为一个单独的硬问题。

1. 更重要的是知道残余物中的一个数字是如此危险的。它怎么能帮我破解密码？

这很容易；能够解决n-剩余问题(不知道因式分解)的Oracle允许我们确定Pallier加密消息是否是0的编码(因为密文是0的编码当且仅当它是n个剩余)。

这本身不仅会被认为是安全性的破坏，我们还可以(例如)测试加密消息是否与任何其他值相等(通过加密该值，同态地从加密值的密文中减去测试密文，并检查这是否是编码为0)。