Scale mismatch after one multiplication

[ttttonyhe]

Hello @D4rkCrypto,

Thank you for your continuous effort in maintaining this project! I was wondering if I can bring your attention to the following two issues that potentially need to be addressed promptly:

1. Unable to perform more than one multiplication consecutively

I noticed that there seems to be no tests covering the case where more than one multiplication are performed consecutively like so:

PhantomCiphertext x_cipher, y_cipher;
public_key.encrypt_asymmetric(context, x_plain, x_cipher);
public_key.encrypt_asymmetric(context, y_plain, y_cipher);

PhantomCiphertext xy_prod(x_cipher);
multiply_inplace(context, xy_prod, y_cipher);
relinearize_inplace(context, xy_prod, relin_keys);
rescale_to_next_inplace(context, xy_prod);

PhantomCiphertext xxy_prod(xy_prod);
mod_switch_to_next_inplace(context, x_cipher);
multiply_inplace(context, xxy_prod, x_cipher); // std::invalid_argument: scale mismatch
relinearize_inplace(context, xxy_prod, relin_keys);
rescale_to_next_inplace(context, xxy_prod);

When running the above code, I got std::invalid_argument exception with message scale mismatch.

Looking at the code in evaluate.cu, it seems like the verification for matching scales between two ciphertexts is simply done via an if statement: if (encrypted1.scale() != encrypted2.scale()). I'm not sure if that's the correct way to do it because even after rescaling two ciphertexts might not have the exact same scale, though they should be very close. In Microsoft SEAL, they instead use something like are_close(encrypted1.scale(), encrypted2.scale()) to achieve the same purpose.

2. rescale_to_next_inplace, mod_switch_to_next_inplace removed

Additionally, I noticed that rescale_to_next_inplace/mod_switch_scale_to_next_inplace, mod_switch_drop_to_next_inplace have been removed in the latest version of the repo, and mod_switch_to_next_inplace now does mod switching and rescaling at the same time. May I ask why are they removed because I think having them as separate functions could be more useful.

Thank you!

[D4rkCrypto]

Thanks for trying the latest version and giving feedbacks! To the first question, we didn't handle this situation properly, I will look into SEAL's code and make a patch. you can get a quick fix by manually set the scale to be the same. To the second question, in fact CKKS's rescaling is the same as BFV/BGV's mod switching, so I unified the function. You can just call mod_switch_to_next to replace legacy rescale_to_next. Drop to next function is not needed in my opinion so I just removed it.

[ttttonyhe]

Thanks for your reply!

I also found that using the latest version the scale actually differs quite a bit (running SEAL's are_close (found a function with the same name in your repo) yields false) after multiplication, was wondering if you can reproduce this:

PhantomCiphertext x;
PhantomCiphertext x2, x3;

x2 = multiply(context, x, x);
relinearize_inplace(context, x2, *relin_keys);
mod_switch_to_next_inplace(context, x2);

mod_switch_to_inplace(context, x, x2.chain_index());
x3 = multiply(context, x, x2); // scale mismatch

The scales look like this:

• x2 scale: 1.09952e+12
• x scale: 1.09951e+12

[D4rkCrypto]

It's a severe bug to me now. I will fix it first and get back to you.

[D4rkCrypto]

Please check the lastest commit: https://github.com/encryptorion-lab/phantom-fhe/commit/4b381cb30998870a071e65dedf41a5ab14a3ef74

Also a running demo: https://github.com/encryptorion-lab/phantom-fhe/blob/4b381cb30998870a071e65dedf41a5ab14a3ef74/example/3_ckks.cu#L491-L503

Sorry that I didn't do a thorough correctness verification for these situations. Now I have fixed the bug and added more tests, so the code is rolled back to old version which has standalone rescale function for CKKS. You can refer to SEAL's tricks for dealing with the scale difference: https://github.com/microsoft/SEAL/blob/3a05febe18e8a096668cd82c75190255eda5ca7d/native/examples/5_ckks_basics.cpp#L248

[ttttonyhe]

Hi @D4rkCrypto, I still think there might be something wrong with the rescaling/multiplication process. Here's a demo:

cout << "x scale: " << x.scale() << endl; // x scale: 1.09951e+12
sub_plain(context, x, p0, b0);
cout << "b0 scale: " << b0.scale() << endl; // b0 scale: 1.09951e+12
multiply_plain_inplace(context, b0, p1);
cout << "b0 scale: " << b0.scale() << endl; // b0 scale: 1.20893e+24
rescale_to_next_inplace(context, b0);
cout << "b0 scale: " << b0.scale() << endl; // b0 scale: 1.09952e+12

After rescaling, b0 should have a scale very close to 1.09951e+12 instead of 1.09952e+12 which is a lot larger than 1.09951e+12. SEAL's trick works only when two ciphertexts have approximately equal scales, which I believe is not the case with this one. Bascially, are_close between the scale before and the scale after produces false.

Running the same code with SEAL using the same parameters results in the correct behaviour (rescaled to 1.09951e+12).

Let me know if you can reproduce this, thank you!

x scale: 1099511627776.000000 b0 scale: 1099511627776.000000 b0 scale: 1208925819614629174706176.000000 b0 scale: 1099522637933.250977

[D4rkCrypto]

There is a difference in implementation of creating modulus chain. In SEAL, modulus of the same bit size are generated in descending order. https://github.com/microsoft/SEAL/blob/3a05febe18e8a096668cd82c75190255eda5ca7d/native/src/seal/modulus.cpp#L174

But in Phantom, it is in ascending order. https://github.com/encryptorion-lab/phantom-fhe/blob/4b381cb30998870a071e65dedf41a5ab14a3ef74/src/modulus.cu#L101-L102

I'm figuring out whether this affects precision or other stuff.

[D4rkCrypto]

It seems fine to just remove std::reverse line. It should be the same behaviour as SEAL now.

BTW, OpenFHE implements a better technique for generating CKKS modulus chain. Phantom may adapt this later. https://github.com/openfheorg/openfhe-development/blob/13bf46f683483da1fe77f591b98035fa455740c6/src/pke/lib/scheme/ckksrns/ckksrns-parametergeneration.cpp#L137

[ttttonyhe]

Thank you so much!

[ttttonyhe]

Hey @D4rkCrypto, sorry for the back and forth, I just found out that my previous issues was probably not caused by whether are_close function was used or not, but the culprit was actually not generating modulus in descending order, which was fixed by your latest commit.

As a matter of fact, I think SEAL is not actually checking for matching scales between two plaintexts/ciphertexts anymore in their evaluator.cpp code, except for add_inplace, sub_inplace, add_plain_inplace and sub_plain_inplace. I think you might want to just remove the scale checking statements from Phantom's evaluation functions (except for those four).

Thank you!

[D4rkCrypto]

Thanks for pointing out this, I will make some adjustments.