BFV scheme: behavior on exceeding noise

[bcebere]

Hello. I have the following code snippet, just a simple ciphertext - ciphertext multiplication.

void replicate(vector<int64_t>& data, size_t times) {
    size_t init_size = data.size();
    data.reserve(times);
    for (size_t i = 0; i < times - init_size; i++) {
        data.push_back(data[i % init_size]);
    }
}

vector<int64_t> decrypt(Decryptor& decryptor, BatchEncoder& encoder,
                        const Ciphertext& ct) {
    vector<int64_t> result;
    Plaintext plaintext;

    decryptor.decrypt(ct, plaintext);
    encoder.decode(plaintext, result);

    return result;
}

TEST_F(BFVVectorTest, TestContextRegressionNoise) {
    EncryptionParameters parameters(scheme_type::bfv);
    parameters.set_poly_modulus_degree(4096);
    parameters.set_plain_modulus(1032193);
    parameters.set_coeff_modulus(CoeffModulus::BFVDefault(4096));

    auto ctx = SEALContext(parameters);
    auto keygen = KeyGenerator(ctx);
    auto sk = SecretKey(keygen.secret_key());

    PublicKey pk;
    keygen.create_public_key(pk);

    auto encryptor = Encryptor(ctx, pk);
    auto decryptor = Decryptor(ctx, sk);
    auto encoder = BatchEncoder(ctx);
    auto evaluator = Evaluator(ctx);

    vector<int64_t> data = {2};
    replicate(data, encoder.slot_count());

    Ciphertext initial(ctx);
    Plaintext plaintext;

    encoder.encode(data, plaintext);
    encryptor.encrypt(plaintext, initial);

    auto test_mul = initial;
    auto expected = 2;

    auto dec = decrypt(decryptor, encoder, test_mul);
    ASSERT_EQ(dec[0], expected);

    for (int step = 0; step < 2; ++step) {
        expected *= 2;
        evaluator.multiply_inplace(test_mul, initial);

        auto dec = decrypt(decryptor, encoder, test_mul);
        ASSERT_EQ(dec[0], expected);
    }
}

I know that it exceeds the limits of the parameters, but instead of throwing an exception, it decrypts to the wrong value

Failure
Expected equality of these values:
 dec[0]
    Which is: 467871
  expected
    Which is: 8

Is this the expected behavior? should we monitor the noise budget? I was hoping that SEAL would throw an exception in situations like this.

Tested with SEAL 3.6.1

[WeiDaiWD]

That is the expected behavior. You probably know how to use the function int Decryptor::invariant_noise_budget(...) to monitor noise growth. This function behaves differently from and takes longer than Decryptor::decrypt(...). Automatically monitoring budget in decryption will make decryption much slower. However, I do think that your suggestion is very useful in DEBUG mode, and I might add it to a future version.

Please do not close this issue. Thanks!

[bcebere]

Thank you for the explanation!

I have 2 more questions, sorry for the spam:

• what similar solutions do I have for CKKS? I understand that I cannot use invariant_noise_budget there to monitor how much precision I'm losing.
• Could I infer from the security parameters the theoretical limits/depths for each operation? Just a generated map that tells be that for a the given context I can do X encrypted multiplications/Y rotations etc.

[WeiDaiWD]

• In CKKS there is no solution to monitor the noise growth. One may try to estimate the noise growth, but the analyzed bound/limit on noise is not tight enough to match the reality.
• In CKKS the noise is rarely the cause of decryption failure but mostly the cause of precision lost. In a rough example: suppose that you expect the result to be 123.456; optimal noise might give you 123.456***; a tolerable noise gives you 123.4**; a big noise gives you 12*.***. The precision you get is the distance between scale and noise. The rescaling after each multiplying/squaring of ciphertexts stabilizes the distance. However, the usual cause of decryption failure is the growth of value before decimal point, for example, when exponentiating 2.0, the value before decimal point eventually grows beyond the CoeffModulus. This will cause a decryption failure and makes the result totally wrong. Therefore, the choice of parameters is less related to noise growth, but the number of rescaling and the precision of your application.
• There is no simple map/table to look up for a suggested depth for each parameter set. Best practices are:
  1. Normalize values for encoding so that they have small size before the decimal point.
  2. Pass sec_level_type::none to SEALContext's constructor to temporarily allow insecure parameters.
  3. The number of primes in CoeffModulus should be the depth of your application plus 2 (or more).
  4. Choose a temporary encoding scale (a power of 2).
  5. All but the first and the last primes of CoeffModulus should have the same bit-size of the scale.
  6. The first and the last primes of CoeffModulus should have the same size and not less than scale.
  7. Repeat iv-vi while changing the scale and prime sizes for an expected precision. Insert primes to the second place of CoeffModulus if the result is totally wrong. Increase the scale and related primes if precision is low. Decrease the scale and related primes if precision is more than enough.
  8. Remove sec_level_type::none to enforce secure parameters. Increase poly_modulus_degree if `SEALContext's constructor fails.