同态加密和SEAL库的介绍（三）BFV - Batch Encoder

写在前面：

        在上一篇中展示了如何使用 BFV 方案执行一个非常简单的计算。该计算在 plain_modulus 参数下进行，并且仅使用了 BFV 明文多项式中的一个系数。这种方法有两个显著的问题：

1. 实际应用通常使用整数或实数运算，而不是模运算；
2. 仅使用了明文多项式的一个系数。这实际上是非常浪费的，因为明文多项式很大，而且无论如何都会被整体加密。

        如果直接增加 plain_modulus 参数，直到没有溢出发生，就能让计算表现得像整数运算。但是问题在于增加 plain_modulus 会增加噪声预算的消耗，并且还会减少初始噪声预算。接下来介绍其他将数据布局到明文元素（编码）的方法，这些方法可以允许更多的计算而不会发生数据类型溢出，并且可以充分利用整个明文多项式。

一、批处理介绍

[BatchEncoder] （适用于 BFV 或 BGV 方案）

        令 N 表示 poly_modulus_degree，T 表示 plain_modulus。批处理允许将 BFV 明文多项式视为  矩阵，每个元素是模 T 的整数。在矩阵视图中，加密操作对加密矩阵进行逐元素操作，使用户能够在完全可向量化的计算中获得数个数量级的速度提升。
        因此，除了最简单的计算，批处理应是与 BFV 一起使用的首选方法，并且如果使用得当，其实现将比不使用批处理的任何实现都要出色。
        此外，批处理对于 BGV 方案的工作方式与此示例中的 BFV 方案类似。例如，只需将`scheme_type::bfv` 更改为 `scheme_type::bgv`  即可使此示例适用于 BGV 方案。

1.1 参数设置

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

        要启用批处理，我们需要将 plain_modulus 设置为一个与 2*poly_modulus_degree 同余于 1 的素数。这个需要特别注意，因为这与普通的Encode不同，并且设置不正确的话 BatchEncoder会校验，设置为满足   的素数即可。
        同时，Microsoft SEAL 提供了一个辅助方法来找到这样的素数。在这个示例中，我们创建了一个支持批处理的 20 位素数。

parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));

        然后就可以用参数创建环境，并且可以通过查看 SEALContext 创建的加密参数限定符来验证批处理是否确实启用了。

SEALContext context(parms);
print_parameters(context);
auto qualifiers = context.first_context_data()->qualifiers();
cout << "批处理已启用：" << boolalpha << qualifiers.using_batching << endl;

        这里输出为：

1.2 创建其他实例

        这里与上篇相同，创建加解密需要的实例：

KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);

        但是注意，编码器与之前不同，批处理通过 BatchEncoder 类的实例进行。：

BatchEncoder batch_encoder(context);

二、批处理运算

        这里需要格外注意槽的概念，批处理 `槽` 的总数等于 poly_modulus_degree，N，这些槽被组织成  矩阵，可以对其进行加密和计算。每个槽包含一个模 plain_modulus 的整数。
        即这里每一个明文或者密文块，可以用的槽数量就是 N，但是内部不是一整个连续存储。逻辑上可以认为是两行的一个矩阵，但是物理上其实是类似于单链表的一种存储形式。
        这里可以查看可用的槽数量，当然为了清晰一行有多少个，可以定义一个 row_size：

size_t slot_count = batch_encoder.slot_count();
size_t row_size = slot_count / 2;

 为了帮助大家理解存储的逻辑形式，这里放几个数字并打印：

vector<uint64_t> pod_matrix(slot_count, 0ULL);
pod_matrix[0] = 0ULL;
pod_matrix[1] = 1ULL;
pod_matrix[2] = 2ULL;
pod_matrix[3] = 3ULL;
pod_matrix[row_size] = 4ULL;
pod_matrix[row_size + 1] = 5ULL;
pod_matrix[row_size + 2] = 6ULL;
pod_matrix[row_size + 3] = 7ULL;

2.1 输入的编码与加密

        使用 BatchEncoder 将矩阵编码成一个明文多项式，并加密：（注意上面是根据 solt_count 创建的输入容器，编码完成后是一个 Plaintext 块，加密完是 Ciphertext 块）

Plaintext plain_matrix;
batch_encoder.encode(pod_matrix, plain_matrix);
Ciphertext encrypted_matrix;
encryptor.encrypt(plain_matrix, encrypted_matrix);
cout <<decryptor.invariant_noise_budget(encrypted_matrix) << " bits";

在示例中这里加密完后立刻解密进行验证，并输出噪声预算：

        对密文的操作会同时在所有 8192 个槽（矩阵元素）上同态执行。为了演示计算，这里编码一个明文矩阵：

vector<uint64_t> pod_matrix2;
for (size_t i = 0; i < slot_count; i++)
{pod_matrix2.push_back((i & size_t(0x1)) + 1);
}
Plaintext plain_matrix2;
batch_encoder.encode(pod_matrix2, plain_matrix2);

2.2 运算

这里展示的运算是：将第二个（明文）矩阵加到加密矩阵上，并对和进行平方。

evaluator.add_plain_inplace(encrypted_matrix, plain_matrix2);
evaluator.square_inplace(encrypted_matrix);
evaluator.relinearize_inplace(encrypted_matrix, relin_keys);

输出噪声，并对结果进行解密解码并打印：

cout <<decryptor.invariant_noise_budget(encrypted_matrix) << " bits";
decryptor.decrypt(encrypted_matrix, plain_result);
batch_encoder.decode(plain_result, pod_result);

        从结果可以看出来，两个向量用 Batch Encoder 编码后进行的运算，是对应位置进行的加法和点乘！

三、总结

        当所需的加密计算高度并行化时，批处理允许我们高效地使用整个明文多项式。但是，它尚未解决在文件开头提到的另一个问题：每个槽只包含一个模 plain_modulus 的整数，除非plain_modulus 非常大，否则我们可能会很快遇到数据类型溢出并在需要进行整数计算时得到意外的结果。请注意，溢出无法在加密形式中检测到。
        CKKS 方案（及其编码器 CKKSEncoder）解决了数据类型溢出问题，但代价是只能得到近似结果（下篇预告）。