arrow-left

Only this pageAll pages
gitbookPowered by GitBook
1 of 45

0.4

Loading...

Getting Started

Loading...

Loading...

Loading...

Loading...

Loading...

Tutorials

Loading...

Loading...

How To

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Fine-grained APIs

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Application Tutorials

Loading...

Loading...

Loading...

Crypto Core API [Advanced users]

Loading...

Loading...

Developers

Loading...

API references

Quick Start

hashtag
Quick Start

The basic steps for using the high-level API of TFHE-rs are:

  1. Importing the TFHE-rs prelude;

  2. Client-side: Configuring and creating keys;

  3. Client-side: Encrypting data;

  4. Server-side: Setting the server key;

  5. Server-side: Computing over encrypted data;

  6. Client-side: Decrypting data.

Here is a full example (combining the client and server parts):

The default configuration for x86 Unix machines:

Configuration options for different platforms can be found . Other rust and homomorphic types features can be found .

hashtag
Imports.

tfhe uses traits to have a consistent API for creating FHE types and enable users to write generic functions. To be able to use associated functions and methods of a trait, the trait has to be in scope.

To make it easier, the prelude 'pattern' is used. All of the important tfhe traits are in a prelude module that you can glob import. With this, there is no need to remember or know the traits that you want to import.

hashtag
1. Configuring and creating keys.

The first step is the creation of the configuration. The configuration is used to declare which type you will (or will not) use, as well as enabling you to use custom crypto-parameters for these types. Custom parameters should only be used for more advanced usage and/or testing.

A configuration can be created by using the ConfigBuilder type.

In this example, 8-bit unsigned integers with default parameters are used. The integers feature must also be enabled, as per the table on .

The config is generated by first creating a builder with all types deactivated. Then, the integer types with default parameters are activated, since we are going to use FheUint8 values.

The generate_keys command returns a client key and a server key.

The client_key is meant to stay private and not leave the client, whereas the server_key can be made public and sent to a server for it to enable FHE computations.

hashtag
2. Setting the server key.

The next step is to call set_server_key

This function will move the server key to an internal state of the crate and manage the details to give a simpler interface.

hashtag
3. Encrypting data.

Encrypting data is achieved via the encrypt associated function of the FheEncrypt trait.

Types exposed by this crate implement at least one of FheEncrypt or FheTryEncrypt to allow encryption.

hashtag
4. Computation and decryption.

Computations should be as easy as normal Rust to write, thanks to the usage of operator overloading.

The decryption is achieved by using the decrypt method, which comes from the FheDecrypt trait.

here
here
this page
use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8};
use tfhe::prelude::*;

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

    // Client-side
    let (client_key, server_key) = generate_keys(config);

    let clear_a = 27u8;
    let clear_b = 128u8;

    let a = FheUint8::encrypt(clear_a, &client_key);
    let b = FheUint8::encrypt(clear_b, &client_key);

    //Server-side
    set_server_key(server_key);
    let result = a + b;

    //Client-side
    let decrypted_result: u8 = result.decrypt(&client_key);

    let clear_result = clear_a + clear_b;

    assert_eq!(decrypted_result, clear_result);
}
tfhe = { version = "0.4.4", features = ["integer", "x86_64-unix"]}
use tfhe::prelude::*;
use tfhe::{ConfigBuilder, generate_keys};

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

    let (client_key, server_key) = generate_keys(config);
}
use tfhe::{ConfigBuilder, generate_keys, set_server_key};

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

    let (client_key, server_key) = generate_keys(config);

    set_server_key(server_key);
}
let clear_a = 27u8;
let clear_b = 128u8;

let a = FheUint8::encrypt(clear_a, &client_key);
let b = FheUint8::encrypt(clear_b, &client_key);
let result = a + b;
let decrypted_result: u8 = result.decrypt(&client_key);

let clear_result = clear_a + clear_b;

assert_eq!(decrypted_result, clear_result);

Installation

hashtag
Importing into your project

To use TFHE-rs in your project, you first need to add it as a dependency in your Cargo.toml.

If you are using an x86 machine:

If you are using an ARM machine:

circle-info

You need to use a Rust version >= 1.72 to compile TFHE-rs.

circle-check

When running code that uses TFHE-rs, it is highly recommended to run in release mode with cargo's --release flag to have the best possible performance

hashtag
Supported platforms

TFHE-rs is supported on Linux (x86, aarch64), macOS (x86, aarch64) and Windows (x86 with RDSEED instruction).

OS
x86
aarch64
tfhe = { version = "0.4.4", features = [ "boolean", "shortint", "integer", "x86_64-unix" ] }

Linux

x86_64-unix

aarch64-unix*

macOS

x86_64-unix

aarch64-unix*

Windows

x86_64

Unsupported

tfhe = { version = "0.4.4", features = [ "boolean", "shortint", "integer", "aarch64-unix" ] }

Contributing

There are two ways to contribute to TFHE-rs. You can:

  • open issues to report bugs and typos and to suggest ideas;

  • ask to become an official contributor by emailing [email protected]. Only approved contributors can send pull requests, so get in touch before you do.

Use Trivial Ciphertext

Sometimes, the server side needs to initialize a value. For example, when computing the sum of a list of ciphertext, one might want to initialize the sum variable to 0.

Instead of asking the client to send a real encryption of zero, the server can do a trivial encryption

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

let config = ConfigBuilder::all_disabled()
    .enable_default_integers()
    .build();
let (client_key, sks) = generate_keys(config);

set_server_key(sks);

let a = FheUint8::try_encrypt_trivial(234u8).unwrap();

let clear: u8 = a.decrypt(&client_key);
assert_eq!(clear, 234);

A trivial encryption will create a ciphertext that contains the desired value, however, the 'encryption' is trivial that is, it is not really encrypted: anyone, any key can decrypt it.

Note that when you want to do an operation that involves a ciphertext and a clear value, you should only use a trivial encryption of the clear value if the ciphertext/clear-value operation (often called scalar operation) you want to run is not supported.

hashtag
Example

Cryptographic Parameters

integer does not come with its own set of parameters. Instead, it relies on parameters from shortint. Currently, parameter sets having the same space dedicated to the message and the carry (i.e. PARAM_MESSAGE_{X}_CARRY_{X} with X in [1,4]) are recommended. See for more details about cryptographic parameters, and to see how to properly instantiate integers depending on the chosen representation.

here
here
use tfhe::prelude::*;
use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint32};

let config = ConfigBuilder::all_disabled()
    .enable_default_integers()
    .build();
let (client_key, sks) = generate_keys(config);

set_server_key(sks);

// This is going to be faster
let a = FheUint32::try_encrypt(2097152u32, &client_key).unwrap();
let shift = 1u32;
let shifted = a << shift;
let clear: u32 = shifted.decrypt(&client_key);
assert_eq!(clear, 2097152 << 1);

// This is going to be slower
let a = FheUint32::try_encrypt(2097152u32, &client_key).unwrap();
let shift = FheUint32::try_encrypt_trivial(1).unwrap();
let shifted = a << shift;
let clear: u32 = shifted.decrypt(&client_key);
assert_eq!(clear, 2097152 << 1);

Serialization/Deserialization

Since the ServerKey and ClientKey types both implement the Serialize and Deserialize traits, you are free to use any serializer that suits you to save and load the keys to disk.

Here is an example using the bincode serialization library, which serializes to a binary format:

use std::fs::File;
use std::io::{Write, Read};
use tfhe::boolean::prelude::*;

fn main() {
// We generate a set of client/server keys, using the default parameters:
    let (client_key, server_key) = gen_keys();

// We serialize the keys to bytes:
    let encoded_server_key: Vec<u8> = bincode::serialize(&server_key).unwrap();
    let encoded_client_key: Vec<u8> = bincode::serialize(&client_key).unwrap();

    let server_key_file = "/tmp/ser_example_server_key.bin";
    let client_key_file = "/tmp/ser_example_client_key.bin";

// We write the keys to files:
    let mut file = File::create(server_key_file)
        .expect("failed to create server key file");
    file.write_all(encoded_server_key.as_slice()).expect("failed to write key to file");
    let mut file = File::create(client_key_file)
        .expect("failed to create client key file");
    file.write_all(encoded_client_key.as_slice()).expect("failed to write key to file");

// We retrieve the keys:
    let mut file = File::open(server_key_file)
        .expect("failed to open server key file");
    let mut encoded_server_key: Vec<u8> = Vec::new();
    file.read_to_end(&mut encoded_server_key).expect("failed to read the key");

    let mut file = File::open(client_key_file)
        .expect("failed to open client key file");
    let mut encoded_client_key: Vec<u8> = Vec::new();
    file.read_to_end(&mut encoded_client_key).expect("failed to read the key");

// We deserialize the keys:
    let loaded_server_key: ServerKey = bincode::deserialize(&encoded_server_key[..])
        .expect("failed to deserialize");
    let loaded_client_key: ClientKey = bincode::deserialize(&encoded_client_key[..])
        .expect("failed to deserialize");


    let ct_1 = client_key.encrypt(false);

// We check for equality:
    assert_eq!(false, loaded_client_key.decrypt(&ct_1));
}

Use Public Key Encryption

Public key encryption refers to the cryptographic paradigm where the encryption key can be publicly distributed, whereas the decryption key remains secret to the owner. This differs from usual case where the same secret key is used to encrypt and decrypt the data. In TFHE-rs, there exists two methods for public key encryptions. First, the usual one, where the public key contains ma y encryption of zeroes. More details can be found in Guide to Fully Homomorphic Encryption over the [Discretized] Torus, Appendix A.arrow-up-right. The second method is based on the paper entitled TFHE Public-Key Encryption Revisitedarrow-up-right. The main advantage of the latter method in comparison with the former lies into the key sizes, which are drastically reduced.

Note that public keys can be compressed

hashtag
classical public key

This example shows how to use public keys.

hashtag
compact public key

This example shows how to use compact public keys. The main difference is in the ConfigBuilder, where the parameter set has been changed.

Cryptographic Parameters

hashtag
Default parameters

The TFHE cryptographic scheme relies on a variant of and is based on a problem so difficult that it is even post-quantum resistant.

Some cryptographic parameters will require tuning to ensure both the correctness of the result and the security of the computation.

To make it simpler, we've provided two sets of parameters, which ensure correct computations for a certain probability with the standard security of 128 bits. There exists an error probability due to the probabilistic nature of the encryption, which requires adding randomness (noise) following a Gaussian distribution. If this noise is too large, the decryption will not give a correct result. There is a trade-off between efficiency and correctness: generally, using a less efficient parameter set (in terms of computation time) leads to a smaller risk of having an error during homomorphic evaluation.

use tfhe::prelude::*;
use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8, PublicKey};

fn main() {
    let config = ConfigBuilder::all_disabled()
        .enable_default_integers()
        .build();
    let (client_key, _) = generate_keys(config);

    let public_key = PublicKey::new(&client_key);

    let a = FheUint8::try_encrypt(255u8, &public_key).unwrap();
    let clear: u8 = a.decrypt(&client_key);
    assert_eq!(clear, 255u8);
}

Serialization/Deserialization

As explained in the introduction, some types (Serverkey, Ciphertext) are meant to be shared with the server that does the computations.

The easiest way to send these data to a server is to use the serialization and deserialization features. TFHE-rs uses the serde framework, so serde's Serialize and Deserialize are implemented.

To be able to serialize our data, a data formatarrow-up-right needs to be picked. Here, bincodearrow-up-right is a good choice, mainly because it is binary format.

# Cargo.toml

[dependencies]
# ...
bincode = "1.3.3"

Serialization/Deserialization

As explained in the introduction, some types (Serverkey, Ciphertext) are meant to be shared with the server that performs the computations.

The easiest way to send these data to a server is to use the serialization and deserialization features. tfhe::shortint uses the serdearrow-up-right framework. Serde's Serialize and Deserialize are then implemented on the tfhe::shortint types.

To serialize the data, we need to pick a data formatarrow-up-right. For our use case, bincodearrow-up-right is a good choice, mainly because it is a binary format.

# Cargo.toml

[dependencies]
# ...
bincode = "1.3.3"
use tfhe::prelude::*;
use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8, CompactPublicKey};

fn main() {
     let config = ConfigBuilder::all_disabled()
        .enable_custom_integers(
            tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_COMPACT_PK_KS_PBS,
            None,
        )
        .build();
    let (client_key, _) = generate_keys(config);

    let public_key = CompactPublicKey::new(&client_key);

    let a = FheUint8::try_encrypt(255u8, &public_key).unwrap();
    let clear: u8 = a.decrypt(&client_key);
    assert_eq!(clear, 255u8);
}
// main.rs

use bincode;

use std::io::Cursor;
use tfhe::integer::{gen_keys_radix, ServerKey, RadixCiphertext};
use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;


fn main() -> Result<(), Box<dyn std::error::Error>> {
    // We generate a set of client/server keys, using the default parameters:
    let num_block = 4;
    let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);

    let msg1 = 201;
    let msg2 = 12;

    // message_modulus^vec_length
    let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
    let ct_1 = client_key.encrypt(msg1);
    let ct_2 = client_key.encrypt(msg2);

    let mut serialized_data = Vec::new();
    bincode::serialize_into(&mut serialized_data, &server_key)?;
    bincode::serialize_into(&mut serialized_data, &ct_1)?;
    bincode::serialize_into(&mut serialized_data, &ct_2)?;

    // Simulate sending serialized data to a server and getting
    // back the serialized result
    let serialized_result = server_function(&serialized_data)?;
    let result: RadixCiphertext = bincode::deserialize(&serialized_result)?;

    let output: u64 = client_key.decrypt(&result);
    assert_eq!(output, (msg1 + msg2) % modulus);
    Ok(())
}


fn server_function(serialized_data: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
    let mut serialized_data = Cursor::new(serialized_data);
    let server_key: ServerKey = bincode::deserialize_from(&mut serialized_data)?;
    let ct_1: RadixCiphertext = bincode::deserialize_from(&mut serialized_data)?;
    let ct_2: RadixCiphertext = bincode::deserialize_from(&mut serialized_data)?;

    let result = server_key.unchecked_add(&ct_1, &ct_2);

    let serialized_result = bincode::serialize(&result)?;

    Ok(serialized_result)
}
// main.rs

use bincode;
use std::io::Cursor;
use tfhe::shortint::prelude::*;


fn main() -> Result<(), Box<dyn std::error::Error>> {
    let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);

    let msg1 = 1;
    let msg2 = 0;

    let ct_1 = client_key.encrypt(msg1);
    let ct_2 = client_key.encrypt(msg2);

    let mut serialized_data = Vec::new();
    bincode::serialize_into(&mut serialized_data, &server_key)?;
    bincode::serialize_into(&mut serialized_data, &ct_1)?;
    bincode::serialize_into(&mut serialized_data, &ct_2)?;

    // Simulate sending serialized data to a server and getting
    // back the serialized result
    let serialized_result = server_function(&serialized_data)?;
    let result: Ciphertext = bincode::deserialize(&serialized_result)?;

    let output = client_key.decrypt(&result);
    assert_eq!(output, msg1 + msg2);
    Ok(())
}


fn server_function(serialized_data: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
    let mut serialized_data = Cursor::new(serialized_data);
    let server_key: ServerKey = bincode::deserialize_from(&mut serialized_data)?;
    let ct_1: Ciphertext = bincode::deserialize_from(&mut serialized_data)?;
    let ct_2: Ciphertext = bincode::deserialize_from(&mut serialized_data)?;

    let result = server_key.unchecked_add(&ct_1, &ct_2);

    let serialized_result = bincode::serialize(&result)?;

    Ok(serialized_result)
}

In the two proposed sets of parameters, the only difference lies in this error probability. The default parameter set ensures an error probability of at most 2−402^{-40}2−40 when computing a programmable bootstrapping (i.e., any gates but the not). The other one is closer to the error probability claimed in the original TFHE paperarrow-up-right, namely 2−1652^{-165}2−165, but it is up-to-date regarding security requirements.

The following array summarizes this:

Parameter set
Error probability

DEFAULT_PARAMETERS

TFHE_LIB_PARAMETERS

hashtag
User-defined parameters

You can also create your own set of parameters. This is an unsafe operation as failing to properly fix the parameters will result in an incorrect and/or insecure computation:

Regev cryptosystemarrow-up-right

Operations

This contains the operations available in tfhe::boolean, along with code examples.

hashtag
The NOT unary gate

hashtag

Integer

tfhe::integer is dedicated to integers smaller than 256 bits. The steps to homomorphically evaluate an integer circuit are described here.

hashtag
Key Types

integer provides 3 basic key types:

Serialize/Deserialize

As explained in the Introduction, most types are meant to be shared with the server that performs the computations.

The easiest way to send these data to a server is to use the serialization and deserialization features. tfhe uses the framework. Serde's Serialize and Deserialize functions are implemented on TFHE's types.

To serialize our data, a should be picked. Here, is a good choice, mainly because it is a binary format.

Configure Rust

hashtag
Using the right toolchain for TFHE-rs.

TFHE-rs only requires a nightly toolchain for building the C API and using advanced SIMD instructions, otherwise you can use a stable toolchain (with version >= 1.72) Install the needed Rust toolchain:

Then, you can either:

Use Parallelized PBS

hashtag
Parallelized Programmable Bootstrapping

The (PBS) is a sequential operation by nature. However, some showed that parallelism could be added at the cost of having larger keys. Overall, the performance of the PBS are improved. This new PBS is called a multi bit PBS. In TFHE-rs, since integer homomorphic operations are already parallelized, activating this feature may improve performance in the case of high core count CPUs if enough cores are available, or for small input message precision.

In what follows, an example on how to use the parallelized bootstrapping by choosing multi bit PBS parameters:

use tfhe::boolean::prelude::*;

fn main() {
// WARNING: might be insecure and/or incorrect
// You can create your own set of parameters
    let parameters = unsafe {
        BooleanParameters::new(
            LweDimension(586),
            GlweDimension(2),
            PolynomialSize(512),
            StandardDev(0.00008976167396834998),
            StandardDev(0.00000002989040792967434),
            DecompositionBaseLog(8),
            DecompositionLevelCount(2),
            DecompositionBaseLog(2),
            DecompositionLevelCount(5),
            EncryptionKeyChoice::Small,
        )
    };
}
2−402^{-40}2−40
2−1652^{-165}2−165
# Cargo.toml

[dependencies]
# ...
tfhe = { version = "0.4.4", features = ["integer","x86_64-unix"]}
bincode = "1.3.3"
serdearrow-up-right
data formatarrow-up-right
bincodearrow-up-right
Binary gates

hashtag
The MUX ternary gate

Let ct_1, ct_2, ct_3 be three Boolean ciphertexts. Then, the MUX gate (abbreviation of MUltipleXer) is equivalent to the operation:

This example shows how to use the MUX ternary gate:

use tfhe::boolean::prelude::*;

fn main() {
// We generate a set of client/server keys, using the default parameters:
    let (client_key, server_key) = gen_keys();

// We use the client secret key to encrypt a message:
    let ct_1 = client_key.encrypt(true);

// We use the server public key to execute the NOT gate:
    let ct_not = server_key.not(&ct_1);

// We use the client key to decrypt the output of the circuit:
    let output = client_key.decrypt(&ct_not);
    assert_eq!(output, false);
}

ClientKey

  • ServerKey

  • PublicKey

  • The ClientKey is the key that encrypts and decrypts messages, thus this key is meant to be kept private and should never be shared. This key is created from parameter values that will dictate both the security and efficiency of computations. The parameters also set the maximum number of bits of message encrypted in a ciphertext.

    The ServerKey is the key that is used to actually do the FHE computations. It contains a bootstrapping key and a keyswitching key. This key is created from a ClientKey that needs to be shared to the server, so it is not meant to be kept private. A user with a ServerKey can compute on the encrypted data sent by the owner of the associated ClientKey.

    To reflect this, computation/operation methods are tied to the ServerKey type.

    The PublicKey is a key used to encrypt messages. It can be publicly shared to allow users to encrypt data such that only the ClientKey holder will be able to decrypt. Encrypting with the PublicKey does not alter the homomorphic capabilities associated to the ServerKey.

    hashtag
    1. Key Generation

    To generate the keys, a user needs two parameters:

    • A set of shortint cryptographic parameters.

    • The number of ciphertexts used to encrypt an integer (we call them "shortint blocks").

    We are now going to build a pair of keys that can encrypt 8-bit integers (signed or unsigned) by using 4 shortint blocks that store 2 bits of message each.

    hashtag
    2. Encrypting values

    Once we have our keys, we can encrypt values:

    hashtag
    3. Encrypting values with the public key

    Once the client key is generated, the public key can be derived and used to encrypt data.

    hashtag
    4. Computing and decrypting

    With our server_key, and encrypted values, we can now do an addition and then decrypt the result.

    Manually specify the toolchain to use in each of the cargo commands:
    • Or override the toolchain to use for the current project:

    To check the toolchain that Cargo will use by default, you can use the following command:

    hashtag
    Choosing your features

    TFHE-rs exposes different cargo features to customize the types and features used.

    hashtag
    Homomorphic Types.

    This crate exposes two kinds of data types. Each kind is enabled by activating its corresponding feature in the TOML line. Each kind may have multiple types:

    Kind
    Features
    Type(s)

    Booleans

    boolean

    Booleans

    ShortInts

    shortint

    Short integers

    Integers

    integer

    Arbitrary-sized integers

    hashtag
    AVX-512

    In general, the library automatically chooses the best instruction sets available by the host. However, in the case of 'AVX-512', this has to be explicitly chosen as a feature. This requires to use a nightly toolchain along with the feature nightly-avx512.

    hashtag
    Deterministic Parallelized Programmable Bootstrapping

    By construction, the parallelized PBS might not be deterministic: the resulting ciphertext will always decrypt to the same plaintext, but the order of the operations could differ so the output ciphertext might differ. In order to activate the deterministic version, the suffix 'with_deterministic_execution()' should be added to the parameters, as shown in the following example:

    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint32};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled()
            .enable_custom_integers(
               tfhe::shortint::parameters::PARAM_MULTI_BIT_MESSAGE_2_CARRY_2_GROUP_3_KS_PBS,
               None,
            )
            .build();
            
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
        
        let clear_a = 673u32;
        let clear_b = 6u32;
        let a = FheUint32::try_encrypt(clear_a, &keys)?;
        let b = FheUint32::try_encrypt(clear_b, &keys)?;
    
        let c = &a >> &b;
        let decrypted: u32 = c.decrypt(&keys);
        assert_eq!(decrypted, clear_a >> clear_b);
    
        Ok(())
    }
    Programmable Bootstrapping
    recent resultsarrow-up-right
    // main.rs
    
    use bincode;
    
    use std::io::Cursor;
    
    use tfhe::{ConfigBuilder, ServerKey, generate_keys, set_server_key, FheUint8};
    use tfhe::prelude::*;
    
    fn main() -> Result<(), Box<dyn std::error::Error>>{
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let ( client_key, server_key) = generate_keys(config);
    
        let msg1 = 1;
        let msg2 = 0;
    
        let value_1 = FheUint8::encrypt(msg1, &client_key);
        let value_2 = FheUint8::encrypt(msg2, &client_key);
    
        // Prepare to send data to the server
        // The ClientKey is _not_ sent
        let mut serialized_data = Vec::new();
        bincode::serialize_into(&mut serialized_data, &server_key)?;
        bincode::serialize_into(&mut serialized_data, &value_1)?;
        bincode::serialize_into(&mut serialized_data, &value_2)?;
    
        // Simulate sending serialized data to a server and getting
        // back the serialized result
        let serialized_result = server_function(&serialized_data)?;
        let result: FheUint8 = bincode::deserialize(&serialized_result)?;
    
        let output: u8 = result.decrypt(&client_key);
        assert_eq!(output, msg1 + msg2);
        Ok(())
    }
    
    
    fn server_function(serialized_data: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
        let mut serialized_data = Cursor::new(serialized_data);
        let server_key: ServerKey = bincode::deserialize_from(&mut serialized_data)?;
        let ct_1: FheUint8 = bincode::deserialize_from(&mut serialized_data)?;
        let ct_2: FheUint8 = bincode::deserialize_from(&mut serialized_data)?;
    
        set_server_key(server_key);
    
        let result = ct_1 + ct_2;
    
        let serialized_result = bincode::serialize(&result)?;
    
        Ok(serialized_result)
    }
    use tfhe::boolean::prelude::*;
    
    fn main() {
    // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys();
    
    // We use the client secret key to encrypt a message:
        let ct_1 = client_key.encrypt(true);
        let ct_2 = client_key.encrypt(false);
    
    // We use the server public key to execute the XOR gate:
        let ct_xor = server_key.xor(&ct_1, &ct_2);
    
    // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_xor);
        assert_eq!(output, true^false);
    }
    if ct_1 {
        return ct_2
    } else {
        return ct_3
    }
    use tfhe::boolean::prelude::*;
    
    fn main() {
    // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys();
    
        let bool1 = true;
        let bool2 = false;
        let bool3 = true;
    
    // We use the client secret key to encrypt a message:
        let ct_1 = client_key.encrypt(true);
        let ct_2 = client_key.encrypt(false);
        let ct_3 = client_key.encrypt(false);
    
    
    // We use the server public key to execute the NOT gate:
        let ct_xor = server_key.mux(&ct_1, &ct_2, &ct_3);
    
    // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_xor);
        assert_eq!(output, if bool1 {bool2} else {bool3});
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 128u64;
        let msg2 = 13u64;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::integer::PublicKey;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let num_block = 4;
        let (client_key, _) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        //We generate the public key from the secret client key:
        let public_key = PublicKey::new(&client_key);
    
        //encryption
        let msg1 = 128u64;
        let msg2 = 13u64;
    
        // We use the public key to encrypt two messages:
        let ct_1 = public_key.encrypt_radix(msg1, num_block);
        let ct_2 = public_key.encrypt_radix(msg2, num_block);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 128;
        let msg2 = 13;
    
        // message_modulus^vec_length
        let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to execute an integer circuit:
        let ct_3 = server_key.unchecked_add(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output: u64 = client_key.decrypt(&ct_3);
    
        assert_eq!(output, (msg1 + msg2) % modulus);
    }
    # If you don't need the C API or the advanced still unstable SIMD instructions use this
    rustup toolchain install stable
    # Otherwise install a nightly toolchain
    rustup toolchain install nightly
    # By default the +stable should not be needed, but we add it here for completeness
    cargo +stable build
    cargo +stable test
    # Or
    cargo +nightly build
    cargo +nightly test
    # This should not be necessary by default, but if you want to make sure your configuration is
    # correct you can still set the overridden toolchain to stable
    rustup override set stable
    # cargo will use the `stable` toolchain.
    cargo build
    # Or
    rustup override set nightly
    # cargo will use the `nightly` toolchain.
    cargo build
    rustup show
    cargo +nightly build --features=nightly-avx512
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint32};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled()
            .enable_custom_integers(
               tfhe::shortint::parameters::PARAM_MULTI_BIT_MESSAGE_2_CARRY_2_GROUP_3_KS_PBS.with_deterministic_execution(),
               None,
            )
            .build();
            
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
        
        let clear_a = 673u32;
        let clear_b = 6u32;
        let a = FheUint32::try_encrypt(clear_a, &keys)?;
        let b = FheUint32::try_encrypt(clear_b, &keys)?;
    
        let c = &a >> &b;
        let decrypted: u32 = c.decrypt(&keys);
        assert_eq!(decrypted, clear_a >> clear_b);
    
        Ok(())
    }

    Quick Start

    The core_crypto module from TFHE-rs is dedicated to the implementation of the cryptographic tools related to TFHE. To construct an FHE application, the shortint and/or Boolean modules (based on core_crypto) are recommended.

    The core_crypto module offers an API to low-level cryptographic primitives and objects, like lwe_encryption or rlwe_ciphertext. The goal is to propose an easy-to-use API for cryptographers.

    The overall code architecture is split in two parts: one for entity definitions and another focused on algorithms. The entities contain the definition of useful types, like LWE ciphertext or bootstrapping keys. The algorithms are then naturally defined to work using these entities.

    The API is convenient to add or modify existing algorithms, or to have direct access to the raw data. Even if the LWE ciphertext object is defined, along with functions giving access to the body, it is also possible to bypass these to get directly the element of LWE mask.

    For instance, the code to encrypt and then decrypt a message looks like:

    Homomorphic Case Changing on Ascii String

    The goal of this tutorial is to build a data type that represents a ASCII string in FHE while implementing the to_lower and to_upper functions.

    An ASCII character is stored in 7 bits. To store an encrypted ASCII we use the FheUint8.

    • The uppercase letters are in the range [65, 90]

    Shortint

    tfhe::shortint is dedicated to unsigned integers smaller than 8 bits. The steps to homomorphically evaluate a circuit are described below.

    hashtag
    Key generation

    tfhe::shortint provides 3 key types:

    ithi^{th}ith

    The lowercase letters are in the range [97, 122]

    lower_case = upper_case + UP_LOW_DISTANCE <=> upper_case = lower_case - UP_LOW_DISTANCE

    Where UP_LOW_DISTANCE = 32

    hashtag
    Types and methods.

    This type will hold the encrypted characters as a Vec<FheUint8> to implement the functions that change the case.

    To use the FheUint8 type, the integer feature must be activated:

    Other configurations can be found here.

    In the FheAsciiString::encrypt function, some data validation is done:

    • The input string can only contain ascii characters.

    It is not possible to branch on an encrypted value, however it is possible to evaluate a boolean condition and use it to get the desired result. Checking if the 'char' is an uppercase letter to modify it to a lowercase can be done without using a branch, like this:

    We can remove the branch this way:

    On an homomorphic integer, this gives

    The whole code is:

    ClientKey

  • ServerKey

  • PublicKey

  • The ClientKey is the key that encrypts and decrypts messages (integer values up to 8 bits here). It is meant to be kept private and should never be shared. This key is created from parameter values that will dictate both the security and efficiency of computations. The parameters also set the maximum number of bits of message encrypted in a ciphertext.

    The ServerKey is the key that is used to evaluate the FHE computations. Most importantly, it contains a bootstrapping key and a keyswitching key. This key is created from a ClientKey that needs to be shared to the server (it is not meant to be kept private). A user with a ServerKey can compute on the encrypted data sent by the owner of the associated ClientKey.

    Computation/operation methods are tied to the ServerKey type.

    The PublicKey is the key used to encrypt messages. It can be publicly shared to allow users to encrypt data such that only the ClientKey holder will be able to decrypt. Encrypting with the PublicKey does not alter the homomorphic capabilities associated to the ServerKey.

    hashtag
    Encrypting values

    Once the keys have been generated, the client key is used to encrypt data:

    hashtag
    Encrypting values using a public key

    Once the keys have been generated, the client key is used to encrypt data:

    hashtag
    Computing and decrypting

    Using the server_key, addition is possible over encrypted values. The resulting plaintext is recovered after the decryption via the secret client key.

    use tfhe::core_crypto::prelude::*;
    
    // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
    // computations
    // Define parameters for LweCiphertext creation
    let lwe_dimension = LweDimension(742);
    let lwe_modular_std_dev = StandardDev(0.000007069849454709433);
    let ciphertext_modulus = CiphertextModulus::new_native();
    
    // Create the PRNG
    let mut seeder = new_seeder();
    let seeder = seeder.as_mut();
    let mut encryption_generator =
        EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
    let mut secret_generator =
        SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
    
    // Create the LweSecretKey
    let lwe_secret_key =
        allocate_and_generate_new_binary_lwe_secret_key(lwe_dimension, &mut secret_generator);
    
    // Create the plaintext
    let msg = 3u64;
    let plaintext = Plaintext(msg << 60);
    
    // Create a new LweCiphertext
    let mut lwe = LweCiphertext::new(0u64, lwe_dimension.to_lwe_size(), ciphertext_modulus);
    
    encrypt_lwe_ciphertext(
        &lwe_secret_key,
        &mut lwe,
        plaintext,
        lwe_modular_std_dev,
        &mut encryption_generator,
    );
    
    let decrypted_plaintext = decrypt_lwe_ciphertext(&lwe_secret_key, &lwe);
    
    // Round and remove encoding
    // First create a decomposer working on the high 4 bits corresponding to our encoding.
    let decomposer = SignedDecomposer::new(DecompositionBaseLog(4), DecompositionLevelCount(1));
    let rounded = decomposer.closest_representable(decrypted_plaintext.0);
    
    // Remove the encoding
    let cleartext = rounded >> 60;
    
    // Check we recovered the original message
    assert_eq!(cleartext, msg);
    # Cargo.toml
    
    [dependencies]
    # Default configuration for x86 Unix machines:
    tfhe = { version = "0.4.4", features = ["integer", "x86_64-unix"]}
    pub const UP_LOW_DISTANCE: u8 = 32;
    
    fn to_lower(c: u8) -> u8 {
        if c > 64 && c < 91 {
            c + UP_LOW_DISTANCE
        } else {
            c
        }
    }
    pub const UP_LOW_DISTANCE: u8 = 32;
    
    fn to_lower(c: u8) -> u8 {
        c + ((c > 64) as u8 & (c < 91) as u8) * UP_LOW_DISTANCE
    }
    use tfhe::prelude::*;
    use tfhe::FheUint8;
    
    pub const UP_LOW_DISTANCE: u8 = 32;
    
    fn to_lower(c: &FheUint8) -> FheUint8 {
        c + (c.gt(64) & c.lt(91)) * UP_LOW_DISTANCE
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ClientKey, ConfigBuilder, FheUint8};
    
    pub const UP_LOW_DISTANCE: u8 = 32;
    
    struct FheAsciiString {
        bytes: Vec<FheUint8>,
    }
    
    fn to_upper(c: &FheUint8) -> FheUint8 {
        c - (c.gt(96) & c.lt(123)) * UP_LOW_DISTANCE
    }
    
    fn to_lower(c: &FheUint8) -> FheUint8 {
        c + (c.gt(64) & c.lt(91)) * UP_LOW_DISTANCE
    }
    
    impl FheAsciiString {
        fn encrypt(string: &str, client_key: &ClientKey) -> Self {
            assert!(
                string.chars().all(|char| char.is_ascii()),
                "The input string must only contain ascii letters"
            );
    
            let fhe_bytes: Vec<FheUint8> = string
                .bytes()
                .map(|b| FheUint8::encrypt(b, client_key))
                .collect();
    
            Self { bytes: fhe_bytes }
        }
    
        fn decrypt(&self, client_key: &ClientKey) -> String {
            let ascii_bytes: Vec<u8> = self
                .bytes
                .iter()
                .map(|fhe_b| fhe_b.decrypt(client_key))
                .collect();
            String::from_utf8(ascii_bytes).unwrap()
        }
    
        fn to_upper(&self) -> Self {
            Self {
                bytes: self.bytes.iter().map(to_upper).collect(),
            }
        }
    
        fn to_lower(&self) -> Self {
            Self {
                bytes: self.bytes.iter().map(to_lower).collect(),
            }
        }
    }
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let (client_key, server_key) = generate_keys(config);
    
        set_server_key(server_key);
    
        let my_string = FheAsciiString::encrypt("Hello Zama, how is it going?", &client_key);
        let verif_string = my_string.decrypt(&client_key);
        println!("Start string: {verif_string}");
    
        let my_string_upper = my_string.to_upper();
        let verif_string = my_string_upper.decrypt(&client_key);
        println!("Upper string: {verif_string}");
        assert_eq!(verif_string, "HELLO ZAMA, HOW IS IT GOING?");
    
        let my_string_lower = my_string_upper.to_lower();
        let verif_string = my_string_lower.decrypt(&client_key);
        println!("Lower string: {verif_string}");
        assert_eq!(verif_string, "hello zama, how is it going?");
    }
    use tfhe::shortint::prelude::*;
    
    fn main()  {
        // We generate a set of client/server keys
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys
       let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 1;
        let msg2 = 0;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys
       let (client_key, _) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
       let public_key = PublicKey::new(&client_key);
    
        let msg1 = 1;
        let msg2 = 0;
    
        // We use the client key to encrypt two messages:
        let ct_1 = public_key.encrypt(msg1);
        let ct_2 = public_key.encrypt(msg2);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 1;
        let msg2 = 0;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to execute an integer circuit:
        let ct_3 = server_key.unchecked_add(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_3);
        assert_eq!(output, (msg1 + msg2) % modulus as u64);
    }

    Use the C API

    This library exposes a C binding to the high-level TFHE-rs primitives to implement Fully Homomorphic Encryption (FHE) programs.

    hashtag
    Setting-up TFHE-rs C API for use in a C program.

    TFHE-rs C API can be built on a Unix x86_64 machine using the following command:

    or on a Unix aarch64 machine using the following command:

    Cryptographic Parameters

    All parameter sets provide at least 128-bits of security according to the , with an error probability equal to when using programmable bootstrapping. This error probability is due to the randomness added at each encryption (see for more details about the encryption process).

    hashtag
    Parameters and message precision

    shortint comes with sets of parameters that permit the use of the library functionalities securely and efficiently. Each parameter set is associated to the message and carry precisions. Therefore, each key pair is entangled to precision.

    The tfhe.h header as well as the static (.a) and dynamic (.so) libtfhe binaries can then be found in "${REPO_ROOT}/target/release/"

    The build system needs to be set up so that the C or C++ program links against TFHE-rs C API binaries.

    Here is a minimal CMakeLists.txt to do just that:

    hashtag
    Commented code of a uint128 subtraction using TFHE-rs C API.

    circle-exclamation

    WARNING: The following example does not have proper memory management in the error case to make it easier to fit the code on this page.

    To run the example below, the above CMakeLists.txt and main.c files need to be in the same directory. The commands to run are:

    RUSTFLAGS="-C target-cpu=native" cargo +nightly build --release --features=x86_64-unix,high-level-c-api -p tfhe

    The user is allowed to choose which set of parameters to use when creating the pair of keys.

    The difference between the parameter sets is the total amount of space dedicated to the plaintext, how it is split between the message buffer and the carry buffer, and the order in which the keyswitch (KS) and bootstrap (PBS) are computed. The syntax chosen for the name of a parameter is: PARAM_MESSAGE_{number of message bits}_CARRY_{number of carry bits}_{KS_PBS | PBS_KS}. For example, the set of parameters for a message buffer of 5 bits, a carry buffer of 2 bits and where the keyswitch is computed before the bootstrap is PARAM_MESSAGE_5_CARRY_2_KS_PBS.

    Note that the KS_PBS order should have better performance at the expense of ciphertext size, PBS_KS is the opposite.

    This example contains keys that are generated to have messages encoded over 2 bits (i.e., computations are done modulus 22=42^2 = 422=4) with 2 bits of carry.

    The PARAM_MESSAGE_2_CARRY_2_KS_PBS parameter set is the default shortint parameter set that you can also use through the tfhe::shortint::prelude::DEFAULT_PARAMETERS constant.

    hashtag
    Impact of parameters on the operations

    As shown here, the choice of the parameter set impacts the operations available and their efficiency.

    hashtag
    Generic bi-variate functions.

    The computations of bi-variate functions is based on a trick: concatenating two ciphertexts into one. Where the carry buffer is not at least as large as the message buffer, this trick no longer works. In this case, many bi-variate operations, such as comparisons, cannot be correctly computed. The only exception concerns multiplication.

    hashtag
    Multiplication.

    In the case of multiplication, two algorithms are implemented: the first one relies on the bi-variate function trick, where the other one is based on the quarter square methodarrow-up-right. To correctly compute a multiplication, the only requirement is to have at least one bit of carry (i.e., using parameter sets PARAM_MESSAGE_X_CARRY_Y with Y>=1). This method is slower than using the other one. Using the smart version of the multiplication automatically chooses which algorithm is used depending on the chosen parameters.

    hashtag
    User-defined parameter sets

    It is possible to define new parameter sets. To do so, it is sufficient to use the function unsecure_parameters() or to manually fill the ClassicPBSParameters structure fields.

    For instance:

    2−402^{-40}2−40
    Lattice-Estimatorarrow-up-right
    here
    RUSTFLAGS="-C target-cpu=native" cargo build +nightly --release --features=aarch64-unix,high-level-c-api -p tfhe
    project(my-project)
    
    cmake_minimum_required(VERSION 3.16)
    
    set(TFHE_C_API "/path/to/tfhe-rs/binaries/and/header")
    
    include_directories(${TFHE_C_API})
    add_library(tfhe STATIC IMPORTED)
    set_target_properties(tfhe PROPERTIES IMPORTED_LOCATION ${TFHE_C_API}/libtfhe.a)
    
    if(APPLE)
        find_library(SECURITY_FRAMEWORK Security)
        if (NOT SECURITY_FRAMEWORK)
            message(FATAL_ERROR "Security framework not found")
        endif()
    endif()
    
    set(EXECUTABLE_NAME my-executable)
    add_executable(${EXECUTABLE_NAME} main.c)
    target_include_directories(${EXECUTABLE_NAME} PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})
    target_link_libraries(${EXECUTABLE_NAME} LINK_PUBLIC tfhe m pthread dl)
    if(APPLE)
        target_link_libraries(${EXECUTABLE_NAME} LINK_PUBLIC ${SECURITY_FRAMEWORK})
    endif()
    target_compile_options(${EXECUTABLE_NAME} PRIVATE -Werror)
    # /!\ Be sure to update CMakeLists.txt to give the absolute path to the compiled tfhe library
    $ ls
    CMakeLists.txt  main.c
    $ mkdir build && cd build
    $ cmake .. -DCMAKE_BUILD_TYPE=RELEASE
    ...
    $ make
    ...
    $ ./my-executable
    FHE computation successful!
    $
    #include <tfhe.h>
    
    #include <assert.h>
    #include <stdio.h>
    
    int main(void)
    {
        int ok = 0;
        // Prepare the config builder for the high level API and choose which types to enable
        ConfigBuilder *builder;
        Config *config;
    
        // Put the builder in a default state without any types enabled
        config_builder_all_disabled(&builder);
        // Enable the uint128 type using the small LWE key for encryption
        config_builder_enable_default_integers_small(&builder);
        // Populate the config
        config_builder_build(builder, &config);
    
        ClientKey *client_key = NULL;
        ServerKey *server_key = NULL;
    
        // Generate the keys using the config
        generate_keys(config, &client_key, &server_key);
        // Set the server key for the current thread
        set_server_key(server_key);
    
        FheUint128 *lhs = NULL;
        FheUint128 *rhs = NULL;
        FheUint128 *result = NULL;
        // A 128-bit unsigned integer containing value: 20 << 64 | 10
        U128 clear_lhs = { .w0 = 10, .w1 = 20 };
        // A 128-bit unsigned integer containing value: 2 << 64 | 1
        U128 clear_rhs = { .w0 = 1, .w1 = 2 };
    
        ok = fhe_uint128_try_encrypt_with_client_key_u128(clear_lhs, client_key, &lhs);
        assert(ok == 0);
    
        ok = fhe_uint128_try_encrypt_with_client_key_u128(clear_rhs, client_key, &rhs);
        assert(ok == 0);
    
        // Compute the subtraction
        ok = fhe_uint128_sub(lhs, rhs, &result);
        assert(ok == 0);
    
        U128 clear_result;
        // Decrypt
        ok = fhe_uint128_decrypt(result, client_key, &clear_result);
        assert(ok == 0);
    
        // Here the subtraction allows us to compare each word
        assert(clear_result.w0 == 9);
        assert(clear_result.w1 == 18);
    
        // Destroy the ciphertexts
        fhe_uint128_destroy(lhs);
        fhe_uint128_destroy(rhs);
        fhe_uint128_destroy(result);
    
        // Destroy the keys
        client_key_destroy(client_key);
        server_key_destroy(server_key);
    
        printf("FHE computation successful!\n");
        return EXIT_SUCCESS;
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
       let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 2;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        let param = unsafe {
            ClassicPBSParameters::new(
                LweDimension(656),
                GlweDimension(2),
                PolynomialSize(512),
                StandardDev(0.000034119201269311964),
                StandardDev(0.00000004053919869756513),
                DecompositionBaseLog(8),
                DecompositionLevelCount(2),
                DecompositionBaseLog(3),
                DecompositionLevelCount(4),
                MessageModulus(4),
                CarryModulus(1),
                CiphertextModulus::new_native(),
                EncryptionKeyChoice::Big,
            )
        };
    }

    Use the JS on WASM API

    TFHE-rs supports WASM for the client api, that is, it supports key generation, encryption, decryption but not doing actual computations.

    TFHE-rs supports 3 WASM 'targets':

    • nodejs: to be used in a nodejs app/package

    • web: to be used in a web browser

    Generic Function Bounds

    If you wish to write generic functions which use operators with mixed reference and non-reference, it might get tricky at first to specify the trait . This page should serve as a cookbook to help you.

    Operators (+, *, >>, etc) are tied to traits in std:::ops, e.g. + is std::ops::Add, so to write a generic function which uses the + operator, you need to use add std::ops::Add as a trait bound.

    Then, depending on if the left hand side / right hand side is an owned value or a reference, the trait bound is slightly different. The table below shows the possibilities.

    Compress Ciphertexts/Keys

    TFHE-rs includes features to reduce the size of both keys and ciphertexts, by compressing them. Most TFHE-rs entities contain random numbers generated by a Pseudo Random Number Generator (PRNG). A PRNG is deterministic, therefore storing only the random seed used to generate those numbers is enough to keep all the required information: using the same PRNG and the same seed, the full chain of random values can be reconstructed when decompressing the entity.

    In the library, entities that can be compressed are prefixed by Compressed. For instance, the type of a compressed FheUint256 is CompressedFheUint256.

    In the following example code, we use the bincode crate dependency to serialize in a binary format and compare serialized sizes.

    web-parallel: to be used in a web browser with multi-threading support

    In all cases, the core of the API is same, only few initialization function changes.

    hashtag
    Example

    hashtag
    nodejs

    hashtag
    Web

    • When using the Web WASM target, there is an additional init function to call.

    • When using the Web WASM target with parallelism enabled, there is also one more initialization function to call initThreadPool

    hashtag
    Example

    hashtag
    Compiling the WASM API

    The TFHE-rs repo has a Makefile that contains targets for each of the 3 possible variants of the API:

    • make build_node_js_api to build the nodejs API

    • make build_web_js_api to build the browser API

    • make build_web_js_api_parallel to build the browser API with parallelism

    The compiled WASM package will be in tfhe/pkg.

    circle-info

    The sequential browser API and the nodejs API are published as npm packages. You can add the browser API to your project using the command npm i tfhe. You can add the nodejs API to your project using the command npm i node-tfhe.

    hashtag
    Using the JS on WASM API

    TFHE-rs uses WASM to expose a JS binding to the client-side primitives, like key generation and encryption, of the Boolean and shortint modules.

    There are several limitations at this time. Due to a lack of threading support in WASM, key generation can be too slow to be practical for bigger parameter sets.

    Some parameter sets lead to FHE keys that are too big to fit in the 2GB memory space of WASM. This means that some parameter sets are virtually unusable.

    hashtag
    First steps using TFHE-rs JS on WASM API

    hashtag
    Setting-up TFHE-rs JS on WASM API for use in nodejs programs.

    To build the JS on WASM bindings for TFHE-rs, you need to install wasm-packarrow-up-right in addition to a compatible (>= 1.67) rust toolchainarrow-up-right.

    In a shell, then run the following to clone the TFHE-rs repo (one may want to checkout a specific tag, here the default branch is used for the build):

    The command above targets nodejs. A binding for a web browser can be generated as well using --target=web. This use case will not be discussed in this tutorial.

    Both Boolean and shortint features are enabled here, but it's possible to use one without the other.

    After the build, a new directory pkg is present in the tfhe directory.

    hashtag
    Commented code to generate keys for shortint and encrypt a ciphertext

    circle-info

    Be sure to update the path of the required clause in the example below for the TFHE package that was just built.

    The example.js script can then be run using nodearrow-up-right, like so:

    operation
    trait bound

    T $op T

    T: $Op<T, Output=T>

    T $op &T

    T: for<'a> $Op<&'a T, Output=T>

    &T $op T

    for<'a> &'a T: $Op<T, Output=T>

    &T $op &T

    for<'a> &'a T: $Op<&'a T, Output=T>

    circle-info

    The for<'a> syntax is something called Higher-Rank Trait Boundsarrow-up-right, often shortened as HRTB

    circle-info

    Writing generic functions will also allow you to call them using clear inputs, only allowing easier debugging.

    hashtag
    Example

    boundsarrow-up-right
    hashtag
    Compressed ciphertexts

    This example shows how to compress a ciphertext encypting messages over 16 bits.

    hashtag
    Compressed server keys

    This example shows how to compress the server keys.

    hashtag
    Compressed public keys

    This example shows how to compress the classical public keys.

    circle-exclamation

    It is not currently recommended to use the CompressedPublicKey to encrypt ciphertexts without first decompressing it. In case the resulting PublicKey is too large to fit in memory the encryption with the CompressedPublicKey will be very slow, this is a known problem and will be addressed in future releases.

    hashtag
    Compressed compact public key

    This example shows how to use compressed compact public keys.

    
    const {
        init_panic_hook,
        ShortintParametersName,
        ShortintParameters,
        TfheClientKey,
        TfheCompactPublicKey,
        TfheCompressedServerKey,
        TfheConfigBuilder,
        CompactFheUint32List
    } = require("./pkg/tfhe.js");
    
    function fhe_uint32_example() {
        // Makes it so that if a rust thread panics,
        // the error message will be displayed in the console
        init_panic_hook();
    
        const block_params = new ShortintParameters(ShortintParametersName.PARAM_SMALL_MESSAGE_2_CARRY_2_COMPACT_PK);
        let config = TfheConfigBuilder.all_disabled()
            .enable_default_integers()
            .build();
    
        let clientKey = TfheClientKey.generate(config);
        let compressedServerKey = TfheCompressedServerKey.new(clientKey);
        let publicKey = TfheCompactPublicKey.new(clientKey);
    
        let values = [0, 1, 2394, U32_MAX];
        let compact_list = CompactFheUint32List.encrypt_with_compact_public_key(values, publicKey);
    
        let serialized_list = compact_list.serialize();
        let deserialized_list = CompactFheUint32List.deserialize(serialized_list);
        let encrypted_list = deserialized_list.expand();
        assert.deepStrictEqual(encrypted_list.length, values.length);
    
        for (let i = 0; i < values.length; i++)
        {
            let decrypted = encrypted_list[i].decrypt(clientKey);
            assert.deepStrictEqual(decrypted, values[i]);
        }
    }
    import init, {
        initThreadPool, // only available with parallelism
        init_panic_hook,
        ShortintParametersName,
        ShortintParameters,
        TfheClientKey,
        TfhePublicKey,
    } from "./pkg/tfhe.js";
    
    async function example() {
        await init()
        await initThreadPool(navigator.hardwareConcurrency);
        await init_panic_hook();
    
        const block_params = new ShortintParameters(ShortintParametersName.PARAM_SMALL_MESSAGE_2_CARRY_2_COMPACT_PK);
        // ....
    }
    $ git clone https://github.com/zama-ai/tfhe-rs.git
    Cloning into 'tfhe-rs'...
    ...
    Resolving deltas: 100% (3866/3866), done.
    $ cd tfhe-rs
    $ cd tfhe
    $ rustup run wasm-pack build --release --target=nodejs --features=boolean-client-js-wasm-api,shortint-client-js-wasm-api
    [INFO]: Compiling to Wasm...
    ...
    [INFO]: :-) Your wasm pkg is ready to publish at ...
    $ ls pkg
    LICENSE  index.html  package.json  tfhe.d.ts  tfhe.js  tfhe_bg.txt  tfhe_bg.wasm  tfhe_bg.wasm.d.ts
    $
    // Here import assert to check the decryption went well and panic otherwise
    const assert = require('node:assert').strict;
    // Import the Shortint module from the TFHE-rs package generated earlier
    const { Shortint } = require("/path/to/built/tfhe/pkg");
    
    function shortint_example() {
        // Get pre-defined parameters from the shortint module to manage messages with 4 bits of useful
        // information in total (2 bits of "message" and 2 bits of "carry")
        let params = Shortint.get_parameters(2, 2);
        // Create a new secret ClientKey, this must not be shared
        console.log("Generating client keys...")
        let cks = Shortint.new_client_key(params);
        // Encrypt 3 in a ciphertext
        console.log("Encrypting 3...")
        let ct = Shortint.encrypt(cks, BigInt(3));
    
        // Demonstrate ClientKey serialization (for example saving it on disk on the user device)
        let serialized_cks = Shortint.serialize_client_key(cks);
        // Deserialization
        let deserialized_cks = Shortint.deserialize_client_key(serialized_cks);
    
        // Demonstrate ciphertext serialization to send over the network
        let serialized_ct = Shortint.serialize_ciphertext(ct);
        // Deserialize a ciphertext received over the network for example
        let deserialized_ct = Shortint.deserialize_ciphertext(serialized_ct);
    
        // Decrypt with the deserialized objects
        console.log("Decrypting ciphertext...")
        let decrypted = Shortint.decrypt(deserialized_cks, deserialized_ct);
        // Check decryption works as expected
        assert.deepStrictEqual(decrypted, BigInt(3));
        console.log("Decryption successful!")
    
        // Generate public evaluation keys, also called ServerKey
        console.log("Generating compressed ServerKey...")
        let sks = Shortint.new_compressed_server_key(cks);
    
        // Can be serialized to send over the network to the machine doing the evaluation
        let serialized_sks = Shortint.serialize_compressed_server_key(sks);
        let deserialized_sks = Shortint.deserialize_compressed_server_key(serialized_sks);
        console.log("All done!")
    }
    
    shortint_example();
    $ node example.js
    Generating client keys...
    Encrypting 3...
    Decrypting ciphertext...
    Decryption successful!
    Generating compressed ServerKey...
    All done!
    $
    use std::ops::{Add, Mul};
    
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint32, FheUint64};
    
    pub fn ex1<'a, FheType, ClearType>(ct: &'a FheType, pt: ClearType) -> FheType
        where
            &'a FheType: Add<ClearType, Output = FheType>,
    {
        ct + pt
    }
    
    pub fn ex2<'a, FheType, ClearType>(a: &'a FheType, b: &'a FheType, pt: ClearType) -> FheType
        where
            &'a FheType: Mul<&'a FheType, Output = FheType>,
            FheType: Add<ClearType, Output = FheType>,
    {
        (a * b) + pt
    }
    
    pub fn ex3<FheType, ClearType>(a: FheType, b: FheType, pt: ClearType) -> FheType
        where
                for<'a> &'a FheType: Add<&'a FheType, Output = FheType>,
                FheType: Add<FheType, Output = FheType> + Add<ClearType, Output = FheType>,
    {
        let tmp = (&a + &b) + (&a + &b);
        tmp + pt
    }
    
    pub fn ex4<FheType, ClearType>(a: FheType, b: FheType, pt: ClearType) -> FheType
        where
            FheType: Clone + Add<FheType, Output = FheType> + Add<ClearType, Output = FheType>,
    {
        let tmp = (a.clone() + b.clone()) + (a.clone() + b.clone());
        tmp + pt
    }
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let (client_key, server_keys) = generate_keys(config);
    
        set_server_key(server_keys);
    
        // Use FheUint32
        {
            let clear_a = 46546u32;
            let clear_b = 6469u32;
            let clear_c = 64u32;
    
            let a = FheUint32::try_encrypt(clear_a, &client_key).unwrap();
            let b = FheUint32::try_encrypt(clear_b, &client_key).unwrap();
            assert_eq!(
                ex1(&clear_a, clear_c),
                ex1(&a, clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex2(&clear_a, &clear_b, clear_c),
                ex2(&a, &b, clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex3(clear_a, clear_b, clear_c),
                ex3(a.clone(), b.clone(), clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex4(clear_a, clear_b, clear_c),
                ex4(a, b, clear_c).decrypt(&client_key)
            );
        }
    
        // Use FheUint64
        {
            let clear_a = 46544866u64;
            let clear_b = 6469446677u64;
            let clear_c = 647897u64;
    
            let a = FheUint64::try_encrypt(clear_a, &client_key).unwrap();
            let b = FheUint64::try_encrypt(clear_b, &client_key).unwrap();
            assert_eq!(
                ex1(&clear_a, clear_c),
                ex1(&a, clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex2(&clear_a, &clear_b, clear_c),
                ex2(&a, &b, clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex3(clear_a, clear_b, clear_c),
                ex3(a.clone(), b.clone(), clear_c).decrypt(&client_key)
            );
            assert_eq!(
                ex4(clear_a, clear_b, clear_c),
                ex4(a, b, clear_c).decrypt(&client_key)
            );
        }
    }
    use tfhe::prelude::*;
    use tfhe::{ConfigBuilder, generate_keys, set_server_key, CompressedFheUint16};
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
        let (client_key, _) = generate_keys(config);
    
        let clear = 12_837u16;
        let compressed = CompressedFheUint16::try_encrypt(clear, &client_key).unwrap();
        println!(
            "compressed size  : {}",
            bincode::serialize(&compressed).unwrap().len()
        );
        
        let decompressed = compressed.decompress();
        
        println!(
            "decompressed size: {}",
            bincode::serialize(&decompressed).unwrap().len()
        );
    
        let clear_decompressed: u16 = decompressed.decrypt(&client_key);
        assert_eq!(clear_decompressed, clear);
    }
    use tfhe::prelude::*;
    use tfhe::{
        generate_keys, set_server_key, ClientKey, CompressedServerKey, ConfigBuilder, FheUint8,
    };
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let cks = ClientKey::generate(config);
        let compressed_sks = CompressedServerKey::new(&cks);
    
        println!(
            "compressed size  : {}",
            bincode::serialize(&compressed_sks).unwrap().len()
        );
    
        let sks = compressed_sks.decompress();
    
        println!(
            "decompressed size: {}",
            bincode::serialize(&sks).unwrap().len()
        );
    
        set_server_key(sks);
    
        let clear_a = 12u8;
        let a = FheUint8::try_encrypt(clear_a, &cks).unwrap();
    
        let c = a + 234u8;
        let decrypted: u8 = c.decrypt(&cks);
        assert_eq!(decrypted, clear_a.wrapping_add(234));
    }
    
    use tfhe::prelude::*;
    use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8, CompressedPublicKey};
    
    fn main() {
       let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
        let (client_key, _) = generate_keys(config);
    
        let compressed_public_key = CompressedPublicKey::new(&client_key);
    
        println!("compressed size  : {}", bincode::serialize(&compressed_public_key).unwrap().len());
    
        let public_key = compressed_public_key.decompress();
    
        println!("decompressed size: {}", bincode::serialize(&public_key).unwrap().len());
    
    
        let a = FheUint8::try_encrypt(213u8, &public_key).unwrap();
        let clear: u8 = a.decrypt(&client_key);
        assert_eq!(clear, 213u8);
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, CompressedCompactPublicKey, ConfigBuilder, FheUint8};
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_custom_integers(
                tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_COMPACT_PK_KS_PBS,
                None,
            )
            .build();
        let (client_key, _) = generate_keys(config);
    
        let public_key_compressed = CompressedCompactPublicKey::new(&client_key);
    
        println!(
            "compressed size  : {}",
            bincode::serialize(&public_key_compressed).unwrap().len()
        );
    
        let public_key = public_key_compressed.decompress();
    
        println!(
            "decompressed size: {}",
            bincode::serialize(&public_key).unwrap().len()
        );
    
        let a = FheUint8::try_encrypt(255u8, &public_key).unwrap();
        let clear: u8 = a.decrypt(&client_key);
        assert_eq!(clear, 255u8);
    }
    

    Migrate Data to Newer Versions of TFHE-rs

    In what follows, the process to manage data when upgrading the TFHE-rs version (starting from the 0.4.4 release) is given. This page details the methods to make data, which have initially been generated with an older version of TFHE-rs, usable with a newer version.

    hashtag
    Forward Compatibility Strategy

    The current strategy that has been adopted for TFHE-rs is the following:

    • TFHE-rs has a global SERIALIZATION_VERSION constant;

    • When breaking serialization changes are introduced, this global version is bumped;

    • Safe serialization primitives check this constant upon deserialization, if the data is incompatible, these primitives return an error.

    To be able to use older serialized data with newer versions, the following is done on new major TFHE-rs releases:

    • A minor update is done to the previously released branch to add the new release as an optional dependency;

    • Conversion code is added to the previous branch to be able to load old data and convert it to the new data format.

    In practice, if we take the 0.5 release as a concrete example, here is what will happen:

    • 0.5.0 is released with breaking changes to the serialization;

    • 0.4.4 has [email protected] as optional dependency gated by the forward_compatibility feature;

    • Conversion code is added to 0.4.4, if possible without any user input, but some data migration will likely require some information to be provided by the developer writing the migration code;

    circle-info

    Note that if you do not need forward compatibility 0.4.4 will be equivalent to 0.4.1 from a usability perspective and you can safely update. Note also that the 0.5.0 has no knowledge of previous releases.

    hashtag
    What it means from a developer perspective

    A set of generic tooling is given to allow migrating data by using several workflows. The data migration is considered to be an application/protocol layer concern to avoid imposing design choices.

    Examples to migrate data:

    An Application uses TFHE-rs 0.4.1 and needs/wants to upgrade to 0.5.0 to benefit from various improvements.

    Example timeline of the data migration or Bulk Data Migration:

    • A new transition version of the Application is compiled with the 0.4.4 release of TFHE-rs;

    • The transition version of the Application adds code to read previously stored data, convert it to the proper format for 0.5.0 and save it back to disk;

    The above case is describing a simple use case, where only a single version of data has to be managed. Moreover, the above strategy is not relevant in the case where the data is so large that migrating it in one go is not doable, or if the service cannot suffer any interruption.

    In order to manage more complicated cases, another method called Migrate On Read can be used.

    Here is an example timeline where data is migrated only as needed with the Migrate On Read approach:

    • A new version of the Application is compiled, it has [email protected] as dependency (the dependency will have to be renamed to avoid conflicts, a possible name is to use the major version like tfhe_0_4) and [email protected] which will not be renamed and can be accessed as tfhe

    • Code to manage reading the data is added to the Application:

    The above is more complicated to manage as data will be present on disk with several versions, however it allows to run the service continuously or near-continuously once the new Application is deployed (it will require careful routing or error handling as nodes with outdated Application won't be able to process the 0.5 data).

    Also, if required, several version of TFHE-rs can be "chained" to upgrade very old data to newer formats. The above pattern can be extended to have tfhe_0_4 ([email protected] renamed), tfhe_0_5 ([email protected] renamed) and tfhe being [email protected], this will require special handling from the developers so that their protocol can handle data from 0.4.4, 0.5.0 and 0.6.0 using all the conversion tooling from the relevant version.

    E.g., if some computation requires data from version 0.4.4 a conversion function could be called upgrade_data_from_0_4_to_0_6 and do:

    • read data from 0.4.4

    • convert to 0.5.0 format using tfhe_0_4

    • convert to 0.6.0 format using tfhe_0_5

    hashtag
    A concrete example for shortint

    The following very small sample project shows how some data can be migrated in a project following the pattern explained above:

    Cargo.toml:

    src/main.rs:

    This will output:

    The noise level here is set at usize::MAX on a 64 bits system, it corresponds to the constant NoiseLevel::UNKNOWN from shortint, as the noise level was not a value that was directly tracked in TFHE-rs the noise level is set to this unknown constant when migrating the ciphertext. It is recommended to first apply a PBS to reset the noise level to a known nominal level as some algorithms will always clean ciphertexts which are not at the nominal noise level.

    hashtag
    Breaking changes and additional migration information

    The main breaking change going from 0.4.4 to 0.5.0 with respect to data migration is that the High Level API dropped support for shortint. The boolean format has changed to use integer's BooleanBlock under the hood.

    This means that any data coming from the High Level API which previously used boolean or shortint is not supported for the data migration.

    Boolean

    In tfhe::boolean, the available operations are mainly related to their equivalent Boolean gates (i.e., AND, OR... etc). What follows are examples of a unary gate (NOT) and a binary gate (XOR). The last one is about the ternary MUX gate, which allows homomorphic computation of conditional statements of the form If..Then..Else.

    This library is meant to be used both on the server side and the client side. The typical use case should follow the subsequent steps:

    1. On the client side, generate the client and server keys.

    2. Send the server key to the server.

    3. Then any number of times:

      • On the client side, encrypt the input data with the client key.

      • Transmit the encrypted input to the server.

    hashtag
    Setup

    In the first step, the client creates two keys, the client key and the server key, with the concrete_boolean::gen_keys function:

    • The client_key is of type ClientKey. It is secret and must never be transmitted. This key will only be used to encrypt and decrypt data.

    • The server_key is of type ServerKey. It is a public key and can be shared with any party. This key has to be sent to the server because it is required for homomorphic computation.

    Note that both the client_key and server_key implement the Serialize and Deserialize traits. This way you can use any compatible serializer to store/send the data. To store the server_key in a binary file, you can use the bincode library:

    hashtag
    Encrypting inputs

    Once the server key is available on the server side, it is possible to perform some homomorphic computations. The client needs to encrypt some data and send it to the server. Again, the Ciphertext type implements the Serialize and the Deserialize traits, so that any serializer and communication tool suiting your use case can be employed:

    hashtag
    Encrypting inputs using a public key

    Anyone (the server or a third party) with the public key can also encrypt some (or all) of the inputs. The public key can only be used to encrypt, not to decrypt.

    hashtag
    Executing a Boolean circuit

    Once the encrypted inputs are on the server side, the server_key can be used to homomorphically execute the desired Boolean circuit:

    hashtag
    Decrypting the output

    Once the encrypted output is on the client side, the client_key can be used to decrypt it:

    What is TFHE-rs?

    📁 | 💛 | 🟨

    TFHE-rs is a pure Rust implementation of TFHE for Boolean and integer arithmetics over encrypted data. It includes a Rust and C API, as well as a client-side WASM API.

    TFHE-rs is meant for developers and researchers who want full control over what they can do with TFHE, while not worrying about the low level implementation.

    The goal is to have a stable, simple, high-performance, and production-ready library for all the advanced features of TFHE.

    hashtag
    Key cryptographic concepts

    The TFHE-rs library implements Zama’s variant of Fully Homomorphic Encryption over the Torus (TFHE). TFHE is based on Learning With Errors (LWE), a well-studied cryptographic primitive believed to be secure even against quantum computers.

    In cryptography, a raw value is called a message (also sometimes called a cleartext), while an encoded message is called a plaintext and an encrypted plaintext is called a ciphertext.

    The idea of homomorphic encryption is that you can compute on ciphertexts while not knowing messages encrypted within them. A scheme is said to be fully homomorphic, meaning any program can be evaluated with it, if at least two of the following operations are supported (xxxis a plaintext and E[x]E[x]E[x] is the corresponding ciphertext):

    • homomorphic univariate function evaluation: f(E[x])=E[f(x)]f(E[x]) = E[f(x)]f(E[x])=E[f(x)]

    • homomorphic addition: E[x]+E[y]=E[x+y]E[x] + E[y] = E[x + y]E[x]+E[y]=E[x+y]

    • homomorphic multiplication: E[x]∗E[y]=E[x∗y]E[x] * E[y] = E[x * y]E[x]∗E[y]=E[x∗y]

    Zama's variant of TFHE is fully homomorphic and deals with fixed-precision numbers as messages. It implements all needed homomorphic operations, such as addition and function evaluation via Programmable Bootstrapping. You can read more about Zama's TFHE variant in the preliminary whitepaperarrow-up-right.

    Using FHE in a Rust program with TFHE-rs consists in:

    • generating a client key and a server key using secure parameters:

      • a client key encrypts/decrypts data and must be kept secret

      • a server key is used to perform operations on encrypted data and could be public (also called an evaluation key)

    • encrypting plaintexts using the client key to produce ciphertexts

    • operating homomorphically on ciphertexts with the server key

    • decrypting the resulting ciphertexts into plaintexts using the client key

    If you would like to know more about the problems that FHE solves, we suggest you review our 6 minute introduction to homomorphic encryptionarrow-up-right.

    Githubarrow-up-right
    Community supportarrow-up-right
    Zama Bounty Programarrow-up-right

    0.4.4 is released.

    The service enters a maintenance period (if relevant);
  • Migration of data from 0.4.4 to 0.5.0 is done with the transition version of the Application, note that depending on the volume of data this transition can take a significant amount of time;

  • The updated version of the Application is compiled with the 0.5.0 release of TFHE-rs and put in production;

  • Service is resumed with the updated Application (if relevant).

  • The code determines whether the data was saved with the 0.4 Application or the 0.5 Application, if the data is already up to date with the 0.5 format it can be loaded right away, if it's in the 0.4 format the Application can check if an updated version of the data is already available in the 0.5 format and loads that if it's available, otherwise it converts the data to 0.5, saves the converted data to avoid having to convert it every time it is accessed and continue processing with the 0.5 data

    save to disk in 0.6.0 format

  • process 0.6.0 data with tfhe which is [email protected]

  • On the server side, perform homomorphic computation with the server key.

  • Transmit the encrypted output to the client.

  • On the client side, decrypt the output data with the client key.

  • [package]
    name = "data_migration_tfhe"
    version = "0.1.0"
    edition = "2021"
    
    # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
    
    [dependencies]
    # The project used tfhe 0.4.1, it now depends on the 0.4.4 with the forward compatibility code
    tfhe_0_4 = { package = "tfhe", version = "0.4.4", features = [
        "x86_64-unix",
        "boolean",
        "shortint",
        "integer",
        "forward_compatibility",
    ] }
    # The project now uses tfhe 0.5.0 as it's "normal/default" tfhe version for all processing except
    # data upgrade, as only old versions will be retrofitted with code to migrate code to newer versions
    tfhe = { version = "0.5", features = [
        "x86_64-unix",
        "boolean",
        "shortint",
        "integer",
    ] }
    fn old_tfhe_data_generation() -> tfhe_0_4::shortint::Ciphertext {
        use tfhe_0_4::shortint::gen_keys;
        use tfhe_0_4::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
        let (cks, sks) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
        let ct = cks.encrypt(2);
    
        ct
    }
    
    fn data_migration(old_ciphertext: tfhe_0_4::shortint::Ciphertext) {
        use tfhe::shortint::Ciphertext;
        use tfhe_0_4::forward_compatibility::ConvertInto;
    
        // Here as tfhe_0_4 depends on tfhe 0.5.0 and tfhe 0.5.0 is a dependency of our project the
        // forward compatibility works out of the box using tfhe types and the tfhe_0_4 conversion code
        let new_ct: Ciphertext = old_ciphertext.convert_into();
    
        println!("{:?}", new_ct.noise_level())
    }
    
    fn main() {
        data_migration(old_tfhe_data_generation())
    }
    NoiseLevel(18446744073709551615)
    use tfhe::boolean::prelude::*;
    
    fn main() {
    
    // We generate the client key and the server key,
    // using the default parameters:
        let (client_key, server_key): (ClientKey, ServerKey) = gen_keys();
    }
    use std::fs::File;
    use std::io::{Write, Read};
    use tfhe::boolean::prelude::*;
    
    fn main() {
    
    //---------------------------- CLIENT SIDE ----------------------------
    
    // We generate a client key and a server key, using the default parameters:
        let (client_key, server_key) = gen_keys();
    
    // We serialize the server key to bytes, and store them in a file:
        let encoded: Vec<u8> = bincode::serialize(&server_key).unwrap();
    
        let server_key_file = "/tmp/tutorial_server_key.bin";
    
    // We write the server key to a file:
        let mut file = File::create(server_key_file)
            .expect("failed to create server key file");
        file.write_all(encoded.as_slice()).expect("failed to write key to file");
    
    // ...
    // We send the key to server side
    // ...
    
    
    //---------------------------- SERVER SIDE ----------------------------
    
    // We read the file:
        let mut file = File::open(server_key_file)
            .expect("failed to open server key file");
        let mut encoded: Vec<u8> = Vec::new();
        file.read_to_end(&mut encoded).expect("failed to read key");
    
    // We deserialize the server key:
        let key: ServerKey = bincode::deserialize(&encoded[..])
            .expect("failed to deserialize");
    }
    use tfhe::boolean::prelude::*;
    
    fn main() {
        // Don't consider the following line; you should follow the procedure above.
        let (client_key, _) = gen_keys();
    
    //---------------------------- CLIENT SIDE
    
    // We use the client key to encrypt the messages:
        let ct_1 = client_key.encrypt(true);
        let ct_2 = client_key.encrypt(false);
    
    // We serialize the ciphertexts:
        let encoded_1: Vec<u8> = bincode::serialize(&ct_1).unwrap();
        let encoded_2: Vec<u8> = bincode::serialize(&ct_2).unwrap();
    
    // ...
    // And we send them to the server somehow
    // ...
    }
    use tfhe::boolean::prelude::*;
    
    fn main() {
        // Don't consider the following line; you should follow the procedure above.
        let (client_key, _) = gen_keys();
        let public_key = PublicKey::new(&client_key);
    
    //---------------------------- SERVER or THIRD_PARTY SIDE
    
    // We use the public key to encrypt the messages:
        let ct_1 = public_key.encrypt(true);
        let ct_2 = public_key.encrypt(false);
    
    // We serialize the ciphertexts (if not on the server already):
        let encoded_1: Vec<u8> = bincode::serialize(&ct_1).unwrap();
        let encoded_2: Vec<u8> = bincode::serialize(&ct_2).unwrap();
    
    // ...
    // And we send them to the server to be deserialized (if not on the server already)
    // ...
    }
    use std::fs::File;
    use std::io::{Write, Read};
    use tfhe::boolean::prelude::*;
    
    fn main() {
        // Don't consider the following lines; you should follow the procedure above.
        let (client_key, server_key) = gen_keys();
        let ct_1 = client_key.encrypt(true);
        let ct_2 = client_key.encrypt(false);
        let encoded_1: Vec<u8> = bincode::serialize(&ct_1).unwrap();
        let encoded_2: Vec<u8> = bincode::serialize(&ct_2).unwrap();
    
    //---------------------------- ON SERVER SIDE ----------------------------
    
    // We deserialize the ciphertexts:
        let ct_1: Ciphertext = bincode::deserialize(&encoded_1[..])
            .expect("failed to deserialize");
        let ct_2: Ciphertext = bincode::deserialize(&encoded_2[..])
            .expect("failed to deserialize");
    
    // We use the server key to execute the boolean circuit:
    // if ((NOT ct_2) NAND (ct_1 AND ct_2)) then (NOT ct_2) else (ct_1 AND ct_2)
        let ct_3 = server_key.not(&ct_2);
        let ct_4 = server_key.and(&ct_1, &ct_2);
        let ct_5 = server_key.nand(&ct_3, &ct_4);
        let ct_6 = server_key.mux(&ct_5, &ct_3, &ct_4);
    
    // Then we serialize the output of the circuit:
        let encoded_output: Vec<u8> = bincode::serialize(&ct_6)
            .expect("failed to serialize output");
    
    // ...
    // And we send the output to the client
    // ...
    }
    use std::fs::File;
    use std::io::{Write, Read};
    use tfhe::boolean::prelude::*;
    
    fn main() {
        // Don't consider the following lines; you should follow the procedure above.
        let (client_key, server_key) = gen_keys();
        let ct_6 = client_key.encrypt(true);
        let encoded_output: Vec<u8> = bincode::serialize(&ct_6).unwrap();
    
    //---------------------------- ON CLIENT SIDE
    
    // We deserialize the output ciphertext:
        let output: Ciphertext = bincode::deserialize(&encoded_output[..])
            .expect("failed to deserialize");
    
    // Finally, we decrypt the output:
        let output = client_key.decrypt(&output);
    
    // And check that the result is the expected one:
        assert_eq!(output, true);
    }

    Security and Cryptography

    hashtag
    TFHE

    TFHE-rs is a cryptographic library dedicated to Fully Homomorphic Encryption. As its name suggests, it is based on the TFHE scheme.

    It is necessary to understand some basics about TFHE in order to consider the limitations. Of particular importance are the precision (number of bits used to represent plaintext values) and execution time (why TFHE operations are slower than native operations).

    hashtag
    LWE ciphertexts

    Although there are many kinds of ciphertexts in TFHE, all of the encrypted values in TFHE-rs are mainly stored as LWE ciphertexts.

    The security of TFHE relies on the LWE problem, which stands for Learning With Errors. The problem is believed to be secure against quantum attacks.

    An LWE Ciphertext is a collection of 32-bit or 64-bit unsigned integers. Before encrypting a message in an LWE ciphertext, one must first encode it as a plaintext. This is done by shifting the message to the most significant bits of the unsigned integer type used.

    Then, a small random value called noise is added to the least significant bits. This noise is crucial in ensuring the security of the ciphertext.

    To go from a plaintext to a ciphertext, one must encrypt the plaintext using a secret key.

    An LWE secret key is a list of n random integers: . is called the

    An LWE ciphertext is composed of two parts:

    • The mask

    • The body

    The mask of a fresh ciphertext (one that is the result of an encryption, and not of an operation such as ciphertext addition) is a list of n uniformly random values.

    The body is computed as follows:

    Now that the encryption scheme is defined, let's review the example of the addition between ciphertexts to illustrate why it is slower to compute over encrypted data.

    To add two ciphertexts, we must add their $mask$ and $body$:

    To add ciphertexts, it is sufficient to add their masks and bodies. Instead of just adding two integers, one needs to add elements. This is an intuitive example to show the slowdown of FHE computation compared to plaintext computation, but other operations are far more expensive (e.g., the computation of a lookup table using Programmable Bootstrapping).

    hashtag
    Programmable Bootstrapping, noise management and carry bits

    In FHE, there are two types of operations that can be applied to ciphertexts:

    • leveled operations, which increase the noise in the ciphertext

    • bootstrapped operations, which reduce the noise in the ciphertext

    In FHE, noise must be tracked and managed to guarantee the correctness of the computation.

    Bootstrapping operations are used across the computation to decrease noise within the ciphertexts, preventing it from tampering with the message. The rest of the operations are called leveled because they do not need bootstrapping operations and are usually very fast as a result.

    The following sections explain the concept of noise and padding in ciphertexts.

    hashtag
    Noise.

    For it to be secure, LWE requires random noise to be added to the message at encryption time.

    In TFHE, this random noise is drawn from a Centered Normal Distribution, parameterized by a standard deviation. The chosen standard deviation has an impact on the security level. With everything else fixed, increasing the standard deviation will lead to an increase in the security level.

    In TFHE-rs, noise is encoded in the least significant bits of each plaintext. Each leveled computation increases the value of the noise. If too many computations are performed, the noise will eventually overflow into the message bits and lead to an incorrect result.

    The figure below illustrates this problem in the case of an addition, where an extra bit of noise is incurred as a result.

    TFHE-rs offers the ability to automatically manage noise by performing bootstrapping operations to reset the noise.

    hashtag
    Programmable BootStrapping (PBS)

    The bootstrapping of TFHE has the particularity of being programmable: this means that any function can be homomorphically computed over an encrypted input, while also reducing the noise. These functions are represented by look-up tables. The computation of a PBS is in general either preceded or followed by a keyswitch, which is an operation used to change the encryption key. The output ciphertext is then encrypted with the same key as the input one. To do this, two (public) evaluation keys are required: a bootstrapping key and a keyswitching key. These operations are quite complex to describe, more information about these operations (or about TFHE in general) can be found here .

    hashtag
    Carry.

    Since encoded values have a fixed precision, operating on them can produce results that are outside of the original interval. To avoid losing precision or wrapping around the interval, TFHE-rs uses additional bits by defining bits of padding on the most significant bits.

    As an example, consider adding two ciphertexts. Adding two values could end up outside the range of either ciphertext, and thus necessitate a carry, which would then be carried onto the first padding bit. In the figure below, each plaintext over 32 bits has one bit of padding on its left (i.e., the most significant bit). After the addition, the padding bit is no longer available, as it has been used in order for the carry. This is referred to as consuming bits of padding. Since no padding is left, there is no guarantee that further additions would yield correct results.

    hashtag
    Security.

    By default, the cryptographic parameters provided by TFHE-rs ensure at least 128 bits of security. The security has been evaluated using the latest versions of the Lattice Estimator () with red_cost_model = reduction.RC.BDGL16.

    For all sets of parameters, the error probability when computing a univariate function over one ciphertext is . Note that univariate functions might be performed when arithmetic functions are computed (i.e., the multiplication of two ciphertexts).

    hashtag
    Classical public key encryption.

    In classical public key encryption, the public key contains a given number of ciphertexts all encrypting the value 0. By setting the number of encryptions to 0 in the public key at , where is the LWE dimension, is the ciphertext modulus, and is the number of security bits. This construction is secure due to the leftover hash lemma, which relates to the impossibility of breaking the underlying multiple subset sum problem. This guarantees both a high-density subset sum and an exponentially large number of possible associated random vectors per LWE sample .

    plaintext=(Δ∗m)+eplaintext = (\Delta * m) + eplaintext=(Δ∗m)+e
    m∈Zpm \in \mathbb{Z}_pm∈Zp​
    S=(s0,...,sn−1)S = (s_0, ..., s_{n-1})S=(s0​,...,sn−1​)
    nnn
    LweDimensionLweDimensionLweDimension
    (a0,...,an−1)(a_0, ..., a_{n-1})(a0​,...,an−1​)
    bbb
    b=(∑i=0n−1ai∗si)+plaintextb = (\sum_{i = 0}^{n-1}{a_i * s_i}) + plaintextb=(∑i=0n−1​ai​∗si​)+plaintext
    ct0=(a0,...,an−1,b)ct1=(a0′,...,an−1′,b′)ct2=ct0+ct1ct2=(a0+a0′,...,an−1+an−1′,b+b′)b+b′=(∑i=0n−1ai∗si)+plaintext+(∑i=0n−1ai′∗si)+plaintext′b+b′=(∑i=0n−1(ai+ai′)∗si)+Δm+Δm′+e+e′ct_0 = (a_{0}, ..., a_{n-1}, b) \\ ct_1 = (a_{0}^{\prime}, ..., a_{n-1}^{\prime}, b^{\prime}) \\ ct_{2} = ct_0 + ct_1 \\ ct_{2} = (a_{0} + a_{0}^{\prime}, ..., a_{n-1} + a_{n-1}^{\prime}, b + b^{\prime})\\ b + b^{\prime} = (\sum_{i = 0}^{n-1}{a_i * s_i}) + plaintext + (\sum_{i = 0}^{n-1}{a_i^{\prime} * s_i}) + plaintext^{\prime}\\ b + b^{\prime} = (\sum_{i = 0}^{n-1}{(a_i + a_i^{\prime})* s_i}) + \Delta m + \Delta m^{\prime} + e + e^{\prime}\\ct0​=(a0​,...,an−1​,b)ct1​=(a0′​,...,an−1′​,b′)ct2​=ct0​+ct1​ct2​=(a0​+a0′​,...,an−1​+an−1′​,b+b′)b+b′=(i=0∑n−1​ai​∗si​)+plaintext+(i=0∑n−1​ai′​∗si​)+plaintext′b+b′=(i=0∑n−1​(ai​+ai′​)∗si​)+Δm+Δm′+e+e′
    n+1n + 1n+1
    2−402^{-40}2−40
    m=⌈(n+1)log⁡(q)⌉+λm = \lceil (n+1) \log(q) \rceil + \lambdam=⌈(n+1)log(q)⌉+λ
    nnn
    qqq
    λ\lambdaλ
    (a,b)(a,b)(a,b)
    TFHE Deep Divearrow-up-right
    repositoryarrow-up-right
    Noise overtaking the plaintexts after homomorphic addition. Most significant bits are on the left.

    Benchmarks

    Due to their nature, homomorphic operations are naturally slower than their cleartext equivalents. Some timings are exposed for basic operations. For completeness, benchmarks for other libraries are also given.

    circle-info

    All benchmarks were launched on an AWS m6i.metal with the following specifications: Intel(R) Xeon(R) Platinum 8375C CPU @ 2.90GHz and 512GB of RAM.

    hashtag
    Integer

    This measures the execution time for some operation sets of tfhe-rs::integer (the unsigned version). Note that the timings for FheInt (i.e., the signed integers) are similar.

    All timings are related to parallelized Radix-based integer operations, where each block is encrypted using the default parameters (i.e., PARAM_MESSAGE_2_CARRY_2_KS_PBS, more information about parameters can be found ). To ensure predictable timings, the operation flavor is the default one: the carry is propagated if needed. The operation costs may be reduced by using unchecked, checked, or smart.

    hashtag
    Shortint

    This measures the execution time for some operations using various parameter sets of tfhe-rs::shortint. Except for unchecked_add, all timings are related to the default operations. This flavor ensures predictable timings for an operation along the entire circuit by clearing the carry space after each operation.

    This uses the Concrete FFT + AVX-512 configuration.

    Parameter set
    PARAM_MESSAGE_1_CARRY_1
    PARAM_MESSAGE_2_CARRY_2
    PARAM_MESSAGE_3_CARRY_3
    PARAM_MESSAGE_4_CARRY_4

    hashtag
    Boolean

    This measures the execution time of a single binary Boolean gate.

    hashtag
    tfhe-rs::boolean.

    Parameter set
    Concrete FFT + AVX-512

    hashtag
    tfhe-lib.

    Using the same m6i.metal machine as the one for tfhe-rs, the timings are:

    Parameter set
    spqlios-fma

    hashtag
    OpenFHE (v1.1.1).

    Following the official instructions from OpenFHE, clang14 and the following command are used to setup the project: cmake -DNATIVE_SIZE=32 -DWITH_NATIVEOPT=ON -DCMAKE_C_COMPILER=clang -DCMAKE_CXX_COMPILER=clang++ -DWITH_OPENMP=OFF ..

    To use the HEXL library, the configuration used is as follows:

    Using the same m6i.metal machine as the one for tfhe-rs, the timings are:

    Parameter set
    GINX
    GINX w/ Intel HEXL

    hashtag
    How to reproduce TFHE-rs benchmarks

    TFHE-rs benchmarks can be easily reproduced from .

    If the host machine does not support AVX512, then turning on AVX512_SUPPORT will not provide any speed-up.

    Operations

    The structure and operations related to short integers are described in this section.

    hashtag
    How a shortint is represented

    In shortint, the encrypted data is stored in an LWE ciphertext.

    Conceptually, the message stored in an LWE ciphertext is divided into a carry buffer

    70.5 ms

    100 ms

    132 ms

    186 ms

    249 ms

    334 ms

    Mul (x)

    144 ms

    216 ms

    333 ms

    832 ms

    2.50 s

    8.85 s

    Equal / Not Equal (eq, ne)

    36.1 ms

    36.5 ms

    57.4 ms

    64.2 ms

    67.3 ms

    78.1 ms

    Comparisons (ge, gt, le, lt)

    52.6 ms

    73.1 ms

    98.8 ms

    124 ms

    165 ms

    201 ms

    Max / Min (max,min)

    76.2 ms

    102 ms

    135 ms

    171 ms

    212 ms

    301 ms

    Bitwise operations (&, |, ^)

    19.4 ms

    20.3 ms

    21.0 ms

    27.2 ms

    31.6 ms

    40.2 ms

    Div / Rem (/, %)

    729 ms

    1.93 s

    4.81 s

    12.2 s

    30.7 s

    89.6 s

    Left / Right Shifts (<<, >>)

    99.4 ms

    129 ms

    180 ms

    243 ms

    372 ms

    762 ms

    Left / Right Rotations (left_rotate, right_rotate)

    103 ms

    128 ms

    182 ms

    241 ms

    374 ms

    763 ms

    121 ms

    835 ms

    mul_lsb

    8.13 ms

    16.8 ms

    121 ms

    827 ms

    keyswitch_programmable_bootstrap

    7.28 ms

    16.6 ms

    121 ms

    811 ms

    Operation \ Size

    FheUint8

    FheUint16

    FheUint32

    FheUint64

    FheUint128

    FheUint256

    Negation (-)

    70.9 ms

    99.3 ms

    129 ms

    180 ms

    239 ms

    333 ms

    unchecked_add

    348 ns

    413 ns

    2.95 µs

    12.1 µs

    add

    7.59 ms

    DEFAULT_PARAMETERS_KS_PBS

    9.19 ms

    PARAMETERS_ERROR_PROB_2_POW_MINUS_165_KS_PBS

    14.1 ms

    TFHE_LIB_PARAMETERS

    10.0 ms

    default_128bit_gate_bootstrapping_parameters

    15.4 ms

    FHEW_BINGATE/STD128_OR

    40.2 ms

    31.0 ms

    FHEW_BINGATE/STD128_LMKCDEY_OR

    38.6 ms

    28.4 ms

    here
    sourcearrow-up-right

    Add / Sub (+,-)

    17.0 ms

    export CXX=clang++
    export CC=clang
    
    scripts/configure.sh
    Release -> y
    hexl -> y
    
    scripts/build-openfhe-development-hexl.sh
    #Boolean benchmarks:
    make AVX512_SUPPORT=ON bench_boolean
    
    #Integer benchmarks:
    make AVX512_SUPPORT=ON bench_integer
    
    #Shortint benchmarks:
    make AVX512_SUPPORT=ON bench_shortint
    and a
    message buffer
    .

    The message buffer is the space where the actual message is stored. This represents the modulus of the input messages (denoted by MessageModulus in the code). When doing computations on a ciphertext, the encrypted message can overflow the message modulus. The part of the message which exceeds the message modulus is stored in the carry buffer. The size of the carry buffer is defined by another modulus, called CarryModulus.

    Together, the message modulus and the carry modulus form the plaintext space that is available in a ciphertext. This space cannot be overflowed, otherwise the computation may result in an incorrect output.

    In order to ensure the correctness of the computation, we track the maximum value encrypted in a ciphertext via an associated attribute called the degree. When the degree reaches a defined threshold, the carry buffer may be emptied to safely resume the computations. In shortint the carry modulus is considered useful as a means to do more computations.

    hashtag
    Types of operations

    The operations available via a ServerKey may come in different variants:

    • operations that take their inputs as encrypted values

    • scalar operations that take at least one non-encrypted value as input

    For example, the addition has two variants:

    • ServerKey::unchecked_add, which takes two encrypted values and adds them.

    • ServerKey::unchecked_scalar_add, which takes an encrypted value and a clear value (a so-called scalar) and adds them.

    Each operation may come in different 'flavors':

    • unchecked: always does the operation, without checking if the result may exceed the capacity of the plaintext space. Using this operation might have an impact on the correctness of the following operations;

    • checked: checks are done before computing the operation, returning an error if operation cannot be done safely;

    • smart: always does the operation. If the operation cannot be computed safely, the smart operation will clear the carry to make the operation possible. Some of those will require a mutable reference as input: this is to allow the modification of the carry, but this will not change the underlying encrypted value;

    • default: always does the operation and always clears the carry. Could be slower than smart, but it ensures that the timings are consistent from one call to another.

    Not all operations have these 4 flavors, as some of them are implemented in a way that the operation is always possible without ever exceeding the plaintext space capacity.

    circle-info

    If you don't know which flavor to use, you should use the default one.

    hashtag
    How to use operation types

    Let's try to do a circuit evaluation using the different flavors of operations that we have already introduced. For a very small circuit, the unchecked flavour may be enough to do the computation correctly. Otherwise,checked and smart are the best options.

    Let's do a scalar multiplication, a subtraction, and a multiplication.

    During this computation, the carry buffer has been overflowed and, as all the operations were unchecked, the output may be incorrect.

    If we redo this same circuit with the checked flavor, a panic will occur:

    The checked flavor permits manual management of the overflow of the carry buffer by raising an error if correctness is not guaranteed.

    Using the smart flavor will output the correct result all the time. However, the computation may be slower as the carry buffer may be cleaned during the computations.

    The main advantage of the default flavor is to ensure predictable timings as long as this is the only kind of operation which is used.

    circle-exclamation

    Using default could slow-down computations.

    #List of available operations

    circle-exclamation

    Certain operations can only be used if the parameter set chosen is compatible with the bivariate programmable bootstrapping, meaning the carry buffer is larger than or equal to the message buffer. These operations are marked with a star (*).

    The list of implemented operations for shortint is:

    • addition between two ciphertexts

    • addition between a ciphertext and an unencrypted scalar

    • comparisons <, <=, >, >=, ==, != between a ciphertext and an unencrypted scalar

    • division of a ciphertext by an unencrypted scalar

    • LSB multiplication between two ciphertexts returning the result truncated to fit in the message buffer

    • multiplication of a ciphertext by an unencrypted scalar

    • bitwise shift <<, >>

    • subtraction of a ciphertext by another ciphertext

    • subtraction of a ciphertext by an unencrypted scalar

    • negation of a ciphertext

    • bitwise and, or and xor (*)

    • comparisons <, <=, >, >=, ==, != between two ciphertexts (*)

    • division between two ciphertexts (*)

    • MSB multiplication between two ciphertexts returning the part overflowing the message buffer (*)

    hashtag
    Public key encryption.

    TFHE-rs supports both private and public key encryption methods. The only difference between both lies in the encryption step: in this case, the encryption method is called using public_key instead of client_key.

    Here is a small example on how to use public encryption:

    hashtag
    Arithmetic operations.

    Classical arithmetic operations are supported by shortint:

    hashtag
    bitwise operations

    Short homomorphic integer types support some bitwise operations.

    A simple example on how to use these operations:

    hashtag
    comparisons

    Short homomorphic integer types support comparison operations.

    A simple example on how to use these operations:

    hashtag
    univariate function evaluations

    A simple example on how to use this operation to homomorphically compute the hamming weight (i.e., the number of bits equal to one) of an encrypted number.

    hashtag
    bi-variate function evaluations

    Using the shortint types offers the possibility to evaluate bi-variate functions, or functions that take two ciphertexts as input. This requires choosing a parameter set such that the carry buffer size is at least as large as the message (i.e., PARAM_MESSAGE_X_CARRY_Y with X <= Y).

    Here is a simple code example:

    Tutorial

    hashtag
    Using the core_crypto primitives

    Welcome to this tutorial about TFHE-rs core_crypto module.

    hashtag
    Setting up TFHE-rs to use the core_crypto module

    To use TFHE-rs, it first has to be added as a dependency in the Cargo.toml:

    This enables the x86_64-unix feature to have efficient implementations of various algorithms for x86_64 CPUs on a Unix-like system. The 'unix' suffix indicates that the UnixSeeder, which uses /dev/random to generate random numbers, is activated as a fallback if no hardware number generator is available (like rdseed on x86_64 or if the on Apple platforms are not available). To avoid having the UnixSeeder as a potential fallback or to run on non-Unix systems (e.g., Windows), the x86_64 feature is sufficient.

    For Apple Silicon, the aarch64-unix or aarch64 feature should be enabled. aarch64 is not supported on Windows as it's currently missing an entropy source required to seed the used in TFHE-rs.

    In short: For x86_64-based machines running Unix-like OSes:

    For Apple Silicon or aarch64-based machines running Unix-like OSes:

    For x86_64-based machines with the running Windows:

    hashtag
    Commented code to double a 2-bit message in a leveled fashion and using a PBS with the core_crypto module.

    As a complete example showing the usage of some common primitives of the core_crypto APIs, the following Rust code homomorphically computes 2 * 3 using two different methods. First using a cleartext multiplication and then using a PBS.

    Operations

    The structure and operations related to integers are described in this section.

    hashtag
    How an integer is represented

    In integer, the encrypted data is split amongst many ciphertexts encrypted with the shortint library. Below is a scheme representing an integer composed by k shortint ciphertexts.

    use tfhe::shortint::prelude::*;
    
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 3;
        let scalar = 4;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        server_key.unchecked_scalar_mul_assign(&mut ct_1, scalar);
        server_key.unchecked_sub_assign(&mut ct_1, &ct_2);
        server_key.unchecked_mul_lsb_assign(&mut ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_1);
        println!("expected {}, found {}", ((msg1 * scalar as u64 - msg2) * msg2) % modulus as u64, output);
    }
    use tfhe::shortint::prelude::*;
    
    use std::error::Error;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 3;
        let scalar = 4;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        let mut ops = || -> Result<(), Box<dyn Error>> {
            server_key.checked_scalar_mul_assign(&mut ct_1, scalar)?;
            server_key.checked_sub_assign(&mut ct_1, &ct_2)?;
            server_key.checked_mul_lsb_assign(&mut ct_1, &ct_2)?;
            Ok(())
        };
    
        match ops() {
            Ok(_) => (),
            Err(e) => {
                println!("correctness of operations is not guaranteed due to error: {}", e);
                return;
            },
        }
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar as u64 - msg2) * msg2) % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 3;
        let scalar = 4;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let mut ct_2 = client_key.encrypt(msg2);
    
        server_key.smart_scalar_mul_assign(&mut ct_1, scalar);
        server_key.smart_sub_assign(&mut ct_1, &mut ct_2);
        server_key.smart_mul_lsb_assign(&mut ct_1, &mut ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar as u64 - msg2) * msg2) % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 3;
        let scalar = 4;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let mut ct_2 = client_key.encrypt(msg2);
    
        server_key.scalar_mul_assign(&mut ct_1, scalar);
        server_key.sub_assign(&mut ct_1, &mut ct_2);
        server_key.mul_lsb_assign(&mut ct_1, &mut ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar as u64 - msg2) * msg2) % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // Generate the client key and the server key:
        let (cks, _) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
        let pks = PublicKey::new(&cks);
    
        let msg = 2;
        // Encryption of one message:
        let ct = pks.encrypt(msg);
        // Decryption:
        let dec = cks.decrypt(&ct);
        assert_eq!(dec, msg);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys to compute over Z/2^2Z, with 2 carry bits
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 2;
        let msg2 = 1;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the private client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to execute an integer circuit:
        let ct_3 = server_key.unchecked_add(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_3);
        assert_eq!(output, (msg1 + msg2) % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys to compute over Z/2^2Z, with 2 carry bits
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 2;
        let msg2 = 1;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the private client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to homomorphically compute a bitwise AND:
        let ct_3 = server_key.unchecked_bitand(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_3);
        assert_eq!(output, (msg1 & msg2) % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys to compute over Z/2^2Z, with 2 carry bits
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 2;
        let msg2 = 1;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the private client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to execute an integer circuit:
        let ct_3 = server_key.unchecked_greater_or_equal(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_3);
        assert_eq!(output, (msg1 >= msg2) as u64 % modulus as u64);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys to compute over Z/2^2Z, with 2 carry bits
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the private client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
    
        let acc = server_key.generate_lookup_table(|n| n.count_ones().into());
    
        // add the two ciphertexts
        let ct_res = server_key.apply_lookup_table(&ct_1, &acc);
    
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_res);
        assert_eq!(output, msg1.count_ones() as u64);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys to compute over Z/2^2Z, with 2 carry bits
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);
    
        let msg1 = 3;
        let msg2 = 2;
    
        let modulus = client_key.parameters.message_modulus().0 as u64;
    
        // We use the private client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let mut ct_2 = client_key.encrypt(msg2);
    
        // Compute the lookup table for the bivariate functions
        let acc = server_key.generate_lookup_table_bivariate(|x,y| (x.count_ones()
            + y.count_ones()) as u64 % modulus );
    
        let ct_res = server_key.smart_apply_lookup_table_bivariate(&ct_1, &mut ct_2, &acc);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_res);
        assert_eq!(output, (msg1.count_ones() as u64 + msg2.count_ones() as u64) % modulus);
    }
    Randomization Servicesarrow-up-right
    CSPRNGsarrow-up-right
    rdseed instructionarrow-up-right
    tfhe = { version = "0.4.4", features = [ "x86_64-unix" ] }
    tfhe = { version = "0.4.4", features = ["x86_64-unix"] }
    tfhe = { version = "0.4.4", features = ["aarch64-unix"] }
    tfhe = { version = "0.4.4", features = ["x86_64"] }
    use tfhe::core_crypto::prelude::*;
    
    pub fn main() {
        // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
        // computations
        // Define the parameters for a 4 bits message able to hold the doubled 2 bits message
        let small_lwe_dimension = LweDimension(742);
        let glwe_dimension = GlweDimension(1);
        let polynomial_size = PolynomialSize(2048);
        let lwe_modular_std_dev = StandardDev(0.000007069849454709433);
        let glwe_modular_std_dev = StandardDev(0.00000000000000029403601535432533);
        let pbs_base_log = DecompositionBaseLog(23);
        let pbs_level = DecompositionLevelCount(1);
        let ciphertext_modulus = CiphertextModulus::new_native();
    
        // Request the best seeder possible, starting with hardware entropy sources and falling back to
        // /dev/random on Unix systems if enabled via cargo features
        let mut boxed_seeder = new_seeder();
        // Get a mutable reference to the seeder as a trait object from the Box returned by new_seeder
        let seeder = boxed_seeder.as_mut();
    
        // Create a generator which uses a CSPRNG to generate secret keys
        let mut secret_generator =
            SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
    
        // Create a generator which uses two CSPRNGs to generate public masks and secret encryption
        // noise
        let mut encryption_generator =
            EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
    
        println!("Generating keys...");
    
        // Generate an LweSecretKey with binary coefficients
        let small_lwe_sk =
            LweSecretKey::generate_new_binary(small_lwe_dimension, &mut secret_generator);
    
        // Generate a GlweSecretKey with binary coefficients
        let glwe_sk =
            GlweSecretKey::generate_new_binary(glwe_dimension, polynomial_size, &mut secret_generator);
    
        // Create a copy of the GlweSecretKey re-interpreted as an LweSecretKey
        let big_lwe_sk = glwe_sk.clone().into_lwe_secret_key();
    
        // Generate the bootstrapping key, we use the parallel variant for performance reason
        let std_bootstrapping_key = par_allocate_and_generate_new_lwe_bootstrap_key(
            &small_lwe_sk,
            &glwe_sk,
            pbs_base_log,
            pbs_level,
            glwe_modular_std_dev,
            ciphertext_modulus,
            &mut encryption_generator,
        );
    
        // Create the empty bootstrapping key in the Fourier domain
        let mut fourier_bsk = FourierLweBootstrapKey::new(
            std_bootstrapping_key.input_lwe_dimension(),
            std_bootstrapping_key.glwe_size(),
            std_bootstrapping_key.polynomial_size(),
            std_bootstrapping_key.decomposition_base_log(),
            std_bootstrapping_key.decomposition_level_count(),
        );
    
        // Use the conversion function (a memory optimized version also exists but is more complicated
        // to use) to convert the standard bootstrapping key to the Fourier domain
        convert_standard_lwe_bootstrap_key_to_fourier(&std_bootstrapping_key, &mut fourier_bsk);
        // We don't need the standard bootstrapping key anymore
        drop(std_bootstrapping_key);
    
        // Our 4 bits message space
        let message_modulus = 1u64 << 4;
    
        // Our input message
        let input_message = 3u64;
    
        // Delta used to encode 4 bits of message + a bit of padding on u64
        let delta = (1_u64 << 63) / message_modulus;
    
        // Apply our encoding
        let plaintext = Plaintext(input_message * delta);
    
        // Allocate a new LweCiphertext and encrypt our plaintext
        let lwe_ciphertext_in: LweCiphertextOwned<u64> = allocate_and_encrypt_new_lwe_ciphertext(
            &small_lwe_sk,
            plaintext,
            lwe_modular_std_dev,
            ciphertext_modulus,
            &mut encryption_generator,
        );
    
        // Compute a cleartext multiplication by 2
        let mut cleartext_multiplication_ct = lwe_ciphertext_in.clone();
        println!("Performing cleartext multiplication...");
        lwe_ciphertext_cleartext_mul(
            &mut cleartext_multiplication_ct,
            &lwe_ciphertext_in,
            Cleartext(2),
        );
    
        // Decrypt the cleartext multiplication result
        let cleartext_multiplication_plaintext: Plaintext<u64> =
            decrypt_lwe_ciphertext(&small_lwe_sk, &cleartext_multiplication_ct);
    
        // Create a SignedDecomposer to perform the rounding of the decrypted plaintext
        // We pass a DecompositionBaseLog of 5 and a DecompositionLevelCount of 1 indicating we want to
        // round the 5 MSB, 1 bit of padding plus our 4 bits of message
        let signed_decomposer =
            SignedDecomposer::new(DecompositionBaseLog(5), DecompositionLevelCount(1));
    
        // Round and remove our encoding
        let cleartext_multiplication_result: u64 =
            signed_decomposer.closest_representable(cleartext_multiplication_plaintext.0) / delta;
    
        println!("Checking result...");
        assert_eq!(6, cleartext_multiplication_result);
        println!(
            "Cleartext multiplication result is correct! \
            Expected 6, got {cleartext_multiplication_result}"
        );
    
        // Now we will use a PBS to compute the same multiplication, it is NOT the recommended way of
        // doing this operation in terms of performance as it's much more costly than a multiplication
        // with a cleartext, however it resets the noise in a ciphertext to a nominal level and allows
        // to evaluate arbitrary functions so depending on your use case it can be a better fit.
    
        // Here we will define a helper function to generate an accumulator for a PBS
        fn generate_accumulator<F>(
            polynomial_size: PolynomialSize,
            glwe_size: GlweSize,
            message_modulus: usize,
            ciphertext_modulus: CiphertextModulus<u64>,
            delta: u64,
            f: F,
        ) -> GlweCiphertextOwned<u64>
        where
            F: Fn(u64) -> u64,
        {
            // N/(p/2) = size of each block, to correct noise from the input we introduce the notion of
            // box, which manages redundancy to yield a denoised value for several noisy values around
            // a true input value.
            let box_size = polynomial_size.0 / message_modulus;
    
            // Create the accumulator
            let mut accumulator_u64 = vec![0_u64; polynomial_size.0];
    
            // Fill each box with the encoded denoised value
            for i in 0..message_modulus {
                let index = i * box_size;
                accumulator_u64[index..index + box_size]
                    .iter_mut()
                    .for_each(|a| *a = f(i as u64) * delta);
            }
    
            let half_box_size = box_size / 2;
    
            // Negate the first half_box_size coefficients to manage negacyclicity and rotate
            for a_i in accumulator_u64[0..half_box_size].iter_mut() {
                *a_i = (*a_i).wrapping_neg();
            }
    
            // Rotate the accumulator
            accumulator_u64.rotate_left(half_box_size);
    
            let accumulator_plaintext = PlaintextList::from_container(accumulator_u64);
    
            let accumulator =
                allocate_and_trivially_encrypt_new_glwe_ciphertext(
                    glwe_size,
                    &accumulator_plaintext,
                    ciphertext_modulus,
                );
    
            accumulator
        }
    
        // Generate the accumulator for our multiplication by 2 using a simple closure
        let accumulator: GlweCiphertextOwned<u64> = generate_accumulator(
            polynomial_size,
            glwe_dimension.to_glwe_size(),
            message_modulus as usize,
            ciphertext_modulus,
            delta,
            |x: u64| 2 * x,
        );
    
        // Allocate the LweCiphertext to store the result of the PBS
        let mut pbs_multiplication_ct = LweCiphertext::new(
            0u64,
            big_lwe_sk.lwe_dimension().to_lwe_size(),
            ciphertext_modulus,
        );
        println!("Computing PBS...");
        programmable_bootstrap_lwe_ciphertext(
            &lwe_ciphertext_in,
            &mut pbs_multiplication_ct,
            &accumulator,
            &fourier_bsk,
        );
    
        // Decrypt the PBS multiplication result
        let pbs_multiplication_plaintext: Plaintext<u64> =
            decrypt_lwe_ciphertext(&big_lwe_sk, &pbs_multiplication_ct);
    
        // Round and remove our encoding
        let pbs_multiplication_result: u64 =
            signed_decomposer.closest_representable(pbs_multiplication_plaintext.0) / delta;
    
        println!("Checking result...");
        assert_eq!(6, pbs_multiplication_result);
        println!(
            "Multiplication via PBS result is correct! Expected 6, got {pbs_multiplication_result}"
        );
    }

    This crate implements two ways to represent an integer:

    • the Radix representation

    • the CRT (Chinese Reminder Theorem) representation

    hashtag
    Radix-based integers.

    The first possibility to represent a large integer is to use a Radix-based decomposition on the plaintexts. Let B∈NB \in \mathbb{N}B∈N be a basis such that the size of BBB is smaller than (or equal to) 4 bits. Then, an integer m∈Nm \in \mathbb{N}m∈N can be written as m=m0+m1∗B+m2∗B2+...m = m_0 + m_1*B + m_2*B^2 + ...m=m0​+m1​∗B+m2​∗B2+..., where each mim_imi​ is strictly smaller than BBB. Each mim_imi​ is then independently encrypted. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.

    The definition of an integer requires a basis and a number of blocks. These parameters are chosen at key generation. Below, the keys are dedicated to integers encrypting messages over 8 bits, using a basis over 2 bits (i.e., B=22B=2^2B=22) and 4 blocks.

    In this representation, the correctness of operations requires the carries to be propagated throughout the ciphertext. This operation is costly, since it relies on the computation of many programmable bootstrapping operations over shortints.

    hashtag
    CRT-based integers.

    The second approach to represent large integers is based on the Chinese Remainder Theorem. In this case, the basis BBB is composed of several integers bib_ibi​, such that there are pairwise coprime, and each b_ib\_ib_i has a size smaller than 4 bits. The CRT-based integer are defined modulus ∏bi\prod b_i∏bi​. For an integer mmm, its CRT decomposition is simply defined as m mod b0,m mod b1,...m \bmod{b_0}, m \bmod{b_1}, ...mmodb0​,mmodb1​,.... Each part is then encrypted as a shortint ciphertext. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.

    In the following example, the chosen basis is B=[2,3,5]B = [2, 3, 5]B=[2,3,5]. The integer is defined modulus 2∗3∗5=302*3*5 = 302∗3∗5=30. There is no need to pre-size the number of blocks since it is determined from the number of values composing the basis. Here, the integer is split over three blocks.

    This representation has many advantages: no carry propagation is required, cleaning the carry buffer of each ciphertext block is enough. This implies that operations can easily be parallelized. It also allows the efficient computation of PBS in the case where the function is CRT-compliant.

    A variant of the CRT is proposed where each block might be associated to a different key couple. Here, a keychain to the computations is required, but this may result in a performance improvement.

    hashtag
    List of available operations

    The list of operations available in integer depends on the type of representation:

    Operation name
    Radix-based
    CRT-based

    Negation

    ✔️

    ✔️

    Addition

    ✔️

    ✔️

    Scalar Addition

    ✔️

    ✔️

    hashtag
    Types of operations

    Much like shortint, the operations available via a ServerKey may come in different variants:

    • operations that take their inputs as encrypted values.

    • scalar operations take at least one non-encrypted value as input.

    For example, the addition has both variants:

    • ServerKey::unchecked_add, which takes two encrypted values and adds them.

    • ServerKey::unchecked_scalar_add, which takes an encrypted value and a clear value (the so-called scalar) and adds them.

    Each operation may come in different 'flavors':

    • unchecked: always does the operation, without checking if the result may exceed the capacity of the plaintext space.

    • checked: checks are done before computing the operation, returning an error if operation cannot be done safely.

    • smart: always does the operation, if the operation cannot be computed safely, the smart operation will propagate the carry buffer to make the operation possible. Some of those will require a mutable reference as input: this is because the inputs' carry might be cleaned, but this will not change the underlying encrypted value.

    • default: always compute the operation and always clear the carry. Could be slower than smart, but ensure that the timings are consistent from one call to another.

    Not all operations have these 4 flavors, as some of them are implemented in a way that the operation is always possible without ever exceeding the plaintext space capacity.

    circle-info

    If you don't know which flavor to use, you should use the default one.

    hashtag
    How to use each operation type

    Let's try to do a circuit evaluation using the different flavors of already introduced operations. For a very small circuit, the unchecked flavor may be enough to do the computation correctly. Otherwise, checked and smart are the best options.

    As an example, let's do a scalar multiplication, a subtraction, and an addition.

    During this computation the carry buffer has been overflowed, and the output may be incorrect as all the operations were unchecked.

    If the same circuit is done but using the checked flavor, a panic will occur:

    The checked flavor permits the manual management of the overflow of the carry buffer by raising an error if correctness is not guaranteed.

    Using the smart flavor will output the correct result all the time. However, the computation may be slower as the carry buffer may be propagated during the computations.

    circle-exclamation

    You must avoid cloning the inputs when calling smart operations to preserve performance. For instance, you SHOULD NOT have these kind of patterns in the code:

    The main advantage of the default flavor is to ensure predictable timings, as long as only this kind of operation is used. Only the parallelized version of the operations is provided.

    circle-exclamation

    Using default could slow down computations.

    SHA256 with Boolean API

    hashtag
    Intro

    In this tutorial we will go through the steps to turn a regular sha256 implementation into its homomorphic version. We explain the basics of the sha256 function first, and then how to implement it homomorphically with performance considerations.

    hashtag
    Sha256

    The first step in this experiment is actually implementing the sha256 function. We can find the specification , but let's summarize the three main sections of the document.

    hashtag
    Padding

    The sha256 function processes the input data in blocks or chunks of 512 bits. Before actually performing the hash computations we have to pad the input in the following way:

    • Append a single "1" bit

    • Append a number of "0" bits such that exactly 64 bits are left to make the message length a multiple of 512

    • Append the last 64 bits as a binary encoding of the original input length

    Or visually:

    Where the numbers on the top represent the length of the padded input at each position, and L+1+k+64 is a multiple of 512 (the length of the padded input).

    hashtag
    Operations and functions

    Let's take a look at the operations that we will use as building blocks for functions inside the sha256 computation. These are bitwise AND, XOR, NOT, addition modulo 2^32 and the Rotate Right (ROTR) and Shift Right (SHR) operations, all working with 32-bit words and producing a new word.

    We combine these operations inside the sigma (with 4 variations), Ch and Maj functions. At the end of the day, when we change the sha256 to be computed homomorphically, we will mainly change the isolated code of each operation.

    Here is the definition of each function:

    There are some things to note about the functions. Firstly we see that Maj can be simplified by applying the boolean distributive law (x AND y) XOR (x AND z) = x AND (y XOR z). So the new Maj function looks like this:

    Next we can also see that Ch can be simplified by using a single bitwise multiplexer. Let's take a look at the truth table of the Ch expression.

    x
    y
    z
    Result

    When x = 0 the result is identical to z, but when x = 1 the result is identical to y. This is the same as saying if x {y} else {z}. Hence we can replace the 4 bitwise operations of Ch by a single bitwise multiplexer.

    Note that all these operations can be evaluated homomorphically. ROTR and SHR can be evaluated by changing the index of each individual bit of the word, even if each bit is encrypted, without using any homomorphic operation. Bitwise AND, XOR and multiplexer can be computed homomorphically and addition modulo 2^32 can be broken down into boolean homomorphic operations as well.

    hashtag
    Sha256 computation

    As we have mentioned, the sha256 function works with chunks of 512 bits. For each chunk, we will compute 64 32-bit words. 16 will come from the 512 bits and the rest will be computed using the previous functions. After computing the 64 words, and still within the same chunk iteration, a compression loop will compute a hash value (8 32-bit words), again using the previous functions and some constants to mix everything up. When we finish the last chunk iteration, the resulting hash values will be the output of the sha256 function.

    Here is how this function looks like using arrays of 32 bools to represent words:

    hashtag
    Making it homomorphic

    The key idea is that we can replace each bit of padded_input with a Fully Homomorphic Encryption of the same bit value, and operate over the encrypted values using homomorphic operations. To achieve this we need to change the function signatures and deal with the borrowing rules of the Ciphertext type (which represents an encrypted bit) but the structure of the sha256 function remains the same. The part of the code that requires more consideration is the implementation of the sha256 operations, since they will use homomorphic boolean operations internally.

    Homomorphic operations are really expensive, so we have to remove their unnecessary use and maximize parallelization in order to speed up the program. To simplify our code we use the Rayon crate which provides parallel iterators and efficiently manages threads.

    The final code is available at https://github.com/zama-ai/tfhe-rs/tree/main/tfhe/examples/sha256_bool

    Let's now take a look at each sha256 operation!

    hashtag
    Rotate Right and Shift Right

    As we have highlighted, these two operations can be evaluated by changing the position of each encrypted bit in the word, thereby requiring 0 homomorphic operations. Here is our implementation:

    hashtag
    Bitwise XOR, AND, Multiplexer

    To implement these operations we will use the xor, and and mux methods provided by the tfhe library to evaluate each boolean operation homomorphically. It's important to note that, since we will operate bitwise, we can parallelize the homomorphic computations. In other words, we can homomorphically XOR the bits at index 0 of two words using a thread, while XORing the bits at index 1 using another thread, and so on. This means we could compute these bitwise operations using up to 32 concurrent threads (since we work with 32-bit words).

    Here is our implementation of the bitwise homomorphic XOR operation. The par_iter and par_iter_mut methods create a parallel iterator that we use to compute each individual XOR efficiently. The other two bitwise operations are implemented in the same way.

    hashtag
    Addition modulo 2^32

    This is perhaps the trickiest operation to efficiently implement in a homomorphic fashion. A naive implementation could use the Ripple Carry Adder algorithm, which is straightforward but cannot be parallelized because each step depends on the previous one.

    A better choice would be the Carry Lookahead Adder, which allows us to use the parallelized AND and XOR bitwise operations. With this design, our adder is around 50% faster than the Ripple Carry Adder.

    To even improve performance more, the function that computes the carry signals can also be parallelized using parallel prefix algorithms. These algorithms involve more boolean operations (so homomorphic operations for us) but may be faster because of their parallel nature. We have implemented the Brent-Kung and Ladner-Fischer algorithms, which entail different tradeoffs.

    Brent-Kung has the least amount of boolean operations we could find (140 when using grey cells, for 32-bit numbers), which makes it suitable when we can't process many operations concurrently and fast. Our results confirm that it's indeed faster than both the sequential algorithm and Ladner-Fischer when run on regular computers.

    On the other hand, Ladner-Fischer performs more boolean operations (209 using grey cells) than Brent-Kung, but they are performed in larger batches. Hence we can compute more operations in parallel and finish earlier, but we need more fast threads available or they will slow down the carry signals computation. Ladner-Fischer can be suitable when using cloud-based computing services, which offer many high-speed threads.

    Our implementation uses Brent-Kung by default, but Ladner-Fischer can be enabled when needed by using the --ladner-fischer command line argument.

    For more information about parallel prefix adders you can read or .

    Finally, with all these sha256 operations working homomorphically, our functions will be homomomorphic as well along with the whole sha256 function (after adapting the code to work with the Ciphertext type). Let's talk about other performance improvements we can make before we finish.

    hashtag
    More parallel processing

    If we inspect the main sha256_fhe function, we will find operations that can be performed in parallel. For instance, within the compression loop, temp1 and temp2 can be computed concurrently. An efficient way to parallelize computations here is using the rayon::join() function, which uses parallel processing only when there are available CPUs. Recall that the two temporary values in the compression loop are the result of several additions, so we can use nested calls to rayon::join() to potentially parallelize more operations.

    Another way to speed up consecutive additions would be using the Carry Save Adder, a very efficient adder that takes 3 numbers and returns a sum and carry sequence. If our inputs are A, B and C, we can construct a CSA with our previously implemented Maj function and the bitwise XOR operation as follows:

    By chaining CSAs, we can input the sum and carry from a preceding stage along with another number into a new CSA. Finally, to get the result of the additions we add the sum and carry sequences using a conventional adder. At the end we are performing the same number of additions, but some of them are now CSAs, speeding up the process. Let's see all this together in the temp1 and temp2 computations.

    The first closure of the outer call to join will return temp1 and the second temp2. Inside the first outer closure we call join recursively until we reach the addition of the value h, the current word w[i] and the current constant K[i] by using the CSA, while potentially computing in parallel the ch function. Then we take the sum, carry and ch values and add them again using the CSA.

    All this is done while potentially computing the sigma_upper_case_1 function. Finally we input the previous sum, carry and sigma values to the CSA and perform the final addition with add. Once again, this is done while potentially computing sigma_upper_case_0 and maj and adding them to get temp2, in the second outer closure.

    With some changes of this type, we finally get a homomorphic sha256 function that doesn't leave unused computational resources.

    hashtag
    How to use sha256_bool

    First of all, the most important thing when running the program is using the --release flag. The use of sha256_bool would look like this, given the implementation of encrypt_bools and decrypt_bools:

    By using stdin we can supply the data to hash using a file instead of the command line. For example, if our file input.txt is in the same directory as the project, we can use the following shell command after building with cargo build --release:

    Our implementation also accepts hexadecimal inputs. To be considered as such, the input must start with "0x" and contain only valid hex digits (otherwise it's interpreted as text).

    Finally see that padding is executed on the client side. This has the advantage of hiding the exact length of the input to the server, who already doesn't know anything about the contents of it but may extract information from the length.

    Another option would be to perform padding on the server side. The padding function would receive the encrypted input and pad it with trivial bit encryptions. We could then integrate the padding function inside the sha256_fhe function computed by the server.

    Homomorphic Parity Bit

    This example is dedicated to the building of a small function that homomorphically computes a parity bit.

    First, a non-generic function is written. Then, generics are used to handle the case where the function inputs are both FheBools and clear bools.

    The parity bit function takes as input two parameters:

    • A slice of Boolean

    sks.smart_add(&mut a.clone(), &mut b.clone());
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    }
    use tfhe::integer::CrtClientKey;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        let basis = vec![2, 3, 5];
        let cks = CrtClientKey::new(PARAM_MESSAGE_2_CARRY_2_KS_PBS, basis);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 12u64;
        let msg2 = 11u64;
        let msg3 = 9u64;
        let scalar = 3u64;
    
        // message_modulus^vec_length
        let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
        let ct_3 = client_key.encrypt(msg2);
    
        server_key.unchecked_small_scalar_mul_assign(&mut ct_1, scalar);
    
        server_key.unchecked_sub_assign(&mut ct_1, &ct_2);
    
        server_key.unchecked_add_assign(&mut ct_1, &ct_3);
    
        // We use the client key to decrypt the output of the circuit:
        let output: u64 = client_key.decrypt(&ct_1);
        // The carry buffer has been overflowed, the result is not correct
        assert_ne!(output, ((msg1 * scalar as u64 - msg2) + msg3) % modulus as u64);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        let num_block = 2;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 12u64;
        let msg2 = 11u64;
        let msg3 = 9u64;
        let scalar = 3u64;
    
        // message_modulus^vec_length
        let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
        let ct_3 = client_key.encrypt(msg3);
    
        let result = server_key.checked_small_scalar_mul_assign(&mut ct_1, scalar);
        assert!(result.is_ok());
    
        let result = server_key.checked_sub_assign(&mut ct_1, &ct_2);
        assert!(result.is_ok());
        
        let result = server_key.checked_add_assign(&mut ct_1, &ct_3);
        assert!(result.is_err());
    
        // We use the client key to decrypt the output of the circuit:
        // Only the scalar multiplication could be done
        let output: u64 = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar) - msg2) % modulus as u64);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 12u64;
        let msg2 = 11u64;
        let msg3 = 9u64;
        let scalar = 3u64;
    
        // message_modulus^vec_length
        let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let mut ct_2 = client_key.encrypt(msg2);
        let mut ct_3 = client_key.encrypt(msg3);
    
        server_key.smart_scalar_mul_assign(&mut ct_1, scalar);
    
        server_key.smart_sub_assign(&mut ct_1, &mut ct_2);
    
        server_key.smart_add_assign(&mut ct_1, &mut ct_3);
    
        // We use the client key to decrypt the output of the circuit:
        let output: u64 = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar as u64 - msg2) + msg3) % modulus as u64);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2_KS_PBS;
    
    fn main() {
        let num_block = 4;
        let (client_key, server_key) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2_KS_PBS, num_block);
    
        let msg1 = 12u64;
        let msg2 = 11u64;
        let msg3 = 9u64;
        let scalar = 3u64;
    
        // message_modulus^vec_length
        let modulus = client_key.parameters().message_modulus().0.pow(num_block as u32) as u64;
    
        // We use the client key to encrypt two messages:
        let mut ct_1 = client_key.encrypt(msg1);
        let mut ct_2 = client_key.encrypt(msg2);
        let mut ct_3 = client_key.encrypt(msg3);
    
        server_key.scalar_mul_assign_parallelized(&mut ct_1, scalar);
    
        server_key.sub_assign_parallelized(&mut ct_1, &mut ct_2);
    
        server_key.add_assign_parallelized(&mut ct_1, &mut ct_3);
    
        // We use the client key to decrypt the output of the circuit:
        let output: u64 = client_key.decrypt(&ct_1);
        assert_eq!(output, ((msg1 * scalar as u64 - msg2) + msg3) % modulus as u64);
    }

    Subtraction

    ✔️

    ✔️

    Scalar Subtraction

    ✔️

    ✔️

    Multiplication

    ✔️

    ✔️

    Scalar Multiplication

    ✔️

    ✔️

    Bitwise OR, AND, XOR

    ✔️

    ✔️

    Equality

    ✔️

    ✔️

    Left/Right Shift

    ✔️

    ✖️

    Comparisons <,<=,>, >=

    ✔️

    ✖️

    Min, Max

    ✔️

    ✖️

    0

    0

    0

    1

    1

    1

    1

    0

    0

    0

    1

    0

    1

    0

    1

    1

    0

    1

    1

    1

    1

    1

    0

    0

    0

    0

    0

    0

    1

    1

    0

    herearrow-up-right
    this paperarrow-up-right
    this other paperarrow-up-right

    1

    A mode (Odd or Even)

    This function returns a Boolean that will be either true or false so that the sum of Booleans (in the input and the returned one) is either an Odd or Even number, depending on the requested mode.


    hashtag
    Non-generic version.

    To use Booleans, the booleans feature in our Cargo.toml must be enabled:

    Other configurations can be found here.

    hashtag
    function definition

    First, the verification function is defined.

    The way to find the parity bit is to initialize it to false, then XOR it with all the bits, one after the other, adding negation depending on the requested mode.

    A validation function is also defined to sum together the number of the bit set within the input with the computed parity bit and check that the sum is an even or odd number, depending on the mode.

    hashtag
    final code

    After the mandatory configuration steps, the function is called:


    hashtag
    Generic version.

    To make the compute_parity_bit function compatible with both FheBool and bool, generics have to be used.

    Writing a generic function that accepts FHE types as well as clear types can help test the function to see if it is correct. If the function is generic, it can run with clear data, allowing the use of print-debugging or a debugger to spot errors.

    Writing generic functions that use operator overloading for our FHE types can be trickier than normal, since FHE types are not copy. So using the reference & is mandatory, even though this is not the case when using native types, which are all Copy.

    This will make the generic bounds trickier at first.

    hashtag
    writing the correct trait bounds

    The function has the following signature:

    To make it generic, the first step is:

    Next, the generic bounds have to be defined with the where clause.

    In the function, the following operators are used:

    • ! (trait: Not)

    • ^ (trait: BitXor)

    By adding them to where, this gives:

    However, the compiler will complain:

    fhe_bit is a reference to a BoolType (&BoolType) since it is borrowed from the fhe_bits slice when iterating over its elements. The first try is to change the BitXor bounds to what the Compiler suggests by requiring &BoolType to implement BitXor and not BoolType.

    The Compiler is still not happy:

    The way to fix this is to use Higher-Rank Trait Bounds:

    The final code will look like this:

    hashtag
    final code

    Here is a complete example that uses this function for both clear and FHE values:

    Ch(x, y, z) = (x AND y) XOR ((NOT x) AND z)
    Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
    
    Σ0(x) = ROTR-2(x) XOR ROTR-13(x) XOR ROTR-22(x)
    Σ1(x) = ROTR-6(x) XOR ROTR-11(x) XOR ROTR-25(x)
    σ0(x) = ROTR-7(x) XOR ROTR-18(x) XOR SHR-3(x)
    σ1(x) = ROTR-17(x) XOR ROTR-19(x) XOR SHR-10(x)
    Maj(x, y, z) = (x AND (y XOR z)) XOR (y AND z)
    fn sha256(padded_input: Vec<bool>) -> [bool; 256] {
    
        // Initialize hash values with constant values
        let mut hash: [[bool; 32]; 8] = [
            hex_to_bools(0x6a09e667), hex_to_bools(0xbb67ae85),
            hex_to_bools(0x3c6ef372), hex_to_bools(0xa54ff53a),
            hex_to_bools(0x510e527f), hex_to_bools(0x9b05688c),
            hex_to_bools(0x1f83d9ab), hex_to_bools(0x5be0cd19),
        ];
    
        let chunks = padded_input.chunks(512);
    
        for chunk in chunks {
            let mut w = [[false; 32]; 64];
    
            // Copy first 16 words from current chunk
            for i in 0..16 {
                w[i].copy_from_slice(&chunk[i * 32..(i + 1) * 32]);
            }
    
            // Compute the other 48 words
            for i in 16..64 {
                w[i] = add(add(add(sigma1(&w[i - 2]), w[i - 7]), sigma0(&w[i - 15])), w[i - 16]);
            }
    
            let mut a = hash[0];
            let mut b = hash[1];
            let mut c = hash[2];
            let mut d = hash[3];
            let mut e = hash[4];
            let mut f = hash[5];
            let mut g = hash[6];
            let mut h = hash[7];
    
            // Compression loop, each iteration uses a specific constant from K
            for i in 0..64 {
                let temp1 = add(add(add(add(h, ch(&e, &f, &g)), w[i]), hex_to_bools(K[i])), sigma_upper_case_1(&e));
                let temp2 = add(sigma_upper_case_0(&a), maj(&a, &b, &c));
                h = g;
                g = f;
                f = e;
                e = add(d, temp1);
                d = c;
                c = b;
                b = a;
                a = add(temp1, temp2);
            }
    
            hash[0] = add(hash[0], a);
            hash[1] = add(hash[1], b);
            hash[2] = add(hash[2], c);
            hash[3] = add(hash[3], d);
            hash[4] = add(hash[4], e);
            hash[5] = add(hash[5], f);
            hash[6] = add(hash[6], g);
            hash[7] = add(hash[7], h);
        }
    
        // Concatenate the final hash values to produce a 256-bit hash
        let mut output = [false; 256];
        for i in 0..8 {
            output[i * 32..(i + 1) * 32].copy_from_slice(&hash[i]);
        }
        output
    }
    fn rotate_right(x: &[Ciphertext; 32], n: usize) -> [Ciphertext; 32] {
        let mut result = x.clone();
        result.rotate_right(n);
        result
    }
    
    fn shift_right(x: &[Ciphertext; 32], n: usize, sk: &ServerKey) -> [Ciphertext; 32] {
        let mut result = x.clone();
        result.rotate_right(n);
        result[..n].fill_with(|| sk.trivial_encrypt(false));
        result
    }
    fn xor(a: &[Ciphertext; 32], b: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {
        let mut result = a.clone();
        result.par_iter_mut()
            .zip(a.par_iter().zip(b.par_iter()))
            .for_each(|(dst, (lhs, rhs))| *dst = sk.xor(lhs, rhs));
        result
    }
    pub fn add(a: &[Ciphertext; 32], b: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {
        let propagate = xor(a, b, sk); // Parallelized bitwise XOR
        let generate = and(a, b, sk); // Parallelized bitwise AND
    
        let carry = compute_carry(&propagate, &generate, sk);
        let sum = xor(&propagate, &carry, sk); // Parallelized bitwise XOR
    
        sum
    }
    
    fn compute_carry(propagate: &[Ciphertext; 32], generate: &[Ciphertext; 32], sk: &ServerKey) -> [Ciphertext; 32] {
        let mut carry = trivial_bools(&[false; 32], sk);
        carry[31] = sk.trivial_encrypt(false);
    
        for i in (0..31).rev() {
            carry[i] = sk.or(&generate[i + 1], &sk.and(&propagate[i + 1], &carry[i + 1]));
        }
    
        carry
    }
    Carry = Maj(A, B, C)
    Sum = A XOR B XOR C
    let (temp1, temp2) = rayon::join(
        || {
            let ((sum, carry), s1) = rayon::join(
                || {
                    let ((sum, carry), ch) = rayon::join(
                        || csa(&h, &w[i], &trivial_bools(&hex_to_bools(K[i]), sk), sk),
                        || ch(&e, &f, &g, sk),
                    );
                    csa(&sum, &carry, &ch, sk)
                },
                || sigma_upper_case_1(&e, sk)
            );
    
            let (sum, carry) = csa(&sum, &carry, &s1, sk);
            add(&sum, &carry, sk)
        },
        || {
            add(&sigma_upper_case_0(&a, sk), &maj(&a, &b, &c, sk), sk)
        },
    );
    fn main() {
        let matches = Command::new("Homomorphic sha256")
            .arg(Arg::new("ladner_fischer")
                .long("ladner-fischer")
                .help("Use the Ladner Fischer parallel prefix algorithm for additions")
                .action(ArgAction::SetTrue))
            .get_matches();
    
        // If set using the command line flag "--ladner-fischer" this algorithm will be used in additions
        let ladner_fischer: bool = matches.get_flag("ladner_fischer");
    
        // INTRODUCE INPUT FROM STDIN
    
        let mut input = String::new();
        println!("Write input to hash:");
    
        io::stdin()
            .read_line(&mut input)
            .expect("Failed to read line");
    
        input = input.trim_end_matches('\n').to_string();
    
        println!("You entered: \"{}\"", input);
    
        // CLIENT PADS DATA AND ENCRYPTS IT
    
        let (ck, sk) = gen_keys();
    
        let padded_input = pad_sha256_input(&input);
        let encrypted_input = encrypt_bools(&padded_input, &ck);
    
        // SERVER COMPUTES OVER THE ENCRYPTED PADDED DATA
    
        println!("Computing the hash");
        let encrypted_output = sha256_fhe(encrypted_input, ladner_fischer, &sk);
    
        // CLIENT DECRYPTS THE OUTPUT
    
        let output = decrypt_bools(&encrypted_output, &ck);
        let outhex = bools_to_hex(output);
    
        println!("{}", outhex);
    }
    ./target/release/examples/sha256_bool < input.txt
    # Cargo.toml
    
    # Default configuration for x86 Unix machines:
    tfhe = { version = "0.4.4", features = ["boolean", "x86_64-unix"]}
    use tfhe::FheBool;
    use tfhe::prelude::*;
    
    #[derive(Copy, Clone, Debug)]
    enum ParityMode {
        // The sum bits of message + parity bit must an odd number
        Odd,
        // The sum bits of message + parity bit must an even number
        Even,
    }
    
    fn compute_parity_bit(fhe_bits: &[FheBool], mode: ParityMode) -> FheBool {
        let mut parity_bit = fhe_bits[0].clone();
        for fhe_bit in &fhe_bits[1..] {
            parity_bit = fhe_bit ^ parity_bit
        }
    
        match mode {
            ParityMode::Odd => !parity_bit,
            ParityMode::Even => parity_bit,
        }
    }
    
    fn is_even(n: u8) -> bool {
        (n & 1) == 0
    }
    
    fn is_odd(n: u8) -> bool {
        !is_even(n)
    }
    
    fn check_parity_bit_validity(bits: &[bool], mode: ParityMode, parity_bit: bool) -> bool {
        let num_bit_set = bits
            .iter()
            .map(|bit| *bit as u8)
            .fold(parity_bit as u8, |acc, bit| acc + bit);
    
        match mode {
            ParityMode::Even => is_even(num_bit_set),
            ParityMode::Odd => is_odd(num_bit_set),
        }
    }
    use tfhe::{FheBool, ConfigBuilder, generate_keys, set_server_key};
    use tfhe::prelude::*;
    
    #[derive(Copy, Clone, Debug)]
    enum ParityMode {
        // The sum bits of message + parity bit must an odd number
        Odd,
        // The sum bits of message + parity bit must an even number
        Even,
    }
    
    fn compute_parity_bit(fhe_bits: &[FheBool], mode: ParityMode) -> FheBool {
        let mut parity_bit = fhe_bits[0].clone();
        for fhe_bit in &fhe_bits[1..] {
            parity_bit = fhe_bit ^ parity_bit
        }
    
        match mode {
            ParityMode::Odd => !parity_bit,
            ParityMode::Even => parity_bit,
        }
    }
    
    fn is_even(n: u8) -> bool {
        (n & 1) == 0
    }
    
    fn is_odd(n: u8) -> bool {
        !is_even(n)
    }
    
    fn check_parity_bit_validity(bits: &[bool], mode: ParityMode, parity_bit: bool) -> bool {
        let num_bit_set = bits
            .iter()
            .map(|bit| *bit as u8)
            .fold(parity_bit as u8, |acc, bit| acc + bit);
    
        match mode {
            ParityMode::Even => is_even(num_bit_set),
            ParityMode::Odd => is_odd(num_bit_set),
        }
    }
    
    fn main() {
        let config = ConfigBuilder::all_disabled().enable_default_bool().build();
    
        let (client_key, server_key) = generate_keys(config);
    
        set_server_key(server_key);
    
        let clear_bits = [0, 1, 0, 0, 0, 1, 1].map(|b| (b != 0) as bool);
    
        let fhe_bits = clear_bits
            .iter()
            .map(|bit| FheBool::encrypt(*bit, &client_key))
            .collect::<Vec<FheBool>>();
    
        let mode = ParityMode::Odd;
        let fhe_parity_bit = compute_parity_bit(&fhe_bits, mode);
        let decrypted_parity_bit = fhe_parity_bit.decrypt(&client_key);
        let is_parity_bit_valid = check_parity_bit_validity(&clear_bits, mode, decrypted_parity_bit);
        println!("Parity bit is set: {} for mode: {:?}", decrypted_parity_bit, mode);
        assert!(is_parity_bit_valid);
    
        let mode = ParityMode::Even;
        let fhe_parity_bit = compute_parity_bit(&fhe_bits, mode);
        let decrypted_parity_bit = fhe_parity_bit.decrypt(&client_key);
        let is_parity_bit_valid = check_parity_bit_validity(&clear_bits, mode, decrypted_parity_bit);
        println!("Parity bit is set: {} for mode: {:?}", decrypted_parity_bit, mode);
        assert!(is_parity_bit_valid);
    }
    fn check_parity_bit_validity(
        fhe_bits: &[FheBool],
        mode: ParityMode,
    ) -> bool
    fn compute_parity_bit<BoolType>(
        fhe_bits: &[BoolType],
        mode: ParityMode,
    ) -> BoolType
    where
        BoolType: Clone + Not<Output = BoolType>,
        BoolType: BitXor<BoolType, Output=BoolType>,
    ---- src/user_doc_tests.rs - user_doc_tests (line 199) stdout ----
    error[E0369]: no implementation for `&BoolType ^ BoolType`
    --> src/user_doc_tests.rs:218:30
        |
    21  | parity_bit = fhe_bit ^ parity_bit
        |              ------- ^ ---------- BoolType
        |             |
        |             &BoolType
        |
    help: consider extending the `where` bound, but there might be an alternative better way to express this requirement
        |
    17  | BoolType: BitXor<BoolType, Output=BoolType>, &BoolType: BitXor<BoolType>
        |                                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    error: aborting due to previous error
    where
        BoolType: Clone + Not<Output = BoolType>,
        &BoolType: BitXor<BoolType, Output=BoolType>,
    ---- src/user_doc_tests.rs - user_doc_tests (line 236) stdout ----
    error[E0637]: `&` without an explicit lifetime name cannot be used here
      --> src/user_doc_tests.rs:251:5
       |
    17 |     &BoolType: BitXor<BoolType, Output=BoolType>,
       |     ^ explicit lifetime name needed here
    
    error[E0310]: the parameter type `BoolType` may not live long enough
      --> src/user_doc_tests.rs:251:16
       |
    17 |     &BoolType: BitXor<BoolType, Output=BoolType>,
       |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...so that the reference type `&'static BoolType` does not outlive the data it points at
       |
    help: consider adding an explicit lifetime bound...
       |
    15 |     BoolType: Clone + Not<Output = BoolType> + 'static,
       |
    where
        BoolType: Clone + Not<Output = BoolType>,
        for<'a> &'a BoolType: BitXor<BoolType, Output = BoolType>,
    use std::ops::{Not, BitXor};
    
    #[derive(Copy, Clone, Debug)]
    enum ParityMode {
        // The sum bits of message + parity bit must an odd number
        Odd,
        // The sum bits of message + parity bit must an even number
        Even,
    }
    
    fn compute_parity_bit<BoolType>(fhe_bits: &[BoolType], mode: ParityMode) -> BoolType
    where
        BoolType: Clone + Not<Output = BoolType>,
        for<'a> &'a BoolType: BitXor<BoolType, Output = BoolType>,
    {
        let mut parity_bit = fhe_bits[0].clone();
        for fhe_bit in &fhe_bits[1..] {
            parity_bit = fhe_bit ^ parity_bit
        }
    
        match mode {
            ParityMode::Odd => !parity_bit,
            ParityMode::Even => parity_bit,
        }
    }
    use tfhe::{FheBool, ConfigBuilder, generate_keys, set_server_key};
    use tfhe::prelude::*;
    
    use std::ops::{Not, BitXor};
    
    #[derive(Copy, Clone, Debug)]
    enum ParityMode {
        // The sum bits of message + parity bit must an odd number
        Odd,
        // The sum bits of message + parity bit must an even number
        Even,
    }
    
    fn compute_parity_bit<BoolType>(fhe_bits: &[BoolType], mode: ParityMode) -> BoolType
        where
            BoolType: Clone + Not<Output=BoolType>,
            for<'a> &'a BoolType: BitXor<BoolType, Output=BoolType>,
    {
        let mut parity_bit = fhe_bits[0].clone();
        for fhe_bit in &fhe_bits[1..] {
            parity_bit = fhe_bit ^ parity_bit
        }
    
        match mode {
            ParityMode::Odd => !parity_bit,
            ParityMode::Even => parity_bit,
        }
    }
    
    fn is_even(n: u8) -> bool {
        (n & 1) == 0
    }
    
    fn is_odd(n: u8) -> bool {
        !is_even(n)
    }
    
    fn check_parity_bit_validity(bits: &[bool], mode: ParityMode, parity_bit: bool) -> bool {
        let num_bit_set = bits
            .iter()
            .map(|bit| *bit as u8)
            .fold(parity_bit as u8, |acc, bit| acc + bit);
    
        match mode {
            ParityMode::Even => is_even(num_bit_set),
            ParityMode::Odd => is_odd(num_bit_set),
        }
    }
    
    fn main() {
        let config = ConfigBuilder::all_disabled().enable_default_bool().build();
    
        let ( client_key, server_key) = generate_keys(config);
    
        set_server_key(server_key);
    
        let clear_bits = [0, 1, 0, 0, 0, 1, 1].map(|b| (b != 0) as bool);
    
        let fhe_bits = clear_bits
            .iter()
            .map(|bit| FheBool::encrypt(*bit, &client_key))
            .collect::<Vec<FheBool>>();
    
        let mode = ParityMode::Odd;
        let clear_parity_bit = compute_parity_bit(&clear_bits, mode);
        let fhe_parity_bit = compute_parity_bit(&fhe_bits, mode);
        let decrypted_parity_bit = fhe_parity_bit.decrypt(&client_key);
        let is_parity_bit_valid = check_parity_bit_validity(&clear_bits, mode, decrypted_parity_bit);
        println!("Parity bit is set: {} for mode: {:?}", decrypted_parity_bit, mode);
        assert!(is_parity_bit_valid);
        assert_eq!(decrypted_parity_bit, clear_parity_bit);
    
        let mode = ParityMode::Even;
        let clear_parity_bit = compute_parity_bit(&clear_bits, mode);
        let fhe_parity_bit = compute_parity_bit(&fhe_bits, mode);
        let decrypted_parity_bit = fhe_parity_bit.decrypt(&client_key);
        let is_parity_bit_valid = check_parity_bit_validity(&clear_bits, mode, decrypted_parity_bit);
        println!("Parity bit is set: {} for mode: {:?}", decrypted_parity_bit, mode);
        assert!(is_parity_bit_valid);
        assert_eq!(decrypted_parity_bit, clear_parity_bit);
    }

    Dark Market with Integer API

    In this tutorial, we are going to build a dark market application using TFHE-rs. A dark market is a marketplace where buy and sell orders are not visible to the public before they are filled. Different algorithms aim to solve this problem, we are going to implement the algorithm defined in this paperarrow-up-right with TFHE-rs.

    We will first implement the algorithm in plain Rust and then we will see how to use TFHE-rs to implement the same algorithm with FHE.

    In addition, we will also implement a modified version of the algorithm that allows for more concurrent operations which improves the performance in hardware where there are multiple cores.

    hashtag
    Specifications

    hashtag
    Inputs:

    • A list of sell orders where each sell order is only defined in volume terms, it is assumed that the price is fetched from a different source.

    • A list of buy orders where each buy order is only defined in volume terms, it is assumed that the price is fetched from a different source.

    hashtag
    Input constraints:

    • The sell and buy orders are within the range [1,100].

    • The maximum number of sell and buy orders is 500, respectively.

    hashtag
    Outputs:

    There is no output returned at the end of the algorithm. Instead, the algorithm makes changes on the given input lists. The number of filled orders is written over the original order count in the respective lists. If it is not possible to fill the orders, the order count is set to zero.

    hashtag
    Example input and output:

    Example 1:

    Sell
    Buy

    Last three indices of the filled sell orders are zero because there is no buy orders to match them.

    Example 2:

    Sell
    Buy

    Last three indices of the filled buy orders are zero because there is no sell orders to match them.

    hashtag
    Plain Implementation

    1. Calculate the total sell volume and the total buy volume.

    1. Find the total volume that will be transacted. In the paper, this amount is calculated with the formula:

    When closely observed, we can see that this formula can be replaced with the min function. Therefore, we calculate this value by taking the minimum of the total sell volume and the total buy volume.

    1. Beginning with the first item, start filling the sell orders one by one. We apply the min function replacement also here.

    The number of orders that are filled is indicated by modifying the input list. For example, if the first sell order is 1000 and the total volume is 500, then the first sell order will be modified to 500 and the second sell order will be modified to 0.

    1. Do the fill operation also for the buy orders.

    hashtag
    The complete algorithm in plain Rust:

    hashtag
    FHE Implementation

    For the FHE implementation, we first start with finding the right bit size for our algorithm to work without overflows.

    The variables that are declared in the algorithm and their maximum values are described in the table below:

    Variable
    Maximum Value
    Bit Size

    As we can observe from the table, we need 16 bits of message space to be able to run the algorithm without overflows. TFHE-rs provides different presets for the different bit sizes. Since we need 16 bits of message, we are going to use the integer module to implement the algorithm.

    Here are the input types of our algorithm:

    • sell_orders is of type Vec<tfhe::integer::RadixCipherText>

    • buy_orders is of type Vec<tfhe::integer::RadixCipherText>

    Now, we can start implementing the algorithm with FHE:

    1. Calculate the total sell volume and the total buy volume.

    1. Find the total volume that will be transacted by taking the minimum of the total sell volume and the total buy volume.

    1. Beginning with the first item, start filling the sell and buy orders one by one. We can create fill_orders closure to reduce code duplication since the code for filling buy orders and sell orders are the same.

    hashtag
    The complete algorithm in TFHE-rs:

    hashtag
    Optimizing the implementation

    • TFHE-rs provides parallelized implementations of the operations. We can use these parallelized implementations to speed up the algorithm. For example, we can use smart_add_assign_parallelized instead of smart_add_assign.

    • We can parallelize vector sum with Rayon and reduce operation.

    • We can run vector summation on buy_orders and sell_orders in parallel since these operations do not depend on each other.

    • We can match sell and buy orders in parallel since the matching does not depend on each other.

    hashtag
    Optimized algorithm

    hashtag
    Modified Algorithm

    When observed closely, there is only a small amount of concurrency introduced in the fill_orders part of the algorithm. The reason is that the volume_left_to_transact is shared between all the orders and should be modified sequentially. This means that the orders cannot be filled in parallel. If we can somehow remove this dependency, we can fill the orders in parallel.

    In order to do so, we closely observe the function of volume_left_to_transact variable in the algorithm. We can see that it is being used to check whether we can fill the current order or not. Instead of subtracting the current order value from volume_left_to_transact in each loop, we can add this value to the next order index and check the availability by comparing the current order value with the total volume. If the current order value (now representing the sum of values before this order plus this order) is smaller than the total number of matching orders, we can safely fill all the orders and continue the loop. If not, we should partially fill the orders with what is left from matching orders.

    We will call the new list the "prefix sum" of the array.

    The new version for the plain fill_orders is as follows:

    To write this new function we need transform the conditional code into a mathematical expression since FHE does not support conditional operations.

    New fill_order function requires a prefix sum array. We are going to calculate this prefix sum array in parallel with the algorithm described .

    The sample code in the paper is written in CUDA. When we try to implement the algorithm in Rust we see that the compiler does not allow us to do so. The reason for that is while the algorithm does not access the same array element in any of the threads(the index calculations using d and k values never overlap), Rust compiler cannot understand this and does not let us share the same array between threads. So we modify how the algorithm is implemented, but we don't change the algorithm itself.

    Here is the modified version of the algorithm in TFHE-rs:

    hashtag
    Running the tutorial

    The plain, FHE and parallel FHE implementations can be run by providing respective arguments as described below.

    hashtag
    Conclusion

    In this tutorial, we've learned how to implement the volume matching algorithm described in plain Rust and in TFHE-rs. We've identified the right bit size for our problem at hand, used operations defined in TFHE-rs, and introduced concurrency to the algorithm to increase its performance.

    Quick Start

    This library makes it possible to execute homomorphic operations over encrypted data, where the data are either Booleans, short integers (named shortint in the rest of this documentation), or integers up to 256 bits. It allows you to execute a circuit on an untrusted server because both circuit inputs and outputs are kept private. Data are indeed encrypted on the client side, before being sent to the server. On the server side, every computation is performed on ciphertexts.

    The server, however, has to know the circuit to be evaluated. At the end of the computation, the server returns the encryption of the result to the user. Then the user can decrypt it with the secret key.

    hashtag
    General method to write an homomorphic circuit program

    The overall process to write an homomorphic program is the same for all types. The basic steps for using the TFHE-rs library are the following:

    1. Choose a data type (Boolean, shortint, integer)

    2. Import the library

    3. Create client and server keys

    hashtag
    API levels.

    This library has different modules, with different levels of abstraction.

    There is the core_crypto module, which is the lowest level API with the primitive functions and types of the TFHE scheme.

    Above the core_crypto module, there are the Boolean, shortint, and integer modules, which contain easy to use APIs enabling evaluation of Boolean, short integer, and integer circuits.

    Finally, there is the high-level module built on top of the Boolean, shortint, integer modules. This module is meant to abstract cryptographic complexities: no cryptographical knowledge is required to start developing an FHE application. Another benefit of the high-level module is the drastically simplified development process compared to lower level modules.

    hashtag
    high-level API

    TFHE-rs exposes a high-level API by default that includes datatypes that try to match Rust's native types by having overloaded operators (+, -, ...).

    Here is an example of how the high-level API is used:

    circle-exclamation

    Use the --release flag to run this example (eg: cargo run --release)

    hashtag
    Boolean example

    Here is an example of how the library can be used to evaluate a Boolean circuit:

    circle-exclamation

    Use the --release flag to run this example (eg: cargo run --release)

    hashtag
    shortint example

    Here is a full example using shortint:

    circle-exclamation

    Use the --release flag to run this example (eg: cargo run --release)

    hashtag
    integer example

    circle-exclamation

    Use the --release flag to run this example (eg: cargo run --release)

    The library is simple to use and can evaluate homomorphic circuits of arbitrary length. The description of the algorithms can be found in the paper (also available as ).

    50000

    16

    sell_order

    100

    7

    buy_order

    100

    7

    server_key is of type tfhe::integer::ServerKey

    Input

    [ 5, 12, 7, 4, 3 ]

    [ 19, 2 ]

    Output

    [ 5, 12, 4, 0, 0 ]

    [ 19, 2 ]

    Input

    [ 3, 1, 1, 4, 2 ]

    [ 5, 3, 3, 2, 4, 1 ]

    Output

    [ 3, 1, 1, 4, 2 ]

    [ 5, 3, 3, 0, 0, 0 ]

    total_sell_volume

    50000

    16

    total_buy_volume

    50000

    16

    total_volume

    50000

    16

    herearrow-up-right
    in this paperarrow-up-right

    volume_left_to_transact

    Encrypt data with the client key
  • Compute over encrypted data using the server key

  • Decrypt data with the client key

  • TFHEarrow-up-right
    ePrint 2018/421arrow-up-right
    let total_sell_volume: u16 = sell_orders.iter().sum();
    let total_buy_volume: u16 = buy_orders.iter().sum();
    (total_sell_volume > total_buy_volume) * (total_buy_volume − total_sell_volume) + total_sell_volume
    let total_volume = std::cmp::min(total_buy_volume, total_sell_volume);
    let mut volume_left_to_transact = total_volume;
    for sell_order in sell_orders.iter_mut() {
        let filled_amount = std::cmp::min(volume_left_to_transact, *sell_order);
        *sell_order = filled_amount;
        volume_left_to_transact -= filled_amount;
    }
    let mut volume_left_to_transact = total_volume;
    for buy_order in buy_orders.iter_mut() {
        let filled_amount = std::cmp::min(volume_left_to_transact, *buy_order);
        *buy_order = filled_amount;
        volume_left_to_transact -= filled_amount;
    }
    fn fill_orders(orders: &mut [u16], total_volume: u16) {
        let mut volume_left_to_transact = total_volume;
        for order in orders {
            let filled_amount = std::cmp::min(volume_left_to_transact, *order);
            *order = filled_amount;
            volume_left_to_transact -= filled_amount;
        }
    }
    
    pub fn volume_match(sell_orders: &mut [u16], buy_orders: &mut [u16]) {
        let total_sell_volume: u16 = sell_orders.iter().sum();
        let total_buy_volume: u16 = buy_orders.iter().sum();
    
        let total_volume = std::cmp::min(total_buy_volume, total_sell_volume);
    
        fill_orders(sell_orders, total_volume);
        fill_orders(buy_orders, total_volume);
    }
    fn vector_sum(server_key: &ServerKey, orders: &mut [RadixCiphertext]) -> RadixCiphertext {
        let mut total_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
        for order in orders {
            server_key.smart_add_assign(&mut total_volume, order);
        }
        total_volume
    }
    
    let mut total_sell_volume = vector_sum(server_key, sell_orders);
    let mut total_buy_volume = vector_sum(server_key, buy_orders);
    
    let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);
    fn fill_orders(
        server_key: &ServerKey,
        orders: &mut [RadixCiphertext],
        total_volume: RadixCiphertext,
    ) {
        let mut volume_left_to_transact = total_volume;
        for order in orders {
            let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, order);
            server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
            *order = filled_amount;
        }
    }
    
    fill_orders(server_key, sell_orders, total_volume.clone());
    fill_orders(server_key, buy_orders, total_volume);
    const NUMBER_OF_BLOCKS: usize = 8;
    
    fn vector_sum(server_key: &ServerKey, orders: &mut [RadixCiphertext]) -> RadixCiphertext {
        let mut total_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
        for order in orders {
            server_key.smart_add_assign(&mut total_volume, order);
        }
        total_volume
    }
    
    fn fill_orders(
        server_key: &ServerKey,
        orders: &mut [RadixCiphertext],
        total_volume: RadixCiphertext,
    ) {
        let mut volume_left_to_transact = total_volume;
        for order in orders {
            let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, order);
            server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
            *order = filled_amount;
        }
    }
    
    pub fn volume_match(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        let mut total_sell_volume = vector_sum(server_key, sell_orders);
        let mut total_buy_volume = vector_sum(server_key, buy_orders);
    
        let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);
    
        fill_orders(server_key, sell_orders, total_volume.clone());
        fill_orders(server_key, buy_orders, total_volume);
    }
    fn vector_sum(server_key: &ServerKey, orders: Vec<RadixCiphertext>) -> RadixCiphertext {
        orders.into_par_iter().reduce(
            || server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS),
            |mut acc: RadixCiphertext, mut ele: RadixCiphertext| {
                server_key.smart_add_parallelized(&mut acc, &mut ele)
            },
        )
    }
    let (mut total_sell_volume, mut total_buy_volume) = rayon::join(
        || vector_sum(server_key, sell_orders.to_owned()),
        || vector_sum(server_key, buy_orders.to_owned()),
    );
    rayon::join(
        || fill_orders(server_key, sell_orders, total_volume.clone()),
        || fill_orders(server_key, buy_orders, total_volume.clone()),
    );
    fn vector_sum(server_key: &ServerKey, orders: Vec<RadixCiphertext>) -> RadixCiphertext {
        orders.into_par_iter().reduce(
            || server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS),
            |mut acc: RadixCiphertext, mut ele: RadixCiphertext| {
                server_key.smart_add_parallelized(&mut acc, &mut ele)
            },
        )
    }
    
    fn fill_orders(
        server_key: &ServerKey,
        orders: &mut [RadixCiphertext],
        total_volume: RadixCiphertext,
    ) {
        let mut volume_left_to_transact = total_volume;
        for order in orders {
            let mut filled_amount =
                server_key.smart_min_parallelized(&mut volume_left_to_transact, order);
            server_key.smart_sub_assign_parallelized(&mut volume_left_to_transact, &mut filled_amount);
            *order = filled_amount;
        }
    }
    
    pub fn volume_match(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        let (mut total_sell_volume, mut total_buy_volume) = rayon::join(
            || vector_sum(server_key, sell_orders.to_owned()),
            || vector_sum(server_key, buy_orders.to_owned()),
        );
    
        let total_volume =
            server_key.smart_min_parallelized(&mut total_sell_volume, &mut total_buy_volume);
        rayon::join(
            || fill_orders(server_key, sell_orders, total_volume.clone()),
            || fill_orders(server_key, buy_orders, total_volume.clone()),
        );
    }
    fn fill_orders(total_orders: u16, orders: &mut [u16], prefix_sum_arr: &[u16]) {
        orders.iter().for_each(|order : &mut u64| {
            let previous_prefix_sum = if i == 0 { 0 } else { prefix_sum_arr[i - 1] };
            
            let diff = total_orders as i64 - previous_prefix_sum as i64;
            
            if (diff < 0) {
                *order = 0;
            } else if diff < order {
                *order = diff as u16;
            } else {
                // *order = *order;
                continue;
            }
        });
    };
    
    fn fill_orders(total_orders: u16, orders: &mut [u16], prefix_sum_arr: &[u16]) {
        for (i, order) in orders.iter_mut().enumerate() {
            let previous_prefix_sum = if i == 0 { 0 } else { prefix_sum_arr[i - 1] };
    
            *order = (total_orders as i64 - previous_prefix_sum as i64)
                .max(0)
                .min(*order as i64) as u16;
        }
    }
    fn compute_prefix_sum(server_key: &ServerKey, arr: &[RadixCiphertext]) -> Vec<RadixCiphertext> {
        if arr.is_empty() {
            return arr.to_vec();
        }
        let mut prefix_sum: Vec<RadixCiphertext> = (0..arr.len().next_power_of_two())
            .into_par_iter()
            .map(|i| {
                if i < arr.len() {
                    arr[i].clone()
                } else {
                    server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS)
                }
            })
            .collect();
        for d in 0..prefix_sum.len().ilog2() {
            prefix_sum
                .par_chunks_exact_mut(2_usize.pow(d + 1))
                .for_each(move |chunk| {
                    let length = chunk.len();
                    let mut left = chunk.get((length - 1) / 2).unwrap().clone();
                    server_key.smart_add_assign_parallelized(chunk.last_mut().unwrap(), &mut left)
                });
        }
        let last = prefix_sum.last().unwrap().clone();
        *prefix_sum.last_mut().unwrap() = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
        for d in (0..prefix_sum.len().ilog2()).rev() {
            prefix_sum
                .par_chunks_exact_mut(2_usize.pow(d + 1))
                .for_each(move |chunk| {
                    let length = chunk.len();
                    let temp = chunk.last().unwrap().clone();
                    let mut mid = chunk.get((length - 1) / 2).unwrap().clone();
                    server_key.smart_add_assign_parallelized(chunk.last_mut().unwrap(), &mut mid);
                    chunk[(length - 1) / 2] = temp;
                });
        }
        prefix_sum.push(last);
        prefix_sum[1..=arr.len()].to_vec()
    }
    
    fn fill_orders(
        server_key: &ServerKey,
        total_orders: &RadixCiphertext,
        orders: &mut [RadixCiphertext],
        prefix_sum_arr: &[RadixCiphertext],
    ) {
        orders
            .into_par_iter()
            .enumerate()
            .for_each(move |(i, order)| {
                // (total_orders - previous_prefix_sum).max(0)
                let mut diff = if i == 0 {
                    total_orders.clone()
                } else {
                    let previous_prefix_sum = &prefix_sum_arr[i - 1];
    
                    // total_orders - previous_prefix_sum
                    let mut diff = server_key.smart_sub_parallelized(
                        &mut total_orders.clone(),
                        &mut previous_prefix_sum.clone(),
                    );
    
                    // total_orders > prefix_sum
                    let mut cond = server_key.smart_gt_parallelized(
                        &mut total_orders.clone(),
                        &mut previous_prefix_sum.clone(),
                    );
    
                    // (total_orders - previous_prefix_sum) * (total_orders > previous_prefix_sum)
                    // = (total_orders - previous_prefix_sum).max(0)
                    server_key.smart_mul_parallelized(&mut cond, &mut diff)
                };
    
                // (total_orders - previous_prefix_sum).max(0).min(*order);
                *order = server_key.smart_min_parallelized(&mut diff, order);
            });
    }
    
    /// FHE implementation of the volume matching algorithm.
    ///
    /// In this function, the implemented algorithm is modified to utilize more concurrency.
    ///
    /// Matches the given encrypted [sell_orders] with encrypted [buy_orders] using the given
    /// [server_key]. The amount of the orders that are successfully filled is written over the original
    /// order count.
    pub fn volume_match(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        println!("Creating prefix sum arrays...");
        let time = Instant::now();
        let (prefix_sum_sell_orders, prefix_sum_buy_orders) = rayon::join(
            || compute_prefix_sum(server_key, sell_orders),
            || compute_prefix_sum(server_key, buy_orders),
        );
        println!("Created prefix sum arrays in {:?}", time.elapsed());
    
        let zero = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    
        let total_buy_orders = prefix_sum_buy_orders.last().unwrap_or(&zero);
    
        let total_sell_orders = prefix_sum_sell_orders.last().unwrap_or(&zero);
    
        println!("Matching orders...");
        let time = Instant::now();
        rayon::join(
            || {
                fill_orders(
                    server_key,
                    total_sell_orders,
                    buy_orders,
                    &prefix_sum_buy_orders,
                )
            },
            || {
                fill_orders(
                    server_key,
                    total_buy_orders,
                    sell_orders,
                    &prefix_sum_sell_orders,
                )
            },
        );
        println!("Matched orders in {:?}", time.elapsed());
    }
    # Runs FHE implementation
    cargo run --release --package tfhe --example dark_market --features="integer internal-keycache" -- fhe
    
    # Runs parallelized FHE implementation
    cargo run --release --package tfhe --example dark_market --features="integer internal-keycache" -- fhe-parallel
    
    # Runs modified FHE implementation
    cargo run --release --package tfhe --example dark_market --features="integer internal-keycache" -- fhe-modified
    
    # Runs plain implementation
    cargo run --release --package tfhe --example dark_market --features="integer internal-keycache" -- plain
    
    # Multiple implementations can be run within same instance
    cargo run --release --package tfhe --example dark_market --features="integer internal-keycache" -- plain fhe-parallel
    use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8};
    use tfhe::prelude::*;
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let (client_key, server_key) = generate_keys(config);
    
        set_server_key(server_key);
    
        let clear_a = 27u8;
        let clear_b = 128u8;
    
        let a = FheUint8::encrypt(clear_a, &client_key);
        let b = FheUint8::encrypt(clear_b, &client_key);
    
        let result = a + b;
    
        let decrypted_result: u8 = result.decrypt(&client_key);
    
        let clear_result = clear_a + clear_b;
    
        assert_eq!(decrypted_result, clear_result);
    }
    use tfhe::boolean::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys, using the default parameters:
        let (client_key, server_key) = gen_keys();
    
        // We use the client secret key to encrypt two messages:
        let ct_1 = client_key.encrypt(true);
        let ct_2 = client_key.encrypt(false);
    
        // We use the server public key to execute a boolean circuit:
        // if ((NOT ct_2) NAND (ct_1 AND ct_2)) then (NOT ct_2) else (ct_1 AND ct_2)
        let ct_3 = server_key.not(&ct_2);
        let ct_4 = server_key.and(&ct_1, &ct_2);
        let ct_5 = server_key.nand(&ct_3, &ct_4);
        let ct_6 = server_key.mux(&ct_5, &ct_3, &ct_4);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_6);
        assert_eq!(output, true);
    }
    use tfhe::shortint::prelude::*;
    
    fn main() {
        // We generate a set of client/server keys
        // using parameters with 2 bits of message and 2 bits of carry
        let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2);
    
        let msg1 = 1;
        let msg2 = 0;
    
        let modulus = client_key.parameters.message_modulus().0;
    
        // We use the client key to encrypt two messages:
        let ct_1 = client_key.encrypt(msg1);
        let ct_2 = client_key.encrypt(msg2);
    
        // We use the server public key to execute an integer circuit:
        let ct_3 = server_key.unchecked_add(&ct_1, &ct_2);
    
        // We use the client key to decrypt the output of the circuit:
        let output = client_key.decrypt(&ct_3);
        assert_eq!(output, (msg1 + msg2) % modulus as u64);
    }
    use tfhe::integer::gen_keys_radix;
    use tfhe::shortint::parameters::PARAM_MESSAGE_2_CARRY_2;
    
    fn main() {
        // We create keys for radix representation to create 16 bits integers
        // using 8 blocks of 2 bits
        let (cks, sks) = gen_keys_radix(PARAM_MESSAGE_2_CARRY_2, 8);
    
        let clear_a = 2382u16;
        let clear_b = 29374u16;
    
        let mut a = cks.encrypt(clear_a as u64);
        let mut b = cks.encrypt(clear_b as u64);
    
        let encrypted_max = sks.smart_max_parallelized(&mut a, &mut b);
        let decrypted_max: u64 = cks.decrypt(&encrypted_max);
    
        assert_eq!(decrypted_max as u16, clear_a.max(clear_b))
    }

    Homomorphic Regular Expressions Integer API

    This tutorial explains how to build a regex Pattern Matching Engine (PME) where ciphertext is the content that is evaluated.

    A regex PME is an essential tool for programmers. It allows you to perform complex searches on content. A less powerful simple search on string can only find matches of the exact given sequence of characters (e.g., your browser's default search function). Regex PMEs are more powerful, allowing searches on certain structures of text, where a structure may take any form in multiple possible sequences of characters. The structure to be searched is defined with the regex, a very concise language.

    Here are some example regexes to give you an idea of what is possible:

    Regex
    Semantics

    Regexes are powerful enough to be able to express structures like email address formats. This capability is what makes regexes useful for many programming solutions.

    There are two main components identifiable in a PME:

    1. The pattern that is to be matched has to be parsed, translated from a textual representation into a recursively structured object (an Abstract Syntax Tree, or AST).

    2. This AST must then be applied to the text that it is to be matched against, resulting in a 'yes' or 'no' to whether the pattern has matched (in the case of our FHE implementation, this result is an encrypted 'yes' or an encrypted 'no').

    Parsing is a well understood problem. There are a couple of different approaches possible here. Regardless of the approach chosen, it starts with figuring out what language we want to support. That is, what are the kinds of sentences we want our regex language to include? A few example sentences we definitely want to support are, for example: /a/, /a?bc/, /^ab$/, /ab|cd/, however example sentences don't suffice as a specification because they can never be exhaustive (they're endless). We need something to specify exactly the full set of sentences our language supports. There exists a language that can help us describe our own language's structure exactly: Grammar.

    hashtag
    The Grammar and datastructure

    It is useful to start with defining the Grammar before starting to write code for the parser because the code structure follows directly from the Grammar. A Grammar consists of a generally small set of rules. For example, a very basic Grammar could look like this:

    This describes a language that only contains the sentence "a". Not a very interesting language.

    We can make it more interesting though by introducing choice into the Grammar with | (called a 'pipe') operators. If we want the above Grammar to accept either "a" or "b":

    So far, only Grammars with a single rule have been shown. However, a Grammar can consist of multiple rules. Most languages require it. So let's consider a more meaningful language, one that accepts sentences consisting of one or more digits. We could describe such a language with the following Grammar:

    The + after Digit is another Grammar operator. With it, we specify that Digit must be matched one or more times. Here are all the Grammar operators that are relevant for this tutorial:

    Operator
    Example
    Semantics

    In the case of the example PME, the Grammar is as follows (notice the unquoted ? and quoted ?, etc. The unquoted characters are Grammar operators, and the quoted are characters we are matching in the parsing).

    We will refer occasionally to specific parts in the Grammar listed above by <rule name>.<variant index> (where the first rule variant has index 1).

    With the Grammar defined, we can start defining a type to parse into. In Rust, we have the enum kind of type that is perfect for this, as it allows you to define multiple variants that may recurse. I prefer to start by defining variants that do not recurse (i.e., that don't contain nested regex expressions):

    With this, we can translate the following basic regexes:

    Pattern
    RegExpr value

    Notice we're not yet able to sequence multiple components together. Let's define the first variant that captures recursive RegExpr for this:

    With this Seq (short for sequence) variant, we allow translating patterns that contain multiple components:

    Pattern
    RegExpr value

    Let's finish the RegExpr datastructure by adding variants for 'Optional' matching, 'Not' logic in a range, and 'Either' left or right matching:

    Some features may make the most sense being implemented during post-processing of the parsed datastructure. For example, the case insensitivity feature (the i Modifier) is implemented in the example implementation by taking the parsed RegExpr and mutating every character mentioned inside to cover both the lower case as well as the upper case variant (see function case_insensitive in parser.rs for the example implementation).

    The modifier i in our Grammar (for enabling case insensitivity) was easiest to implement by applying a post-processing step to the parser.

    We are now able to translate any complex regex into a RegExpr value. For example:

    Pattern
    RegExpr value

    With both the Grammar and the datastructure to parse into defined, we can now start implementing the actual parsing logic. There are multiple ways this can be done. For example, there exist tools that can automatically generate parser code by giving it the Grammar definition (these are called parser generators). However, you might prefer to write parsers with a parser combinator library. This may be the better option for you because the behavior in runtime is easier to understand for parsers constructed with a parser combinator library than of parsers that were generated with a parser generator tool.

    Rust offers a number of popular parser combinator libraries. This tutorial used combine, but any other library would work just as well. Choose whichever appeals the most to you (including any parser generator tool). The implementation of our regex parser will differ significantly depending on the approach you choose, so we will not cover this in detail here. You may look at the parser code in the example implementation to get an idea of how this could be done. In general though, the Grammar and the datastructure are the important components, while the parser code follows directly from these.

    hashtag
    Matching the RegExpr to encrypted content

    The next challenge is to build the execution engine, where we take a RegExpr value and recurse into it to apply the necessary actions on the encrypted content. We first have to define how we actually encode our content into an encrypted state. Once that is defined, we can start working on how we will execute our RegExpr onto the encrypted content.

    hashtag
    Encoding and encrypting the content.

    It is not possible to encrypt the entire content into a single encrypted value. We can only encrypt numbers and perform operations on those encrypted numbers with FHE. Therefore, we have to find a scheme where we encode the content into a sequence of numbers that are then encrypted individually to form a sequence of encrypted numbers.

    We recommend the following two strategies:

    1. to map each character of the content into the u8 ascii value, and then encrypt each bit of these u8 values individually.

    2. to, instead of encrypting each bit individually, encrypt each u8 ascii value in its entirety.

    Strategy 1 requires more high-level TFHE-rs operations to check for a simple character match (we have to check each bit individually for equality as opposed to checking the entire byte in one, high-level TFHE-rs operation), though some experimentation did show that both options performed equally well on a regex like /a/. This is likely because bitwise FHE operations are relatively cheap compared to u8 FHE operations. However, option 1 falls apart as soon as you introduce '[a-z]' regex logic. With option 2, it is possible to complete this match with just three TFHE-rs operations: ge, le, and bitand.

    If, on the other hand, we had encrypted the content with the first strategy, there would be no way to test for greater/equal than from and less/equal than to. We'd have to check for the potential equality of each character between from and to, and then join the results together with a sequence of sk.bitor; that would require far more cryptographic operations than in strategy 2.

    Because FHE operations are computationally expensive, and strategy 1 requires significantly more FHE operations for matching on [a-z] regex logic, we should opt for strategy 2.

    hashtag
    Matching with the AST versus matching with a derived DFA.

    There are a lot of regex PMEs. It's been built many times and it's been researched thoroughly. There are different strategies possible here. A straight forward strategy is to directly recurse into our RegExpr value and apply the necessary matching operations onto the content. In a way, this is nice because it allows us to link the RegExpr structure directly to the matching semantics, resulting in code that is easier to understand, maintain, etc.

    Alternatively, there exists an algorithm that transforms the AST (i.e., the RegExpr, in our case) into a Deterministic Finite Automata (DFA). Normally, this is a favorable approach in terms of efficiency because the derived DFA can be walked over without needing to backtrack (whereas the former strategy cannot prevent backtracking). This means that the content can be walked over from character to character, and depending on what the character is at this cursor, the DFA is conjunctively traveled in a definite direction which ultimately leads us to the yes, there is a match or the no, there is no match. There is a small upfront cost of having to translate the AST into the DFA, but the lack of backtracking during matching generally makes up for this, especially if the content that it is matched against is significantly big.

    In our case though, we are matching on encrypted content. We have no way to know what the character at our cursor is, and therefore no way to find this definite direction to go forward in the DFA. Therefore, translating the AST into the DFA does not help us as it does in normal regex PMEs. For this reason, consider opting for the former strategy because it allows for matching logic that is easier to understand.

    hashtag
    Matching.

    In the previous section, we decided we'll match by traversing into the RegExpr value. This section will explain exactly how to do that. Similarly to defining the Grammar, it is often best to start with working out the non-recursive RegExpr variants.

    We'll start by defining the function that will recursively traverse into the RegExpr value:

    sk is the server key (aka, public key),content is what we'll be matching against, re is the RegExpr value we built when parsing the regex, and c_pos is the cursor position (the index in content we are currently matching against).

    The result is a vector of tuples, with the first value of the tuple being the computed ciphertext result, and the second value being the content position after the regex components were applied. It's a vector because certain RegExpr variants require the consideration of a list of possible execution paths. For example, RegExpr::Optional might succeed by applying or and not applying the optional regex (notice that in the former case, c_pos moves forward whereas in the latter case it stays put).

    On first call, a match of the entire regex pattern starts with c_pos=0. Then match is called again for the entire regex pattern with c_pos=1, etc. until c_pos exceeds the length of the content. Each of these alternative match results are then joined together with sk.bitor operations (this works because if one of them results in 'true' then, in general, our matching algorithm should return 'true').

    The ... within the match statement above is what we will be working out for some of the RegExpr variants now. Starting with RegExpr::Char:

    Let's consider an example of the variant above. If we apply /a/ to content bac, we'll have the following list of match calls re and c_pos values (for simplicity, re is denoted in regex pattern instead of in RegExpr value):

    re
    c_pos
    Ciphertext operation

    And we would arrive at the following sequence of ciphertext operations:

    AnyChar is a no operation:

    The sequence iterates over its re_xs, increasing the content position accordingly, and joins the results with bitand operations:

    Other variants are similar, as they recurse and manipulate re and c_pos accordingly. Hopefully, the general idea is already clear.

    Ultimately the entire pattern-matching logic unfolds into a sequence of the following set of FHE operations:

    1. eq (tests for an exact character match)

    2. ge (tests for 'greater than' or 'equal to' a character)

    3. le (tests for 'less than' or 'equal to' a character)

    hashtag
    Optimizations.

    Generally, the included example PME follows the approach outlined above. However, there were two additional optimizations applied. Both of these optimizations involved reducing the number of unnecessary FHE operations. Given how computationally expensive these operations are, it makes sense to optimize for this (and to ignore any suboptimal memory usage of our PME, etc.).

    The first optimization involved delaying the execution of FHE operations to after the generation of all possible execution paths to be considered. This optimization allows us to prune execution paths during execution path construction that are provably going to result in an encrypted false value, without having already performed the FHE operations up to the point of pruning. Consider the regex /^a+b$/, and we are applying this to a content of size 4. If we are executing execution paths naively, we would go ahead and check for all possible amounts of a repetitions: ab, aab, aaab. However, while building the execution paths, we can use the fact that a+ must begin at the beginning of the content, and that b must be the final character of the content. From this follows that we only have to check for the following sentence: aaab. Delaying execution of the FHE operations until after we've built the possible execution paths in this example reduced the number of FHE operations applied by approximately half.

    The second optimization involved preventing the same FHE conditions to be re-evaluated. Consider the regex /^a?ab/. This would give us the following possible execution paths to consider:

    1. content[0] == a && content[1] == a && content[2] == b (we match the a in a?)

    2. content[0] == a && content[1] == b (we don't match the a in a?

    Notice that, for both execution paths, we are checking for content[0] == a. Even though we cannot see what the encrypted result is, we do know that it's either going to be an encrypted false for both cases or an encrypted true for both cases. Therefore, we can skip the re-evaluation of content[0] == a and simply copy the result from the first evaluation over. This optimization involves maintaining a cache of known expression evaluation results and reusing those where possible.

    hashtag
    Trying out the example implementation

    The implementation that guided the writing of this tutorial can be found under tfhe/examples/regex_engine.

    When compiling with --example regex_engine, a binary is produced that serves as a basic demo. Simply call it with the content string as a first argument and the pattern string as a second argument. For example, cargo run --release --features=x86_64-unix,integer --example regex_engine -- 'this is the content' '/^pattern$/'; note it's advised to compile the executable with --release flag as the key generation and homomorphic operations otherwise seem to experience a heavy performance penalty.

    On execution, a private and public key pair are created. Then, the content is encrypted with the client key, and the regex pattern is applied onto the encrypted content string - with access given only to the server key. Finally, it decrypts the resulting encrypted result using the client key and prints the verdict to the console.

    To get more information on exact computations and performance, set the RUST_LOG environment variable to debug or to trace.

    hashtag
    Supported regex patterns

    This section specifies the supported set of regex patterns in the regex engine.

    hashtag
    Components

    A regex is described by a sequence of components surrounded by /, the following components are supported:

    Name
    Notation
    Examples

    hashtag
    Modifiers

    Modifiers are mode selectors that affect the entire regex behavior. One modifier is currently supported:

    • Case insensitive matching, by appending an i after the regex pattern. For example: /abc/i

    hashtag
    General examples

    These components and modifiers can be combined to form any desired regex pattern. To give some idea of what is possible, here is a non-exhaustive list of supported regex patterns:

    Pattern
    Description

    a?

    optionally match 'a' (match zero or one time)

    .

    .

    match any character

    ..

    a .. b

    match on a range of alphabetically ordered characters from 'a', up to and including 'b'

    a b

    sequencing; match on 'a' and then on 'b'

    /[acd]/

    RegExpr::Range { vec!['a', 'c', 'd'] }

    /[a-g]/

    RegExpr::Between { from: 'a', to: 'g' }

    bitand (bitwise AND, used for sequencing multiple regex components)
  • bitor (bitwise OR, used for folding multiple possible execution variants' results into a single result)

  • bitxor (bitwise XOR, used for the 'not' logic in ranges)

  • )

    \<symbol>

    /\^/, /\$/

    Parenthesis

    (<regex>)

    /(abc)*/, /d(ab)?/

    Optional

    <regex>?

    /a?/, /(az)?/

    Zero or more

    <regex>*

    /a*/, /ab*c/

    One or more

    <regex>+

    /a+/, /ab+c/

    Exact repeat

    <regex{<number>}>

    /ab{2}c/

    At least repeat

    <regex{<number>,}>

    /ab{2,}c/

    At most repeat

    <regex{,<number>}>

    /ab{,2}c/

    Repeat between

    <regex{<number>,<number>}>

    /ab{2,4}c/

    Either

    <regex>|<regex>

    /a|b/, /ab|cd/

    Start matching

    /^<regex>

    /^abc/

    End matching

    <regex>$/

    /abc$/

    Matches with: ab, bb, cb, cd

    /^[a-c]b|cd$/i

    Matches with: ab, Ab, aB, ..., cD, CD

    /^d(abc)+d$/

    For example, matches with: dabcd, dabcabcd, dabcabcabcd

    /^a.*d$/

    Matches with any content that starts with a and ends with d

    /abc/

    Searches for the sequence abc (equivalent to a simple text search)

    /^abc/

    Searches for the sequence abc at the beginning of the content

    /a?bc/

    Searches for sequences abc, bc

    /ab|c+d/

    Searches for sequences of ab, c repeated 1 or more times, followed by d

    |

    a | b

    we first try matching on 'a' - if no match, we try to match on 'b'

    +

    a+

    match 'a' one or more times

    *

    a*

    match 'a' any amount of times (including zero times)

    /a/

    RegExpr::Char { c: 'a' }

    /\\^/

    RegExpr::Char { c: '^' }

    /./

    RegExpr::AnyChar

    /^/

    RegExpr::SOF

    /$/

    RegExpr::EOF

    /ab/

    RegExpr::Seq { re_xs: vec![RegExpr::Char { c: 'a' }, RegExpr::Char { c: 'b' }] }

    /^a.$/

    RegExpr::Seq { re_xs: vec![RegExpr::SOF, RexExpr::Char { 'a' }, RegExpr::AnyChar, RegExpr::EOF] }

    /a[f-l]/

    RegExpr::Seq { re_xs: vec![RegExpr::Char { c: 'a' }, RegExpr::Between { from: 'f', to: 'l' }] }

    /a?/

    RegExpr::Optional { opt_re: Box::new(RegExpr::Char { c: 'a' }) }

    /[a-d]?/

    RegExpr::Optional { opt_re: Box::new(RegExpr::Between { from: 'a', to: 'd' }) }

    /[^ab]/

    RegExpr::Not { not_re: Box::new(RegExpr::Range { cs: vec!['a', 'b'] }) }

    /av|d?/

    RegExpr::Either { l_re: Box::new(RegExpr::Seq { re_xs: vec![RegExpr::Char { c: 'a' }, RegExpr::Char { c: 'v' }] }), r_re: Box::new(RegExpr::Optional { opt_re: Box::new(RegExpr::Char { c: 'd' }) }) }

    /(av|d)?/

    RegExpr::Optional { opt_re: Box::new(RegExpr::Either { l_re: Box::new(RegExpr::Seq { re_xs: vec![RegExpr::Char { c: 'a' }, RegExpr::Char { c: 'v' }] }), r_re: Box::new(RegExpr::Char { c: 'd' }) }) }

    /a/

    0

    sk.eq(content[0], a)

    /a/

    1

    sk.eq(content[1], a)

    /a/

    2

    sk.eq(content[2], a)

    Character

    Simply the character itself

    /a/, /b/, /Z/, /5/

    Character range

    [<character>-<character]

    /[a-d]/, /[C-H]/

    Any character

    .

    /a.c/

    /^abc$/

    Matches with content that equals exactly abc (case sensitive)

    /^abc$/i

    Matches with content that equals abc (case insensitive)

    /abc/

    Matches with content that contains somewhere abc

    /ab?c/

    Matches with content that contains somewhere abc or somewhere ab

    /^ab*c$/

    For example, matches with: ac, abc, abbbbc

    ?

    Escaped symbol

    /^[a-c]b|cd$/

    Start := 'a'
    Start := 'a' | 'b'
    Start := Digit+
    
    Digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
    Start := '/' '^'? Regex '$'? '/' Modifier?
    
    Regex := Term '|' Term
           | Term
    
    Term := Factor*
    
    Factor := Atom '?'
            | Repeated
            | Atom
    
    Repeated := Atom '*'
              | Atom '+'
              | Atom '{' Digit* ','? '}'
              | Atom '{' Digit+ ',' Digit* '}'
    
    Atom := '.'
          | '\' .
          | Character
          | '[' Range ']'
          | '(' Regex ')'
    
    Range := '^' Range
           | AlphaNum '-' AlphaNum
           | AlphaNum+
    
    Digit := '0' .. '9'
    
    Character := AlphaNum
               | '&' | ';' | ':' | ',' | '`' | '~' | '-' | '_' | '!' | '@' | '#' | '%' | '\'' | '\"'
    
    AlphaNum := 'a' .. 'z'
              | 'A' .. 'Z'
              | '0' .. '9'
    
    Modifier := 'i'
    enum RegExpr {
        Char { c: char },  // matching against a single character (Atom.2 and Atom.3)
        AnyChar,  // matching _any_ character (Atom.1)
        SOF,  // matching only at the beginning of the content ('^' in Start.1)
        EOF,  // matching only at the end of the content (the '$' in Start.1)
        Range { cs: Vec<char> },  // matching on a list of characters (Range.3, eg '[acd]')
        Between { from: char, to: char },  // matching between 2 characters based on ascii ordering (Range.2, eg '[a-g]')
    }
    enum RegExpr {
        ...
        Seq { re_xs: Vec<RegExpr> },  // matching sequences of RegExpr components (Term.1)
    }
    enum RegExpr {
        ...
        Optional { opt_re: Box<RegExpr> },  // matching optionally (Factor.1)
        Not { not_re: Box<RegExpr> },  // matching inversely on a range (Range.1)
        Either { l_re: Box<RegExpr>, r_re: Box<RegExpr> },  // matching the left or right regex (Regex.1)
    }
    // note: this is pseudocode
    c       = <the encrypted character under inspection>;
    sk      = <the server key, aka the public key>
    
    ge_from = sk.ge(c, 'a');
    le_to   = sk.le(c, 'z');
    result  = sk.bitand(ge_from, le_to);
    
    type StringCiphertext = Vec<RadixCiphertext>;
    type ResultCiphertext = RadixCiphertext;
    
    fn match(
        sk: &ServerKey,
        content: &StringCipherText,
        re: &RegExpr,
        content_pos: usize,
    ) -> Vec<(ResultCiphertext, usize)> {
        let content_char = &content[c_pos];
        match re {
            ...
        }
    }
    case RegExpr::Char { c } => {
        vec![(sk.eq(content_char, c), c_pos + 1)]
    },
    sk.bitor(sk.eq(content[0], a), sk.bitor(sk.eq(content[1], a), sk.eq(content[2], a)))
    case RegExpr::AnyChar => {
        // note: ct_true is just some constant representing True that is trivially encoded into ciphertext
        return vec![(ct_true, c_pos + 1)];
    }
    case RegExpr::Seq { re_xs } => {
        re_xs.iter().fold(|prev_results, re_x| {
            prev_results.iter().flat_map(|(prev_res, prev_c_pos)| {
                (x_res, new_c_pos) = match(sk, content, re_x, prev_c_pos);
                (sk.bitand(prev_res, x_res), new_c_pos)
            })
        }, (ct_true, c_pos))
    },

    Types & Operations

    hashtag
    Types

    TFHE-rs includes two main types to represent encrypted data:

    • FheUint: this is the homomorphic equivalent of Rust unsigned integers u8, u16, ...

    • FheInt: this is the homomorphic equivalent of Rust (signed) integers i8, i16, ...

    In the same manner as many programming languages, the number of bits used to represent the data must be chosen when declaring a variable. For instance:

    hashtag
    Operation list

    The table below contains an overview of the available operations in TFHE-rs. The notation Enc (for Encypted) either refers to FheInt or FheUint, for any size between 1 and 256-bits.

    More details, and further examples, are given in the following sections.

    hashtag
    Integer

    In TFHE-rs, integers are used to encrypt all messages which are larger than 4 bits. All supported operations are listed below.

    hashtag
    Arithmetic operations.

    Homomorphic integer types support arithmetic operations.

    The list of supported operations is:

    name
    symbol
    type

    For division by 0, the convention is to return modulus - 1. For instance, for FheUint8, the modulus is , so a division by 0 will return an encryption of 255. For the remainder operator, the convention is to return the first input without any modification. For instance, if ct1 = FheUint8(63) and ct2 = FheUint8(0) then ct1 % ct2 will return FheUint8(63).

    A simple example of how to use these operations:

    hashtag
    Bitwise operations.

    Homomorphic integer types support some bitwise operations.

    The list of supported operations is:

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Comparisons.

    Homomorphic integers support comparison operations.

    Due to some Rust limitations, it is not possible to overload the comparison symbols because of the inner definition of the operations. This is because Rust expects to have a Boolean as an output, whereas a ciphertext is returned when using homomorphic types.

    You will need to use different methods instead of using symbols for the comparisons. These methods follow the same naming conventions as the two standard Rust traits:

    The list of supported operations is:

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Min/Max.

    Homomorphic integers support the min/max operations.

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Ternary conditional operator.

    The ternary conditional operator allows computing conditional instructions of the form if cond { choice_if } else { choice_else }.

    name
    symbol
    type

    The syntax is encrypted_condition.if_then_else(encrypted_choice_if, encrypted_choice_else). The encrypted_condition should be an encryption of 0 or 1 in order to be valid.

    hashtag
    Casting.

    Casting between integer types is possible via the cast_from associated function or the cast_into method.

    hashtag
    ShortInt Operations

    Native small homomorphic integer types (e.g., FheUint3 or FheUint4) can easily compute various operations. In general, computing over encrypted data in TFHE-rs is as easy as computing over clear data, since the same operation symbol is used. The addition between two ciphertexts is done using the symbol + between two FheUint values. Many operations can be computed between a clear value (i.e. a scalar) and a ciphertext.

    In Rust, operations on native types are modular. For example, computations on u8 are carried out modulo . A similar idea applies for FheUintX, where operations are done modulo . For FheUint3, operations are done modulo .

    hashtag
    Arithmetic operations.

    Small homomorphic integer types support all common arithmetic operations, meaning +, -, x, /, mod.

    The division operation presents a subtlety: since data is encrypted, it is possible to compute a division by 0. In this case, the division is tweaked so that dividing by 0 returns the maximum possible value for the message.

    The list of supported operations is:

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Bitwise operations.

    Small homomorphic integer types support some bitwise operations.

    The list of supported operations is:

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Comparisons.

    Small homomorphic integer types support comparison operations.

    Due to some Rust limitations, it is not possible to overload the comparison symbols because of the inner definition of the operations. Rust expects to have a Boolean as an output, whereas a ciphertext is returned when using homomorphic types.

    You will need to use different methods instead of using symbols for the comparisons. These methods follow the same naming conventions as the two standard Rust traits:

    The list of supported operations is:

    name
    symbol
    type

    A simple example of how to use these operations:

    hashtag
    Univariate function evaluation.

    The shortint type also supports the computation of univariate functions, which make use of TFHE's programmable bootstrapping.

    A simple example of how to use these operations:

    hashtag
    Bivariate function evaluations.

    Using the shortint type allows you to evaluate bivariate functions (i.e., functions that take two ciphertexts as input).

    A simple code example:

    hashtag
    Boolean Operations

    Native homomorphic Booleans support common Boolean operations.

    The list of supported operations is:

    name
    symbol
    type

    ✔️

    ✔️

    Mul

    *

    ✔️

    ✔️

    Div

    /

    ✔️

    ✔️

    Rem

    %

    ✔️

    ✔️

    Not

    !

    ✔️

    ✔️

    BitAnd

    &

    ✔️

    ✔️

    BitOr

    |

    ✔️

    ✔️

    BitXor

    ^

    ✔️

    ✔️

    Shr

    >>

    ✔️

    ✔️

    Shl

    <<

    ✔️

    ✔️

    Min

    min

    ✔️

    ✔️

    Max

    max

    ✔️

    ✔️

    Greater than

    gt

    ✔️

    ✔️

    Greater or equal than

    ge

    ✔️

    ✔️

    Lower than

    lt

    ✔️

    ✔️

    Lower or equal than

    le

    ✔️

    ✔️

    Equal

    eq

    ✔️

    ✔️

    Cast (into dest type)

    cast_into

    ✔️

    ✖️

    Cast (from src type)

    cast_from

    ✔️

    ✖️

    Ternary operator

    if_then_else

    ✔️

    ✖️

    *

    Binary

    *

    /

    Binary

    *

    %

    Binary

    ^

    Binary

    >>

    Binary

    <<

    Binary

    rotate_right

    Binary

    rotate_left

    Binary

    ge

    Binary

    lt

    Binary

    le

    Binary

    /

    Binary

    %

    Binary

    -

    Unary

    ^

    Binary

    >>

    Binary

    <<

    Binary

    rotate_right

    Binary

    rotate_left

    Binary

    ge

    Binary

    lt

    Binary

    le

    Binary

    !

    Unary

    name

    symbol

    Enc/Enc

    Enc/ Int

    Neg

    -

    ✔️

    ✔️

    Add

    +

    ✔️

    ✔️

    Sub

    Negarrow-up-right

    -

    Unary

    Addarrow-up-right

    +

    Binary

    Subarrow-up-right

    -

    Binary

    28=2562^8=25628=256

    Notarrow-up-right

    !

    Unary

    BitAndarrow-up-right

    &

    Binary

    BitOrarrow-up-right

    |

    Binary

    Equalarrow-up-right

    eq

    Binary

    Not Equalarrow-up-right

    ne

    Binary

    Greater Thanarrow-up-right

    gt

    Binary

    Min

    min

    Binary

    Max

    max

    Binary

    Ternary operator

    if_then_else

    Ternary

    282^{8}28
    2X2^{X}2X
    8=238 = 2^{3}8=23

    Addarrow-up-right

    +

    Binary

    Subarrow-up-right

    -

    Binary

    Mularrow-up-right

    *

    Binary

    Notarrow-up-right

    !

    Unary

    BitAndarrow-up-right

    &

    Binary

    BitOrarrow-up-right

    |

    Binary

    Equalarrow-up-right

    eq

    Binary

    Not Equalarrow-up-right

    ne

    Binary

    Greater Thanarrow-up-right

    gt

    Binary

    BitAndarrow-up-right

    &

    Binary

    BitOrarrow-up-right

    |

    Binary

    BitXorarrow-up-right

    ^

    Binary

    PartialOrdarrow-up-right
    PartialEqarrow-up-right
    PartialOrdarrow-up-right
    PartialEqarrow-up-right

    -

        // let clear_a: u64 = 7;
        let mut a = FheUint64::try_encrypt(clear_a, &keys)?;
    
        // let clear_b: i8 = 3;
        let mut b = FheInt8::try_encrypt(clear_b, &keys)?;
    
        // let clear_c: u128 = 2;
        let mut c = FheUint128::try_encrypt(clear_c, &keys)?;
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheInt8, FheUint8};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_integers().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 15_u64;
        let clear_b = 27_u64;
        let clear_c = 43_u64;
        let clear_d = -87_i64;
    
        let mut a = FheUint8::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint8::try_encrypt(clear_b, &keys)?;
        let mut c = FheUint8::try_encrypt(clear_c, &keys)?;
        let mut d = FheInt8::try_encrypt(clear_d, &keys)?;
    
    
        a = a * &b;     // Clear equivalent computations: 15 * 27 mod 256 = 149
        b = &b + &c;    // Clear equivalent computations: 27 + 43 mod 256 = 70
        b = b - 76u8;   // Clear equivalent computations: 70 - 76 mod 256 = 250
        d = d - 13i8;   // Clear equivalent computations: -87 - 13 = 100 in [-128, 128[
    
        let dec_a: u8 = a.decrypt(&keys);
        let dec_b: u8 = b.decrypt(&keys);
        let dec_d: i8 = d.decrypt(&keys);
    
        assert_eq!(dec_a, ((clear_a * clear_b) % 256_u64) as u8);
        assert_eq!(dec_b, (((clear_b  + clear_c).wrapping_sub(76_u64)) % 256_u64) as u8);
        assert_eq!(dec_d, (clear_d - 13) as i8);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint8};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_integers().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 164;
        let clear_b = 212;
    
        let mut a = FheUint8::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint8::try_encrypt(clear_b, &keys)?;
    
        a = a ^ &b;
        b = b ^ &a;
        a = a ^ &b;
    
        let dec_a: u8 = a.decrypt(&keys);
        let dec_b: u8 = b.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_a, clear_b);
        assert_eq!(dec_b, clear_a);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheInt8};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_integers().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a: i8 = -121;
        let clear_b: i8 = 87;
    
        let mut a = FheInt8::try_encrypt(clear_a, &keys)?;
        let mut b = FheInt8::try_encrypt(clear_b, &keys)?;
    
        let greater = a.gt(&b);
        let greater_or_equal = a.ge(&b);
        let lower = a.lt(&b);
        let lower_or_equal = a.le(&b);
        let equal = a.eq(&b);
    
        let dec_gt: i8 = greater.decrypt(&keys);
        let dec_ge: i8 = greater_or_equal.decrypt(&keys);
        let dec_lt: i8 = lower.decrypt(&keys);
        let dec_le: i8 = lower_or_equal.decrypt(&keys);
        let dec_eq: i8 = equal.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_gt, (clear_a > clear_b ) as i8);
        assert_eq!(dec_ge, (clear_a >= clear_b) as i8);
        assert_eq!(dec_lt, (clear_a < clear_b ) as i8);
        assert_eq!(dec_le, (clear_a <= clear_b) as i8);
        assert_eq!(dec_eq, (clear_a == clear_b) as i8);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint8};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_integers().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a:u8 = 164;
        let clear_b:u8 = 212;
    
        let mut a = FheUint8::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint8::try_encrypt(clear_b, &keys)?;
    
        let min = a.min(&b);
        let max = a.max(&b);
    
        let dec_min : u8 = min.decrypt(&keys);
        let dec_max : u8 = max.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_min, u8::min(clear_a, clear_b));
        assert_eq!(dec_max, u8::max(clear_a, clear_b));
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheInt32};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
       // Basic configuration to use homomorphic integers
       let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
    	// Key generation
    	let (client_key, server_keys) = generate_keys(config);
    	
    	let clear_a = 32i32;
    	let clear_b = -45i32;
    	
    	// Encrypting the input data using the (private) client_key
    	// FheInt32: Encrypted equivalent to i32
    	let encrypted_a = FheInt32::try_encrypt(clear_a, &client_key)?;
    	let encrypted_b = FheInt32::try_encrypt(clear_b, &client_key)?;
    	
    	// On the server side:
    	set_server_key(server_keys);
    	
    	// Clear equivalent computations: 32 > -45
    	let encrypted_comp = &encrypted_a.gt(&encrypted_b);
    	let clear_res: i32 = encrypted_comp.decrypt(&client_key);
    	assert_eq!(clear_res, (clear_a > clear_b) as i32);
    	
    	// `encrypted_comp` contains the result of the comparison, i.e.,
    	// a boolean value. This acts as a condition on which the
    	// `if_then_else` function can be applied on.
    	// Clear equivalent computations:
    	// if 32 > -45 {result = 32} else {result = -45}
    	let encrypted_res = &encrypted_comp.if_then_else(&encrypted_a, &encrypted_b);
    	
    	let clear_res: i32 = encrypted_res.decrypt(&client_key);
    	assert_eq!(clear_res, clear_a);
    	
    	Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheInt16, FheUint8, FheUint32, FheUint16};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
        let (client_key, server_key) = generate_keys(config);
    
        // Casting requires server_key to set
        // (encryptions/decryptions do not need server_key to be set)
        set_server_key(server_key);
    
        {
            let clear = 12_837u16;
            let a = FheUint16::encrypt(clear, &client_key);
    
            // Downcasting
            let a: FheUint8 = a.cast_into();
            let da: u8 = a.decrypt(&client_key);
            assert_eq!(da, clear as u8);
    
            // Upcasting
            let a: FheUint32 = a.cast_into();
            let da: u32 = a.decrypt(&client_key);
            assert_eq!(da, (clear as u8) as u32);
        }
    
        {
            let clear = 12_837u16;
            let a = FheUint16::encrypt(clear, &client_key);
    
            // Upcasting
            let a = FheUint32::cast_from(a);
            let da: u32 = a.decrypt(&client_key);
            assert_eq!(da, clear as u32);
    
            // Downcasting
            let a = FheUint8::cast_from(a);
            let da: u8 = a.decrypt(&client_key);
            assert_eq!(da, (clear as u32) as u8);
        }
    
        {
            let clear = 12_837i16;
            let a = FheInt16::encrypt(clear, &client_key);
    
            // Casting from FheInt16 to FheUint16
            let a = FheUint16::cast_from(a);
            let da: u16 = a.decrypt(&client_key);
            assert_eq!(da, clear as u16);
        }
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint3};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_uint3().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 7;
        let clear_b = 3;
        let clear_c = 2;
    
        let mut a = FheUint3::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint3::try_encrypt(clear_b, &keys)?;
        let mut c = FheUint3::try_encrypt(clear_c, &keys)?;
    
    
        a = a * &b;  // Clear equivalent computations: 7 * 3 mod 8 = 5
        b = &b + &c; // Clear equivalent computations: 3 + 2 mod 8 = 5
        b = b - 5;   // Clear equivalent computations: 5 - 5 mod 8 = 0
    
        let dec_a = a.decrypt(&keys);
        let dec_b = b.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_a, (clear_a * clear_b) % 8);
        assert_eq!(dec_b, ((clear_b + clear_c) - 5) % 8);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint3};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_uint3().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 7;
        let clear_b = 3;
    
        let mut a = FheUint3::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint3::try_encrypt(clear_b, &keys)?;
    
        a = a ^ &b;
        b = b ^ &a;
        a = a ^ &b;
    
        let dec_a = a.decrypt(&keys);
        let dec_b = b.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_a, clear_b);
        assert_eq!(dec_b, clear_a);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint3};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_uint3().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 7;
        let clear_b = 3;
    
        let mut a = FheUint3::try_encrypt(clear_a, &keys)?;
        let mut b = FheUint3::try_encrypt(clear_b, &keys)?;
    
        assert_eq!(a.gt(&b).decrypt(&keys) != 0, true);
        assert_eq!(b.le(&a).decrypt(&keys) != 0, true);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint4};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_uint4().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let pow_5 = |value: u64| {
            value.pow(5) % FheUint4::MODULUS as u64
        };
    
        let clear_a = 12;
        let a = FheUint4::try_encrypt(12, &keys)?;
    
        let c = a.map(pow_5);
        let decrypted = c.decrypt(&keys);
        assert_eq!(decrypted, pow_5(clear_a) as u8);
    
        Ok(())
    }
    use tfhe::prelude::*;
    use tfhe::{generate_keys, set_server_key, ConfigBuilder, FheUint2};
    
    fn main() -> Result<(), Box<dyn std::error::Error>> {
        let config = ConfigBuilder::all_disabled().enable_default_uint2().build();
        let (keys, server_keys) = generate_keys(config);
        set_server_key(server_keys);
    
        let clear_a = 1;
        let clear_b = 3;
        let a = FheUint2::try_encrypt(clear_a, &keys)?;
        let b = FheUint2::try_encrypt(clear_b, &keys)?;
    
    
        let c = a.bivariate_function(&b, std::cmp::max);
        let decrypted = c.decrypt(&keys);
        assert_eq!(decrypted, std::cmp::max(clear_a, clear_b) as u8);
    
        Ok(())
    }
    Mularrow-up-right
    Divarrow-up-right
    Remarrow-up-right
    BitXorarrow-up-right
    Shrarrow-up-right
    Shlarrow-up-right
    Rotate Rightarrow-up-right
    Rotate Leftarrow-up-right
    Greater or Equalarrow-up-right
    Lowerarrow-up-right
    Lower or Equalarrow-up-right
    Divarrow-up-right
    Remarrow-up-right
    Negarrow-up-right
    BitXorarrow-up-right
    Shrarrow-up-right
    Shlarrow-up-right
    Rotate Rightarrow-up-right
    Rotate Leftarrow-up-right
    Greater or Equalarrow-up-right
    Lowerarrow-up-right
    Lower or Equalarrow-up-right
    Notarrow-up-right