BGV Decryption Algorithm

[wyunhao]

Hi there,

We are trying to inspect the BGV decryption logic and somehow cannot reproduce the correct result by manually performing the calculation "aSK+b". The following is what we tried to do:

• pick ring dimension to be 16, plaintext modulus 65537 (the primitive root would be 2 in this case)
• encrypt a message with 0101010101010101 into a ciphertext ct, with three levels for the coefficient modulus chain {28, 30, 60}
• print out the SK value (under non-ntt form)
• decrypt this message (without decoding), directly print out the plaintext value pl
• print out the ciphertext ct data value, with data(0) to be the b part, and data(1) to be the a part

We expect <a, SK> + b should be equal to the plaintext value pl, but got a mismatch in our result.
For example, with:

• SK = [0, 0, 268435360, 268435360, 268435360, 1, 1, 1, 268435360, 268435360, 268435360, 268435360, 1, 1, 0, 268435360]
• ct.b = [179363586, 33962475, 250845597, 9728578, 25426230, 117056600, 123757182, 214305055, 250227586, 111810925, 67428290, 154288270, 251561573, 109070231, 138778501, 132073358]
• ct.a = [203294126, 139672165, 35567408, 130490400, 42190130, 3708511, 59231688, 232045029, 124680310, 133267504, 192120702, 117746625, 150047787, 208174536, 55664166, 159960287]

The result of <a, SK> + b = [28578, 61346, 0, 0, 64517, 61346, 61346, 61346, 61346, 0, 0, 0, 1020, 0, 0, 0] (we also printed out the correction factor for encrypted ciphertext, which is just 1 in this case), while the expected plaintext vector pl is [32769, 0, 0, 0, 64517, 0, 0, 0, 0, 0, 0, 0, 1020, 0, 0, 0].

We wonder if we are missing something critical in the decryption logic. Could you please help us to identify the issue?
The code we used for experiments is given as below.

int ring_dim = 16;
int p = 65537;


EncryptionParameters bfv_params(scheme_type::bgv);
bfv_params.set_poly_modulus_degree(ring_dim);
auto coeff_modulus = CoeffModulus::Create(ring_dim, { 28, 30, 60 });
bfv_params.set_coeff_modulus(coeff_modulus);
bfv_params.set_plain_modulus(p);

prng_seed_type seed;
for (auto &i : seed) {
    i = random_uint64();
}
auto rng = make_shared<Blake2xbPRNGFactory>(Blake2xbPRNGFactory(seed));
bfv_params.set_random_generator(rng);

SEALContext seal_context(bfv_params, true, sec_level_type::none);

KeyGenerator keygen(seal_context);
SecretKey bfv_secret_key = keygen.secret_key();

MemoryPoolHandle my_pool = MemoryPoolHandle::New();

PublicKey bfv_public_key;
keygen.create_public_key(bfv_public_key);

RelinKeys relin_keys;
keygen.create_relin_keys(relin_keys);

Encryptor encryptor(seal_context, bfv_public_key);
Evaluator evaluator(seal_context);
BatchEncoder batch_encoder(seal_context);
Decryptor decryptor(seal_context, bfv_secret_key);


vector<uint64_t> msg(ring_dim);
for (int i = 0; i < ring_dim; i++) {
    msg[i] = (i% 2 == 0) ? 1 : 0;
}
Plaintext pl;
Ciphertext c;
batch_encoder.encode(msg, pl);
encryptor.encrypt(pl, c);

/////////////////////////////////////// print the secret key value
inverse_ntt_negacyclic_harvey(bfv_secret_key.data().data(), seal_context.key_context_data()->small_ntt_tables()[0]);
for (int i = 0; i < ring_dim; i++) {
    cout <<  bfv_secret_key.data()[i] << ", ";
}
cout << endl << endl;
seal::util::RNSIter key_rns(bfv_secret_key.data().data(), ring_dim);
ntt_negacyclic_harvey(key_rns, coeff_modulus.size(), seal_context.key_context_data()->small_ntt_tables());


decryptor.decrypt(c, pl);
/////////////////////////////////////// print the expected plaintext value
cout << "decoded (sanity check): \n";
for (int i = 0; i < ring_dim; i++) {
    cout << pl.data()[i] << " ";
}
cout << endl;

/////////////////////////////////////// print the ciphertext b, A coefficients value
cout << "Print ciphertext: " << endl;
for (int i = 0; i < ring_dim; i++) {
    cout << c.data(0)[i] << ", ";
}
cout << endl;
for (int i = 0; i < ring_dim; i++) {
    cout << c.data(1)[i] << ", ";
}
cout << endl;`