Paillier密码体制中的搜索

Question

我已经实现了Paillier密码系统。比方说，我有一个加密的数组E(x) = 2,4,5,10,0,20，我想要找到如果该数组中存在0。由于Paillier密码体制的局限性，我不能将两个密文相乘。还有别的方法可以找到吗？

Answer 1

Paillier是一个CPA安全的密码，因此我们可以从密文中推断出的任何东西都需要私钥。因此“我想找到…”要求“我”拥有私钥，然后“我有一个加密的数组”意味着“我”可以解密每一封密文，这使得问题没有意义。

因此，我们将问题语句更改为:我们最多有k小整数m_i\in[0,\ell) (在手头的问题中，我们需要k\ge6和\ell>20)；我们希望有一种公共方法来表示这些使用Paillier密码系统加密为c_i的m_i，并像我们在Paillier中所做的那样，将c_i组合成一个单一的c。这是使产品模块化n的c_i，并可选择乘模n由密文为0进一步掩盖的结果。我们需要一些东西，以便持有私钥的人可以从c中确定0是否存在于m_i的初始数据集中。这将改变初始问题陈述中的两项重要内容：

• 有一种将密文c_i组合到c中的概念，私钥持有者无法使用c_i。
• 我们没有“加密数组”。我们想要一个，但可以自由地定义它是如何制作的，只要它是使用Paillier加密的。没有这样的自由，就没有解决方案，因为Paillier解密只会让一个人获得m=(\sum m_i)\bmod n，如果一个m_i是0，就无法从中判断出来。

在这里，我们不仅可以知道0是否存在于m_i中，还将知道[0,\ell)中每个整数在原始数组中出现的次数。

为此，在应用Paillier加密之前，我们将m_i编码为m'_i=(k+1)^{m_i}。帕里尔将让我们将密文c_i合并，然后将组合c解码成m'=(\sum m'_i)\bmod n。从m'中我们可以推断出[0,\ell)中的每一个整数在m_i中存在的次数，只要是k(k+1)^{\ell-1}<n，我们就可以通过在基k+1中表示m'并查看数字/四肢来推断它的存在时间。我将跳过代数关于如何，并使用一个十进制的例子(例如k=9)。m_0=2，m_1=4，m_2=5，m_3=10，m_4=0，m_5=20编码m'_0=100，m'_1=10000，m'_2=100000，m'_3=10000000000，m'_4=1，m'_5=0，m'_6=100000000000000000000在十进制中。我们将得到m'=1000000000010000110101，从这里我们可以看出，在原始的m_i数组中，只有一个是0，2，4，5，10，20，通过查看非零位数的位置，看到它们是1。如果20改为0，结果将是m'=10000110102，我们就知道有两个m_i=0，因为最右边的数字是2。

这个问题并没有说明我们不希望私钥持有者能够从c中确定什么。也许我们希望将其限制在确定是否存在0，尽可能少地泄漏多少0。

为此，我们可以将每个m_i\ne0编码为m'_i=0，并将每个m_i=0编码为[1,\lfloor n/k\rfloor)中任意选取的整数m'_i，其分布严重偏向低值。当组合的解密为零时，就知道m_i中没有零，而没有其他任何东西。否则，它知道有一个零，它是泄露了很少的信息有多少。可以优化分发以尽量减少泄漏，这是留给读者的练习。

可以对事物进行细化，以便具有私钥和c_i的用户能够找到m_i，但是(如上面所示)使用私钥和c可以获得很少关于m_i的信息，除此之外是0。我不会详细说明，因为这不在问题陈述中。

和许多同态加密一样，这些都是很好的理论系统，几乎没有匹配的现实问题。