Hints to circumvent scale out of bounds

[eduardolfalcao]

Hello everyone :)

I have an application, in which I perform some homomorphic multiplications. When I perform x2^2, x2x, and x2x3, the result is correct. But when performing the last multiplication, x2*x7, the application simply breakes with the following error:

terminate called after throwing an instance of 'std::invalid_argument' what(): scale out of bounds

This is the snippet code of function: ` Ciphertext g(Ciphertext x, Evaluator* evaluator, RelinKeys relin_keys){

    Ciphertext x1 = x;
    Ciphertext x2 = x;
    (*evaluator).square_inplace(x2);
    (*evaluator).relinearize_inplace(x2, relin_keys);

    Ciphertext x3 = x2;
    (*evaluator).multiply_inplace(x3,x);
    (*evaluator).relinearize_inplace(x3, relin_keys);

    Ciphertext x5 = x2;
    (*evaluator).multiply_inplace(x5,x3);
    (*evaluator).relinearize_inplace(x5, relin_keys);

    Ciphertext x7 = x2;
    (*evaluator).multiply_inplace(x7,x5);
    (*evaluator).relinearize_inplace(x7, relin_keys);

    return x7;

}`

This is the vector I am trying: vector<double> input{ 2.2 , 0, 1, -3, -0.5 };

And this is my setup: `EncryptionParameters parms = createParameters();

    auto context = SEALContext::Create(parms);
    print_line(__LINE__);
    cout << "Set encryption parameters and print" << endl;
    print_parameters(context);
    cout << endl;

    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();
    cout << "Number of slots: " << slot_count << endl;

    double scale = pow(2.0, 30);`

Could anyone point a direction for me to solve this issue? Actually, I will need to perform lots of multiplications, and I was thinking that the relinearize function would allow me to lighten my polynomial so that it could handle several multiplications.

Best regards :)

[eduardolfalcao]

`EncryptionParameters createParameters(){

    EncryptionParameters parms(scheme_type::CKKS);

    size_t poly_modulus_degree = 16384;
    parms.set_poly_modulus_degree(poly_modulus_degree);
    parms.set_coeff_modulus(CoeffModulus::Create(poly_modulus_degree, { 40, 40, 40, 40, 40 }));

    return parms;

} `

[WeiDaiWD]

The reason is that you didn't "rescale" the ciphertexts after multiplication/relinearization. Then if you add "rescale", you also need to match the scales of two ciphertexts given into a multiplication function. Please compile, execute, and check the native/examples/4_ckks_basics.cpp. Let me know if you get it working or have further questions.

[eduardolfalcao]

Thanks for the response. When applying rescaling after multiplication and relinearization it works (i.e., runs without error). However, the first multiplication after rescaling is yielding wrong results.

For instance, I am trying to get x^3. First, I compute as an example the square of 2.2, and I get 4.84. But when I do the next multiplication to get x^3, the outcome gets unpredictable (completely different from expected).

Is there anything else I am missing?

My new code snippet:

`Ciphertext g(Ciphertext x, Evaluator* evaluator, RelinKeys relin_keys){

Ciphertext x1 = x;
Ciphertext x2 = x;
(*evaluator).square(x1, x2);
(*evaluator).relinearize_inplace(x2, relin_keys);
(*evaluator).rescale_to_next_inplace(x2);

(*evaluator).rescale_to_next_inplace(x);
Ciphertext x3 = x2;
(*evaluator).multiply_inplace(x3,x);
(*evaluator).relinearize_inplace(x3, relin_keys);
(*evaluator).rescale_to_next_inplace(x3);

return x3;

}`

Best regards

[eduardolfalcao]

Nevermind. I just noticed that I have to match the modulus index of the Ciphertexts for it to work properly. Now I have it working. Thanks ;-)

[eduardolfalcao]

Although the results of my multiplications are correct, in a given moment I get the "not enough relinearization keys" error. I've already spent a few hours trying to figure out how to increase this value but I couldn't find.

Does anyone have a clue of how to circumvent this problem?

Best regards

[WeiDaiWD]

Increasing this value is not necessary or recommended. Every multiplication of ciphertext and ciphertext or square of ciphertext should be followed by a relinearization. The error is likely caused by missing one relinearization.

[eduardolfalcao]

Thanks for the quick reply. It was exactly what you said. I was missing one relinearization. :-)

[eduardolfalcao]

Hi WeiDaiWD,

First of all, I apologize for flooding here with my doubts :)

I have two more questions:

1. is there any way of limiting the size of the Ciphertext other than poly_modulus_degree / 2 (I am using CKKSEncoder).
2. I am trying to perform matrix multiplications. Is there any simplified form to do that? I am trying to implement it from scratch but, in my implementation, I would need to sum the values of all elements of a single Ciphertext. However, it seems that there is no such function that does that. Is there any approach you would recommend?

Best regards

[WeiDaiWD]

1. The size of Ciphertext (Ciphertext::size()) should be 2. After ciphertext and ciphertext multiplication, it should be 3. After relinearization, it goes back to 2. This is the same in BFV and CKKS. It has nothing to do with encoder or poly_modulus_degree. poly_modulus_degree / 2 is the maximum number of message slots that can be packed into a plaintext, using CKKSEncoder.
2. An optimal way to perform matrix multiplication is not trivial. It depends on the dimensions of both matrices. Each ciphertext (and the plaintext encrypted) can pack all elements or some elements of a column, row, or a submatrix. This paper explains some techniques to compute matrix multiplication with the CKKS scheme. Sum all the values of all elements of a single ciphertext is doable. See the (pseudo) code below.

// Try any encryption 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, { 60, 30, 60 }));
auto context = SEALContext::Create(parms);
KeyGenerator keygen(context);
SecretKey secret_key = keygen.secret_key();
PublicKey public_key = keygen.public_key();
GaloisKeys galois_keys = keygen.galois_keys();

CKKSEncoder encoder(context);
auto m = encoder.slot_count();
vector<double> msg(m, 1.0); // m instances of 1.0
Plaintext pt;
double scale = pow(2.0, 30); // just an example, change it to whatever you want
encoder.encode(msg, scale, pt);

Encryptor encryptor(context, public_key);
Ciphertext ct;
encryptor.encrypt(pt, ct);

// sum all m slots of ct, store the results in the first slot of ct
Evaluator evaluator(context);
Ciphertext ct_temp;
for (size_t i = m / 2; i > 0; i >>= 1) {
evaluator.rotate_vector(ct, i, galois_keys, ct_temp);
evaluator.add_inplace(ct, ct_temp);
}

// further set all other slots of ct to zero, which consumes 1 prime
Plaintext pt_mask;
vector<double> mask(m, 0.0);
mask[0] = 1.0; // set the first slot to 1.0
encoder.encode(mask, scale, pt_mask);
evaluator.multiply_plain_inplace(ct, pt_mask);
evaluator.rescale_to_next_inplace(ct);

// examine result
Decryptor decryptor(context, secret_key);
decryptor.decrypt(ct, pt);
vector<double> result;
encoder.decode(pt, result);
// result should be [4096.0, 0.0, ..., 0.0]