1

目前正在尝试使用PALISADE 库进行同态加密。

我想在大型加密输入上应用简单的运算，例如加法和乘法。例如输入A[3200]和输入B[4096]两个向量/int值数组都被加密。有了这两个输入Enc(A)，Enc(B)我想应用一个乘法：

EvalMult(Enc(A[0]), Enc(B[42])) 

*0 and 42 denoting the indexes of the corresponding inputs
** no SIMD needed

就我而言，上述要求的实现可以通过两种不同的方式解决：

  1. 将输入打包在单个密文（类似 SIMD）中，对于我可以用来EvalIndexAt()从加密输入中获取正确值的操作。

  2. 分别加密来自 A 和 B 的每个值。

我不太确定所描述的解决方案在效率方面是最好的。第一种方法的主要优点是整个输入只需要一个加密过程，但这也带来了缺点，即我总是必须使用该 EvalAtIndex()方法访问正确的元素，并且输入越大，获取的计算越慢EvalAtIndexKeyGen()。（至少在我的机器上）

第二种方法似乎更合适，因为EvalAtIndex()不需要，但它带来了单独加密每个值的成本，这需要相当长的时间。

有什么想法建议吗？

4

1 回答 1

2

感谢你的提问。

方法 #1 (SIMD) 的主要好处是您可以使用单个同态加法或乘法来执行向量（4096 或更多整数/实数）的加法和乘法（非常有效）。旋转（EvalAtIndex在 PALISADE 中调用）是一种额外的操作，它允许访问单个索引或进行有效的求和（如内积）、矩阵乘法等。这种方法的密文扩展因子（4096 倍或更多）也比方法#2。通常，选项#1 在实践中是首选（而且我想不出任何我想使用选项#2 的实际用例）。

为了最小化乘法的成本，也许您可​​以将向量打包在连续的块中，以便一个块需要单次旋转。例如，

EvalMult(Enc(A[0:5]),Enc(B[42:47))

您可以使用的另一种技术是EvalFastRotation（仅适用于 PALISADE v1.10.x 中的 CKKS 和 BGVrns）。如果您需要同一密文的多次轮换，您可以为密文预先计算一些东西，然后使用更便宜的轮换（BV 密钥切换获得最大的好处） - 请参阅https://gitlab.com/palisade/palisade-development/ -/blob/master/src/pke/examples/advanced-real-numbers.cpp为例。

如果您需要多次旋转（仅计算所需旋转次数的大致平方根），还有一些方法可以最小化要生成的键的数量，例如，使用https:/中描述的 baby-step-giant-step 技术/eprint.iacr.org/2018/244（这些技术可以在基于 PALISADE 的应用程序中实现）。

如果执行乘法的模式已知，您还可以使用打包向量的特殊顺序（这样您的旋转将使用单个旋转操作在向量上准备几个块）。当 # plaintext slot (batch size) 等于ring dimension/ 2 时，旋转在 CKKS 和 BGVrns 中都是循环的（环绕）。如果你有一个比这更小的向量，你总是可以根据需要多次克隆/复制小向量填充ring dimension/ 2。

总而言之，如果您以类似 SIMD 的向量来考虑您的问题，则可以实现最大的效率提升。然后，您可以重新制定您的问题/模型，以充分利用 HE 提供的工具集。在某种程度上，这类似于使用向量化指令进行编程，例如 AVX，或面向矩阵的编程（如在 MATLAB 中）。

于 2020-08-19T15:00:07.837 回答