Seal库官方示例（二）：encoders.cpp解析

补充一个常用的SIMD操作原理

图片来自的Hang Shao的文章。

完整代码
这个代码主要功能是编码明文，使得能够使用更加完整的明文多项式（前一个只用到了一个多项式的常量），也就是SIMD操作。主要包含了两个部分，一个是BGV、BFV的BatchEncoder，另一个是CKKS的CKKSEncoder。

BatchEncoder

for BFV or BGV
批处理编码，将明文多项式视为一个矩阵（假设多项式阶数为N，明文模数为T，那么这个矩阵就是一个$2\times \frac{N}{2}$的矩阵，其中每个元素都需要mod T），在矩阵视角之下，批处理可以通过一些方法来加速运算优势就是，对密文的操作相当于对所有N个明文（也就是插槽）做同样的操作，速度远超过没有使用批处理的。

首先是比较常规的参数设置，bgv和bfv一样的，直接换方案名字就行了。

EncryptionParameters parms(scheme_type::bfv);
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));
1
2
3
4

要能使用批处理，需要设置明文模数为一个 **1mod2*多项式阶数 **的一个素数，下面的代码创建了这样一个20-bits大小的素数。

parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));

SEALContext context(parms);
print_parameters(context);
cout << endl;
1
2
3
4
5

看看输出结果

验证一下批处理是否是启用状态

auto qualifiers = context.first_context_data()->qualifiers();
cout << "Batching enabled: " << boolalpha << qualifiers.using_batching << endl;
1
2

结果

接着生成加密相关的公钥，私钥，评估密钥等。

KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
1
2
3
4
5
6
7
8
9

创建批处理实例和设置批处理的插槽，插槽的数量等于多项式的模阶数N，

BatchEncoder batch_encoder(context);
size_t slot_count = batch_encoder.slot_count();
size_t row_size = slot_count / 2;
cout << "Plaintext matrix row size: " << row_size << endl;
1
2
3
4

创建明文矩阵$2\times \frac{N}{2}$，每个元素要模T

vector<uint64_t> pod_matrix(slot_count, 0ULL);
pod_matrix[0] = 0ULL;
pod_matrix[1] = 1ULL;
pod_matrix[2] = 2ULL;
pod_matrix[3] = 3ULL;
pod_matrix[row_size] = 4ULL;
pod_matrix[row_size + 1] = 5ULL;
pod_matrix[row_size + 2] = 6ULL;
pod_matrix[row_size + 3] = 7ULL;

cout << "Input plaintext matrix:" << endl;
print_matrix(pod_matrix, row_size);
1
2
3
4
5
6
7
8
9
10
11
12

这里创建的矩阵输出如下

接着是将矩阵编码为多项式

Plaintext plain_matrix;
print_line(__LINE__);
cout << "Encode plaintext matrix:" << endl;
batch_encoder.encode(pod_matrix, plain_matrix);
1
2
3
4

可以解码来看看正确性

vector<uint64_t> pod_result;
cout << "    + Decode plaintext matrix ...... Correct." << endl;
batch_encoder.decode(plain_matrix, pod_result);
print_matrix(pod_result, row_size);
1
2
3
4

结果

现在，来加密明文

Ciphertext encrypted_matrix;
print_line(__LINE__);
cout << "Encrypt plain_matrix to encrypted_matrix." << endl;
encryptor.encrypt(plain_matrix, encrypted_matrix);
cout << "    + Noise budget in encrypted_matrix: " << decryptor.invariant_noise_budget(encrypted_matrix) << " bits"
     << endl;
1
2
3
4
5
6

看看噪声预算

现在，操作密文就相当于对8192个明文槽同时进行操作！为了显示效果，首先创建第二个明文矩阵

vector<uint64_t> pod_matrix2;
for (size_t i = 0; i < slot_count; i++)
{
    pod_matrix2.push_back((i & size_t(0x1)) + 1);
}
Plaintext plain_matrix2;
batch_encoder.encode(pod_matrix2, plain_matrix2);
cout << endl;
cout << "Second input plaintext matrix:" << endl;
print_matrix(pod_matrix2, row_size);
1
2
3
4
5
6
7
8
9
10

这里执行的同态操作是第一个矩阵的密文加上第二个矩阵的明文，并且取平方

print_line(__LINE__);
cout << "Sum, square, and relinearize." << endl;
evaluator.add_plain_inplace(encrypted_matrix, plain_matrix2);
evaluator.square_inplace(encrypted_matrix);
evaluator.relinearize_inplace(encrypted_matrix, relin_keys);
1
2
3
4
5

查看一下噪声预算，看看是否能正确的解密

cout << "    + Noise budget in result: " << decryptor.invariant_noise_budget(encrypted_matrix) << " bits" << endl;
1

不为0，那么可以解密

解密，解码并输出

Plaintext plain_result;
print_line(__LINE__);
cout << "Decrypt and decode result." << endl;
decryptor.decrypt(encrypted_matrix, plain_result);
batch_encoder.decode(plain_result, pod_result);
cout << "    + Result plaintext matrix ...... Correct." << endl;
print_matrix(pod_result, row_size);
1
2
3
4
5
6
7

然后有个奇怪的点，密文加上明文的操作怎么单独写了一个函数，同态操作是密文之间的运算，那么大概这个密文加上明文就是，先把明文加密，再相加，于是写了段代码试了一下

/*
自己添加的代码
*/
cout << "+++++++++++++++" << endl;
Ciphertext encrypted_matrix1, encrypted_matrix2, ciphertext_result;
encryptor.encrypt(plain_matrix2, encrypted_matrix2);
encryptor.encrypt(plain_matrix, encrypted_matrix1);
evaluator.add(encrypted_matrix2, encrypted_matrix1, ciphertext_result);
evaluator.square_inplace(ciphertext_result);
evaluator.relinearize_inplace(ciphertext_result, relin_keys);
cout << "    + Noise budget in result: " << decryptor.invariant_noise_budget(ciphertext_result) << " bits"
     << endl;
Plaintext plain_result2;
decryptor.decrypt(ciphertext_result, plain_result2);
batch_encoder.decode(plain_result2, pod_result);
print_matrix(pod_result, row_size);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

运行截图，噪声预算是一样的，那么这个函数的实质就是先明文加密，再相加，调用能少写点代码。

当然，bfv，bgv方案里面的处理都是以整数形式，那么在代码中，整数类型的位数是比较少的，那么通过多次同态计算后就容易造成数据类型溢出。所以接下来就有了ckks的编码。

CKKSEncoder

CKKS是针对浮点数类型的近似运算，也就是会丢失一定的精度。CKKS没有明文模数哦。
首先依然是方案参数设置，至于为什么这么设置5个40bit的，ckks方案用的是模数链，每一个模数因子都接近缩放因子$\Delta$,用于rescale重缩放。

EncryptionParameters parms(scheme_type::ckks);

size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 40, 40, 40, 40, 40 }));
SEALContext context(parms);
print_parameters(context);
cout << endl;
1
2
3
4
5
6
7
8

参数结果

密钥生成（包含私钥，公钥，评估密钥）

KeyGenerator keygen(context);
auto secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
1
2
3
4
5
6

加解密器，同态计算，编码的实例化

Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
CKKSEncoder encoder(context);
1
2
3
4

ckks的编码是把复数或实数数字向量编码为明文对象

ckks的插槽数量为多项式阶数/2（它的明文空间就是${\mathbb{C}}^{N/2}$），这里就没有像BFV一样化为两行矩阵了。

size_t slot_count = encoder.slot_count();
cout << "Number of slots: " << slot_count << endl;
1
2

定义明文向量

vector<double> input{ 0.0, 1.1, 2.2, 3.3 };
cout << "Input vector: " << endl;
print_vector(input);
1
2
3

好了，现在来回顾一下CKKS算法里的编码步骤：首先从N/2维扩张到N维，接着乘以一个缩放因子（用于提高精确度，这个因子就接近与重缩放要用的模数），最后是取整并编码为多项式

设立缩放因子并编码，这里设置的为2^30，使用0填充到N维（这好像跟方案里写的不一样，方案里是取的共轭再拼接）

Plaintext plain;
double scale = pow(2.0, 30);
print_line(__LINE__);
cout << "Encode input vector." << endl;
encoder.encode(input, scale, plain);
1
2
3
4
5

可以立刻解码看看

vector<double> output;
cout << "    + Decode input vector ...... Correct." << endl;
encoder.decode(plain, output);
print_vector(output);
1
2
3
4

接着是加密

Ciphertext encrypted;
print_line(__LINE__);
cout << "Encrypt input vector, square, and relinearize." << endl;
encryptor.encrypt(plain, encrypted);
1
2
3
4

计算平方，重线性化缩小密文规模

evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
1
2

平方后，缩放因子也跟着平方，所以现在缩放因子达到了2^60

cout << "    + Scale in squared input: " << encrypted.scale() << " (" << log2(encrypted.scale()) << " bits)"
     << endl;

print_line(__LINE__);
cout << "Decrypt and decode." << endl;
decryptor.decrypt(encrypted, plain);
encoder.decode(plain, output);
cout << "    + Result vector ...... Correct." << endl;
print_vector(output);
1
2
3
4
5
6
7
8
9

当然这里演示的不是完整的ckks方案，还少了rescale过程，也就是重缩放（还原缩放因子和降低噪声），主要看看如何编码。