Accuracy along the output vector with CKKS

[laek3]

Regarding the use of CKKS without batching, I was wondering why I observe different accuracy along the output vector. I noticed on multiple examples that the first 3 or 4 values of the vector have less accuracy compared to the following ones. Here is one example showing this behavior, I have as input 98.123456789, and I simply encrypt then decrypt it.

// Parameters
EncryptionParameters parms(scheme_type::CKKS);
size_t poly_modulus_degree = 8192;
parms.set_poly_modulus_degree(poly_modulus_degree);
parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 40, 30, 30, 40 }));
double scale = pow(2.0, 30);

auto context = SEALContext::Create(parms);
KeyGenerator keygen(context);
auto public_key = keygen.public_key();
auto secret_key = keygen.secret_key();
auto relin_keys = keygen.relin_keys();
Encryptor encryptor(context, public_key);
Evaluator evaluator(context);
Decryptor decryptor(context, secret_key);
CKKSEncoder encoder(context);
size_t slot_count = encoder.slot_count();

Plaintext plain, plain_output;
Ciphertext cipher;
vector<double> res;

float val = 98.123456789;

// Encode then encrypt the value
encoder.encode(val, scale, plain);
encryptor.encrypt(plain, cipher);

// Decrypt then decode the cipher
decryptor.decrypt(cipher, plain_output);
encoder.decode(plain_output, res);

cout << "Result = " << endl;
std::cout << std::setprecision(20);
int acc;
for (std::size_t i = 0; i < 20; i++)
{
        std::cout << res[i];
        acc = (-1) * round(val>res[i] ? log2(val-res[i]) : log2(res[i]-val));
        std::cout << ", accuracy : " << acc << "\n";
}

This is the output I get:

Result = 
98.123208870796077008, accuracy : 12
98.123450072802540944, accuracy : 17
98.123455446539892932, accuracy : 18
98.12346096075420121, accuracy : 19
98.123461018082238638, accuracy : 19
98.123459733768370938, accuracy : 20
98.123459644911221744, accuracy : 20
98.123459607719823339, accuracy : 20
98.123458459306192481, accuracy : 21
98.123459128922007721, accuracy : 22
98.123459203155206865, accuracy : 21
98.123457288371128016, accuracy : 19
98.123459230694592748, accuracy : 21
98.123458432719559141, accuracy : 21
98.123458786141469545, accuracy : 24
98.123457520335165327, accuracy : 20
98.123459134442754248, accuracy : 22
98.123459030688607641, accuracy : 23
98.123459054974986771, accuracy : 22
98.123457867560333057, accuracy : 20

[yaronf]

Resurfacing this issue. We are seeing the same problem on multiple experiments with different numbers (but the same parameters): the first 3 locations of the output vector are less numerically accurate than the others.

[kimlaine]

Looking into it.

[KyoohyungHan]

Previously I was suffering with the same problem and I figure out that this is from moduls switching process. When this process do "flooring" (n instead of "rounding"), this makes positive error to all coefficient. If you see the decoding from polynomial to vector of double variable, it is corresponding to multiplying some matrix. From the property of this matrix, positive error becomes larger especially for the first element of vector.

[WeiDaiWD]

@HanKyoohyung Thanks, Kay. We also have narrowed it down to "flooring". I still can't be sure why this happens. Have you tried to implement "rounding"? Does the problem go away? If we raise the root of unity to its 3rd power, encoding/decoding should still be correct, does the more affected slots rotate?

[KyoohyungHan]

When I change from floor to round, this problem was solved.

It is quite hard to explain the reason in text, but following is brief explaination.

The decode is evalute roots in complex field. In case of the first slot, decode evaluate w = exp(2pi / M) for M = 2 × degree. When the polynomial is f(x) = Sum f_i x^i, f(w) is Sum f_i w^i. Here we only use w^i for i < degree, so all imag part is w^i is positive. This means that 1st slot can be larger than other when f_i > 0 for all i.

[KyoohyungHan]

In addition, raising the root of unity to its 3rd power those not help to solve the problem. Always decode will use exp(2pi/M) in some place.

[WeiDaiWD]

@HanKyoohyung I have also switched to rounding. The error is vastly improved rather than eliminated. Rounding still introduces a very little bias: [0, (p-1)/2] are rounded to 0, [(p+1)/2, p-1] are rounded to 1. The set rounded to 1 has one less element. I guess this is the best we can do now. Thank you for the help!

@lae3C069 @yaronf Internally the error is fixed. We will run more tests and release the fix soon in 3.3.2. This does not affect security, which is a relief. Thank you very much for the "scrutiny". It is extremely valuable. I'll close the issue now.