4_ckks_basics

本例中演示了一个多项式函数的求值

1
PI*x^3 + 0.4*x + 1

x是位于区间[0,1]的一组4096等距点中的一个加密浮点输入数据。这个例子演示了CKKS方案的主要特性。

首先选择方案

1
EncryptionParameters parms(scheme_type::ckks);

在2_encoders中看到CKKS的乘法导致密文规模增长。任意密文的规模都不能太接近coeff_modulus的总大小，否则存储放大的明文将耗尽空间。CKKS方案提供了一个rescale功能，用于减小scale并稳定scale扩展。

rescale是一种模切换操作(参考3_levels)。在转换模数时，会从coeff_modulus中移除最后一个素数，这将缩小密文。更精确地说，假设CKKS密文中的scale为S，当前coeff_modulus中的最后一个素数是P，rescale下一层将scale更改为S/P，并从coeff_modulus中去除P。素数的数量限制了rescale的次数，从而限制了计算的乘法深度。

自由选择初始scale是可能的。一个方法是在coeff_modulus中设置初始scale S和素数P_i非常接近。如果在乘法操作之前的scale是S，则操作后scale变为\(S^2\)，rescale后scale变为\(S^2/P_i\)。若所有\(P_i\)都接近于S，则\(S^2/P_i\)就接近于S。通过这种方法，可以在整个计算过程中使scale稳定在接近S。一般来说，对于深度为D的电路，需要rescale D次，即把D个素数从coeff_modulus中去除。一旦coeff_moudlus中只剩下一个素数，要求这个素数必须比S大几个位，以保留明文在小数点前的值。

通常选择CKKS方案的参数如下：
(1)选择一个60位素数作为coeff_modulus中的第一个素数。这提供了解密时的最高精度；
(2)选择另一个60位素数作为coeff_modulus的最后一个元素，它作为特殊素数，应该与其他素数中的最大素数相等；
(3)中间的素数应该相接近。

使用CoeffModulus::Create生成合适大小的素数。注意coeff_modulus是200位的，低于poly_modulus_degree的界限：coeff_modulus_degree::MaxBitCount(8192)返回218.

1
2
3
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 60, 40, 40, 60 }));

选择初始规模位\(2^{40}\)。在最后一层，小数点前留下60-40=20位精度，小数点后留下足够的精度(大约10-20位)。

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
double scale = pow(2.0, 40);

SEALContext context(parms);
print_parameters(context);
cout << endl;

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);
GaloisKeys gal_keys;
keygen.create_galois_keys(gal_keys);
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);

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

vector<double> input;
input.reserve(slot_count);
double curr_point = 0;
double step_size = 1.0 / (static_cast<double>(slot_count) - 1);
for (size_t i = 0; i < slot_count; i++)
{
    input.push_back(curr_point);
    curr_point += step_size;
}
cout << "Input vector: " << endl;
print_vector(input, 3, 7);

cout << "Evaluating polynomial PI*x^3 + 0.4x + 1 ..." << endl;

为PI、0.4和1创建明文，使用CKKSEncoder将给定浮点值编码为向量的每个slot

1
2
3
4
5
6
7
8
9
10
11
Plaintext plain_coeff3, plain_coeff1, plain_coeff0;
encoder.encode(3.14159265, scale, plain_coeff3);
encoder.encode(0.4, scale, plain_coeff1);
encoder.encode(1.0, scale, plain_coeff0);

Plaintext x_plain;
print_line(__LINE__);
cout << "Encode input vectors." << endl;
encoder.encode(input, scale, x_plain);
Ciphertext x1_encrypted;
encryptor.encrypt(x_plain, x1_encrypted);

为了计算\(x^3\)，首先计算\(x^2\)并执行relinearize操作，scale增长至\(2^{80}\)

1
2
3
4
5
6
Ciphertext x3_encrypted;
print_line(__LINE__);
cout << "Compute x^2 and relinearize:" << endl;
evaluator.square(x1_encrypted, x3_encrypted);
evaluator.relinearize_inplace(x3_encrypted, relin_keys);
cout << "    + Scale of x^2 before rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

执行rescale操作；除了模数切换之外，scale减少了一个因子，该因子等于被去掉的素数(40位素数)。因此新的scale应该接近\(2^{40}\)。

1
2
3
4
print_line(__LINE__);
cout << "Rescale x^2." << endl;
evaluator.rescale_to_next_inplace(x3_encrypted);
cout << "    + Scale of x^2 after rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

现在得到的x3_encrypted和x1_encrypted位于不同的level，这使得我们无法直接将其相乘来计算\(x^{3}\)。我们可以简单地将x1_encryption切换到模数转换链的下一个元素。但是由于我们还需要将\(x^{3}\)与PI(plain_coeff3)相乘，所以我们可以先将PI与x相乘(得到x1_encrypted_coeff3)，再将得到的结果与\(x^{2}\)相乘，得到\(PI*x^{3}\).

1
2
3
4
5
6
7
8
print_line(__LINE__);
cout << "Compute and rescale PI*x." << endl;
Ciphertext x1_encrypted_coeff3;
evaluator.multiply_plain(x1_encrypted, plain_coeff3, x1_encrypted_coeff3);
cout << "    + Scale of PI*x before rescale: " << log2(x1_encrypted_coeff3.scale()) << " bits" << endl;
evaluator.rescale_to_next_inplace(x1_encrypted_coeff3);
cout << "    + Scale of PI*x after rescale: " << log2(x1_encrypted_coeff3.scale()) << " bits" << endl;

因为x3_encrypted与x1_encrypted_coeff3具有相同的scale，且使用相同的加密参数，因此可以直接将其相乘。

1
2
3
4
5
6
7
print_line(__LINE__);
cout << "Compute, relinearize, and rescale (PI*x)*x^2." << endl;
evaluator.multiply_inplace(x3_encrypted, x1_encrypted_coeff3);
evaluator.relinearize_inplace(x3_encrypted, relin_keys);
cout << "    + Scale of PI*x^3 before rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;
evaluator.rescale_to_next_inplace(x3_encrypted);
cout << "    + Scale of PI*x^3 after rescale: " << log2(x3_encrypted.scale()) << " bits" << endl;

接下来计算一次项

1
2
3
4
5
6
print_line(__LINE__);
cout << "Compute and rescale 0.4*x." << endl;
evaluator.multiply_plain_inplace(x1_encrypted, plain_coeff1);
cout << "    + Scale of 0.4*x before rescale: " << log2(x1_encrypted.scale()) << " bits" << endl;
evaluator.rescale_to_next_inplace(x1_encrypted);
cout << "    + Scale of 0.4*x after rescale: " << log2(x1_encrypted.scale()) << " bits" << endl;

接下来需要求三项的和，但是问题是这三项使用的加密参数是不同的，因为模数经过了rescale转换(加密的加法和减法要求level相同且加密参数匹配，若不匹配则抛出异常)

1
2
3
4
5
6
7
8
9
10
cout << endl;
print_line(__LINE__);
cout << "Parameters used by all three terms are different." << endl;
cout << "    + Modulus chain index for x3_encrypted: "
     << context.get_context_data(x3_encrypted.parms_id())->chain_index() << endl;
cout << "    + Modulus chain index for x1_encrypted: "
     << context.get_context_data(x1_encrypted.parms_id())->chain_index() << endl;
cout << "    + Modulus chain index for plain_coeff0: "
     << context.get_context_data(plain_coeff0.parms_id())->chain_index() << endl;
cout << endl;

将系数中的素数表示为\(P_{0}、P_{1}、P_{2}、P_{3}\)，其中\(P_{3}\)作为特殊模数不涉及rescale

1
2
3
4
5
6
7
8
- Product x^2 has scale 2^80 and is at level 2;
- Product PI*x has scale 2^80 and is at level 2;
- We rescaled both down to scale 2^80/P_2 and level 1;
- Product PI*x^3 has scale (2^80/P_2)^2;
- We rescaled it down to scale (2^80/P_2)^2/P_1 and level 0;
- Product 0.4*x has scale 2^80;
- We rescaled it down to scale 2^80/P_2 and level 1;
- The contant term 1 has scale 2^40 and is at level 2.

虽然三项的scale都大约是\(2^{40}\)，但它们的确切值是不同的，因此不能相加

1
2
3
4
5
6
7
8
9
10
print_line(__LINE__);
cout << "The exact scales of all three terms are different:" << endl;
ios old_fmt(nullptr);
old_fmt.copyfmt(cout);
cout << fixed << setprecision(10);
cout << "    + Exact scale in PI*x^3: " << x3_encrypted.scale() << endl;
cout << "    + Exact scale in  0.4*x: " << x1_encrypted.scale() << endl;
cout << "    + Exact scale in      1: " << plain_coeff0.scale() << endl;
cout << endl;
cout.copyfmt(old_fmt);

解决方法：
(1)由于\(P_{1}\)和\(P_{2}\)非常接近\(2^40\)，我们可以简单"欺骗"SEAL，直接设置为相同的scale。
(2)用\(2^{80}/P_{2}\)对1进行编码，然后用0.4*x进行乘法运算，最后rescale。这种方法还需要我们确保使用适当的加密参数(parms_id)对1进行编码。

本例中使用第一种(最简单的)方法，将\(PI*x^{3}\)和0.4*x的scale设置为\(2^{40}\).

1
2
3
4
print_line(__LINE__);
cout << "Normalize scales to 2^40." << endl;
x3_encrypted.scale() = pow(2.0, 40);
x1_encrypted.scale() = pow(2.0, 40);

还有加密参数不匹配的问题。使用传统的模数切换(没有rescale)就可以解决。

1
2
3
4
5
print_line(__LINE__);
cout << "Normalize encryption parameters to the lowest level." << endl;
parms_id_type last_parms_id = x3_encrypted.parms_id();
evaluator.mod_switch_to_inplace(x1_encrypted, last_parms_id);
evaluator.mod_switch_to_inplace(plain_coeff0, last_parms_id);

现在即可将三个密文相加

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
print_line(__LINE__);
cout << "Compute PI*x^3 + 0.4*x + 1." << endl;
Ciphertext encrypted_result;
evaluator.add(x3_encrypted, x1_encrypted, encrypted_result);
evaluator.add_plain_inplace(encrypted_result, plain_coeff0);

/*
First print the true result.
*/
Plaintext plain_result;
print_line(__LINE__);
cout << "Decrypt and decode PI*x^3 + 0.4x + 1." << endl;
cout << "    + Expected result:" << endl;
vector<double> true_result;
for (size_t i = 0; i < input.size(); i++)
{
    double x = input[i];
    true_result.push_back((3.14159265 * x * x + 0.4) * x + 1);
}
print_vector(true_result, 3, 7);

/*
Decrypt, decode, and print the result.
*/
decryptor.decrypt(encrypted_result, plain_result);
vector<double> result;
encoder.decode(plain_result, result);
cout << "    + Computed result ...... Correct." << endl;
print_vector(result, 3, 7);
SEAL
SEAL FHE 密码学

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！