Question about order of operations Associativity and commutativity in bgv cipherspace

[elkanatovey]

Based on my understanding of the scheme, so long relinearization and mod switching aren't applied, ciphertext plaintext addition and multiplication are linear operations.

I've written some code to test this and as far as I can tell this only works for small(relative to the plaintext modulus) plaintext coefficients.

I'm adding my code in here so you can see for yourself. The code tests that e * (a + c) + f * (b + d) = (a*e + b*f) + (c*e + d*f) where e,f are encrypted and equlity is in the ciphertext space i.e. e * (a + c) + f * (b + d) - (a*e + b*f) + (c*e + d*f) gives a transparent ciphertext.

Any insight on why this doesn't end with a transparent ciphertext would be appreciated. My assumption is that it's something to do with modular arithmetic.

The code:

//
// test that  ([x, y] * [[a, b], [c, d]]) * [e, f]^T = [x, y] * ([[a, b], [c, d]] * [e, f]^T) in the ciphertext space
// were e, f are both ciphertexts and x, y are both set to 1.
//
// in other words, test that e * (a + c) + f * (b + d) = (a*e + b*f) + (c*e + d*f)
//

#include <cassert>
#include <cstdint>
#include <memory>
#include <seal/seal.h>

using namespace std;
using namespace seal;

void add_plaintexts(const EncryptionParameters &enc_params, const Plaintext &a, const Plaintext &c, Plaintext &a_plus_c);

int main(int argc, char *argv[]) {

    uint32_t N = 4096;

    uint32_t logt = 20;

    EncryptionParameters enc_params(scheme_type::bgv);

    // Generates all parameters

    cout << "Main: Generating SEAL parameters" << endl;
    enc_params.set_poly_modulus_degree(N);
    enc_params.set_coeff_modulus(CoeffModulus::BFVDefault(N));
    enc_params.set_plain_modulus(PlainModulus::Batching(N, logt + 1));

    SEALContext context(enc_params, true);
    KeyGenerator keygen(context);

    SecretKey secret_key = keygen.secret_key();
    Encryptor encryptor(context, secret_key);
    Decryptor decryptor(context, secret_key);
    Evaluator evaluator(context);

    cout << "Main: SEAL parameters generated" << endl;

    cout << "Main: generating matrices" << endl;

    std::string poly = "123D7D"; // multiples with/without mod operator: "247AFA" "51AF9" for some reason this
    // example only works when removing the modulo t from plaintext addition

    Plaintext a(poly);         // example poly that doesn't work at all:" 1CBB5Bx^3 + A59B8x^2 + 6C3D2x^1 + 123D7D"
    Plaintext b(poly);
    Plaintext c(poly);
    Plaintext d(poly);
    Plaintext e(poly);
    Plaintext f(poly);

    Ciphertext e_encrypted;
    Ciphertext f_encrypted;

    encryptor.encrypt_symmetric(e, e_encrypted);
    encryptor.encrypt_symmetric(f, f_encrypted);
    std::cout << "Encrypting e f" << std::endl;
    std::cout << "Plain Modulus:"<<enc_params.plain_modulus().value() << std::endl;

    std::cout << "calculating e * (a + c) + f * (b + d)"<< std::endl;

    Plaintext a_plus_c;
    Plaintext b_plus_d;

    add_plaintexts(enc_params, a, c, a_plus_c);
    add_plaintexts(enc_params, b, d, b_plus_d);

    std::cout << a_plus_c.to_string()<<" plaintext addition result..........................."<< std::endl;
    Ciphertext e_times_a_plus_c; // e * (a + c)
    Ciphertext f_times_b_plus_d; // f * (b + d)
    evaluator.multiply_plain(e_encrypted, a_plus_c, e_times_a_plus_c);
    evaluator.multiply_plain(f_encrypted, b_plus_d, f_times_b_plus_d);

    Ciphertext e_times_a_plus_c_plus_f_times_b_plus_d; // e * (a + c) + f * (b + d)
    evaluator.add(e_times_a_plus_c, f_times_b_plus_d, e_times_a_plus_c_plus_f_times_b_plus_d);

    std::cout << "finished e * (a + c) + f * (b + d)"<< std::endl;//1958182 1

    std::cout << "calculating (a*e + b*f) + (c*e + d*f)"<< std::endl;//1958182 1
    Ciphertext a_times_e; // a * e
    Ciphertext b_times_f; // b * f
    Ciphertext c_times_e; // c * e
    Ciphertext d_times_f; // d * f
    evaluator.multiply_plain(e_encrypted, a, a_times_e);
    evaluator.multiply_plain(f_encrypted, b, b_times_f);
    evaluator.multiply_plain(e_encrypted, c, c_times_e);
    evaluator.multiply_plain(f_encrypted, d, d_times_f);

    Ciphertext ae_plus_bf; // (a*e + b*f)
    Ciphertext ce_plus_df; // (c*e + d*f)
    evaluator.add(a_times_e, b_times_f, ae_plus_bf);
    evaluator.add(c_times_e, d_times_f, ce_plus_df);

    Ciphertext ae_plus_bf_plus_ce_plus_df; // (a*e + b*f) + (c*e + d*f)
    evaluator.add(ae_plus_bf, ce_plus_df, ae_plus_bf_plus_ce_plus_df);
    std::cout << "finished (a*e + b*f) + (c*e + d*f)"<< std::endl;//1958182 1

    Ciphertext trivial_result;
    evaluator.sub(e_times_a_plus_c_plus_f_times_b_plus_d, ae_plus_bf_plus_ce_plus_df, trivial_result);

    Plaintext decrypted_trivial_result;
    decryptor.decrypt(trivial_result, decrypted_trivial_result);
    assert(decrypted_trivial_result.is_zero());

    Plaintext result_way_one;
    decryptor.decrypt(e_times_a_plus_c_plus_f_times_b_plus_d, result_way_one);

    Plaintext result_way_two;
    decryptor.decrypt(ae_plus_bf_plus_ce_plus_df, result_way_two);
    assert(result_way_one == result_way_two);

    assert(trivial_result.is_transparent());

    std::cout << "Worked" << std::endl;

    return 0;
}

void add_plaintexts(const EncryptionParameters &enc_params, const Plaintext &a, const Plaintext &c, Plaintext &a_plus_c) {
    Plaintext to_add;
    if(a.coeff_count() > c.coeff_count()){
        a_plus_c = a;
        to_add = c;
    }
    else{
        a_plus_c = c;
        to_add = a;
    }
    for(int current_coeff =0; current_coeff < to_add.coeff_count(); current_coeff++){
        a_plus_c[current_coeff] = (a_plus_c[current_coeff] + to_add[current_coeff])%enc_params.plain_modulus().value();
    }
}

[WeiDaiWD]

My best guess is that, if you use this method to create coeff_modulus, you should get transparent ciphertext. Would you please give it a try?

The reason behind it is that, when primes in coeff_modulus are not congruent to 1 modulo the plain_modulus, the correction_factor of each ciphertext become not 1 and gets modified whenever there is an addition or multiplication. This introduces some inconsistency which makes BGV operations neither associative or commutative in the ciphertext space. They always preserve associativity and commutativity in the plaintext space.

[elkanatovey]

I tried your suggestion and I still have the same issue. I'm attaching an updated example that still won't work after selecting the coefficient modulus as per your suggestion. Do you have any other ideas?

//
// test that  ([x, y] * [[a, b], [c, d]]) * [e, f]^T = [x, y] * ([[a, b], [c, d]] * [e, f]^T) in the ciphertext space
// were e, f are both ciphertexts and x, y are both set to 1.
//
// in other words, test that e * (a + c) + f * (b + d) = (a*e + b*f) + (c*e + d*f)
//

#include <cassert>
#include <cstdint>
#include <memory>
#include <seal/seal.h>

using namespace std::chrono;
using namespace std;
using namespace seal;

void add_plaintexts(const EncryptionParameters &enc_params, const Plaintext &a, const Plaintext &c, Plaintext &a_plus_c);

int main(int argc, char *argv[]) {

    uint32_t N = 8192;

    uint32_t logt = 20;

    EncryptionParameters enc_params(scheme_type::bgv);

    // Generates all parameters

    cout << "Main: Generating SEAL parameters" << endl;
    enc_params.set_poly_modulus_degree(N);
    auto plaimmod = PlainModulus::Batching(N, logt + 1);
    enc_params.set_plain_modulus(plaimmod);

    auto coeffmod = CoeffModulus::Create(N, plaimmod, {43, 43, 43, 44, 44});

    enc_params.set_coeff_modulus(coeffmod);

    SEALContext context(enc_params, true);
    KeyGenerator keygen(context);

    SecretKey secret_key = keygen.secret_key();
    Encryptor encryptor(context, secret_key);
    Decryptor decryptor(context, secret_key);
    Evaluator evaluator(context);

    cout << "Main: SEAL parameters generated" << endl;

    cout << "Main: generating matrices" << endl;

    std::string poly = "144D8Cx^1 + 26B95";
    Plaintext a(poly);
    Plaintext b(poly);
    Plaintext c(poly);
    Plaintext d(poly);
    Plaintext e(poly);
    Plaintext f(poly);

    Ciphertext e_encrypted;
    Ciphertext f_encrypted;

    encryptor.encrypt_symmetric(e, e_encrypted);
    encryptor.encrypt_symmetric(f, f_encrypted);
    std::cout << "Encrypting e f" << std::endl;
    std::cout << "Plain Modulus:"<<enc_params.plain_modulus().value() << std::endl;

    std::cout << "calculating e * (a + c) + f * (b + d)"<< std::endl;

    Plaintext a_plus_c;
    Plaintext b_plus_d;

    add_plaintexts(enc_params, a, c, a_plus_c);
    add_plaintexts(enc_params, b, d, b_plus_d);

    std::cout << a_plus_c.to_string()<<" plaintext addition result..........................."<< std::endl;
    Ciphertext e_times_a_plus_c; // e * (a + c)
    Ciphertext f_times_b_plus_d; // f * (b + d)
    evaluator.multiply_plain(e_encrypted, a_plus_c, e_times_a_plus_c);
    evaluator.multiply_plain(f_encrypted, b_plus_d, f_times_b_plus_d);

    Ciphertext e_times_a_plus_c_plus_f_times_b_plus_d; // e * (a + c) + f * (b + d)
    evaluator.add(e_times_a_plus_c, f_times_b_plus_d, e_times_a_plus_c_plus_f_times_b_plus_d);

    std::cout << "finished e * (a + c) + f * (b + d)"<< std::endl;//1958182 1

    std::cout << "calculating (a*e + b*f) + (c*e + d*f)"<< std::endl;//1958182 1
    Ciphertext a_times_e; // a * e
    Ciphertext b_times_f; // b * f
    Ciphertext c_times_e; // c * e
    Ciphertext d_times_f; // d * f
    evaluator.multiply_plain(e_encrypted, a, a_times_e);
    evaluator.multiply_plain(f_encrypted, b, b_times_f);
    evaluator.multiply_plain(e_encrypted, c, c_times_e);
    evaluator.multiply_plain(f_encrypted, d, d_times_f);

    Ciphertext ae_plus_bf; // (a*e + b*f)
    Ciphertext ce_plus_df; // (c*e + d*f)
    evaluator.add(a_times_e, b_times_f, ae_plus_bf);
    evaluator.add(c_times_e, d_times_f, ce_plus_df);

    Ciphertext ae_plus_bf_plus_ce_plus_df; // (a*e + b*f) + (c*e + d*f)
    evaluator.add(ae_plus_bf, ce_plus_df, ae_plus_bf_plus_ce_plus_df);
    std::cout << "finished (a*e + b*f) + (c*e + d*f)"<< std::endl;//1958182 1

    Ciphertext trivial_result;
    evaluator.sub(e_times_a_plus_c_plus_f_times_b_plus_d, ae_plus_bf_plus_ce_plus_df, trivial_result);

    Plaintext decrypted_trivial_result;
    decryptor.decrypt(trivial_result, decrypted_trivial_result);
    cout<<decryptor.invariant_noise_budget(trivial_result)<<"....................."<<endl;
    assert(decrypted_trivial_result.is_zero());

    Plaintext result_way_one;
    decryptor.decrypt(e_times_a_plus_c_plus_f_times_b_plus_d, result_way_one);

    Plaintext result_way_two;
    decryptor.decrypt(ae_plus_bf_plus_ce_plus_df, result_way_two);
    assert(result_way_one == result_way_two);

    assert(trivial_result.is_transparent());

    std::cout << "Worked" << std::endl;

    return 0;
}

void add_plaintexts(const EncryptionParameters &enc_params, const Plaintext &a, const Plaintext &c, Plaintext &a_plus_c) {
    Plaintext to_add;
    if(a.coeff_count() > c.coeff_count()){
        a_plus_c = a;
        to_add = c;
    }
    else{
        a_plus_c = c;
        to_add = a;
    }
    for(int current_coeff =0; current_coeff < to_add.coeff_count(); current_coeff++){
        a_plus_c[current_coeff] = (a_plus_c[current_coeff] + to_add[current_coeff])%enc_params.plain_modulus().value();
    }
}

[elkanatovey]

Hi Again, After some further testing, I've discovered that the above issue of not receiving a transparent ciphertext at the end only happens in computations that have ciphertext-plaintext operations. If I encrypt all my data and use only ciphertext-ciphertext operations than the computation works as expected. This is true for actual encryption or a "dummy encryption" where I add my plaintext data to a transparent ciphertext in order to use evaluator.multiply() instead of evaluator.multiply_plain().

Is it possible that there is something in how the plaintext is represented when executing evaluator.multiply_plain() that could be causing this?

The below code is an example of the problem, I'd expect result to be transparent at the end of execution but this only seems to happen for small plaintext coefficients.

evaluator.add_plain(transparent_ciphertext, ptext, x);
evaluator.multiply_inplace(x, data);
evaluator.multiply_plain(ptext, data, y);
evaluator.sub(x, y, result);

[WeiDaiWD]

@elkanatovey Sorry for the late response. Evaluator methods in SEAL are not commutative, although the underly plaintext arithmetic they preserve is commutative. The reason is Plaintext is first mapped to a larger Ciphertext's RNS space before being multiplied with a Ciphertext, see lines 1935~1968 in "evaluator.cpp". For example, suppose you plaintext modulus is 7, plaintexts are 1 and 6, ciphertext modulus is 37; although 1 and 6 in plaintext space are mapped to 1 and 6 in ciphertext space, 1+6=0 mod 7 in plaintext space and is mapped to 0 in ciphertext space, while 1+6=7 mod 37 in ciphertext space. This is why you do not get "transparent" ciphertexts.

[elkanatovey]

@WeiDaiWD No problem. As far as I can tell, the only method that doesn't commute is Evaluator.multiply_plain() and it's also the only one that does the RNS mapping. Why is it that the other methods don't need to do said mapping?

I also noticed that the RNS mapping is only problematic for coefficients that are mapped to negative numbers in a plaintext for plaintext multiplication but not in a newly encrypted ciphertext for ciphertext multiplication. Do you know why it's so?

Essentially, the only time that this specific RNS mappping is done is in Evaluator.multiply_plain() and I'd appreciate some intuition as to why, if possible.

[WeiDaiWD]

Why is it that the other methods don't need to do said mapping?

Among Evaluator methods that involve a Plaintext, only multply_plain() affects the second polynomial in a Ciphertext; a transparent ciphertext is defined by that polynomial.

I also noticed that the RNS mapping is only problematic for coefficients that are mapped to negative numbers in a plaintext for plaintext multiplication but not in a newly encrypted ciphertext for ciphertext multiplication. Do you know why it's so?

I'm not clear on what you meant by "problematic".

the only time that this specific RNS mappping is done is in Evaluator.multiply_plain()

Plaintexts and ciphertexts are represented with different algebraic structures. The mapping transforms a plaintext into an image in the ciphertext structure. It is also done in add_plain_without_scaling_variant which is called by Evaluator::add_plain_inplace.

[elkanatovey]

Among Evaluator methods that involve a Plaintext, only multply_plain() affects the second polynomial in a Ciphertext; a transparent ciphertext is defined by that polynomial.

Are you saying that this mapping is to ensure that plaintext multiplication doesn't result in a transparent ciphertext? If so, why is this problematic? it shouldn't reveal anything about the ciphertext being multiplied with.

I'm not clear on what you meant by "problematic".

I mean that associativity of multiplication holds for for plaintexts whose coefficients are mapped to positive numbers - the coefficients that are less than 0.5t. My problem is why doesn't it work for plaintexts with coefficients mapped to negative numbers

Plaintexts and ciphertexts are represented with different algebraic structures. The mapping transforms a plaintext into an image in the ciphertext structure. It is also done in add_plain_without_scaling_variant which is called by Evaluator::add_plain_inplace.

Evaluator::add_plain actually associates and commutes. I'd appreciate some insight on the difference.