SEAL学习笔记（一）

SEAL(Simple Encrypted Arithmetic Library)是微软开源的基于C++的同态加密库，支持BFV、CKKS等多种同态加密算法，近期摆烂摆够了ORZ，想学一学。项目地址：SEAL: An easy-to-use and powerful homomorphic encryption library

BFV 同态加密基础

一、准备工作

1.设置参数

• poly_modulus_degree:多项式模度，为2的幂次，值越大计算越慢，但可支持更复杂的加密运算。推荐值：1024, 2048, 4096, 8192, 16384, 32768。

• coefficient modulus：（密文）系数模量，大整数，素数之积。其长度为其素因子长度之和。值越大，噪声预算越大，加密计算能力越强，但其上限由poly_modulus_degree决定，关系如下：

  +----------------------------------------------------+
  
  | poly_modulus_degree | max coeff_modulus bit-length |
  
  +---------------------+------------------------------+
  
  | 1024         | 27              |
  
  | 2048         | 54              |
  
  | 4096         | 109              | 36+36+37
  
  | 8192         | 218              |
  
  | 16384        | 438              |
  
  | 32768        | 881              |
  
  +---------------------+------------------------------+
  

  初学者可使用CoeffModulus::BFVDefault(poly_modulus_degree)来确定它的值，它会返回std::vector<Modulus>包含推荐的取值。

parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));

• plaintext modulus: 取值任意，这里取了2的模数。它决定了明文数据的规模以及乘法计算所消耗的噪声预算。因此，可以尽量取小值来保证效率。

  一个新加密的密文的噪声预算为：

  一次同态乘法所消耗的噪声预算为：

  plaintext modulus为BFV独有，CKKS无法设置

2.创建 SEALcontext

SEALContext context(parms)

SEALcontext 对设置的参数进行验证

3.KeyGenerator class生成公私钥

    KeyGenerator keygen(context);
    SecretKey secret_key = keygen.secret_key();
    PublicKey public_key;
    keygen.create_public_key(public_key);

4.生成加密器encryptor、执行器evaluator和解密器decryptor

Encryptor只需公钥

Encryptor encryptor(context, public_key);

Computations on the ciphertexts are performed with the Evaluator class。密文计算由执行器执行，实际使用中，执行器不会由持有私钥的同一方创建

Evaluator evaluator(context);

解密器需要私钥

Decryptor decryptor(context, secret_key);

BFV的明文空间为多项式环， 所以明文多项式最高次数比N小1，N为poly_modulus_degree（多项式模度）

二、计算示例

明文元素我们使用一个构造函数，它将所需的多项式作为一个字符串，其系数表示为十六进制数。

uint64_t x = 6;   
Plaintext x_plain(uint64_to_hex_string(x));
# Express x = 6 as a plaintext polynomial 0x6.

#加密未输入公钥
Ciphertext x_encrypted;
encryptor.encrypt(x_plain, x_encrypted);

密文包含两个或者更多的多项式（系数模coefficient modulus），其数目称为”size“ ，可通过Ciphertext::size()函数获得。一个新加密的密文size=2。

cout << "    + size of freshly encrypted x: " << x_encrypted.size() << endl;

cout << "    + noise budget in freshly encrypted x: " << decryptor.invariant_noise_budget(x_encrypted) << " bits"
         << endl;

解密 并输出：

Plaintext x_decrypted;
    cout << "    + decryption of x_encrypted: ";
    decryptor.decrypt(x_encrypted, x_decrypted);
    cout << "0x" << x_decrypted.to_string() << " ...... Correct." << endl;

三、同态乘法的特性和基本函数

• 最小化最长的连续乘法链，噪声消耗与乘法深度成正比，所以要尽可能减小加密乘法深度。例如，将左式转化为右式计算更高效：

左式最大乘法深度为4，右式为2

• 一次同态乘法所消耗的噪声预算为：

• 代码：计算：

  evaluator.square(x_encrypted, x_sq_plus_one);

  evaluator.add_plain_inplace(x_sq_plus_one, plain_one);

Ciphertext x_sq_plus_one;
evaluator.square(x_encrypted, x_sq_plus_one);#结果保存在x_sq_plus_one
Plaintext plain_one("1");
evaluator.add_plain_inplace(x_sq_plus_one, plain_one);

• size为M、N的两密文相乘，结果size为M+N-1

• 输出损耗

  x_sq_plus_one.size() 3

  decryptor.invariant_noise_budget(x_sq_plus_one) 55-22=33bit

  cout << "    + size of x_sq_plus_one: " << x_sq_plus_one.size() << endl;
      cout << "    + noise budget in x_sq_plus_one: " << decryptor.invariant_noise_budget(x_sq_plus_one) << " bits"
           << endl;
  

• 计算

  Ciphertext x_plus_one_sq;
  evaluator.add_plain(x_encrypted, plain_one, x_plus_one_sq);
  evaluator.square_inplace(x_plus_one_sq); #加了inplace不需新变量保存结果，而是新结果对原变量inplace，即保存在函数第一个参数当中，否则保存在最后一个变量里
  

  加了inplace：不需新变量保存结果，而是新结果对原变量inplace，即保存在函数第一个参数当中；

  不加inplace: 函数最后额外需要输入一个变量，结果保存在最后一个参数里

• 计算

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

四、Relinearization

• 相乘之后size变M+N-1，需要更多噪声预算

• Relinearization：每次同态乘法之后，将密文结果size减小到初始值2，但会带来额外的计算开销。BFV和CKKS皆采用。

• 需要relinearization keys,可以用KeyGenerator生成

• 代码步骤

  • 生成keys ：keygen.create_relin_keys(relin_keys)
  • 重线性化：evaluator.relinearize_inplace(x_squared, relin_keys)

• 完整代码(计算)

  Ciphertext x_squared;
  evaluator.square(x_encrypted, x_squared);
  evaluator.relinearize_inplace(x_squared, relin_keys);
  
  evaluator.add_plain(x_squared, plain_one, x_sq_plus_one);
  
  decryptor.decrypt(x_sq_plus_one, decrypted_result);