这代码主要讲的是modulus switching这个东西,简单来说功能就是用来缩减密文噪声的。这个应该是BGV方案里的,但是官方给的例子却是BFV的,BFV里面没有这个过程,它是把模切换内嵌到了乘法运算里面。代码的最后最后面说了BFV可以不用设置模数链,那么它自带的乘法相关运算应该是自带了模切换。(个人感觉这篇代码应该用BGV来举例更好,BFV效果不明显,代码后面也说了。。。应该是和SEAL库最初是没有BGV代码有关,它是后面添加的)
当SEALContext被创建的时候,SEAL库将会自动生成一条模交换链,模交换链中的参数和原始参数是一样的,区别在于模数会减小,每一层将会去掉模数链的最后一个模数,直到模数链不可用。每个模数链中的参数集都有自己的唯一索引,可以随时获取,索引值越大,代表它越位于链的前面。
首先是参数设置
EncryptionParameters parms(scheme_type::bfv);
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 50, 30, 30, 50, 50 }));
parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 20));//only for bfv
SEALContext context(parms);
print_parameters(context);
cout << endl;
模数链的顺序很重要,最后一个素数被称为special prime,因为所有的密钥对象都是在这个最高level创建的,而所有数据对象只能在低level。一个非严格的要求就是,special prime应该与coeff_modules中其他质数中最大的一样大。(咱也不知道为啥)
参数输出结果
获取模交换链数据信息的方法
SEALContext::key_context_data(): access to key level ContextData
SEALContext::first_context_data(): access to highest data level ContextData
SEALContext::last_context_data(): access to lowest level ContextData
打印模交换链数据信息,共5层(4-0)
第一段key level
print_line(__LINE__);
cout << "Print the modulus switching chain." << endl;
auto context_data = context.key_context_data();
cout << "----> Level (chain index): " << context_data->chain_index();
cout << " ...... key_context_data()" << endl;
cout << " parms_id: " << context_data->parms_id() << endl;
cout << " coeff_modulus primes: ";
cout << hex;
for (const auto &prime : context_data->parms().coeff_modulus())
{
cout << prime.value() << " ";
}
cout << dec << endl;
cout << "\\" << endl;
cout << " \\-->";
长这样,主要是参数集的ID和模数
剩下的data level
context_data = context.first_context_data();
while (context_data)
{
cout << " Level (chain index): " << context_data->chain_index();
if (context_data->parms_id() == context.first_parms_id())
{
cout << " ...... first_context_data()" << endl;
}
else if (context_data->parms_id() == context.last_parms_id())
{
cout << " ...... last_context_data()" << endl;
}
else
{
cout << endl;
}
cout << " parms_id: " << context_data->parms_id() << endl;
cout << " coeff_modulus primes: ";
cout << hex;
for (const auto &prime : context_data->parms().coeff_modulus())
{
cout << prime.value() << " ";
}
cout << dec << endl;
cout << "\\" << endl;
cout << " \\-->";
/*
Step forward in the chain.
*/
context_data = context_data->next_context_data();
}
长这样,可以看到模数链在逐层变小,每次去掉最末尾的一个模数。
在创建密钥的时候会调用到key level的参数,下面的代码,创建了密钥并看看是否调用的那些参数
KeyGenerator keygen(context);
auto secret_key = keygen.secret_key();
PublicKey public_key;
keygen.create_public_key(public_key);
RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);
print_line(__LINE__);
cout << "Print the parameter IDs of generated elements." << endl;
cout << " + public_key: " << public_key.parms_id() << endl;
cout << " + secret_key: " << secret_key.parms_id() << endl;
cout << " + relin_keys: " << relin_keys.parms_id() << endl;
对比前面的key level的参数集id,是一样的,说明确实调用了。
BFV的明文没有调用参数集,但是密文调用了
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
Plaintext plain("1x^3 + 2x^2 + 3x^1 + 4");
Ciphertext encrypted;
encryptor.encrypt(plain, encrypted);
cout << " + plain: " << plain.parms_id() << " (not set in BFV)" << endl;
cout << " + encrypted: " << encrypted.parms_id() << endl << endl;
模交换功能就是减小同态运算带来的噪声,其操作是密文运算中将自己所用的参数集切换到下一个level的参数,以进行下一层的计算,这个功能不可逆,也就是不能向上切换,只能向下切换。因为,每一层都少了一个模数,假定上一个是
Q
Q
Q,下一层是
Q
′
Q'
Q′,那么模切换的操作实质就是密文乘以了
Q
′
/
Q
Q'/Q
Q′/Q也就是
1
/
q
i
1/q_i
1/qi,对应噪声也乘以了这么多,就达到了减小噪声的目的。库中提供的函数如下,
Evaluator::mod_switch_to_next:切换到下一层
Evaluator::mod_switch_to:可以切换参数id进行交换
下面的代码展示了每一层data level的模数切换情况
print_line(__LINE__);
cout << "Perform modulus switching on encrypted and print." << endl;
context_data = context.first_context_data();
cout << "---->";
while (context_data->next_context_data())
{
cout << " Level (chain index): " << context_data->chain_index() << endl;
cout << " parms_id of encrypted: " << encrypted.parms_id() << endl;
cout << " Noise budget at this level: " << decryptor.invariant_noise_budget(encrypted) << " bits" << endl;
cout << "\\" << endl;
cout << " \\-->";
evaluator.mod_switch_to_next_inplace(encrypted);
context_data = context_data->next_context_data();
}
cout << " Level (chain index): " << context_data->chain_index() << endl;
cout << " parms_id of encrypted: " << encrypted.parms_id() << endl;
cout << " Noise budget at this level: " << decryptor.invariant_noise_budget(encrypted) << " bits" << endl;
cout << "\\" << endl;
cout << " \\-->";
cout << " End of chain reached" << endl << endl;
结果如下,可以看到每一层的ID都是对应了上面data level的参数id,每一层的噪声预算也在减少
看起来啥也没做,单单是切换一下层数,噪声预算就被消耗了?前面的文章说了,多项式系数模越大,计算能力就越强,计算能力的体现就在噪声运算上。这里的模减小了。
噪声预算不为0,解密正确
print_line(__LINE__);
cout << "Decrypt still works after modulus switching." << endl;
decryptor.decrypt(encrypted, plain);
cout << " + Decryption of encrypted: " << plain.to_string();
cout << " ...... Correct." << endl << endl;
未使用模切换,计算密文的2次幂,4次幂。
cout << "Computation is more efficient with modulus switching." << endl;
print_line(__LINE__);
cout << "Compute the 8th power." << endl;
encryptor.encrypt(plain, encrypted);
cout << " + Noise budget fresh: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << " + Noise budget of the 2nd power: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << " + Noise budget of the 4th power: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
使用了模切换后计算第8次幂
evaluator.mod_switch_to_next_inplace(encrypted);
cout << " + Noise budget after modulus switching: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
evaluator.square_inplace(encrypted);
evaluator.relinearize_inplace(encrypted, relin_keys);
cout << " + Noise budget of the 8th power: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
evaluator.mod_switch_to_next_inplace(encrypted);
cout << " + Noise budget after modulus switching: " << decryptor.invariant_noise_budget(encrypted) << " bits"
<< endl;
decryptor.decrypt(encrypted, plain);
cout << " + Decryption of the 8th power (hexadecimal) ...... Correct." << endl;
cout << " " << plain.to_string() << endl << endl;
结果如下,
可以看到BFV中应用模交换没有什么影响,这意味着,在做了足够的计算后,降低一些系数根本没有坏处。在某些情况下,也就是密文计算不需要更多的噪声运算时,我们可以稍微提前切换到较低的级别以加快计算。解密是可以在任意层进行解密的,层数越低,模数越低,计算速度就越快。
另外,BFV中,modulus switching不是必须的,在BFV方案里把这个操作近似的放进了乘法运算中,那么也就不需要太长的模数切换链,可以通过设置改变,使其只生成前两层,也就是key level和highest data level(所以我说其实应该拿BGV来举例的)
context = SEALContext(parms, false);
打印一下看看
cout << "Optionally disable modulus switching chain expansion." << endl;
print_line(__LINE__);
cout << "Print the modulus switching chain." << endl;
cout << "---->";
for (context_data = context.key_context_data(); context_data; context_data = context_data->next_context_data())
{
cout << " Level (chain index): " << context_data->chain_index() << endl;
cout << " parms_id: " << context_data->parms_id() << endl;
cout << " coeff_modulus primes: ";
cout << hex;
for (const auto &prime : context_data->parms().coeff_modulus())
{
cout << prime.value() << " ";
}
cout << dec << endl;
cout << "\\" << endl;
cout << " \\-->";
}
cout << " End of chain reached" << endl << endl;
这就没有生成后续的链。
BGV里是需要的,ckks里面用的是重缩放,但原理基本类似。