赞
踩
本文对bfv_basics.cpp中的注释做翻译并展示examples.cpp的运行结果。
SEAL库的安装推荐这篇博客。(不过我安装的是SEAL3.7,和4.0相比少了bgv_basics.cpp)
这篇博客有结合BFV的原理介绍源码。
这篇博客给代码加了注释很详细。
运行examples.cpp,输入1展示BFV例子:
在此示例中,我们演示了使用BFV加密方案对加密整数执行简单计算(多项式求值)。第一个任务是设置EncryptionParameters类的实例。了解不同参数的行为、它们如何影响加密方案、性能和安全级别至关重要。需要设置三个加密参数:
参数 | 说明 |
---|---|
poly_modulus_degree | 多项式模数 |
coeff_modulus_modulus | [密文]系数模数 |
plain_modulus | 明文模数;仅适用于BFV方案 |
BFV方案不能对加密数据执行任意计算。相反,每个密文都有一个特定的量,称为“不变噪声预算”,简称“噪声预算”。新加密密文中的噪声预算(初始噪声预算)由加密参数确定。同态运算以同样由加密参数确定的速率消耗噪声预算。在BFV中,对加密数据允许的两个基本操作是加法和乘法,其中加法与乘法相比,通常可以认为在噪声预算消耗方面几乎是免费的。由于噪声预算消耗在顺序乘法中合成,因此选择适当加密参数的最重要因素是用户希望对加密数据进行评估的算术电路的乘法深度。一旦密文的噪声预算达到零,它就会变得太坏而无法解密。因此,必须选择足够大的参数以支持所需的计算;否则,即使使用密钥,也不可能理解结果。
EncryptionParameters parms(scheme_type::bfv);
我们设置的第一个参数是“多项式模”的阶数。这必须是2的正幂,表示两个分圆多项式的幂次;不必理解这意味着什么。
poly_modulus_degree越大,密文大小越大,所有操作速度越慢,但加密计算越复杂。建议值为1024、2048、4096、8192、16384、32768,但也可以超出此范围。
在本例中,我们使用相对较小的多项式模(4096)。任何小于此值的值都只能进行非常有限的加密计算
size_t poly_modulus_degree = 4096;
parms.set_poly_modulus_degree(poly_modulus_degree);
接下来,我们设置[密文]“系数模数”(coeff_modum)。这个参数是一个大整数,它是不同素数的乘积,每个素数的大小可达60位。它被表示为这些素数的向量,每个由模类的一个实例表示。coeff_modum的比特长度是指其素因子的比特长度之和。
更大的coeff_模数意味着更大的噪声预算,因此加密计算能力更强。然而,系数模的总比特长度的上限由poly_modulus_degree确定,如下所示:
poly_modulus_degree | max coeff_modulus bit-length |
---|---|
1024 | 27 |
2048 | 54 |
4096 | 109 |
8192 | 218 |
16384 | 438 |
32768 | 881 |
这些数字也可以在函数seal_HE_TSTD_PARMS_128_TC中编码的native/src/seal/util/hestdparms.h中找到,也可以从函数CoeffModulus::MaxBitCount(poly_modulus_degree)中找到。
例如,如果poly_modulus_degree为4096,则系数模可以由三个36位素数(108位)组成。
Microsoft SEAL附带了用于选择coeff_modum的助手函数。对于新用户,最简单的方法是使用CoeffModulus::BFVDefault(poly_modulus_degree),它返回std::vector<Module>,由给定poly_modulus_degree的一个通常好的选择组成。
parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));
明文模可以是任何正整数,尽管这里我们将其取为2的幂。事实上,在许多情况下,人们可能希望它是一个素数;我们将在后面的示例中看到这一点。明文模数决定明文数据类型的大小和乘法中噪声预算的消耗。因此,为了获得最佳性能,必须尽量减小明文数据类型。新加密密文中的噪声预算为 ~ log2(coeff_modulus/plain_modulus) (bits),并且同态乘法中的噪声预算消耗的形式为log2(plain_modulus)+(其他项)。
明文模数特定于BFV方案,在使用CKKS方案时无法设置
parms.set_plain_modulus(1024);
现在设置了所有参数,我们就可以构造SEALContext对象了。这是一个大型的类,用于检查我们刚刚设置的参数的有效性和属性。
SEALContext context(parms);
打印我们选择的参数。
print_line(__LINE__);
cout << "Set encryption parameters and print" << endl;
print_parameters(context);
当使用参数创建SEALContext时,Microsoft SEAL将首先验证这些参数。此处选择的参数有效。
cout << "Parameter validation (success): " << context.parameter_error_message() << endl;
cout << endl;
Microsoft SEAL中的加密方案是公钥加密方案。对于不熟悉此术语的用户,公钥加密方案具有用于加密数据的单独公钥和用于解密数据的单独私钥。这样,多方可以使用相同的共享公钥加密数据,但只有数据的正确接收方才能使用私钥解密数据。
我们现在可以生成密钥和公钥了。为此,我们需要KeyGenerator类的一个实例。构造KeyGenerator会自动生成私钥。然后,我们可以使用KeyGenerator::create_public_key为其创建任意数量的公钥。
请注意,KeyGenerator::create_public_key有另一个重载,它不接受参数,并返回一个Serializable<PublicKey>对象。我们将在“6_serialization.cpp”中对此进行讨论。
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
为了能够加密,我们需要构造一个Encryptor实例。请注意,正如预期的那样,Encryptor只需要公钥。通过提供加密器私钥,也可以在私钥模式下使用Microsoft SEAL。我们将在“6_serialization.cpp”中对此进行讨论。
Encryptor encryptor(context, public_key);
使用Evaluator类对密文进行计算。在真实的用例中,Evaluator不会由持有私钥的同一方构建。
Evaluator evaluator(context);
当然,我们需要解密我们的结果以验证一切是否正常,因此我们还需要构造Decryptor的实例。请注意,Decryptor需要私钥。
Decryptor decryptor(context, secret_key);
作为一个例子,当加密的x=6时,我们计算4次多项式4x4 + 8x3 + 8x2 + 8x + 4。多项式的系数可以被视为明文输入,我们将在下面看到。计算以plain_modulus 1024为模进行。
虽然这个例子简单易懂,但没有太多实用价值。在后面的示例中,我们将演示如何更有效地计算加密整数和实数或复数。
BFV方案中的明文是次数小于多项式模的次数的多项式,以及系数整数模明文模。对于具有环理论背景的读者,明文空间是多项式商环Z_T[X]/(X^N+1),其中N是poly_modulus_degree,T是plain_modulus。
首先,我们创建一个包含常量6的明文。对于明文元素,我们使用一个构造函数,它将所需的多项式作为一个字符串,其系数表示为十六进制数。
cout << "~~~~~~ A naive way to calculate 4(x^2+1)(x+1)^2. ~~~~~~" << endl;
print_line(__LINE__);
uint64_t x = 6;
Plaintext x_plain(uint64_to_hex_string(x));
cout << "Express x = " + to_string(x) + " as a plaintext polynomial 0x" + x_plain.to_string() + "." << endl;
然后,我们对明文进行加密,生成密文。我们注意到Encryptor::encrypt函数有另一个重载,它只将明文作为输入,并返回一个Serializable<Ciphertext>对象。我们将在“6_serialization.cpp”中对此进行讨论。
print_line(__LINE__);
Ciphertext x_encrypted;
cout << "Encrypt x_plain to x_encrypted." << endl;
encryptor.encrypt(x_plain, x_encrypted);
在Microsoft SEAL中,有效的密文由两个或多个多项式组成,这些多项式的系数是系数模中素数乘积的整数。密文中多项式的数量称为“大小(size)”,由Ciphertext::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;
当使用Microsoft SEAL时,以最小化最长的顺序乘法链的方式进行计算通常是有利的。换句话说,加密计算最好以最小化计算的乘法深度的方式进行评估,因为总噪声预算消耗与乘法深度成比例。例如,对于我们的示例计算,将多项式分解为
4x4 + 8x3 + 8x2 + 8x + 4 = 4(x + 1)2(x2 + 1)
以获得简单的深度2表示。因此,我们分别计算(x+1)2和 (x2 + 1)。
首先,我们计算x2并加一个明文“1”。从打印结果中我们可以清楚地看到,乘法消耗了大量的噪声预算。用户可以改变plain_modulus参数,以查看其对噪声预算消耗率的影响。
print_line(__LINE__);
cout << "Compute x_sq_plus_one (x^2+1)." << endl;
Ciphertext x_sq_plus_one;
evaluator.square(x_encrypted, x_sq_plus_one);
Plaintext plain_one("1");
evaluator.add_plain_inplace(x_sq_plus_one, plain_one);
加密的乘法导致输出密文的大小增加。更准确地说,如果输入密文具有大小M和N,那么同态乘法之后的输出密文将具有大小M+N-1。在这种情况下,我们执行平方,并观察尺寸增长和噪声预算消耗。
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;
即使大小有所增加,只要噪声预算未达到0,解密仍照常工作。
Plaintext decrypted_result;
cout << " + decryption of x_sq_plus_one: ";
decryptor.decrypt(x_sq_plus_one, decrypted_result);
cout << "0x" << decrypted_result.to_string() << " ...... Correct." << endl;
接下来,我们计算(x+1)2。
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;
最后,我们将(x2+1),(x+1)2和4相乘。
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都由3个多项式组成,并且大密文上的同态运算比小密文上的计算消耗更多的噪声预算。在较小的密文上进行计算在计算上也显著便宜。
“重线性化”是一种操作,它将密文的大小在相乘后减小到初始大小2。因此,在下一次乘法之前重新排列一个或两个输入密文可以对噪声增长和性能产生巨大的积极影响,即使重新排列本身具有显著的计算成本。只有将大小为3的密文重新排列为大小为2的密文才是可能的,因此用户通常希望在每次乘法后重新排列,以保持密文大小为2。
重新排列需要特殊的“重新排列密钥”,可以将其视为一种公钥。使用KeyGenerator可以轻松创建重新线性化密钥。
在BFV和CKKS方案中使用了类似的重线性化,但在本例中,我们继续使用BFV。我们重复之前的计算,但这次在每次乘法后都要重新排队。
print_line(__LINE__);
cout << "Generate relinearization keys." << endl;
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
现在,我们在每次乘法后重复重新排列的计算。
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;
重新线性化明显改善了我们的噪声消耗。我们还有很多噪音预算,所以我们可以在解密时得到正确的答案。
print_line(__LINE__);
cout << "Decrypt encrypted_result (4(x^2+1)(x+1)^2)." << endl;
decryptor.decrypt(encrypted_result, decrypted_result);
cout << " + decryption of 4(x^2+1)(x+1)^2 = 0x" << decrypted_result.to_string() << " ...... Correct." << endl;
cout << endl;
对于x=6,4(x2+1)(x+1)2=7252。由于明文模数被设置为1024,因此该结果以整数模1024计算。因此,预期输出应为7252%1024==84,或十六进制的0x54。
有时,我们会创建自定义的加密参数,但结果却是无效的。Microsoft SEAL可以解释参数被视为无效的原因。这里,我们简单地减少多项式模次数,使参数不符合同态加密.org安全标准。
print_line(__LINE__);
cout << "An example of invalid parameters" << endl;
parms.set_poly_modulus_degree(2048);
context = SEALContext(parms);
print_parameters(context);
cout << "Parameter validation (failed): " << context.parameter_error_message() << endl << endl;
此信息有助于修复无效的加密参数。
总代码如下:
#include "examples.h" using namespace std; using namespace seal; void example_bfv_basics() { print_example_banner("Example: BFV Basics"); EncryptionParameters parms(scheme_type::bfv); size_t poly_modulus_degree = 4096; parms.set_poly_modulus_degree(poly_modulus_degree); parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree)); parms.set_plain_modulus(1024); 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; KeyGenerator keygen(context); SecretKey secret_key = keygen.secret_key(); PublicKey public_key; keygen.create_public_key(public_key); Encryptor encryptor(context, public_key); Evaluator evaluator(context); Decryptor decryptor(context, secret_key); print_line(__LINE__); uint64_t x = 6; Plaintext x_plain(uint64_to_hex_string(x)); cout << "Express x = " + to_string(x) + " as a plaintext polynomial 0x" + x_plain.to_string() + "." << endl; print_line(__LINE__); Ciphertext x_encrypted; cout << "Encrypt x_plain to x_encrypted." << endl; encryptor.encrypt(x_plain, x_encrypted); 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; print_line(__LINE__); cout << "Compute x_sq_plus_one (x^2+1)." << endl; Ciphertext x_sq_plus_one; evaluator.square(x_encrypted, x_sq_plus_one); Plaintext plain_one("1"); evaluator.add_plain_inplace(x_sq_plus_one, plain_one); 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; Plaintext decrypted_result; 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__); 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; 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; print_line(__LINE__); cout << "Generate relinearization keys." << endl; RelinKeys relin_keys; keygen.create_relin_keys(relin_keys); print_line(__LINE__); cout << "Generate relinearization keys." << endl; RelinKeys relin_keys; keygen.create_relin_keys(relin_keys); 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; print_line(__LINE__); cout << "Decrypt encrypted_result (4(x^2+1)(x+1)^2)." << endl; decryptor.decrypt(encrypted_result, decrypted_result); cout << " + decryption of 4(x^2+1)(x+1)^2 = 0x" << decrypted_result.to_string() << " ...... Correct." << endl; cout << endl; print_line(__LINE__); cout << "An example of invalid parameters" << endl; parms.set_poly_modulus_degree(2048); context = SEALContext(parms); print_parameters(context); cout << "Parameter validation (failed): " << context.parameter_error_message()
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。