PBS not working as expected

Zama Concrete Library (Deprecated)
1

Hi! First of all, I am not at all a crypto expert.
I am trying to compare two numbers of any length. I am doing so by arranging the digits in each number inside a vector of FheUint4 shortints. So, each of these elements goes from 0 to 9, so I don’t use the total range of the 4 bit integer ciphertext.

I use two instances of the PBS feature in Concrete in my code: The OtherLT::set_lowest() and the OtherLT::compare() in the following code:

fn operate(number_a: Vec<FheUint4>, number_b: Vec<FheUint4>, client_key: &ClientKey) -> FheUint4 {
        let mut order: FheUint4 = (number_a.first().unwrap() * 0u8).clone();
        for (digit_a, digit_b) in number_a.iter().zip(number_b.iter()) {
            let _order = digit_a.bivariate_function(digit_b, OtherLT::compare);
            println!("//\nOrder: {}, Comparing ({},{}), _order: {}", order.decrypt(&client_key), digit_a.decrypt(&client_key), digit_b.decrypt(&client_key), _order.decrypt(&client_key));
            order = order.bivariate_function(&_order, OtherLT::set_lowest);
            println!("Order: {}\n", order.decrypt(&client_key));
        }
        order
    }

Here I go through each pair of digits from left to right and compare them to see which is the bigger one. Then, I store it in the “order” variable which is a way of setting for the rest of the loop which number is the smaller one.
The functions that are being used for the PBS are:

    fn compare(a: u8, b: u8) -> u8 {
        if a > b {
            2
        } else if a < b {
            1
        } else {
            0
        }
    }
    fn set_lowest(order: u8, _order: u8) -> u8 {
        if order != 0 {
            order
        } else {
            _order
        }
    }

The compare LUT evaluation seems to be working correctly, but the set_lowest is not:

image
image792×865 39.9 KB

Here is a screenshot of some debug messages showing the comparison between the numbers 352 000 010 and 252 000 012. I would expect the "Order: " to print 2 in the second iteration after evaluating the set_lowest() the second time, since in that instance the “order” variable is 2, if 2 != 0 should evaluate to returning the “order” value. The exact same python code (working on unencrypted) data returns the correct results, so I assume that the logic is correct but I am missing something crypto related or Concrete related.

Any help would be much appreciated, Thank you!!

2

Hello,

There is indeed a problem with concrete, however, concrete is not supported anymore as the work has shifted to the tfhe-rs crate.

We identified the same bug in tfhe-rs a few days ago and a fix is comming to it.
Also parts of the high-level API exposed by concrete is likely going to be integrated back into tfhe-rs.
(Using a custom branch with both of these, i was able to run your code and it gave me the correct result)

Sadly I don’t think I will be able to provide you with a work around that uses the concrete crate

3 Likes
3

Hi! Oh that’s good! I am glad that you found the bug! I was eventually going to switch to tfhe-rs but was still more used to the concrete API.
So, for it to be working on tfhe-rs on a experimental branch is what I need.
What implementation/API of the tfhe-rs PBS did you choose to replace the one I am using?
I am asking this since there is multiple ones, the one without padding and another for the chinese reminder theorem representation and also the normal PBS. Correct me if I am wrong on anything I am saying.

4

It is still using the bivariate PBS as this is where the bug was. And it does not use the without_padding one, nor the Chinese Remainder Theorem (this one is used as one of the two ways we have to represent larger (>8bits integers))

You can try by using the following code (note that the branch is not likely to stay online for more than a few months)

Cargo.toml

[package]
name = "something"
version = "0.1.0"
edition = "2021"

[dependencies]
tfhe = { git = "https://github.com/zama-ai/tfhe-rs", branch = "new-front-bivarfix", features = ["shortint", "x86_64-unix"] }

src/main.rs:

use tfhe::prelude::*;
use tfhe::{generate_keys, set_server_key, ClientKey, ConfigBuilder, FheUint4};

mod OtherLT {
    pub fn compare(a: u8, b: u8) -> u8 {
        if a > b {
            2
        } else if a < b {
            1
        } else {
            0
        }
    }
    pub fn set_lowest(order: u8, _order: u8) -> u8 {
        if order != 0 {
            order
        } else {
            _order
        }
    }
}

fn operate(number_a: Vec<FheUint4>, number_b: Vec<FheUint4>, client_key: &ClientKey) -> FheUint4 {
    let mut order: FheUint4 = (number_a.first().unwrap() * 0u8).clone();
    for (digit_a, digit_b) in number_a.iter().zip(number_b.iter()) {
        let mut _order = digit_a.bivariate_function(digit_b, OtherLT::compare);
        println!(
            "//\nOrder: {}, Comparing ({},{}), _order: {}",
            order.decrypt(&client_key),
            digit_a.decrypt(&client_key),
            digit_b.decrypt(&client_key),
            _order.decrypt(&client_key)
        );
        order = order.bivariate_function(&_order, OtherLT::set_lowest);
        println!("Order: {}\n", order.decrypt(&client_key));
    }
    order
}

fn main() {
    let config = ConfigBuilder::all_disabled().enable_default_uint4().build();

    let (cks, sks) = generate_keys(config);

    set_server_key(sks);

    let clear_a = vec![3, 5, 2, 0, 0, 0, 0, 1, 0];
    let clear_b = vec![2, 5, 2, 0, 0, 0, 0, 1, 2];

    let number_a = clear_a
        .iter()
        .copied()
        .map(|n| FheUint4::try_encrypt(n, &cks))
        .collect::<Result<Vec<_>, _>>()
        .unwrap();

    let number_b = clear_b
        .iter()
        .copied()
        .map(|n| FheUint4::try_encrypt(n, &cks))
        .collect::<Result<Vec<_>, _>>()
        .unwrap();

    operate(number_a, number_b, &cks);
}
1 Like
5

Just tested on my side and yup! It works :slight_smile: . Thank you very much for the help!
Side question that came up while I was testing out the code.
On my concrete code I was saving the ClientKey and ServerKey using serialization, with bincode.
In this branch the tfhe::ClientKey and tfhe::ServerKey do not implement Serialize.
Is this because this branch doesn’t have that work and so, when it is eventually merged to the main branch this will all be fixed? Thank you again!!

6

Yes it is an oversight when doing the transition it will exist in the final code.

I pushed a fix to the same branch as the example which should allow to serialize/deserialize the different keys.

1 Like