同态加密之SEAL（一）

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的模数。它决定了明文数据的规模以及乘法计算所消耗的噪声预算。因此，可以尽量取小值来保证效率。

一个新加密的密文的噪声预算为： $log_2(\frac{coeff\_modulus}{plain\_modulus})\ bits$

一次同态乘法所消耗的噪声预算为： $log_2(plain\_moduls)\ +\ 其他项$

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的明文空间为多项式环 $Z_{T_{[X]}/(X^N+1)}$ ，所以明文多项式最高次数比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;

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

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

$4x^4 + 8x^3 + 8x^2 + 8x + 4 = 4(x + 1)^2 * (x^2 + 1)$

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

一次同态乘法所消耗的噪声预算为： $log_2(plain\_moduls)\ +\ 其他项$
代码：计算 $x^2 + 1$ ：

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;

计算 $( x + 1)^2$

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: 函数最后额外需要输入一个变量，结果保存在最后一个参数里

计算 $(x^2 + 1) * (x + 1)^2 * 4$

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)

完整代码(计算 $x^2 + 1$ )

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