对大型加密数据应用同态运算 [英] Apply homomorphic operations on large encrypted data

问题描述

当前正在使用 PALISADE库进行同态加密.

Currently experimenting on homomorphic encryption using the PALISADE library.

我想对大型加密输入应用简单的运算，例如加法和乘法.例如，输入 A [3200] 和输入 B [4096] 都将对int值的矢量/数组进行加密.使用这两个输入 Enc(A)和 Enc(B)，我想应用乘法:

I want to apply simple he operations like additions and multiplications on large encrypted inputs. For example input A[3200] and input B[4096] both vectors/arrays of int values get encrypted. With those two inputs Enc(A) and Enc(B) I want to apply an multiplication:

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

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

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

As far as I am concerned the he implementation of the above described requirenments could be solved in two different ways:

1. 将输入打包为单个密文(类似于SIMD)，对于这些操作，我可以使用 EvalIndexAt()从加密的输入中获取正确的值.

1. Pack the inputs in a single ciphertext (SIMD like) and for the he operations I could use EvalIndexAt() to get the right value out of the encrypted input.

分别加密A和B中的每个值.

Encrypt each value from A and B separately.

我不太确定所描述的解决方案中哪种会在效率方面是最好的.第一种方法具有一个主要优点，即整个输入只需要一个加密过程，但这带来的缺点是，我总是必须使用 EvalAtIndex()方法访问正确的元素，而更大的则是输入得到的 EvalAtIndexKeyGen()的计算速度变慢.(至少在我的机器上)

I am not quite sure what of the described solutions would be the best in terms of efficiency. The first approach has this major advantage that only one encryption process for the whole input is needed but this comes with the disadvantage that I always have to access the correct element using the EvalAtIndex() method and the bigger the inputs get the slower the computation of the EvalAtIndexKeyGen() gets. (At least on my machine)

第二种方法似乎更合适，因为不需要 EvalAtIndex()，但是它带有分别加密每个值的成本，这需要花费相当长的时间.

The second approach seems the fit better because EvalAtIndex() is not needed but it comes with the cost of encrypting each value separately which takes quite some time.

有什么想法建议吗?

推荐答案

谢谢您的提问.

方法1(SIMD)的主要好处是，您可以使用单个同态加法或乘法(非常有效)对向量(4096个或更多的整数/实数)进行加法和乘法.旋转(在PALISADE中称为 EvalAtIndex )是一项额外的操作，允许一个访问单个索引或进行有效的求和(如内部乘积)，矩阵乘法等.此方法还具有较小的密文扩展系数(比4096x或更大)多于方法2.通常，在实践中首选选项#1(并且我无法想到要使用选项#2的任何实际用例).

The main benefit of approach #1 (SIMD) is that you can perform addition and multiplication of vectors (of 4096 or more integers/real numbers) using a single homomorphic addition or multiplication (very efficient). Rotation (called EvalAtIndex in PALISADE) is an extra operation that allows one access individual indices or do efficient summation (as in inner product), matrix multiplication, etc. This approach also has a much a smaller ciphertext expansion factor (by 4096x or more) than approach #2. Generally option #1 is preferred in practice (and I cannot think of any real use case where I would want to go with option #2).

为了最小化乘法的开销，也许您可​​以将向量打包在连续的块中，这样您就需要对一个块进行一次旋转.例如，

To minimize the cost of multiplication, maybe you could pack the vector in contiguous blocks so that you need a single rotation for one block. For example,

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

您可以使用的另一种技术是 EvalFastRotation (仅适用于PALISADE v1.10.x中的CKKS和BGVrns).如果您需要多次旋转相同的密文，则可以为密文预先计算一些内容，然后使用便宜的旋转方式(BV密钥切换最大的好处)-请参见

Another technique you can use is EvalFastRotation (available only for CKKS and BGVrns in PALISADE v1.10.x). If you need multiple rotations of the same ciphertext, you can precompute something for the ciphertext, and then use cheaper rotations (the most benefit is achieved for BV key switching) - see https://gitlab.com/palisade/palisade-development/-/blob/master/src/pke/examples/advanced-real-numbers.cpp for an example.

如果需要多次旋转(也仅计算所需旋转数的平方根)，也有一些方法可以最大程度地减少要生成的键的数量，例如，使用 https://eprint.iacr.org/2018/244 (这些技术可以在您基于PALISADE的应用程序.)

There are also ways to minimize the number of keys to be generated if you need multiple rotations (only compute roughly a square root of the number of rotations needed), e.g., using the baby-step-giant-step technique described in https://eprint.iacr.org/2018/244 (these techniques can be implemented in your PALISADE-based application).

如果已知用于执行乘法的模式，则也可以使用打包向量的特殊顺序(这样，您的旋转将使用单个旋转操作在向量上准备好几个块).当#个纯文本插槽(批处理大小)等于 ring尺寸/2时，CKKS和BGVrns中的旋转都是周期性的(环绕).如果矢量小于此尺寸，则始终可以克隆/根据需要多次复制小矢量，以填充环尺寸/2.

You can also use a special order of packing a vector if the pattern for performing multiplication is known (this way your rotation will prepare several blocks across the vector using a single rotation operation). Rotations are cyclical (wrap around) in both CKKS and BGVrns when the # plaintext slots (batch size) is equal to ring dimension / 2. If you have a smaller vector than that, you can always clone/replicate the small vector as many times as needed to fill ring dimension / 2.

总而言之，如果您从类似于SIMD的向量的角度考虑问题，则可以最大程度地提高效率.然后，您可以重新构造您的问题/模型，以充分利用HE提供的工具集.在某种程度上，这类似于使用矢量化指令(例如AVX)或面向矩阵的编程(例如在MATLAB中)进行编程.

In summary, the biggest efficiency improvement can be achieved if you think of your problem in terms of SIMD-like vectors. Then you can reformulate your problem / model to take full advantage of the toolset HE provides. In a way, this is similar to programming using vectorized instructions, e.g., AVX, or matrix-oriented programming (like in MATLAB).

这篇关于对大型加密数据应用同态运算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！