同态加密可以用来交换密钥吗？

Question

全同态加密(FHE)允许对密文进行计算。这种技术可以用来交换钥匙吗？

例如，Alice和Bob需要就一个4位的密钥达成一致。Alice向Bob发送4个不同的字符串，它们分别是0001、0010、0100和1000的密文。现在，鲍勃选择了秘密密钥0101。他对对应于0100和0001的密文执行位-或计算，并将结果发回给Alice。爱丽丝破译结果，得到0101。

这个计划是否安全？(除了密钥通常要长得多的事实外)

Answer 1

In

它可以是安全的，但它将非常低效。

详细

如果将这些位字符串0001、0010、0100、1000等看作整数(例如，2^0, 2^1, 2^2, 2^3等)，并按逻辑位数或对其中的某些字符串进行应用，则它们只是二次方的幂。

因此，您建议的场景是，Alice发布多个二次幂加密，c_i := Enc(2^i)和Bob以某种随机方式组合它们，也就是说，Bob选择b_i \in \{0,1\}并进行计算。

c_B := \sum_{i=0}^{n-1} b_i\cdot c_i = Enc\left(\sum_{i=0}^{n-1} b_i\cdot 2^i\right).

很容易看出，如果每个b_i都是一致选择的，那么c_B加密的值在\{0, 1, ..., 2^n-1\}上的分布是一致的，这是一个完美的场景(交换的密钥是一致的，那么很难猜测)。

然而，这种方法的问题在于，攻击者可以查看c_B和所有的c_i's，并试图找出b_i's的值。注意，如果我们设法发现至少一个b_i，那么我们就知道交换密钥的i-th位是什么。因此，我们必须排除这种可能性。

一种标准的方法是使用剩余的哈希引理来保证c_B的分布在统计上接近密文集\mathcal C上的一致，但它需要比安全参数\lambda大得多的n。这意味着，Alice需要发布的不仅仅是\lambda密文，每个密文都有多个\lambda位，这意味着发布的比\lambda^2位要多得多(可能比\lambda^3还要多)。我们仍然需要考虑到加密和合并所有这些值所需的时间.

此外，我不认为还有另一种使密钥交换安全的方法，因为隐藏这些b_i's的问题基本上与同态加密方案转化为公开密钥方案时所面临的问题相同，而我在文件中经常看到的解决方案就是我所说的(使用剩余的Hash引理)。