RLWE同态加密编码打包——系数打包

RLWE同态加密的明文域

RLWE的加密方案，如BGV、BFV，加密的对象，实际上是分圆多项式环上的一个整系数多项式。而我们在平时接触到的需要加密的数据，如图像或者工资，通常是一个数。所以，在使用RLWE同态加密时，需要将数转化为多项式，这就是同态加密的明文编码，或者叫做明文的打包。

打包并不是说将数直接映射到多项式就可以了，我们需要保持打包的同态性质，这样才能使得同态运算的结果保持真正的同态性质。本文主要介绍更适用于加密同态加密的打包方法，系数打包。也就是将剩余环${\mathbb{Z}}_T$中的元素映射到多项式环${\mathbb{Z}}_T[x]/(x^N+1)$上。

单系数打包

最朴素的思想就是，一个数对应于一个多项式。设需要加密的数为$a$, 则，我们可以用$a$构造一个多项式，使得打包是加法同态的。

1. 将$a$作为多项式的一个系数，其他的系数随机生成。
2. 将$a$切分到多个系数，剩余的系数使用随机数。

方法1

固定位置$i$，构造的明文多项式的第$i$个系数等于需要打包的明文$a$。

则$$P=p_0+p_{1}x+p_2{x}^2+\cdots +p_i{x}^i+\cdots +p_{N-1}{x}^{N-1}$$,其中$p_i=a$.

接下来我们证明这种打包是加法同态的。
假设明文$b$打包成的明文多项式为$$Q=q_0+q_{1}x+q_2{x}^2+\cdots +q_i{x}^i+\cdots +p_{N-1}{x}^{N-1}$$,其中$q_i=b$.
那么$$S=P+Q=\sum _{j=0}^{N-1}(p_j+q_j\mathrm{mod}T)x^j$$
加法并不会导致多项式的次数增加，所以$S$的次数为$N-1$.
所以$S$的第$i$个系数$s_i\equiv a+b\mathrm{mod}T$.
也就是打包是加法同态的。

方法2

将$a$切分成随机的$k$份，然后将这$k$份作为明文多项式的其中一部分系数。
$a=a_0+a_1+\cdots +a_{k-1}\mathrm{mod}T$.
则$$P=a_0+a_{1}x+\cdots +a_{k-1}{x}^{k-1}+p_k{x}^k+p_{k+1}{x}^{k+1}+\cdots +p_{N-1}{x}^{N-1}$$.
同样由于加法不会导致多项式次数增加，从而模$x^N+1$，所以这样的打包是加法同态的。

相比于方法1，这样打包可以使得当$T$较小的时候，需要加密的数很大，而且需要的加法次数比较多的时候，能避免溢出，从而保持正确的结果。

SIMD系数打包

SIMD是单指令多数据（Single Instruction Multiple Data）的缩写。对应于打包，也就是将$d$个数映射为一个多项式，$d$叫做打包的批次大小。SIMD系数打包是单系数打包的一般性推广，也就是单系数打包是打包批次为1时的SIMD打包。

设要加密的数据为$A=(a_0,a_1,a_2,\cdots ,a_{d-1})$，则$$P=a_0+a_{1}x+a_2{x}^2+\cdots +a_{d-1}{x}^{d-1}+p_d{x}^d+p_{d+1}{x}^{d+1}+\cdots +p_{N-1}{x}^{N-1}$$
这样的打包方式，显然是加法同态的。

代码示例

在OpenFHE中实现了SIMD的系数打包，但是其效率并不是很高。
下面是一个怎么使用系数打包的例子。

/*
OpenFHE test code by zyf.
coefficient packing example of bgv.
*/
#include
#include"openfhe.h"
//The functions or classes of OpenFHE are in the namespace lbcrypto
using namespace lbcrypto;
using namespace std;

int main(){
    // set the parameters of bgv
    CCParams<CryptoContextBGVRNS> parameters;
    //plaintext modulus
    parameters.SetPlaintextModulus(536903681);
    //set the multiplication depth
    parameters.SetMultiplicativeDepth(4);
    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);
    //enable the functions of scheme.
    cryptoContext->Enable(PKE);
    cryptoContext->Enable(LEVELEDSHE);
    //cryptoContext->Enable(ADVANCEDSHE);
    KeyPair<DCRTPoly> keyPair;
    //generate key
    keyPair = cryptoContext->KeyGen();
    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
    //cout<<"ring dimension "<GetCryptoParameters()->GetElementParams()->GetRingDimension()<
    //original data
    vector<int64_t> v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    vector<int64_t> v2 = {-1, -2, -3, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    //pack the original data to plaintext polynomial
    Plaintext p1,p2;
    p1=cryptoContext->MakeCoefPackedPlaintext(v1);
    p2=cryptoContext->MakeCoefPackedPlaintext(v2);
    //encryption
    auto c1 = cryptoContext->Encrypt(keyPair.publicKey, p1);
    auto c2 = cryptoContext->Encrypt(keyPair.publicKey, p2);
    auto sum=c1+c2;
    //decryption
    Plaintext ans_sum;
    cryptoContext->Decrypt(keyPair.secretKey,sum,&ans_sum);
    cout<<ans_sum<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43