Bivariate pbs

Zama TFHE-rs
1

hello, sorry I wanted to carry on the last conversation but the topic has been closed two days ago… When you do that:

        self.unchecked_scalar_mul_assign(ct_left, acc.ct_right_modulus.0 as u8);

        unchecked_add_assign(ct_left, ct_right, self.max_noise_level);

how do you know that the carry of the right ciphertext is empty?

2

Hello,

It’s not clear from where you took this code, it possibly a precondition that the carry of the right ciphertext is empty

Anyhow, you can check this by checking ct_right.degree < ct_right.message_modulus

3

Hello, thanks for the reply. It’s in unchecked_apply_lookup_table_bivariate_assign in bivariate_pbs for shortint.
There is actually an assert but not an if, so it’s not clear what happens when the carry is non empty, besides, those check the message modulus no? Confusion comes from that it says nothing about the carry, there is something missing in my understanding. Nevermind, I will try to handle that by myself, thanks.

4

If it comes from an unchecked_ it means its a precondition to the function that the ct_right’s carry is empty, and so that’s on the caller to make sure its the case, that is why there is an assert to still catch mis-calls, the smart_ equivalent will do the necessary cleaning

The degree is the max possible value currently possibly encrypted in the ciphertext, so checking that degree < message_modulus checks that the carry is empty

1 Like
5

you’re right silly me, but i’m using it with no check whatsoever for multiplication between two bits and if the carry is twice bigger than the message space it always work i don’t get why, while if the carry is only the same size, it does not.

6

Actually the assert in the unchecked_apply_lookup_table_bivariate_assign checks something other than whether the ct_right’s carry is empty, it checks that max value currently encrypted, is <= than what is allowed by the bivariate LUT. Which depending on how you created the bivariate lookup table it may be equivalent or not

Do you have concrete examples to share ?

7

I just make one

sk.unchecked_mul_lsb(&ct_l,&ct_r)

then unchecked additions
then an unchecked multiplication
then unchecked additions
then an unchecked multiplication
I tried with smart but the cloning takes too much time and weirdly enough the unchecked multiplication is always right. no matter the initial value
Parameter: V1_4_PARAM_MESSAGE_1_CARRY_2_KS_PBS_GAUSSIAN_2M128
It’s ok, I think I know why. When the carry is bigger there are not enough additions to push the carry so that it wraps around and changes the message bits.
Sorry

9

It’s funny because in the morning I should say “I get it” and it’s the opposite. I get it less. Say I have a 1 message modulus and 1 message carry. Say two ciphertexts are added and tge carry is non empty. the cases are 1+3≡0 mod 4 which translates to 1+1≡0 mod 2 in the message space 0+2 ≡2 mod 4 => 0+0≡ 0 mod 2 in the message space 2+3≡5 mod 4 => 0+1≡1 mod 2 in the message space. 3+3≡2 mod 4 => 1+1≡0 mod 2 in the message space, so I really do not get how the carry could affect the value of the message soace it does not make sense at all to me, and no matter whether I use 4 or 8 as a modulus, it should be the same.

10

I don’t understand what you mean by that, and generally speaking I don’t get what you don’t understand

In a message earlier you said you use unchecked_mul_lsb, this function uses a bivariate PBS, the precondition (which is not checked or not fully checked by an unchecked_ function) is that you can concatenate the 2 inputs into 1 single block, which for symmetric parameters like MESSAGE_1_CARRY_1, MESSAGE_2_CARRY_2, means carries should be clean, otherwise whether the value ends up to be correct depends on the actual encrypted value and so its not safe to compute.

11

sorry, let me rephrase it, and not sound like chatgpt.
i have a program where i use both mul_lsb and add.
if i use a carry of 2, i have no wrong values in my program while if i take a carry of 1 i have plenty of errors. problems are

  1. the additions i make are bitwise additions, so the carry should not have an influence here so the error should be on mul_lsb
  2. mul_lsb or smart_mul_lsb make two pbs one to extract the message, the other to perform the multiplication after having shifted the message value of the ctl of message modulus.
    i use unchecked_mul_lsb which seems to not perform the additionnal pbs for message extraction and the program works fine when the carry is 2 but not when it’s 1. is it just by chance? the likeliness of it is quite small
12

The carry will have an influence just by existing, when you use parmeters with 1 bit of message, and add somes ciphertext, there will still be a carry

Also what you need to know is that there is a padding bit, so with V1_4_PARAM_MESSAGE_1_CARRY_1_KS_PBS_GAUSSIAN_2M128 there are 1 + 1 + 1 = 3 bits, but padding bit is a special bit that needs to stay 0 in order to have a correct PBS output, when the padding bit is not zero, the output of the PBS is the negation

Example 1, getting correct result, but by luck

fn main() {
    let params = V1_4_PARAM_MESSAGE_1_CARRY_1_KS_PBS_GAUSSIAN_2M128;
    let (cks, sks) = gen_keys(params);

    let mut a = cks.encrypt(1);
    let b = cks.encrypt(1);

    sks.unchecked_add_assign(&mut a, &b);
    assert_eq!(cks.decrypt_message_and_carry(&a), 2);

    // mul_lsb is going to do a PBS on a ciphertext that encrypts
    // (a * 2) + b = 4 + 1 = 5 which is 0b101, the padding bit is no longer 0
    let c = sks.unchecked_mul_lsb(&a, &b);
   // luckily the result is still correct, (2 * 1) % 2 = 0
    assert_eq!(cks.decrypt_message_and_carry(&c), 0); 

    let c = sks.unchecked_mul_lsb(&b, &a);
    assert_eq!(cks.decrypt_message_and_carry(&c), 0);
}

Example 2, getting incorrect result

We do one more addition

fn main() {
    let params = V1_4_PARAM_MESSAGE_1_CARRY_1_KS_PBS_GAUSSIAN_2M128;
    let (cks, sks) = gen_keys(params);

    let mut a = cks.encrypt(1);
    let b = cks.encrypt(1);

    sks.unchecked_add_assign(&mut a, &b);
    sks.unchecked_add_assign(&mut a, &b);
    assert_eq!(cks.decrypt_message_and_carry(&a), 3);

    // mul_lsb is going to do a PBS on a ciphertext that encrypts
    // (a * 2) + b = 6 + 1 = 7 which is 0b111, the padding bit is no longer 0
    let c = sks.unchecked_mul_lsb(&a, &b);
    // incorrect (3 * 1) % 2 = 1
    assert_eq!(cks.decrypt_message_and_carry(&c), 7); 

    let c = sks.unchecked_mul_lsb(&b, &a);
    assert_eq!(cks.decrypt_message_and_carry(&c), 0); // incorrect
}

Example 3 with 2 bits of carry

fn main() {
    let params = V1_4_PARAM_MESSAGE_1_CARRY_2_KS_PBS_GAUSSIAN_2M128;
    let (cks, sks) = gen_keys(params);

    let mut a = cks.encrypt(1);
    let b = cks.encrypt(1);

    sks.unchecked_add_assign(&mut a, &b);
    sks.unchecked_add_assign(&mut a, &b);
    assert_eq!(cks.decrypt_message_and_carry(&a), 3);

    // mul_lsb is going to do a PBS on a ciphertext that encrypts
    // (a * 2) + b = 6 + 1 = 7 which is 0b0111the padding bit is still 0, so its ok
    let c = sks.unchecked_mul_lsb(&a, &b);
    assert_eq!(cks.decrypt_message_and_carry(&c), 1);

    let c = sks.unchecked_mul_lsb(&b, &a);
    assert_eq!(cks.decrypt_message_and_carry(&c), 1);

However, I would point out that, the degree is not the only thing to keep track of, in order to ensure the correctness, there is also the noise level, which grows on each additions, and scalar_muliplication (used to do a bivariate PBS), and example 1&2 are also not OK with regards to the nosie level. If you run them with the noise-asserts feature you’ll get a panic, however, the example 3 is fine

13

Thank you, I did not think about the padding bit. I do not have more than 3 sequential additions before the pbs, I need to be careful with the padding bit then.