Paillier同态加密中值的比较

Question

对于一个项目，我使用的同态加密与Paillier密码系统，我必须比较两个值.

• 这能用同态加密来完成吗？
• 我知道减法可以用同态加密完成，但是谁能简化步骤呢？

任何建议都会有帮助。

Answer 1

可以用同态加密吗？

不是没有与私人钥匙的人的互动。

假设有一种可能的方法；给定E_k(a)和E_k(b)，您可以确定a < b是否。如果是这样的话，那么我们可以使用它来解密给定的E_k(a)，您可以加密b的各种值，然后检查是否存在a < b --当我们找到像a < b和a \not\lt b-1这样的值时，我们就知道a的值了。

现在，另一个可能的比较含义是，给定E_k(a), E_k(b) create E_k(0) if a < b和E_k(1) if a \ge b。在这种情况下，随着比较运算变得完全同态；例如，要计算E_k(a)和E_k(b)的NAND，只需将E_k(1-a) (很容易用Pallier计算)与E_k(b)进行比较--一旦我们有了同态NAND函数，我们就可以构造任何电路。

我知道减法可以用同态加密完成，但是谁能简化步骤呢？

给定E_k(b)，我们可以通过计算E_k(b)的模逆来计算E_k(-b) --这是因为E_k(b) = g^b r^n和(E_k(b))^{-1} = g^{-b}(r^{-1})^n，这是对-b的有效加密。

然后，我们可以用正规同态加法来计算E_k(a - b)。