全同态加密：基于PACDP的高效整数方案

"这篇文档是关于可评估多项式次数的PointNet++的中文翻译，讨论了同态加密中的加法和乘法同态性质，以及它们如何影响对电路深度和多项式次数的评估。文中还介绍了全同态加密方案的安全性和效率优化，特别是基于部分近似最大公因子问题(PACDP)的整数全同态加密方案。" 在同态加密领域，可评估多项式次数是一个关键概念，因为它关系到加密方案能够处理的计算复杂度。在3.2节中，文章解释了解密过程中的正确性，指出当噪声（即明文除以公钥的余数）的绝对值小于2p时，可以正确解密。为了控制二进制小数精度对噪声的影响，噪声的上界被调整为8p。 3.3节中，加同态和乘同态的性质被探讨。加同态意味着对加密的消息执行加法操作，解密后可以得到原始消息的加法结果。乘同态则是对加密的消息进行乘法，解密后能得到原始消息的乘积。在这个过程中，噪声在加法中线性增长，在乘法中平方增长。因此，评估方案能力时，主要关注的是电路中的乘法深度或多项式次数。 3.4节中，定义了可评估的多项式次数，这是指加密方案能够正确处理的最大多项式次数。如果一个电路C（有t个输入）可以表示为一个多变元的多项式f(x1,...,xt)，其次数为d，为了确保解密的正确性，输出密文中的噪声不能超过8p。这要求多项式次数d满足一定的不等式，以保证在解密时噪声不会超出界限。 3.5节提到了全同态方案的安全性，依赖于部分近似最大公因子问题（PACDP），这是该加密方案的基础难题。文献中的方案通过优化公钥尺寸和计算复杂度，提高了全同态加密的效率，并在允许解密错误概率可忽略的情况下，降低了解密算法的复杂度，同时证明了方案的语义安全性。 全同态加密是一种高级的加密技术，允许在密文上直接进行各种计算，而无需先解密，这对云计算和数据隐私保护有着重要的应用价值。然而，它也面临着效率和安全性的挑战，如文中提到的部分近似最大公因子问题，这是保证全同态加密安全性的核心问题之一。通过不断的研究和优化，这些挑战正在逐步被克服，以适应更广泛的实际应用场景。