SEAL: Incorrect decryption after square operation, even if the Ciphertext has greater than zero noise budget

Question

I have a series of calculations on a Ciphertext and a square at the end. The problem is that even if there is sufficient noise budget to perform the square and the relinearization(both before and after the operation), when I decrypt it, I get an incorrect result.

What's strange is that, if I decrypt and decode, and then encode and encrypt again in a fresh Ciphertext, the number, before the square, the computation is performed correctly.

I don't understand where the problem is, since if the set parameters where wrong, than I should have an incorrect result anyway.

I specify that I use a Fractional Encoder with 64 coefficients of the polynomial for the integral part and 32 digits of precision for the fractional part (in base 3) and that all my calculations before the square are performed between Ciphertext and Plaintext.

This is an example of what I mean:

#include <vector>
#include "seal/seal.h"

using namespace std;
using namespace seal;



int main(int argc, char const *argv[])
{
    //Set parameters
    EncryptionParameters parms;
    parms.set_poly_modulus("1x^4096 + 1");
    parms.set_coeff_modulus(coeff_modulus_128(4096));
    parms.set_plain_modulus(1<<20);
    SEALContext context(parms);
    KeyGenerator keygen(context);
    PublicKey public_key = keygen.public_key();
    SecretKey secret_key = keygen.secret_key();
    EvaluationKeys ev_keys16;
    keygen.generate_evaluation_keys(16, ev_keys16);
    Encryptor encryptor(context, public_key);
    Evaluator evaluator(context);
    Decryptor decryptor(context, secret_key);
    FractionalEncoder fraencoder(context.plain_modulus(), context.poly_modulus(), 64, 32, 3);




    float data=0.5;
    float weight= 1.5;

    //encrypt data and encode weight

    Ciphertext encrypted_data;
    encryptor.encrypt(fraencoder.encode(data),encrypted_data);
    cout<<"Noise budget in a freshly encrypted: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;
    Plaintext encoded_weight=fraencoder.encode(weight);

    //Operation: (0.5*1.5)*5=3.75
    vector<Ciphertext> mul_vector(5);
    for(int i=0;i<5;i++){
        evaluator.multiply_plain(encrypted_data,encoded_weight,mul_vector[i]);
    }

    evaluator.add_many(mul_vector,encrypted_data);
    cout<<"Noise budget after 5 plain multiplications and 4 additions: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;

    //Operation: 3.75*4=15
    vector<Ciphertext> add_vector(4);
    for(int i=0;i<4;i++){
        add_vector[i]= Ciphertext(encrypted_data);
    }
    evaluator.add_many(add_vector,encrypted_data);

    cout<<"Noise budget after 4 additions: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;

    //Operation: (15-1.5)*1.5=20.25
    evaluator.sub_plain(encrypted_data,encoded_weight);
    evaluator.multiply_plain(encrypted_data,encoded_weight);

    cout<<"Noise budget after 1 plain sub and 1 plain multiplication: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;

    //Operation: (20.25*1.5)*6=182.25
    vector<Ciphertext> mul_vector2(6);
    for(int i=0;i<6;i++){
        evaluator.multiply_plain(encrypted_data,encoded_weight,mul_vector2[i]);
    }

    evaluator.add_many(mul_vector2,encrypted_data);
    cout<<"Noise budget after 6 plain multiplications and 5 additions: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;

    // here I decrypt, decode and encrypt again, to obtain the right result
    Plaintext tmp;
    float res;
    //If I remove the following 4 lines the final result is incorrect
    decryptor.decrypt(encrypted_data,tmp);
    res = fraencoder.decode(tmp);
    cout<<"Decrypted result before square: "<<res<<endl;
    encryptor.encrypt(fraencoder.encode(res),encrypted_data);

    //182.25^2=33215.1
    evaluator.square(encrypted_data);
    evaluator.relinearize(encrypted_data,ev_keys16);

    cout<<"Noise budget after square and relianearization: "<<decryptor.invariant_noise_budget(encrypted_data)<<endl;


    decryptor.decrypt(encrypted_data,tmp);
    res= fraencoder.decode(tmp);
    cout<<res<<endl;


    return 0;
}

What am I missing?

Answer 1

The problem is that your plain_modulus is too small for this computation.

If you print out tmp at the end (tmp.to_string()) you'll see that it has very large coefficients. Note that those coefficients are modulo plain_modulus so many of them are expected to look large. Nevertheless, the infinity norm of res as an integer (i.e. if you use a large enough plain_modulus) is 266441508, which is just below 2²⁹. Since your plain_modulus is only 2²⁰, you'll end up with incorrect results at the end. Your re-encoding helps because before the last computations the coefficients are still not too large and re-encoding the polynomial lowers the coefficients back to infinity norm 1 (in your case with base=3).

The solution is to increase plain_modulus to at least 2²⁹. Of course this will result in more noise growth and you'll be already very close to noise overflow but it will still work.