Open Yinbenxin opened 3 months ago
为了说明这个问题,可以用以下例子进行说明:
#include <iostream>
#include "seal/seal.h"
#include "seal/util/polyarithsmallmod.h"
using namespace std;
using namespace seal;
using namespace seal::util;
inline void multiply_power_of_X(const Ciphertext &encrypted,EncryptionParameters enc_params_,
Ciphertext &destination,
uint32_t index) {
auto coeff_mod_count = enc_params_.coeff_modulus().size() - 1;
auto coeff_count = enc_params_.poly_modulus_degree();
auto encrypted_count = encrypted.size();
destination = encrypted;
for (int i = 0; i < encrypted_count; i++) {
for (int j = 0; j < coeff_mod_count; j++) {
negacyclic_shift_poly_coeffmod(encrypted.data(i) + (j * coeff_count),
coeff_count, index,
enc_params_.coeff_modulus()[j],
destination.data(i) + (j * coeff_count));
}
}
}
int main() {
// 初始化 SEAL 库
int N = 4096;
EncryptionParameters parms(scheme_type::bfv);
parms.set_poly_modulus_degree(N);
parms.set_coeff_modulus(CoeffModulus::BFVDefault(N));
parms.set_plain_modulus(PlainModulus::Batching(N, 20));
auto context = SEALContext(parms);
uint64_t plain_mod = parms.plain_modulus().value();
// 生成密钥
seal::PublicKey public_key;
seal::SecretKey secret_key;
KeyGenerator keygen(context);
keygen.create_public_key(public_key);
secret_key = keygen.secret_key();
// 创建加密器
Encryptor encryptor(context, public_key);
// 创建一个多项式
Plaintext plain_coefficients(N);
plain_coefficients.set_zero();
plain_coefficients[1] = 10;
// 加密多项式
Ciphertext ciphertext;
encryptor.encrypt(plain_coefficients, ciphertext);
// 创建一个 x^10 的明文
Plaintext plain_power(N);
int step = 1 << 4;
plain_coefficients.set_zero();
int index_raw = (N << 1) - step;
plain_power[N - step] = plain_mod - 1;
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
Ciphertext mpfx= ciphertext;
Ciphertext mp= ciphertext;
for (int i = 0; i < 4; ++i) {
Ciphertext mpfx_result;
Ciphertext mp_result ;
Plaintext mpfx_plaint;
Plaintext mp_plaint;
multiply_power_of_X(mpfx, parms, mpfx_result,index_raw);
evaluator.multiply_plain(mp, plain_power,mp_result);
decryptor.decrypt(mpfx_result, mpfx_plaint);
decryptor.decrypt(mp_result, mp_plaint);
cout << "multiply_power_of_X result: " << mpfx_plaint.to_string().substr(0,50) << endl;
cout << "multiply_plain result: " << mp_plaint.to_string().substr(0,50) << endl;
cout << "multiply_power_of_X 剩余可用噪音: " << decryptor.invariant_noise_budget(mpfx_result) << endl;
cout << "multiply_plain 剩余可用噪音: " << decryptor.invariant_noise_budget(mp_result) << endl;
mpfx= mpfx_result;
mp= mp_result;
}
return 0;
}
multiply_power_of_X result: FBFF7x^4081 multiply_plain result: FBFF7x^4081 multiply_power_of_X 剩余可用噪音: 45 multiply_plain 剩余可用噪音: 25 multiply_power_of_X result: FBFF7x^4065 multiply_plain result: FBFF7x^4065 multiply_power_of_X 剩余可用噪音: 45 multiply_plain 剩余可用噪音: 5 multiply_power_of_X result: FBFF7x^4049 multiply_plain result: FAD3Ax^4095 + 1E1x^4094 + F0x^4093 + FBF11x^4092 + multiply_power_of_X 剩余可用噪音: 45 multiply_plain 剩余可用噪音: 0 multiply_power_of_X result: FBFF7x^4033 multiply_plain result: 5DCD2x^4095 + 4065Ex^4094 + 4065Ex^4093 + 9E32Fx^4 multiply_power_of_X 剩余可用噪音: 45 multiply_plain 剩余可用噪音: 0
可以看到噪音会迅速降低,从而导致计算错误。
之前仅仅支持8192是因为查询的总量较小,噪音并未消耗完毕,在数据量较大时会出现噪音不够所导致的计算错误问题。
@qxzhou1010 Would you mind to take a look at this?
@Yinbenxin 非常感谢您提出这个issue,并给出了优化的实现。这里我们是想在密文下计算 c1 = c0*(-x)^(-2j),由于 BFV 中多项式模采用了非常特殊的负循环多项式(x^N+1),因此这里的乘法运算本质上就是对 c0 的负循环移位操作。所以我们可以使用 negacyclic_shift_poly_coeffmod 来加速这个运算,并且这个过程对噪声消耗是零的,因为只涉及到对密文多项式一些简单的移位操作,所以并不会增加密文中所包含的噪声。
multiply_plain 是因为涉及到密文*明文,因此结果密文中的噪声项会被放大,所以每一次操作都会导致对噪声预算的消耗。
实际上,在 SealPIR 官方仓库中正是采用的这个实现。可以参考:https://github.com/microsoft/SealPIR/blob/ee1a5a3922fc9250f9bb4e2416ff5d02bfef7e52/src/pir_server.cpp#L415。
我们后续将会对这个点的实现进行优化,再次感谢您提出的问题和进行的验证。
此问题发生在尝试使用4096安全强度来进行匿踪查询,经过为期1周的排查,问题终于浮出水面并得以解决。 问题代码: seal_pir.cc中std::vector SealPirServer::ExpandQuery函数:
建议修改为:
主要原因是,multiply_plain会严重损耗seal密态计算的噪音,但是negacyclic_shift_poly_coeffmod不会导致噪音增大,并且在乘x^n时该函数具有更快的计算速度。