1_bfv_basics

BFV源码分析

1.设置EncryptionParameters类实例

1
2
3
4
5
6
7
8
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));

parms.set_plain_modulus(2048);
  • poly_modulus_degree(多项式模数)：2的正幂，表示分圆多项式的degree。值越大则密文大小越大，导致所有操作更慢但能够实现更加复杂的加密计算，推荐值为1024/2048/4096/8192/16384/32768或更大
  • coeff_modulus([密文]系数模数)：不同质数的乘积，每个质数最多60位。其位长是指其质因数位长之和，值越大噪声预算越大，意味着更强的加密计算能力，总位长受到poly_modulus_degree限制
1
2
3
4
5
6
7
8
9
10
+---------------------+---------------------------- ---+
| poly_modulus_degree | 最大 coeff_modulus 位长 |
+---------------------+---------------------------- ---+
| 1024  |  27 |
| 2048  |  54 |
| 4096  | 109 |
| 8192  | 218 |
| 16384 | 438 |
| 32768 | 881 |
+---------------------+---------------------------- ---+
  • plain_modulus(明文模数，仅适用于BFV方案)：可以是任意正整数。它决定了明文数据类型的大小和乘法中噪声预算的消耗，因此必须尽量保持明文数据类型尽可能小。

新加密密文的噪声预算：~\(log_{2}(coeff\_modulus/plain\_modulus)\)(位)
同态乘法的噪声预算消耗为\(log_{2}(plain\_modulus)+(other\ terms)\).

2. 构造SEALContext对象

1
2
3
4
5
6
7
8
9
10
SEALContext context(parms);

print_line(__LINE__);
cout << "Set encryption parameters and print" << endl;
print_parameters(context);

cout << "Parameter validation (success): " << context.parameter_error_message() << endl;

cout << endl;
cout << "~~~~~~ A naive way to calculate 4(x^2+1)(x+1)^2. ~~~~~~" << endl;

3. 设置KeyGenerator类实例

用于生成公私钥对 

1
2
3
4
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);

4. 设置Encryptor/Evaluator/Decryptor类实例

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

5.示例

对于加密的x=6，计算\(4x^{4}+8x^{3}+8x^{2}+8x+4\)

首先创建一个包含常数6的明文。对于明文元素，使用构造函数将所需的多项式作为一个字符串，其系数表示为十六进制数

1
2
3
4
5
print_line(__LINE__);
int x = 6;
Plaintext x_plain(to_string(x));
cout << "Express x = " + to_string(x) +
    " as a plaintext polynomial 0x" + x_plain.to_string() + "." << endl;

然后对明文进行加密，生成密文

1
2
3
4
print_line(__LINE__);
Ciphertext x_encrypted;
cout << "Encrypt x_plain to x_encrypted." << endl;
encryptor.encrypt(x_plain, x_encrypted);

在SEAL中，一个有效的密文由两个或多个多项式组成，它们的系数是整数mod(在coeff_modulus中素数的乘积)。密文中多项式的个数称为它的"size"，由Ciphertext::size()给出。新加密的密文size总是2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cout << "    + size of freshly encrypted x: " << x_encrypted.size() << endl;

/*
There is plenty of noise budget left in this freshly encrypted ciphertext.
*/
cout << "    + noise budget in freshly encrypted x: "
    << decryptor.invariant_noise_budget(x_encrypted) << " bits" << endl;

/*
We decrypt the ciphertext and print the resulting plaintext in order to
demonstrate correctness of the encryption.
*/
Plaintext x_decrypted;
cout << "    + decryption of x_encrypted: ";
decryptor.decrypt(x_encrypted, x_decrypted);
cout << "0x" << x_decrypted.to_string() << " ...... Correct." << endl;

当使用SEAL时，以最小化最长的顺序乘法链的方式进行计算通常是有利的。换句话说，加密计算最好以最小化计算乘法深度的方式进行评估，因为总噪声预算消耗与乘法深度成正比。例如，在计算给定多项式时，因式分解多项式是有利的：

\(4x^{4}+8x^{3}+8x^{2}+8x+4=4(x+1)^{2}*(x^{2}+1)\)

因此我们可以分别计算\(x^{2}+1\)和\((x+1)^{2}\)，再将其相乘，最后乘上一个明文'4'.

首先计算\(x^{2}\)，并加上一个明文'1'.

1
2
3
4
5
6
7
8
print_line(__LINE__);
cout << "Compute x_sq_plus_one (x^2+1)." << endl;
Ciphertext x_sq_plus_one;  //把密文记作x_sq_plus_one
evaluator.square(x_encrypted, x_sq_plus_one); 
 //先利用内置函数square ,平方x_encrypted,刷新入x_sq_plus_one
Plaintext plain_one("1");  //添加明文 1
evaluator.add_plain_inplace(x_sq_plus_one, plain_one);
//利用内置函数密文加

再计算\((x+1)^{2}\)

1
2
3
4
5
6
7
8
9
10
11
print_line(__LINE__);
cout << "Compute x_plus_one_sq ((x+1)^2)." << endl;
Ciphertext x_plus_one_sq;
evaluator.add_plain(x_encrypted, plain_one, x_plus_one_sq);
evaluator.square_inplace(x_plus_one_sq);
cout << "    + size of x_plus_one_sq: " << x_plus_one_sq.size() << endl;
cout << "    + noise budget in x_plus_one_sq: " << decryptor.invariant_noise_budget(x_plus_one_sq) << " bits"
     << endl;
cout << "    + decryption of x_plus_one_sq: ";
decryptor.decrypt(x_plus_one_sq, decrypted_result);
cout << "0x" << decrypted_result.to_string() << " ...... Correct." << endl;

最后计算\(4(x+1)^{2}*(x^{2}+1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
print_line(__LINE__);
cout << "Compute encrypted_result (4(x^2+1)(x+1)^2)." << endl;
Ciphertext encrypted_result;
Plaintext plain_four("4");
evaluator.multiply_plain_inplace(x_sq_plus_one, plain_four);
evaluator.multiply(x_sq_plus_one, x_plus_one_sq, encrypted_result);
cout << "    + size of encrypted_result: " << encrypted_result.size() << endl;
cout << "    + noise budget in encrypted_result: " << decryptor.invariant_noise_budget(encrypted_result) << " bits"
     << endl;
cout << "NOTE: Decryption can be incorrect if noise budget is zero." << endl;

cout << endl;
cout << "~~~~~~ A better way to calculate 4(x^2+1)(x+1)^2. ~~~~~~" << endl;

当噪声预算达到0，则意味着不能期望解密给出正确的结果。在上述计算方法中，由于密文x_sq_plus_one和x_plus_one_sq都由三个多项式组成(这是由平方运算造成的)，对大密文的同态运算比小密文的计算消耗更多的噪声预算。

"Relinearization"是一种将密文的size刷新为初始size(2)的一种操作。因此，在下一次乘法之前对密文进行重新线性化操作，可以降低噪声增长，优化性能。"Relinearization"需要特殊的"Relinearization密钥"，可以将其视为一种公钥，使用KeyGenerator生成。在BFV和CKKS方案中都有类似用到。

1
2
3
4
5
//生成Relinearation密钥
print_line(__LINE__);
cout << "Generate relinearization keys." << endl;
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
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
print_line(__LINE__);
cout << "Compute and relinearize x_squared (x^2)," << endl;
cout << string(13, ' ') << "then compute x_sq_plus_one (x^2+1)" << endl;
Ciphertext x_squared;
evaluator.square(x_encrypted, x_squared);
cout << "    + size of x_squared: " << x_squared.size() << endl;
evaluator.relinearize_inplace(x_squared, relin_keys);
cout << "    + size of x_squared (after relinearization): " << x_squared.size() << endl;
evaluator.add_plain(x_squared, plain_one, x_sq_plus_one);
cout << "    + noise budget in x_sq_plus_one: " << decryptor.invariant_noise_budget(x_sq_plus_one) << " bits"
     << endl;
cout << "    + decryption of x_sq_plus_one: ";
decryptor.decrypt(x_sq_plus_one, decrypted_result);
cout << "0x" << decrypted_result.to_string() << " ...... Correct." << endl;

print_line(__LINE__);
Ciphertext x_plus_one;
cout << "Compute x_plus_one (x+1)," << endl;
cout << string(13, ' ') << "then compute and relinearize x_plus_one_sq ((x+1)^2)." << endl;
evaluator.add_plain(x_encrypted, plain_one, x_plus_one);
evaluator.square(x_plus_one, x_plus_one_sq);
cout << "    + size of x_plus_one_sq: " << x_plus_one_sq.size() << endl;
evaluator.relinearize_inplace(x_plus_one_sq, relin_keys);
cout << "    + noise budget in x_plus_one_sq: " << decryptor.invariant_noise_budget(x_plus_one_sq) << " bits"
     << endl;
cout << "    + decryption of x_plus_one_sq: ";
decryptor.decrypt(x_plus_one_sq, decrypted_result);
cout << "0x" << decrypted_result.to_string() << " ...... Correct." << endl;

print_line(__LINE__);
cout << "Compute and relinearize encrypted_result (4(x^2+1)(x+1)^2)." << endl;
evaluator.multiply_plain_inplace(x_sq_plus_one, plain_four);
evaluator.multiply(x_sq_plus_one, x_plus_one_sq, encrypted_result);
cout << "    + size of encrypted_result: " << encrypted_result.size() << endl;
evaluator.relinearize_inplace(encrypted_result, relin_keys);
cout << "    + size of encrypted_result (after relinearization): " << encrypted_result.size() << endl;
cout << "    + noise budget in encrypted_result: " << decryptor.invariant_noise_budget(encrypted_result) << " bits"
     << endl;

cout << endl;
cout << "NOTE: Notice the increase in remaining noise budget." << endl;

主流FHE方案比较

1.FHEW/TFHE/GSW

  • 快速比较
  • 支持任意布尔电路
  • 快速bootstrapping(噪声刷新过程，减少因密文计算而产生的噪声，降低失败的可能性)

2.BGV/BFV

  • 在整数向量上进行高效的SIMD计算(使用批处理)
  • 快速高精度整数算术
  • 快速向量的标量乘法
  • Leveled design(通常不使用bootstrapping)

3.CKKS

  • 快速多项式近似计算
  • 相对快速的倒数和离散傅里叶变换
  • 深度近似计算，如逻辑回归学习
  • 在实数向量上进行高效的SIMD计算(使用批处理)
  • Leveled design(通常不使用bootstrapping)

参考：

https://blog.csdn.net/ldxcsdn/category_11390861.html

SEAL
SEAL FHE 密码学

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