Inconsistent results with insufficient multiplicative depth

Hello,

I am encountering some unexpected behavior while performing operations with insufficient multiplicative depth specified by coeff_modulus. I would like to report these cases and seek guidance from your team regarding their implications.

Q1: Inconsistent results under insufficient multiplicative depth I'm aware that giving insufficient level is considered an invalid use case, thus not expected to yield correct results. However, when I generated and executed such cases in real, I noticed inconsistencies in the outcomes. Some cases return correct outputs, while others yield unexpected results. Please refer to Example 1 - 3 below for clarification.

Considering the observed inconsistencies, I propose terminating such operations with an exception, like std::invalid_argument, which is commonly used for handling invalid parameter sets. I would appreciate your thoughts on this suggestion.

Q2: Random outputs from one program (with insufficient multiplicative depth) Furthermore, I also observed instances where executing certain operations with insufficient multiplicative depth resulted in random outputs. For instance, in Example 4 below, the operation alternates between returning expected outputs and producing unpredictable results. These unexpected outputs vary with each execution. I seek clarification on whether such behavior is expected or if there are specific environment settings I should check. Any insights or instructions regarding this observation would greatly aid my understanding.

Thank you for your attention and dedication to addressing this issue.

Examples

Here's the example code that I used:

SEAL version: 4.1.1

Common encryption context (with each scheme: bfv, bgv)

size_t poly_modulus_degree = 16384;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, vector<int>{54, 54}));
parms.set_plain_modulus(65537);
double scale = pow(2.0, 42);
SEALContext context(parms, true, sec_level_type::tc128);
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key;
RelinKeys relin_keys;
GaloisKeys gal_keys;
keygen.create_public_key(public_key);
keygen.create_relin_keys(relin_keys);
keygen.create_galois_keys(gal_keys);
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
BatchEncoder batch_encoder(context);
size_t slots = batch_encoder.slot_count();
Plaintext tmp;
Ciphertext tmp_;

As coeff_modulus is given as {54, 54}, this context allows no multiplication (since the last one is the special prime).
However, I found incoherent results when the number of multiplication exists at least once.

Example 1. 1 multiplication: both BFV & BGV return the expected output

Ciphertext x, y;
int yP;
int c;
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, x);
yP = 4;
tmp = uint64_to_hex_string(yP);
evaluator.multiply_plain(x, tmp, x);
vector<uint64_t> tmp_vec_1 = decrypt_array_batch_to_nums(
  decryptor, batch_encoder, x, slots);
for (int tmp_i = 0; tmp_i < 20; ++tmp_i)
{
cout << tmp_vec_1[tmp_i] << " ";
}
cout << endl;
return 0;

Both BFV & BGV prints out the expected result: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

Example 2. 1 multiplication: BFV returns correct result, while BGV returns weird output

Ciphertext x, y;
int yP;
int c;
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, x);
tmp = uint64_to_hex_string(4);
encryptor.encrypt(tmp, y);
evaluator.multiply(x, y, x);
evaluator.relinearize_inplace(x, relin_keys);
vector<uint64_t> tmp_vec_1 = decrypt_array_batch_to_nums(
decryptor, batch_encoder, x, slots);
for (int tmp_i = 0; tmp_i < 20; ++tmp_i) {
cout << tmp_vec_1[tmp_i] << " ";
}
cout << endl;
return 0;

With BFV, it prints out: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 (expected result)
With BGV, it prints out: 38016 19064 25215 35222 38220 54588 55619 36306 48141 38691 1905 32626 49573 64329 2810 15880 25103 51615 6528 34031

Example 3. 2 multiplications: both BFV & BGV return weird outputs

Ciphertext x, y;
int yP;
int c;
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, x);
yP = 4;
tmp = uint64_to_hex_string(yP);
evaluator.multiply_plain(x, tmp, x);
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, y);
evaluator.multiply(x, y, x);
evaluator.relinearize_inplace(x, relin_keys);
vector<uint64_t> tmp_vec_1 = decrypt_array_batch_to_nums(
  decryptor, batch_encoder, x, slots);
for (int tmp_i = 0; tmp_i < 20; ++tmp_i)
{
cout << tmp_vec_1[tmp_i] << " ";
}
cout << endl;
return 0;

Expected result: 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
With BFV, it prints out: 32901 14075 6865 4148 51675 16769 17296 45267 22997 16855 50745 37015 33820 34897 7055 46295 55382 44518 3044 37466
With BGV, it prints out: 2933 59218 4727 2741 3616 19127 35624 10762 34847 54044 53548 32103 21800 11947 46591 52454 50808 47452 33543 36035

Example 4. 2 multiplications where BFV gives different outputs every time it is executed (including expected output and weird ouputs)
```
Ciphertext x, y;
int yP;
int c;
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, x);
yP = 3;
tmp = uint64_to_hex_string(yP);
evaluator.multiply_plain(x, tmp, x);
tmp = uint64_to_hex_string(1);
encryptor.encrypt(tmp, y);
evaluator.multiply(x, y, x);
evaluator.relinearize_inplace(x, relin_keys);
vector<uint64_t> tmp_vec_1 = decrypt_array_batch_to_nums(
  decryptor, batch_encoder, x, slots);
for (int tmp_i = 0; tmp_i < 20; ++tmp_i)
{
cout << tmp_vec_1[tmp_i] << " ";
}
cout << endl;
return 0;
```
- Expected result: 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
- 5 example of weird outputs:
- 62356 42073 53847 5632 43237 39231 2972 25083 41213 21151 16773 46787 28641 7637 13108 11541 60124 21230 55640 786
- 49144 30661 30505 42703 46906 54376 13570 22078 27187 55568 37513 37527 21844 41976 35168 51053 53951 5050 10157 38348
- 802 3290 1231 9971 46497 23023 27172 28404 21099 45430 43672 49116 40555 40403 43139 7433 50227 20767 38596 2182
- 51566 35722 63428 12677 54038 33774 43044 8648 26163 33096 16965 16694 40849 23453 17349 25975 19176 28882 1059 14803
- 6721 17283 43477 43256 36650 46771 37991 27536 10201 53209 17613 63618 52524 9093 19023 36958 17899 55170 15755 8813

microsoft / SEAL

Inconsistent results with insufficient multiplicative depth #684

Examples