noise budget lower than expected for 3.3.1

[haochenuw]

It seems like for poly_modulus_degree equal to 16384 and a 40 bit plaintext modulus which enables batching, the noise budget of a encryption of zero is 340 bits but noise budget of a encryption of random vector with has only 310 bits of noise budget. The code below reproduces this issue.

#include "examples.h"

using namespace std;
using namespace seal;

void example_noise_budget()
{

    EncryptionParameters parms(scheme_type::BFV);


    size_t poly_modulus_degree = 16384;
    parms.set_poly_modulus_degree(poly_modulus_degree);


    parms.set_coeff_modulus(CoeffModulus::BFVDefault(poly_modulus_degree));


    parms.set_plain_modulus(PlainModulus::Batching(poly_modulus_degree, 40));


    auto context = SEALContext::Create(parms);

    print_line(__LINE__);
    cout << "Set encryption parameters and print" << endl;
    print_parameters(context);


    KeyGenerator keygen(context);
    PublicKey public_key = keygen.public_key();
    SecretKey secret_key = keygen.secret_key();

    Encryptor encryptor(context, public_key);


    Decryptor decryptor(context, secret_key);
    BatchEncoder batch_encoder(context);

    size_t slot_count = batch_encoder.slot_count();

   
    
    random_device rd;

    vector<uint64_t> data_1(slot_count, 0);
    vector<uint64_t> data_2(slot_count ,0); 
    for(size_t i =0; i < slot_count; i++){
	data_1[i] = rd() % parms.plain_modulus().value();
    }    


    Plaintext plain_1(parms.poly_modulus_degree(), 0);
    batch_encoder.encode(data_1, plain_1);

    Plaintext plain_2(parms.poly_modulus_degree(), 0);
    batch_encoder.encode(data_2, plain_2);

    Ciphertext encrypted_1(context);
    encryptor.encrypt(plain_1, encrypted_1);

    Ciphertext encrypted_2(context);
    encryptor.encrypt(plain_2, encrypted_2);


    cout << " noise budget of fresh encryption = "
        << decryptor.invariant_noise_budget(encrypted_1)  << endl;
    
    cout << " noise budget of fresh encryption of zero = " << decryptor.invariant_noise_budget(encrypted_2) << endl;  

}

[WeiDaiWD]

Let me summarize the problem here for other users. In short, this issue is caused by some smart-but-too-smart tricks we did in invariant_noise_budget(...) and only affects a fresh encryption or maybe ciphertexts after very few levels of multiplications, if the plain modulus is chosen to be large. We will have a fix for this ready in the next minor release.

Here is a more detailed reasoning. The decryption of a ciphertext is in the form of dec = delta * m + noise, where delta = floor(q, p) is the largest integer smaller or equal to q/p, p is the chosen plaintext modulus, q is the chosen ciphertext modulus, and m is the plaintext polynomial. Noise budget should be calculated as log(q) - log(p) - log(noise), where noise denotes the absolute value of itself. However, in SEAL, we calculate noise budget by computing log(q) - log(dec * p % q) which is different from the accurate calculation. Since delta is not exactly q/p, our calculate will introduce an error term (q % p) * m. The resulting noise budget is in fact log(q) - log(p) - log(noise - (q % p) * m). For a fresh encryption or ciphertexts resulted from very few levels of multiplications, with a large selection of p, (q % p) * m has a larger infinity norm than noise, resulting in a smaller noise budget than accurate calculation. This can be easily fixed by calculating the correct decryption in invariant_noise_budget(...).

I'm closing this issue now.