2021SC@SDUSC

2021-12-26

前言

前幾篇我們討論了SEAL對于BFV、CKKS的實作，本篇開始我將開始討論SEAL中encoders.cpp代碼實作，

背景

在“1 _bfv_basics，我們展示了如何使用BFV方案執行一個非常簡單的計算，計算以明文模為引數，僅利用一個BFV明文多項式的系數，這種方法有兩個值得注意的問題:

(1)實際應用中一般采用整數或實數演算法，而不是模運算;
(2)我們只使用了明文多項式的一個系數，這是非常浪費的，因為明文多項式很大，而且在任何情況下都將全部加密，

對于(1)，有人可能會問，為什么不直接增加plain_modules引數，直到沒有溢位發生，并且計算的行為就像整數算術一樣，問題是增加plain_module會增加噪聲預算消耗，同時降低初始噪聲預算，

在這些示例中，我們將討論將資料放入明文元素(編碼)的其他方法，這些方法允許進行更多的計算，而不會出現資料型別溢位，并且允許使用完整的明文多項式，

原始碼分析

void example_batch_encoder()

void example_batch_encoder()
{
    print_example_banner("Example: Encoders / Batch Encoder");

設N為poly_modulus_degree，T為plain_modulus，批處理允許BFV明文多項式被視為2×(N/2)矩陣，每個元素都是一個模T整數，在矩陣視圖中，加密操作在加密矩陣上逐個執行element-wise，允許用戶在完全向量化計算中獲得幾個數量級的速度提升，因此，除了最簡單的計算之外，批處理應該是首選的方法，使用BFV時，如果使用得當，實作的性能將超過使用IntegerEncoder完成的任何作業，

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_modules設定為一個素數，它全等于1模2*poly_modulus_degree，（這里是指要求素數滿足的條件），Microsoft SEAL提供了一種輔助方法來查找這樣的素數，在本例中，我們創建了一個支持批處理的20位素數，

parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));
SEALContext context(parms);
print_parameters(context);
cout << endl;

我們可以通過查看由SEALContext創建的加密引數限定符來驗證是否確實啟用了批處理，

    auto qualifiers = context.first_context_data()->qualifiers();
    cout << "Batching enabled: " << boolalpha << qualifiers.using_batching << endl;

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

批處理“槽slot”的總數等于poly_modulus_degree, N，這些槽被組織成2×(N/2)矩陣，可以對其進行加密和計算，每個槽都包含一個整數 modulo plain_modulus，

    size_t slot_count = batch_encoder.slot_count();
    size_t row_size = slot_count / 2;
    cout << "Plaintext matrix row size: " << row_size << endl;

矩陣明文被簡單地作為一個扁平的向量提供給BatchEncoder 的數字，第一 row_size 多的數字組成第一行，其余的組成第二行，這里我們創建以下矩陣:

        [ 0,  1,  2,  3,  0,  0, ...,  0 ]
        [ 4,  5,  6,  7,  0,  0, ...,  0 ]

    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;

    cout << "Input plaintext matrix:" << endl;
    print_matrix(pod_matrix, row_size);

首先，我們使用BatchEncoder將矩陣編碼為明文多項式，

    Plaintext plain_matrix;
    print_line(__LINE__);
    cout << "Encode plaintext matrix:" << endl;
    batch_encoder.encode(pod_matrix, plain_matrix);

我們可以立即解碼，以驗證編碼的正確性，注意，還沒有進行加密或解密，

vector<uint64_t> pod_result;
cout << "    + Decode plaintext matrix ...... Correct." << endl;
batch_encoder.decode(plain_matrix, pod_result);
print_matrix(pod_result, row_size);

接下來我們加密編碼后的明文，

    Ciphertext encrypted_matrix;
    print_line(__LINE__);
    cout << "Encrypt plain_matrix to encrypted_matrix." << endl;
    encryptor.encrypt(plain_matrix, encrypted_matrix);
    cout << "    + Noise budget in encrypted_matrix: " << decryptor.invariant_noise_budget(encrypted_matrix) << " bits"
         << endl;

對密文的操作導致在所有8192個槽(矩陣元素)中同時執行同態操作，為了說明這一點，我們構造了另一個明文矩陣：

[ 1,  2,  1,  2,  1,  2, ..., 2 ]
[ 1,  2,  1,  2,  1,  2, ..., 2 ]

并將其編碼為明文，

 vector<uint64_t> pod_matrix2;
for (size_t i = 0; i < slot_count; i++)
{
    pod_matrix2.push_back((i % 2) + 1);
}
Plaintext plain_matrix2;
batch_encoder.encode(pod_matrix2, plain_matrix2);
cout << endl;
cout << "Second input plaintext matrix:" << endl;
print_matrix(pod_matrix2, row_size);

現在，我們將第二個(明文)矩陣添加到加密矩陣中，并將其平方

 print_line(__LINE__);
cout << "Sum, square, and relinearize." << endl;
evaluator.add_plain_inplace(encrypted_matrix, plain_matrix2);
evaluator.square_inplace(encrypted_matrix);
evaluator.relinearize_inplace(encrypted_matrix, relin_keys);

輸出：我們還剩下多少噪音預算？

cout << "    + Noise budget in result: " << decryptor.invariant_noise_budget(encrypted_matrix) << " bits" << endl;

接下來，解密并分解明文以將結果恢復為矩陣，

    Plaintext plain_result;
    print_line(__LINE__);
    cout << "Decrypt and decode result." << endl;
    decryptor.decrypt(encrypted_matrix, plain_result);
    batch_encoder.decode(plain_result, pod_result);
    cout << "    + Result plaintext matrix ...... Correct." << endl;
    print_matrix(pod_result, row_size);

當所需的加密計算高度可并行化時，批處理允許我們有效地使用全明文多項式，但是，它并沒有解決這個檔案開頭提到的另一個問題:每個槽只包含一個整數模的明文模量，除非明文模量非常大，否則我們可以很快遇到資料型別溢位，并在需要整數計算時會得到意外的結果，注意，溢位并不能以加密的形式檢測到，CKKS方案(以及CKKSEncoder)解決了資料型別溢位問題，但代價是只產生近似的結果，

void example_ckks_encoder()

example_ckks_encoder演示了用于計算加密的實數或復數的Cheon-Kim-Kim-Song
(CKKS)方案，我們首先為CKKS方案創建加密引數，與BFV方案相比，有兩個重要的區別:

(1) CKKS不使用明文模數加密引數;
(2)在使用CKKS方案時，以特定的方式選擇coeff_modules是非常重要的，我們將在“ckks_basic.cpp”檔案中進一步解釋這一點，在這個例子中，我們使用CoeffModulus::Create來生成5個40位素數，

這是其有別于batch_encoder的地方，不過兩者作用大同小異，限于時間，暫時不對其展開分析了，這篇分析報告到此告一段落，