全同态加密BFV-(section 3-FHE)

陆叁 2021-10-12

822

点击上方蓝字获取更多新鲜资讯

5 Fully Homomorphic Encryption

为了将有限同态的加密方案变成完全同态的加密方案，我们需要一种在达到最大噪声级别之前降低噪声的方法。的的思想真的很简单[7]，即在数据加密的情况下同态解密。此操作得到的结果将是对同一明文的加密，但具有固定大小的噪声。如果解密电路可以在深度中进行评估，那么后的噪声等于通过评估深度电路获得的噪声，这显然与密文中存在的起始噪声无关。因此，如果可以处理深度的电路，在后仍然可以处理一个乘法，从而得到一个完全同态的方案。实际上，最好“ ”该方案的同态能力，即选择参数，使最大深度严格大于。

由于我们需要同态运行，所以我们要求解密电路尽可能简单。在方案的早期，这通常是通过写密钥来压缩解密电路来处理的，该问题引入了一个新的安全性假设。然而，在我们的例子中，我们可以简单地在不需要压缩的情况下，处理。

回想一下，给定一个密文，对于，的我们有。在第一步中，我们将计算，然后可以轻松地通过 "centered reduction" 转换为。关键是，如果我们不允许的范数增长到它的最大大小，而只增长到，其中，我们可以通过忽略大部分和来优化解密。事实上，如果我们用和替换为和，其中（例如通过将所有低阶位设置为零），那么我们就有了

因此，这个截断密文中的噪声项从上升到。为了约束新噪声的大小，我们需要两个函数：定义作为取其系数绝对值得到的多项式，并定义函数

对于形式的多项式，我们有。如果我们现在让表示的"Hamming weight"，那么我们得出结论，新的噪声以为界。因此，截断的密文仍然会解密，只要。通过，我们可以得到。这表明，我们可以简单地处理的顶部和比特的。请注意，由于我们首先计算结果模，所有这些系数都是正的，我们不必混乱符号位 (sign bit)。

因此，结果的每个系数都可以计算为整数的总和来计算,每个整数都有位。我们可以用这些整数的每个位的矩阵来表示这种情况 (第一列中最小有效位，小端序表示法)。请注意，矩阵中大约一半的位将为零，通过将所有零向下移动，我们实际上将使用大约一半大小的矩阵。为了简化论述，我们提出了两种情况的分析：第一，和的优化情况，这是非常容易分析和提供最优结果，第二，一般情况，与以前的论文中直接处理一般情况不同，我们使用模数转换 (modulus switching) 技巧 (几乎) 将其减少到最优情况。

5.1 Optimised case: and

这种情况更容易处理的原因是解密函数大大简化了：实际上，由于和，我们可以认为。利用表达式，很容易看出

因此，我们不需要 "centered reduction"，且除以可归结为一个简单的移位。此外，由于也是的幂，所以最终的 "centered reduction" 是得到模的 bits 的一个简单函数。准确地说，我们总结了如何对消息的一个系数（例如常量系数）进行解密：

给定密文考虑的顶部比特，即，设置和，其中表示右移。
考虑从和的常数系数中得到的整数模，并将这些常数的每个位放入矩阵中。
将整数加在一起模导致一个整数。
定义舍入位，输出。

因此，解密中的主要计算只是通过计算矩阵的行和来计算整数模的和。为此，我们使用了一个标准的两阶段过程：我们首先重复使用一个进位加法器，它以的行作为输入，并将它们减少到两行，其和相同。更详细：用表示三行中的位，然后进位保存加法器 (carry save adder) 返回包含在第位置的两行

其中被定义为零。请注意，由于我们只计算模的和，所以我们可以忽略第位以外的任何进位传播 (carry propagation)。这里需要注意的关键一点是，当我们在加密域中执行此计算时，第一行的噪声没有增加多少，因为它不涉及任何乘法。在下一次迭代中，我们应该注意最大限度地将具有相似噪声级别的行组合起来。其原因是两个密文乘积的噪声是一个常数因子，大于噪声的最大值。因此，我们需要尝试以平衡的方式乘以密文，根据它们的噪声大小组合它们。我们可以重复进位加法器，直到我们剩下两行。在第二阶段，我们使用一个简单的 "schoolbook" 加法来最终恢复比特表示的全部和。很容易看出，第位（从开始计数）作为布尔表达式在位是由给出的，所以我们需要一个深度电路将这些数字模相加。舍入位就是第（对于，它开始从开始计数），结果模通过将该位加到最后位获得。注意，这一步不会增加所需的深度，因为我们正在工作模。此外，请注意，知道结果模与 "knowing the centered reduction" 结果是等价的，因此我们可以跳过最后一步。因此，我们的意思是，如果我们将，那么解密仍然会得到。

我们之所以把解密写成二进制电路，是因为这允许我们对电路在加密域中进行同态评估。请注意，这需要给出秘密的位的加密，因此我们引入以下过程：

请注意，在实践中，不会分开加密所有比特，而是使用 SIMD 技术同时加密几个比特，从而大大降低了的使用。

对所要求的乘法深度的分析可以归纳在下面的定理中。

虽然一般情况下可以直接处理，即，通过分析，我们将使用一个小技巧，进而大大简化分析。回想一下，一个有效的密文满足

如果我们假设噪声不是最大，我们可以简单地从模数切换到，其中通过简单的缩放超过。事实上，如果我们为定义，那么就可以很容易地验证这一点

其中。只要，我们得到了一个有效的密文相对于模数而不是。

通过考虑作为解密的密文，解密现在几乎变得和优化的情况一样简单。第一步与之前完全相同：我们仅通过和处理最高位，因此使用深度的电路通过获得的近似值。令为的常数系数，则消息的常数项为

然而，由于不再需要除以，我们真的需要使用 centered reduction，而不仅仅是模，但这是相当容易的。如果，我们需要用代替它，所以如果我们定义，那么 centered reduction 是通过组合的方式给出的

和等于的符号位( 表示负数)。注意，通过 negating 的所有位并添加非常容易计算。由于这些操作增加了两个 levels，所以用深度电路可以得到 centered reduction 。为了计算，我们需要一个额外的 levels，其中表示的。除以是免费的，并且舍入是在最佳情况下进行的，即通过简单地在二进制点之后添加第一位来完成，这最多需要一个深度级别。和以前一样，我们可以再次忽略最终的 centered reduction 模。最终证明了更一般的定理。

定理 3. 如果可以评估深度的电路 (其中表示的，并且如公式 (5) 所定义)，则可以通过使用将具有的二进制秘密的有限同态加密 SHE 方案转换为完全同态加密 FHE 方案。

以上便是中将转化为的全过程。

如果第一次看到这篇文章，那么你可能需要去重头看起：

全同态加密学习路线

一、全同态加密BFV-(section 1-基础知识)

全同态加密BFV-(section 2-SHE)

参考文献：

Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Advances in Cryptology - CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science, pages 595–618. Springer, 2009.
Zvika Brakerski.Flly Homomorphic Encryption without Modulus Switching from Clas- sical GapSVP.IACR Cryptology ePrint Archive,2012:78,2012.
Zvika Brakerski, Craig Gentry,and Vinod Vaikuntanathan.(Leveled)fully homomorphic encryption without bootstrapping. In Innovations in Theoretical Computer Science 2012, pages 309-325. ACM, 2012.
Zvika Brakerski and Vinod Vaikuntanathan. Fully Homomorphic Encryption from Ring- LWE and Security for Key Dependent Messages.In Advances in Cryptology-CRYPTO 2011,volume 6841 of Lecture Notes in Computer Science,pages505-524. Springer,2011.
Jean-Sébastien Coron, Avradip Mandal, David Naccache,and Mehdi Tibouchi. Fully Homomorphic Encryption over the Integers with Shorter Public Keys.In Advances in Cryptology-CRYPTO 2011, volume6841 of Lecture Notes in Computer Science,pages 487-504. Springer, 2011
Nicolas Gama and Phong Q.Nguyen.Predicting Lattice Reduction.In Advances in Cryptology-EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science, pages 31-51. Springer,2008.
Craig Gentry. A fully homomorphicencryption scheme.PhD thesis, Stanford University, 2009. Craig Gentry's PhD Thesis
Craig Gentry. Fully homomorphic encryption using ideallattices.In STOC2009,pages 169-178.ACM,2009.
Craig Gentry and Shai Halevi.Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic circuits.in is almost here! FOCS 2011, pages 107-109.IEEE,2011
Craig Gentry and Shai Halevi. Implementing Gentry's Fully-Homomorphic Encryption scheme.in -&nbsp Advances in Cryptology-EUROCRYPT2011, volume 6632 of Lecture Notes in Computer Science,pages 129-148. Springer, 2011.
Craig Gentry, Shai Halevi,and Nigel P.Smart.Homomorphic Evaluation of the AES Circuit.IACR Cryptology ePrint Archive,2012:99,2012.
Shafi Goldwasser,Yael Tauman Kalai, Chris Peikert,and Vinod Vaikuntanathan. Ro- bustness ofthe Learning with Errors Assumption.In ICS 2010,pages 230-240.Tsinghua University Press, 2010.
Adeline Langlois and Damien Stehlé. Hardness of decision(R)LWE for any modulus. IACR Cryptology ePrint Archive,2012:91, 2012.
Richard Lindner and Chris Peikert.Better Key Sizes(and Attacks) for LWE-Based Encryption.In Topics in Cryptology-CT-RSA 2011,volume 6558 of Lecture Notes in Computer Science, pages 319-339.Springer,2011.
Vadim Lyubashevsky, Chris Peikert,and Oded Regev. On Ideal Lattices and Learning with Errors over Rings.In Advances in Cryptology-EUROCRYPT 2010,volume 6110 of Lecture Notes in Computer Science,pages 1-23.Springer,2010.Full version of the paper available upon request from authors.
Michael Naehrig, Kristin Lauter,and Vinod Vaikuntanathan. Can homomorphicen- cryption be practical? In CCSW 2011,pages 113-124.ACM,2011.
Oded Regev. On lattices,learning with errors, random linear codes,and cryptography. In STOC 2005, pages 84-93. ACM, 2005.
Nigel P.Smart and Frederik Vercauteren. Fully Homomorphic Encryption with Rela- tively Small Key and Ciphertext Sizes.In PKC 2010, wolume 6056 of Lecture Notes in Computer Science, pages 420-443.Springer,2010.
Nigel P.Smart and Frederik Vercauteren.Fully Homomorphic SIMD Operations.IACR Cryptology ePrint Archive, 2011:133, 2011.
Damien Stehléand Ron Steinfeld.Faster Fully Homomorphic Encryption.In Advances in Cryptology-ASIACRYPT2010,volume 6477 of Lecture Notes in ComputerScience pages 377-394. Springer, 2010.
Marten van Dijk, Craig Gentry, Shai Halevi,and Vinod Vaikuntanathan. Fully Homo- morphic Encryption over the integers.in Domain Name Is Available to Buy - Domain Name Marketplace Adances in Cryptology-EUROCRYPT2010, volume 6110 of Lecture Notes in Computer Science,pages 24-43.Springer,2010.