SEAL全同态加密开源库(十三) CKKS-源码浅析_seal ckks

2021SC@SDUSC
2021-12-26

前言

这是SEAL全同态加密开源库分析报告的第13篇，我们继续上一篇的CKKS源码分析。

代码分析

现在x3_encryption与x1_encryption处于不同的级别，这阻止我们将它们相乘来计算x³。
我们可以简单地将x1_encrypted切换到模数转换链中的下一个参数。然而，由于我们仍然需要将x³，乘以PI(plain_coeff3)，所以我们先计算PI*x，然后将它与x²相乘，得到PI *x³。最后，我们计算PI *x 并将其从2⁸⁰缩放到接近2^40的值。

    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;

1
2
3
4
5
6
7
8
9
10

因为x3_encrypted和x1_encrypted_coeff3具有相同的scale和使用相同的加密参数，所以我们可以将它们相乘。我们将结果写入x3_encrypted，relinearize和rescale。再次注意scale是接近2^40，但不完全是2的40次方due to yet another scaling by a prime。我们已经到了模切换链的最后一个level。

    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
7
8
9
10

接下来计算1次项。所有这些都需要一个带有plain_coeff1的multiply_plain。我们使用结果覆盖x1_encryption。

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;

1
2
3
4
5
6
7
8
9

继续。
现在我们希望计算所有三项的和。但是，有一个严重的问题:这三个术语所使用的加密参数是不同的，这是由于模量从rescaling而来的。
加密的加法和减法要求输入的level相同，并且加密参数(parms_id)匹配。如果不匹配，Evaluate将抛出异常。

    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;

1
2
3
4
5
6
7
8
9
10
11

让我们仔细考虑一下在这一点上的scales是多少。我们把系数中的质数表示为P_0, P_1, P_2, P_3，按这个顺序。P_3作为特殊的模量，不涉及重调scaling。经过以上规模的计算，密文的scale为:

    - 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.

1
2
3
4
5
6
7
8
9

虽然这三项的比例大约是2^40，但它们的确切值是不同的，因此不能相加。

    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
2
3
4
5
6
7
8
9
10
11

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

1
2
3
4
5

我们还有一个加密参数不匹配的问题。这是很容易修复，使用传统的模切换(没有重新缩放)。CKKS支持模切换，就像BFV方案一样，允许我们在根本不需要时切换部分系数模量。

    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);

    /*三个密文兼容，可加了
    All three ciphertexts are now compatible and can be added.
    */
    print_line(__LINE__);
    cout << "Compute PI*x^3 + 0.4*x + 1." << endl;
    Ciphertext encrypted_result;
    evaluator.add(x3_encrypted, x1_encrypted, encrypted_result);
    //计算结果存入 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);

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

虽然我们没有在这些例子中显示任何复数的计算，但是CKKSEncoder可以让我们很容易地做到这一点。复数的加法和乘法就像人们所期望的那样。

运行结果

Microsoft SEAL version: 3.7.1
+---------------------------------------------------------+
| The following examples should be executed while reading |
| comments in associated files in native/examples/.       |
+---------------------------------------------------------+
| Examples                   | Source Files               |
+----------------------------+----------------------------+
| 1. BFV Basics              | 1_bfv_basics.cpp           |
| 2. Encoders                | 2_encoders.cpp             |
| 3. Levels                  | 3_levels.cpp               |
| 4. CKKS Basics             | 4_ckks_basics.cpp          |
| 5. Rotation                | 5_rotation.cpp             |
| 6. Serialization           | 6_serialization.cpp        |
| 7. Performance Test        | 7_performance.cpp          |
+----------------------------+----------------------------+
[      0 MB] Total allocation from the memory pool

> Run example (1 ~ 7) or exit (0): 4

+--------------------------------------+
|         Example: CKKS Basics         |
+--------------------------------------+
/
| Encryption parameters :
|   scheme: CKKS
|   poly_modulus_degree: 8192
|   coeff_modulus size: 200 (60 + 40 + 40 + 60) bits
\

Number of slots: 4096
Input vector:

    [ 0.0000000, 0.0002442, 0.0004884, ..., 0.9995116, 0.9997558, 1.0000000 ]

Evaluating polynomial PI*x^3 + 0.4x + 1 ...
Line 129 --> Encode input vectors.
Line 140 --> Compute x^2 and relinearize:
    + Scale of x^2 before rescale: 80 bits
Line 152 --> Rescale x^2.
    + Scale of x^2 after rescale: 40 bits
Line 165 --> Compute and rescale PI*x.
    + Scale of PI*x before rescale: 80 bits
    + Scale of PI*x after rescale: 40 bits
Line 180 --> Compute, relinearize, and rescale (PI*x)*x^2.
    + Scale of PI*x^3 before rescale: 80 bits
    + Scale of PI*x^3 after rescale: 40 bits
Line 192 --> Compute and rescale 0.4*x.
    + Scale of 0.4*x before rescale: 80 bits
    + Scale of 0.4*x after rescale: 40 bits

Line 209 --> Parameters used by all three terms are different.
    + Modulus chain index for x3_encrypted: 0
    + Modulus chain index for x1_encrypted: 1
    + Modulus chain index for plain_coeff0: 2

Line 237 --> The exact scales of all three terms are different:
    + Exact scale in PI*x^3: 1099512659965.7514648438
    + Exact scale in  0.4*x: 1099511775231.0197753906
    + Exact scale in      1: 1099511627776.0000000000

Line 262 --> Normalize scales to 2^40.
Line 273 --> Normalize encryption parameters to the lowest level.
Line 282 --> Compute PI*x^3 + 0.4*x + 1.
Line 292 --> Decrypt and decode PI*x^3 + 0.4x + 1.
    + Expected result:

    [ 1.0000000, 1.0000977, 1.0001954, ..., 4.5367965, 4.5391940, 4.5415926 ]

    + Computed result ...... Correct.

    [ 1.0000000, 1.0000977, 1.0001954, ..., 4.5367995, 4.5391970, 4.5415957 ]

+---------------------------------------------------------+
| The following examples should be executed while reading |
| comments in associated files in native/examples/.       |
+---------------------------------------------------------+
| Examples                   | Source Files               |
+----------------------------+----------------------------+
| 1. BFV Basics              | 1_bfv_basics.cpp           |
| 2. Encoders                | 2_encoders.cpp             |
| 3. Levels                  | 3_levels.cpp               |
| 4. CKKS Basics             | 4_ckks_basics.cpp          |
| 5. Rotation                | 5_rotation.cpp             |
| 6. Serialization           | 6_serialization.cpp        |
| 7. Performance Test        | 7_performance.cpp          |
+----------------------------+----------------------------+
[     51 MB] Total allocation from the memory pool
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

结语

有关CKKS的源码分析到此为止。后面的篇幅我会分析完5_rotation和6_serialization的代码，分析完后有时间我会专门开一两篇文章来做一些理论知识详解。完成这些工作后我们的SEAL库源码分析也接近尾声了。