arrow-left

Only this pageAll pages
gitbookPowered by GitBook
1 of 43

0.3

Loading...

Getting Started

Loading...

Loading...

Loading...

Loading...

Loading...

Tutorials

Loading...

Loading...

How To

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

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:

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
circle-info

Users who have ARM devices can use TFHE-rs by compiling using the nightly toolchain (see for more details).

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.

tfhe = { version = "0.3.2", features = [ "boolean", "shortint", "integer", "x86_64-unix" ] }

Linux

x86_64-unix

aarch64-unix*

macOS

x86_64-unix

aarch64-unix*

Windows

x86_64

Unsupported

Configuration
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

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 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.

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

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.

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);
}
hashtag
Example
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);
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);
}
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);

Shortint

tfhe::shortint is dedicated to small 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:

  • 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 Parallelized PBS

hashtag
Parallelized Programmable Bootstrapping

The Programmable Bootstrapping(PBS) is a sequential operation by nature. However, some recent resultsarrow-up-right showed that parallelism could be added at the cost of having larger keys. Overall, the performance of the PBS are improved. 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:

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 = 673;
    let clear_b = 6;
    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(())
}

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:

Operations

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

hashtag
The NOT unary gate

hashtag

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:

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 framework. Serde's Serialize and Deserialize are then implemented on the tfhe::shortint types.

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

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 = 673;
    let clear_b = 6;
    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(())
}
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));
}
# Cargo.toml

[dependencies]
# ...
bincode = "1.3.3"
serdearrow-up-right
data formatarrow-up-right
bincodearrow-up-right

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"
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);
}
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);
}
// 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)
}
// 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)
}
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});
}

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.

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.

Quick Start

hashtag
Quick Start

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

  1. Importing the TFHE-rs prelude;

# Cargo.toml

[dependencies]
# ...
tfhe = { version = "0.3.2", features = ["integer","x86_64-unix"]}
bincode = "1.3.3"
serdearrow-up-right
data formatarrow-up-right
bincodearrow-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 adressed in future releases.

hashtag
Compressed compact public key

This example shows how to use compressed compact public keys.

Client-side: Configuring and creating keys;

  • Client-side: Encrypting data;

  • Server-side: Setting the server key;

  • Server-side: Computing over encrypted data;

  • 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 here. Other rust and homomorphic types features can be found here.

    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 this page.

    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.

    // 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::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();
        let decompressed = compressed.decompress();
        let clear_decompressed: u16 = decompressed.decrypt(&client_key);
        assert_eq!(clear_decompressed, clear);
    }
    use tfhe::prelude::*;
    use tfhe::{ConfigBuilder, generate_keys, set_server_key, FheUint8, CompressedServerKey, ClientKey};
    
    fn main() {
        let config = ConfigBuilder::all_disabled()
            .enable_default_integers()
            .build();
    
        let cks = ClientKey::generate(config);
        let compressed_sks = CompressedServerKey::new(&cks);
        let sks = compressed_sks.decompress();
    
        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 public_key = CompressedPublicKey::new(&client_key);
    
        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::{ConfigBuilder, generate_keys, set_server_key, FheUint8, CompressedCompactPublicKey};
    
    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);
        let public_key = public_key_compressed.decompress();
        
        let a = FheUint8::try_encrypt(255u8, &public_key).unwrap();
        let clear: u8 = a.decrypt(&client_key);
        assert_eq!(clear, 255u8);
    }
    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.3.2", 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);

    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 ).

    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 boostrapping 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 .

    Integer

    tfhe::integer is dedicated to unsigned 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:

    • 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 an 8-bit integer 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.

    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

    Homomorphic Case Changing on Latin String

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

    The allowed characters in a Latin string are:

    • Uppercase letters: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

    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.

    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.
    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

    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:

    Lowercase letters: a b c d e f g h i j k l m n o p q r s t u v w x y z

    For the code point of the letters,ascii codes are used:

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

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

    lower_case = upper_case + 32 <=> upper_case = lower_case - 32

    For this type, the FheUint8 type is used.

    hashtag
    Types and methods.

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

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

    • The input string can only contain ascii letters (no digit, no special characters).

    • The input string cannot mix lower and upper case letters.

    These two points are to work around a limitation of FHE. It is not possible to create branches, meaning the function cannot use conditional statements. Checking if the 'char' is an uppercase letter to modify it to a lowercase one cannot be done, like in the example below.

    With these preconditions checked, implementing to_lower and to_upper is rather simple.

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

    Other configurations can be found here.

    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 represention 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))
    }
    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);
    }
    
    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!
    $
    fn to_lower(string: &String) -> String {
        let mut result = String::with_capacity(string.len());
        for char in string.chars() {
            if char.is_uppercase() {
                result.extend(char.to_lowercase().to_string().chars())
            }
        }
        result
    }
    # Cargo.toml
    
    [dependencies]
    # Default configuration for x86 Unix machines:
    tfhe = { version = "0.3.2", features = ["integer", "x86_64-unix"]}
    use tfhe::{FheUint8, ConfigBuilder, generate_keys, set_server_key, ClientKey};
    use tfhe::prelude::*;
    
    struct FheLatinString{
        bytes: Vec<FheUint8>,
        // Constant used to switch lower case <=> upper case
        cst: FheUint8,
    }
    
    impl FheLatinString {
        fn encrypt(string: &str, client_key: &ClientKey) -> Self {
            assert!(
                string.chars().all(|char| char.is_ascii_alphabetic()),
                "The input string must only contain ascii letters"
            );
    
            let has_mixed_case = string.as_bytes().windows(2).any(|window| {
                let first = char::from(*window.first().unwrap());
                let second = char::from(*window.last().unwrap());
    
                (first.is_ascii_lowercase() && second.is_ascii_uppercase())
                    || (first.is_ascii_uppercase() && second.is_ascii_lowercase())
            });
    
            assert!(
                !has_mixed_case,
                "The input string cannot mix lower case and upper case letters"
            );
    
            let fhe_bytes = string
                .bytes()
                .map(|b| FheUint8::encrypt(b, client_key))
                .collect::<Vec<FheUint8>>();
            let cst = FheUint8::encrypt(32u8, client_key);
    
            Self {
                bytes: fhe_bytes,
                cst,
            }
        }
    
        fn decrypt(&self, client_key: &ClientKey) -> String {
            let ascii_bytes = self
                .bytes
                .iter()
                .map(|fhe_b| fhe_b.decrypt(client_key))
                .collect::<Vec<u8>>();
            String::from_utf8(ascii_bytes).unwrap()
        }
    
        fn to_upper(&self) -> Self {
            Self {
                bytes: self
                    .bytes
                    .iter()
                    .map(|b| b - &self.cst)
                    .collect::<Vec<FheUint8>>(),
                cst: self.cst.clone(),
            }
        }
    
        fn to_lower(&self) -> Self {
            Self {
                bytes: self
                    .bytes
                    .iter()
                    .map(|b| b + &self.cst)
                    .collect::<Vec<FheUint8>>(),
                cst: self.cst.clone(),
            }
        }
    }
    
    
    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 = FheLatinString::encrypt("zama", &client_key);
        let verif_string = my_string.decrypt(&client_key);
        println!("{}", verif_string);
    
        let my_string_upper = my_string.to_upper();
        let verif_string = my_string_upper.decrypt(&client_key);
        println!("{}", verif_string);
        assert_eq!(verif_string, "ZAMA");
    
        let my_string_lower = my_string_upper.to_lower();
        let verif_string = my_string_lower.decrypt(&client_key);
        println!("{}", verif_string);
        assert_eq!(verif_string, "zama");
    }

    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

    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

    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:

    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
    and
    server keys
    .
  • Send the server key to the server.

  • Then any number of times:

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

    • Transmit the encrypted input to the server.

    • 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.

  • 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

    Once the server key is available on the server side, it is possible to perform some homomorphic computations. The client simply 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 utilized:

    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:

    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
    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();
    
    //---------------------------- SERVER 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 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:
        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 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);
    }
    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
    Result: 2
    $
    #include <tfhe.h>
    
    #include <assert.h>
    #include <inttypes.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_uint128_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;
    
        // Encrypt a u128 using 64 bits words, we encrypt 20 << 64 | 10
        ok = fhe_uint128_try_encrypt_with_client_key_u128(10, 20, client_key, &lhs);
        assert(ok == 0);
    
        // Encrypt a u128 using words, we encrypt 2 << 64 | 1
        ok = fhe_uint128_try_encrypt_with_client_key_u128(1, 2, client_key, &rhs);
        assert(ok == 0);
    
        // Compute the subtraction
        ok = fhe_uint128_sub(lhs, rhs, &result);
        assert(ok == 0);
    
        uint64_t w0, w1;
        // Decrypt
        ok = fhe_uint128_decrypt(result, client_key, &w0, &w1);
        assert(ok == 0);
    
        // Here the subtraction allows us to compare each word
        assert(w0 == 9);
        assert(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);
        return EXIT_SUCCESS;
    }

    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:

    Cryptographic Parameters

    All parameter sets provide at least 128-bits of security according to the Lattice-Estimatorarrow-up-right, with an error probability equal to 2−402^{-40}2−40 when using programmable bootstrapping. This error probability is due to the randomness added at each encryption (see here 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 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 ) 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 , 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 . 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:

    Configure Rust

    hashtag
    Using TFHE-rs with nightly toolchain.

    Install the needed Rust toolchain:

    Then, you can either:

    • 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)

    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 explicitly chosen as a feature. This requires to use the along with the feature nightly-avx512.

    rustup toolchain install nightly
    ithi^{th}ith
    22=42^2 = 422=4
    here
    quarter square methodarrow-up-right

    Booleans

    boolean

    Booleans

    ShortInts

    shortint

    Short unsigned integers

    Integers

    integer

    Arbitrary-sized unsigned integers

    nightly toolchain
    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);
    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,
            )
        };
    }
    cargo +nightly build
    cargo +nightly test
    rustup override set nightly
    # cargo will use the `nightly` toolchain.
    cargo build
    rustup show
    cargo +nightly build --features=nightly-avx512

    Benchmarks

    Due to their nature, homomorphic operations are naturally slower than their clear equivalent. 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
    Boolean

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

    hashtag
    tfhe-rs::boolean.

    Parameter set
    Concrete FFT
    Concrete FFT + AVX-512

    hashtag
    tfhe-lib.

    Parameter set
    fftw
    spqlios-fma

    hashtag
    OpenFHE.

    Parameter set
    GINX
    GINX (Intel HEXL)

    hashtag
    Integer

    This measures the execution time for some operation sets of tfhe-rs::integer.

    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, 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 could 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.

    This uses the Concrete FFT + AVX-512 configuration.

    Parameter set
    unchecked_add
    unchecked_mul_lsb
    keyswitch_programmable_bootstrap

    Next, the timings for the operation flavor default are given. This flavor ensures predictable timings of an operation along the entire circuit by clearing the carry space after each operation.

    Parameter set
    add
    mul_lsb
    keyswitch_programmable_bootstrap

    hashtag
    How to reproduce benchmarks

    TFHE-rs benchmarks can easily be reproduced from the .

    If the host machine supports AVX-512, then the argument `AVX512_SUPPORT=ON' should be added, e.g.:

    Tutorial

    hashtag
    Using the core_crypto primitives

    Welcome to this tutorial about TFHE-rs core_crypto module.

    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 here for more details about cryptographic parameters, and here to see how to properly instantiate integers depending on the chosen representation.

    81.5 ms

    110 ms

    139 ms

    200 ms

    262 ms

    355 ms

    Mul (x)

    150 ms

    221 ms

    361 ms

    928 ms

    2.90 s

    10.97 s

    Equal / Not Equal (eq, ne)

    39.4 ms

    40.2 ms

    61.1 ms

    66.4 ms

    74.5 ms

    85.7 ms

    Comparisons (ge, gt, le, lt)

    57.5 ms

    79.6 ms

    105 ms

    136 ms

    174 ms

    219 ms

    Max / Min (max,min)

    100 ms

    130 ms

    163 ms

    204 ms

    245 ms

    338 ms

    Bitwise operations (&, `

    , ^`)

    20.7 ms

    21.1 ms

    22.6 ms

    30.2 ms

    34.1 ms

    Div / Rem (/, %)

    1.37 s

    3.50 s

    9.12 s

    23.9 s

    59.9 s

    149.2 s

    Left / Right Shifts (<<, >>)

    106 ms

    140 ms

    202 ms

    262 ms

    403 ms

    827 ms

    Left / Right Rotations (left_rotate, right_rotate)

    105 ms

    140 ms

    199 ms

    263 ms

    403 ms

    829 ms

    3.06 µs

    134 ms

    129.4 ms

    PARAM_MESSAGE_4_CARRY_4

    11.7 µs

    854 ms

    828.1 ms

    131.5 ms

    129.5 ms

    129.4 ms

    PARAM_MESSAGE_4_CARRY_4

    852.5 ms

    839.7 ms

    828.1 ms

    DEFAULT_PARAMETERS

    8.8ms

    6.8ms

    TFHE_LIB_PARAMETERS

    13.6ms

    10.9ms

    default_128bit_gate_bootstrapping_parameters

    28.9ms

    15.7ms

    STD_128

    172ms

    78ms

    MEDIUM

    113ms

    50.2ms

    Operation \ Size

    FheUint8

    FheUint16

    FheUint32

    FheUint64

    FheUint128

    FheUint256

    Negation (-)

    80.4 ms

    106 ms

    132 ms

    193 ms

    257 ms

    348 ms

    PARAM_MESSAGE_1_CARRY_1

    338 ns

    8.3 ms

    8.1 ms

    PARAM_MESSAGE_2_CARRY_2

    406 ns

    18.4 ms

    18.4 ms

    PARAM_MESSAGE_1_CARRY_1

    7.90 ms

    8.00 ms

    8.10 ms

    PARAM_MESSAGE_2_CARRY_2

    18.4 ms

    18.1 ms

    18.4 ms

    here
    sourcesarrow-up-right

    Add / Sub (+,-)

    PARAM_MESSAGE_3_CARRY_3

    PARAM_MESSAGE_3_CARRY_3

    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 Randomization Servicesarrow-up-right 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 CSPRNGsarrow-up-right 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 rdseed instructionarrow-up-right 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.

    #Boolean benchmarks:
    make bench_boolean
    
    #Integer benchmarks:
    make bench_integer
    
    #Shortint benchmarks:
    make bench_shortint
    #Integer benchmarks:
    make AVX512_SUPPORT=ON bench_integer
    tfhe = { version = "0.3.2", features = [ "x86_64-unix" ] }
    tfhe = { version = "0.3.2", features = ["x86_64-unix"] }
    tfhe = { version = "0.3.2", features = ["aarch64-unix"] }
    tfhe = { version = "0.3.2", 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!(
            "Mulitplication via PBS result is correct! Expected 6, got {pbs_multiplication_result}"
        );
    }

    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.

    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 be a basis such that the size of is smaller than (or equal to) 4 bits. Then, an integer can be written as , where each is strictly smaller than . Each 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. This is done at key generation. Below, the keys are dedicated to unsigned integers encrypting messages over 8 bits, using a basis over 2 bits (i.e., ) 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 is composed of several integers , such that there are pairwise coprime, and each has a size smaller than 4 bits. The CRT-based integer are defined modulus . For an integer , its CRT decomposition is simply defined as . 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 . The integer is defined modulus . 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

    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

    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.

    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.

    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.

    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 and a

    ✔️

    ✔️

    Scalar Subtraction

    ✔️

    ✔️

    Multiplication

    ✔️

    ✔️

    Scalar Multiplication

    ✔️

    ✔️

    Bitwise OR, AND, XOR

    ✔️

    ✔️

    Equality

    ✔️

    ✔️

    Left/Right Shift

    ✔️

    ✖️

    Comparisons <,<=,>, >=

    ✔️

    ✖️

    Min, Max

    ✔️

    ✖️

    : 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.

  • B∈NB \in \mathbb{N}B∈N
    BBB
    m∈Nm \in \mathbb{N}m∈N
    m=m0+m1∗B+m2∗B2+...m = m_0 + m_1*B + m_2*B^2 + ...m=m0​+m1​∗B+m2​∗B2+...
    mim_imi​
    BBB
    mim_imi​
    B=22B=2^2B=22
    BBB
    bib_ibi​
    b_ib\_ib_i
    ∏bi\prod b_i∏bi​
    mmm
    m mod b0,m mod b1,...m \bmod{b_0}, m \bmod{b_1}, ...mmodb0​,mmodb1​,...
    B=[2,3,5]B = [2, 3, 5]B=[2,3,5]
    2∗3∗5=302*3*5 = 302∗3∗5=30

    Negation

    ✔️

    ✔️

    Addition

    ✔️

    ✔️

    Scalar Addition

    ✔️

    ✔️

    Subtraction

    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_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) % 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);
    }
    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.

    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:

    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

    • 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 .

    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:

    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);
    }
    here
    # Cargo.toml
    
    # Default configuration for x86 Unix machines:
    tfhe = { version = "0.3.2", 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);
    }

    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. 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.

    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

    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

    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.

    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

    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 volume_match_plain(sell_orders: &mut Vec<u16>, buy_orders: &mut Vec<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);
    
        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;
        }
    }
    let mut total_sell_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    for sell_order in sell_orders.iter_mut() {
        server_key.smart_add_assign(&mut total_sell_volume, sell_order);
    }
    
    let mut total_buy_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    for buy_order in buy_orders.iter_mut() {
        server_key.smart_add_assign(&mut total_buy_volume, buy_order);
    }
    let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);
    let fill_orders = |orders: &mut [RadixCiphertext]| {
        let mut volume_left_to_transact = total_volume.clone();
        for mut order in orders.iter_mut() {
            let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, &mut order);
            server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
            *order = filled_amount;
        }
    };
    
    fill_orders(sell_orders);
    fill_orders(buy_orders);
    const NUMBER_OF_BLOCKS: usize = 8;
    
    fn volume_match_fhe(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        let mut total_sell_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
        for sell_order in sell_orders.iter_mut() {
            server_key.smart_add_assign(&mut total_sell_volume, sell_order);
        }
    
        let mut total_buy_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
        for buy_order in buy_orders.iter_mut() {
            server_key.smart_add_assign(&mut total_buy_volume, buy_order);
        }
    
        let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);
    
        let fill_orders = |orders: &mut [RadixCiphertext]| {
            let mut volume_left_to_transact = total_volume.clone();
            for mut order in orders.iter_mut() {
                let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, &mut order);
                server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
                *order = filled_amount;
            }
        };
    
        fill_orders(sell_orders);
        fill_orders(buy_orders);
    }
    
    let parallel_vector_sum = |vec: &mut [RadixCiphertext]| {
        vec.to_vec().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(sell_orders), || vector_sum(buy_orders));
    rayon::join(|| fill_orders(sell_orders), || fill_orders(buy_orders));
    fn volume_match_fhe_parallelized(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        let parallel_vector_sum = |vec: &mut [RadixCiphertext]| {
            vec.to_vec().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(
            || parallel_vector_sum(sell_orders),
            || parallel_vector_sum(buy_orders),
        );
    
        let total_volume =
            server_key.smart_min_parallelized(&mut total_sell_volume, &mut total_buy_volume);
    
        let fill_orders = |orders: &mut [RadixCiphertext]| {
            let mut volume_left_to_transact = total_volume.clone();
            for mut order in orders.iter_mut() {
                let mut filled_amount =
                    server_key.smart_min_parallelized(&mut volume_left_to_transact, &mut order);
                server_key
                    .smart_sub_assign_parallelized(&mut volume_left_to_transact, &mut filled_amount);
                *order = filled_amount;
            }
        };
        
        rayon::join(|| fill_orders(sell_orders), || fill_orders(buy_orders));
    }
    let fill_orders = |orders: &mut [u64], prefix_sum: &[u64], total_orders: u64|{
        orders.iter().for_each(|order : &mut u64| {
            if (total_orders >= prefix_sum[i]) {
                continue;
            } else if total_orders >= prefix_sum.get(i-1).unwrap_or(0) {
                *order = total_orders - prefix_sum.get(i-1).unwrap_or(0);
            } else {
                *order = 0;
            }
        });
    };
    
    let fill_orders = |orders: &mut [u64], prefix_sum: &[u64], total_orders: u64| {
        orders.iter().for_each(|order| : &mut){
            *order = *order + ((total_orders >= prefix_sum - std::cmp::min(total_orders, prefix_sum.get(i - 1).unwrap_or(&0).clone()) - *order);
        }
    };
    fn volume_match_fhe_modified(
        sell_orders: &mut [RadixCiphertext],
        buy_orders: &mut [RadixCiphertext],
        server_key: &ServerKey,
    ) {
        let compute_prefix_sum = |arr: &[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();
            // Up sweep
            for d in 0..(prefix_sum.len().ilog2() as u32) {
                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)
                    });
            }
            // Down sweep
            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() as u32)).rev() {
                prefix_sum
                    .par_chunks_exact_mut(2_usize.pow(d + 1))
                    .for_each(move |chunk| {
                        let length = chunk.len();
                        let t = chunk.last().unwrap().clone();
                        let mut left = chunk.get((length - 1) / 2).unwrap().clone();
                        server_key.smart_add_assign_parallelized(chunk.last_mut().unwrap(), &mut left);
                        chunk[(length - 1) / 2] = t;
                    });
            }
            prefix_sum.push(last);
            prefix_sum[1..=arr.len()].to_vec()
        };
    
        println!("Creating prefix sum arrays...");
        let time = Instant::now();
        let (prefix_sum_sell_orders, prefix_sum_buy_orders) = rayon::join(
            || compute_prefix_sum(sell_orders),
            || compute_prefix_sum(buy_orders),
        );
        println!("Created prefix sum arrays in {:?}", time.elapsed());
    
        let fill_orders = |total_orders: &RadixCiphertext,
                            orders: &mut [RadixCiphertext],
                            prefix_sum_arr: &[RadixCiphertext]| {
            orders
                .into_par_iter()
                .enumerate()
                .for_each(move |(i, order)| {
                    server_key.smart_add_assign_parallelized(
                        order,
                        &mut server_key.smart_mul_parallelized(
                            &mut server_key
                                .smart_ge_parallelized(&mut order.clone(), &mut total_orders.clone()),
                            &mut server_key.smart_sub_parallelized(
                                &mut server_key.smart_sub_parallelized(
                                    &mut total_orders.clone(),
                                    &mut server_key.smart_min_parallelized(
                                        &mut total_orders.clone(),
                                        &mut prefix_sum_arr
                                            .get(i - 1)
                                            .unwrap_or(
                                                &server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS),
                                            )
                                            .clone(),
                                    ),
                                ),
                                &mut order.clone(),
                            ),
                        ),
                    );
                });
        };
    
        let total_buy_orders = &mut prefix_sum_buy_orders
            .last()
            .unwrap_or(&server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS))
            .clone();
    
        let total_sell_orders = &mut prefix_sum_sell_orders
            .last()
            .unwrap_or(&server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS))
            .clone();
    
        println!("Matching orders...");
        let time = Instant::now();
        rayon::join(
            || fill_orders(total_sell_orders, buy_orders, &prefix_sum_buy_orders),
            || fill_orders(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

    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 somwhere 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))
    },

    Operations

    The table below contains an overview of the available operations in TFHE-rs. More details, and further examples, are given in the following sections.

    name
    symbol
    FheUint/FheUint
    FheUint/Uint
    Uint/FheUint

    Neg

    -

    ✔️

    hashtag
    Boolean Operations

    Native homomorphic Booleans support common Boolean operations.

    The list of supported operations is:

    name
    symbol
    type

    hashtag
    ShortInt Operations

    Native small homomorphic integer types (e.g., FheUint3 or FheUint4) easily compute various operations. In general, computing over encrypted data 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 implements 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 max possible value for the message.

    The list of supported operations is:

    name
    symbol
    type

    A simple example on 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 on 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 on 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 on 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
    Integer

    In TFHE-rs, integers are used to encrypt any messages 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 the division operator, the convention is to return the 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, for ct1 = FheUint8(63) and ct2 = FheUint8(0), then ct1 % ct2 will return FheUint8(63).

    A simple example on 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 on how to use these operations:

    hashtag
    Comparisons.

    Homomorphic integers support comparison operations. Since Rust does not allow the overloading of these operations, a simple function has been associated to each one.

    The list of supported operations is:

    name
    symbol
    type

    A simple example on how to use these operations:

    hashtag
    Min/Max.

    Homomorphic integers support the min/max operations.

    name
    symbol
    type

    A simple example on how to use these operations:

    hashtag
    Casting.

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

    !

    Unary

    /

    Binary

    %

    Binary

    -

    Unary

    ^

    Binary

    >>

    Binary

    <<

    Binary

    rotate_right

    Binary

    rotate_left

    Binary

    ge

    Binary

    lt

    Binary

    le

    Binary

    *

    Binary

    *

    /

    Binary

    *

    %

    Binary

    ^

    Binary

    >>

    Binary

    <<

    Binary

    rotate_right

    Binary

    rotate_left

    Binary

    ge

    Binary

    lt

    Binary

    le

    Binary

    ✔️

    ✔️

    Add

    +

    ✔️

    ✔️

    ✔️

    Sub

    -

    ✔️

    ✔️

    ✔️

    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

    ✔️

    ✖️

    ✖️

    BitAndarrow-up-right

    &

    Binary

    BitOrarrow-up-right

    |

    Binary

    BitXorarrow-up-right

    ^

    Binary

    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

    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

    PartialOrdarrow-up-right
    PartialEqarrow-up-right

    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(())
    }
    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 = 15_u64;
        let clear_b = 27_u64;
        let clear_c = 43_u64;
    
        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)?;
    
    
        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
    
        let dec_a: u8 = a.decrypt(&keys);
        let dec_b: u8 = b.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);
    
        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, 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 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 : u8 = greater.decrypt(&keys);
        let dec_ge : u8 = greater_or_equal.decrypt(&keys);
        let dec_lt : u8 = lower.decrypt(&keys);
        let dec_le : u8 = lower_or_equal.decrypt(&keys);
        let dec_eq : u8 = equal.decrypt(&keys);
    
        // We homomorphically swapped values using bitwise operations
        assert_eq!(dec_gt, (clear_a > clear_b ) as u8);
        assert_eq!(dec_ge, (clear_a >= clear_b) as u8);
        assert_eq!(dec_lt, (clear_a < clear_b ) as u8);
        assert_eq!(dec_le, (clear_a <= clear_b) as u8);
        assert_eq!(dec_eq, (clear_a == clear_b) as u8);
    
        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, 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);
        }
    
        Ok(())
    }
    Notarrow-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
    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