1 of 49

0.5 What is TFHE-rs?

📁 Github | 💛 Community support | 🟨 Zama Bounty Program

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.

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.

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

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

Getting Started

Installation

Importing into your project

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

If you are using an x86 machine:

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

If you are using an ARM machine:

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

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

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

Supported platforms

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

x86

aarch64

Quick Start

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

Importing the TFHE-rs prelude;
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:

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.

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.

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.

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.

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.

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.

Types & Operations

Types

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

FheUint: this is the homomorphic equivalent of Rust unsigned integers u8, u16, ...
FheInt: this is the homomorphic equivalent of Rust (signed) integers i8, i16, ...

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

Operation list

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

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

Integer

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

Arithmetic operations.

Homomorphic integer types support arithmetic operations.

The list of supported operations is:

A simple example of how to use these operations:

Bitwise operations.

Homomorphic integer types support some bitwise operations.

The list of supported operations is:

A simple example of how to use these operations:

Comparisons.

Homomorphic integers support comparison operations.

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

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

The list of supported operations is:

A simple example of how to use these operations:

Min/Max.

Homomorphic integers support the min/max operations.

A simple example of how to use these operations:

Ternary conditional operator.

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

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

Casting.

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

Boolean Operations

Native homomorphic Booleans support common Boolean operations.

The list of supported operations is:

Benchmarks

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

All benchmarks were launched on an AWS hpc7a.96xlarge instance with the following specifications: AMD EPYC 9R14 CPU @ 2.60GHz and 740GB of RAM.

Integer

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

The table below reports the timing when the inputs of the benchmarked operation are encrypted.

The table below reports the timing when the left input of the benchmarked operation is encrypted and the other is a clear scalar of the same size.

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

Shortint

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

This uses the Concrete FFT + AVX-512 configuration.

Boolean

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

tfhe-rs::boolean.

tfhe-lib.

Using the same hpc7a.96xlarge machine as the one for tfhe-rs, the timings are:

OpenFHE (v1.1.2).

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

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

export CXX=clang++
export CC=clang

scripts/configure.sh
Release -> y
hexl -> y

scripts/build-openfhe-development-hexl.sh

Using the same hpc7a.96xlarge machine as the one for tfhe-rs, the timings are:

How to reproduce TFHE-rs benchmarks

TFHE-rs benchmarks can be easily reproduced from source.

#Boolean benchmarks:
make AVX512_SUPPORT=ON bench_boolean

#Integer benchmarks:
make AVX512_SUPPORT=ON bench_integer

#Shortint benchmarks:
make AVX512_SUPPORT=ON bench_shortint

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

Security and Cryptography

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

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 ciphertext is composed of two parts:

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

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.

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.

Programmable BootStrapping (PBS)

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.

Security.

Classical public key encryption.

Tutorials

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.

Non-generic version.

Other configurations can be found .

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.

final code

After the mandatory configuration steps, the function is called:

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.

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:

final code

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

Homomorphic Case Changing on Ascii String

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

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

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

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

Where UP_LOW_DISTANCE = 32

Types and methods.

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

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

# Cargo.toml

[dependencies]
# Default configuration for x86 Unix machines:
tfhe = { version = "0.5.5", features = ["integer", "x86_64-unix"]}

Other configurations can be found here.

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

The input string can only contain ascii characters.

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

pub const UP_LOW_DISTANCE: u8 = 32;

fn to_lower(c: u8) -> u8 {
    if c > 64 && c < 91 {
        c + UP_LOW_DISTANCE
    } else {
        c
    }
}

We can remove the branch this way:

pub const UP_LOW_DISTANCE: u8 = 32;

fn to_lower(c: u8) -> u8 {
    c + ((c > 64) as u8 & (c < 91) as u8) * UP_LOW_DISTANCE
}

On an homomorphic integer, this gives

use tfhe::prelude::*;
use tfhe::FheUint8;

pub const UP_LOW_DISTANCE: u8 = 32;

fn to_lower(c: &FheUint8) -> FheUint8 {
    c + FheUint8::cast_from(c.gt(64) & c.lt(91)) * UP_LOW_DISTANCE
}

The whole code is:

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

pub const UP_LOW_DISTANCE: u8 = 32;

struct FheAsciiString {
    bytes: Vec<FheUint8>,
}

fn to_upper(c: &FheUint8) -> FheUint8 {
    c - FheUint8::cast_from(c.gt(96) & c.lt(123)) * UP_LOW_DISTANCE
}

fn to_lower(c: &FheUint8) -> FheUint8 {
    c + FheUint8::cast_from(c.gt(64) & c.lt(91)) * UP_LOW_DISTANCE
}

impl FheAsciiString {
    fn encrypt(string: &str, client_key: &ClientKey) -> Self {
        assert!(
            string.chars().all(|char| char.is_ascii()),
            "The input string must only contain ascii letters"
        );

        let fhe_bytes: Vec<FheUint8> = string
            .bytes()
            .map(|b| FheUint8::encrypt(b, client_key))
            .collect();

        Self { bytes: fhe_bytes }
    }

    fn decrypt(&self, client_key: &ClientKey) -> String {
        let ascii_bytes: Vec<u8> = self
            .bytes
            .iter()
            .map(|fhe_b| fhe_b.decrypt(client_key))
            .collect();
        String::from_utf8(ascii_bytes).unwrap()
    }

    fn to_upper(&self) -> Self {
        Self {
            bytes: self.bytes.iter().map(to_upper).collect(),
        }
    }

    fn to_lower(&self) -> Self {
        Self {
            bytes: self.bytes.iter().map(to_lower).collect(),
        }
    }
}

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

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

    set_server_key(server_key);

    let my_string = FheAsciiString::encrypt("Hello Zama, how is it going?", &client_key);
    let verif_string = my_string.decrypt(&client_key);
    println!("Start string: {verif_string}");

    let my_string_upper = my_string.to_upper();
    let verif_string = my_string_upper.decrypt(&client_key);
    println!("Upper string: {verif_string}");
    assert_eq!(verif_string, "HELLO ZAMA, HOW IS IT GOING?");

    let my_string_lower = my_string_upper.to_lower();
    let verif_string = my_string_lower.decrypt(&client_key);
    println!("Lower string: {verif_string}");
    assert_eq!(verif_string, "hello zama, how is it going?");
}

How To

Run on GPU

TFHE-rs now includes a GPU backend, featuring a CUDA implementation for performing integer arithmetics on encrypted data. In what follows, a simple tutorial is introduced: it shows how to update your existing program to use GPU acceleration, or how to start a new one using GPU.

Prerequisites

Cuda version >= 10
Compute Capability >= 3.0
>= 8.0 - check this for more details about nvcc/gcc compatible versions
>= 3.24
Rust version - check this

Importing to your project

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

If you are using an x86 machine:

If you are using an ARM machine:

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

Supported platforms

TFHE-rs GPU backend is supported on Linux (x86, aarch64).

A first example

Configuring and creating keys.

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

Setting the keys

The configuration of the key is different from the CPU. More precisely, if both client and server keys are still generated by the Client (which is assumed to run on a CPU), the server key has then to be decompressed by the Server to be converted into the right format. To do so, the server should run this function: decompressed_to_gpu(). From then on, there is no difference between the CPU and the GPU.

Encrypting data

On the client-side, the method to encrypt the data is exactly the same than the CPU one, i.e.:

Computation.

Decryption.

Finally, the client gets the decrypted results by computing:

Improving performance.

TFHE-rs includes the possibility to leverage the high number of threads given by a GPU. To do so, the configuration should be updated with Rust let config = ConfigBuilder::with_custom_parameters(PARAM_MULTI_BIT_MESSAGE_2_CARRY_2_GROUP_3_KS_PBS, None).build(); The complete example becomes:

List of available operations

The GPU backend includes the following operations:

Benchmarks

The tables below contain benchmarks for homomorphic operations running on a single V100 from AWS (p3.2xlarge machines), with the default parameters:

Configure Rust

Using the right toolchain for TFHE-rs.

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

Then, you can either:

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:

Choosing your features

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

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:

AVX-512

Detect Overflow

TFHE-rs includes a list of specific operations to detect overflows. The overall idea is to have a specific ciphertext encrypting a flag reflecting the status of the computations. When an overflow occurs, this flag is set to true. Since the server is not able to evaluate this value (since it is encrypted), the client has to check the flag value when decrypting to determine if an overflow has happened. These operations might be slower than their equivalent which do not detect overflow, so they are not enabled by default (see the table below). In order to use them, specific operators must be called. At the moment, only additions, subtractions, multiplications are supported. Missing operations will be added soon.

The list of operations along with their symbol is:

name

symbol

type

These operations are then used exactly in the same way than the usual ones. The only difference lies into the decryption, as shown in following example:

The current benchmarks are given in the following tables (the first one for unsigned homomorphic integers and the second one for the signed integers):

Fine-grained APIs

Application Tutorials

Crypto Core API [Advanced users]

Developers

API references

Security and Cryptography

TFHE

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

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.

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

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}\\

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

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.

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

Noise.

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

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.

Programmable BootStrapping (PBS)

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

Carry.

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

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 .

Migrate Data to Newer Versions of TFHE-rs

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

Forward Compatibility Strategy

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

TFHE-rs has a global SERIALIZATION_VERSION constant;
When breaking serialization changes are introduced, this global version is bumped;
Safe serialization primitives check this constant upon deserialization, if the data is incompatible, these primitives return an error.

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

A minor update is done to the previously released branch to add the new release as an optional dependency;
Conversion code is added to the previous branch to be able to load old data and convert it to the new data format.

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

0.6.0 is released with breaking changes to the serialization;
0.5.5 has tfhe@0.6.0 as optional dependency gated by the forward_compatibility feature;
Conversion code is added to 0.5.5, if possible without any user input, but some data migration will likely require some information to be provided by the developer writing the migration code;
0.5.5 is released.

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

What it means from a developer perspective

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

Examples to migrate data:

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

Example timeline of the data migration or Bulk Data Migration:

A new transition version of the Application is compiled with the 0.5.5 release of TFHE-rs;
The transition version of the Application adds code to read previously stored data, convert it to the proper format for 0.6.0 and save it back to disk;
The service enters a maintenance period (if relevant);
Migration of data from 0.5.5 to 0.6.0 is done with the transition version of the Application, note that depending on the volume of data this transition can take a significant amount of time;
The updated version of the Application is compiled with the 0.6.0 release of TFHE-rs and put in production;
Service is resumed with the updated Application (if relevant).

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

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

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

A new version of the Application is compiled, it has tfhe@0.5.5 as dependency (the dependency will have to be renamed to avoid conflicts, a possible name is to use the major version like tfhe_0_5) and tfhe@0.6.0 which will not be renamed and can be accessed as tfhe
Code to manage reading the data is added to the Application:
The code determines whether the data was saved with the 0.5 Application or the 0.6 Application, if the data is already up to date with the 0.6 format it can be loaded right away, if it's in the 0.5 format the Application can check if an updated version of the data is already available in the 0.6 format and loads that if it's available, otherwise it converts the data to 0.6, saves the converted data to avoid having to convert it every time it is accessed and continue processing with the 0.6 data

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

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

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

read data from 0.5.5
convert to 0.6.0 format using tfhe_0_6
convert to 0.7.0 format using tfhe_0_7
save to disk in 0.7.0 format
process 0.7.0 data with tfhe which is tfhe@0.7.0

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:

On the client side, generate the client 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.

Setup

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

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();
}

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:

use std::fs::{File, create_dir_all};
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();

// Create a tmp dir with the current user name to avoid cluttering the /tmp dir
    let user = std::env::var("USER").unwrap_or_else(|_| "unknown_user".to_string());
    let tmp_dir_for_user = &format!("/tmp/{user}");

    create_dir_all(tmp_dir_for_user).unwrap();

    let server_key_file = &format!("{tmp_dir_for_user}/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");
}

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:

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

fn main() {
    // Don't consider the following line; you should follow the procedure above.
    let (client_key, _) = gen_keys();

//---------------------------- CLIENT SIDE

// We use the client key to encrypt the messages:
    let ct_1 = client_key.encrypt(true);
    let ct_2 = client_key.encrypt(false);

// We serialize the ciphertexts:
    let encoded_1: Vec<u8> = bincode::serialize(&ct_1).unwrap();
    let encoded_2: Vec<u8> = bincode::serialize(&ct_2).unwrap();

// ...
// And we send them to the server somehow
// ...
}

Encrypting inputs using a public key

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

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

fn main() {
    // Don't consider the following line; you should follow the procedure above.
    let (client_key, _) = gen_keys();
    let public_key = PublicKey::new(&client_key);

//---------------------------- SERVER or THIRD_PARTY SIDE

// We use the public key to encrypt the messages:
    let ct_1 = public_key.encrypt(true);
    let ct_2 = public_key.encrypt(false);

// We serialize the ciphertexts (if not on the server already):
    let encoded_1: Vec<u8> = bincode::serialize(&ct_1).unwrap();
    let encoded_2: Vec<u8> = bincode::serialize(&ct_2).unwrap();

// ...
// And we send them to the server to be deserialized (if not on the server already)
// ...
}

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:

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

Decrypting the output

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

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

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

Example

nodejs


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]);
    }
}

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

Example

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

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.

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.

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.

First steps using TFHE-rs JS on WASM API

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-pack in addition to a compatible (>= 1.67) rust toolchain.

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

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

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.

$ ls pkg
LICENSE  index.html  package.json  tfhe.d.ts  tfhe.js  tfhe_bg.txt  tfhe_bg.wasm  tfhe_bg.wasm.d.ts
$

Commented code to generate keys for shortint and encrypt a ciphertext

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

// 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();

The example.js script can then be run using node, like so:

$ node example.js
Generating client keys...
Encrypting 3...
Decrypting ciphertext...
Decryption successful!
Generating compressed ServerKey...
All done!
$

Operations

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

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

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.

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

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.

Using default could slow-down computations.

#List of available operations

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 (*)

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:

Arithmetic operations.

Classical arithmetic operations are supported by shortint:

bitwise operations

Short homomorphic integer types support some bitwise operations.

A simple example on how to use these operations:

comparisons

Short homomorphic integer types support comparison operations.

A simple example on how to use these operations:

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.

bi-variate function evaluations

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

Here is a simple code example:

Tutorial

Using the `core_crypto` primitives

Welcome to this tutorial about TFHE-rs core_crypto module.

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:

tfhe = { version = "0.5.5", features = [ "x86_64-unix" ] }

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 Services 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 CSPRNGs used in TFHE-rs.

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

tfhe = { version = "0.5.5", features = ["x86_64-unix"] }

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

tfhe = { version = "0.5.5", features = ["aarch64-unix"] }

For x86_64-based machines with the rdseed instruction running Windows:

tfhe = { version = "0.5.5", features = ["x86_64"] }

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.

use tfhe::core_crypto::prelude::*;

pub fn main() {
    // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
    // computations
    // Define the parameters for a 4 bits message able to hold the doubled 2 bits message
    let small_lwe_dimension = LweDimension(742);
    let glwe_dimension = GlweDimension(1);
    let polynomial_size = PolynomialSize(2048);
    let lwe_modular_std_dev = StandardDev(0.000007069849454709433);
    let glwe_modular_std_dev = StandardDev(0.00000000000000029403601535432533);
    let pbs_base_log = DecompositionBaseLog(23);
    let pbs_level = DecompositionLevelCount(1);
    let ciphertext_modulus = CiphertextModulus::new_native();

    // Request the best seeder possible, starting with hardware entropy sources and falling back to
    // /dev/random on Unix systems if enabled via cargo features
    let mut boxed_seeder = new_seeder();
    // Get a mutable reference to the seeder as a trait object from the Box returned by new_seeder
    let seeder = boxed_seeder.as_mut();

    // Create a generator which uses a CSPRNG to generate secret keys
    let mut secret_generator =
        SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());

    // Create a generator which uses two CSPRNGs to generate public masks and secret encryption
    // noise
    let mut encryption_generator =
        EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);

    println!("Generating keys...");

    // Generate an LweSecretKey with binary coefficients
    let small_lwe_sk =
        LweSecretKey::generate_new_binary(small_lwe_dimension, &mut secret_generator);

    // Generate a GlweSecretKey with binary coefficients
    let glwe_sk =
        GlweSecretKey::generate_new_binary(glwe_dimension, polynomial_size, &mut secret_generator);

    // Create a copy of the GlweSecretKey re-interpreted as an LweSecretKey
    let big_lwe_sk = glwe_sk.clone().into_lwe_secret_key();

    // Generate the bootstrapping key, we use the parallel variant for performance reason
    let std_bootstrapping_key = par_allocate_and_generate_new_lwe_bootstrap_key(
        &small_lwe_sk,
        &glwe_sk,
        pbs_base_log,
        pbs_level,
        glwe_modular_std_dev,
        ciphertext_modulus,
        &mut encryption_generator,
    );

    // Create the empty bootstrapping key in the Fourier domain
    let mut fourier_bsk = FourierLweBootstrapKey::new(
        std_bootstrapping_key.input_lwe_dimension(),
        std_bootstrapping_key.glwe_size(),
        std_bootstrapping_key.polynomial_size(),
        std_bootstrapping_key.decomposition_base_log(),
        std_bootstrapping_key.decomposition_level_count(),
    );

    // Use the conversion function (a memory optimized version also exists but is more complicated
    // to use) to convert the standard bootstrapping key to the Fourier domain
    convert_standard_lwe_bootstrap_key_to_fourier(&std_bootstrapping_key, &mut fourier_bsk);
    // We don't need the standard bootstrapping key anymore
    drop(std_bootstrapping_key);

    // Our 4 bits message space
    let message_modulus = 1u64 << 4;

    // Our input message
    let input_message = 3u64;

    // Delta used to encode 4 bits of message + a bit of padding on u64
    let delta = (1_u64 << 63) / message_modulus;

    // Apply our encoding
    let plaintext = Plaintext(input_message * delta);

    // Allocate a new LweCiphertext and encrypt our plaintext
    let lwe_ciphertext_in: LweCiphertextOwned<u64> = allocate_and_encrypt_new_lwe_ciphertext(
        &small_lwe_sk,
        plaintext,
        lwe_modular_std_dev,
        ciphertext_modulus,
        &mut encryption_generator,
    );

    // Compute a cleartext multiplication by 2
    let mut cleartext_multiplication_ct = lwe_ciphertext_in.clone();
    println!("Performing cleartext multiplication...");
    lwe_ciphertext_cleartext_mul(
        &mut cleartext_multiplication_ct,
        &lwe_ciphertext_in,
        Cleartext(2),
    );

    // Decrypt the cleartext multiplication result
    let cleartext_multiplication_plaintext: Plaintext<u64> =
        decrypt_lwe_ciphertext(&small_lwe_sk, &cleartext_multiplication_ct);

    // Create a SignedDecomposer to perform the rounding of the decrypted plaintext
    // We pass a DecompositionBaseLog of 5 and a DecompositionLevelCount of 1 indicating we want to
    // round the 5 MSB, 1 bit of padding plus our 4 bits of message
    let signed_decomposer =
        SignedDecomposer::new(DecompositionBaseLog(5), DecompositionLevelCount(1));

    // Round and remove our encoding
    let cleartext_multiplication_result: u64 =
        signed_decomposer.closest_representable(cleartext_multiplication_plaintext.0) / delta;

    println!("Checking result...");
    assert_eq!(6, cleartext_multiplication_result);
    println!(
        "Cleartext multiplication result is correct! \
        Expected 6, got {cleartext_multiplication_result}"
    );

    // Now we will use a PBS to compute the same multiplication, it is NOT the recommended way of
    // doing this operation in terms of performance as it's much more costly than a multiplication
    // with a cleartext, however it resets the noise in a ciphertext to a nominal level and allows
    // to evaluate arbitrary functions so depending on your use case it can be a better fit.

    // Here we will define a helper function to generate an accumulator for a PBS
    fn generate_accumulator<F>(
        polynomial_size: PolynomialSize,
        glwe_size: GlweSize,
        message_modulus: usize,
        ciphertext_modulus: CiphertextModulus<u64>,
        delta: u64,
        f: F,
    ) -> GlweCiphertextOwned<u64>
    where
        F: Fn(u64) -> u64,
    {
        // N/(p/2) = size of each block, to correct noise from the input we introduce the notion of
        // box, which manages redundancy to yield a denoised value for several noisy values around
        // a true input value.
        let box_size = polynomial_size.0 / message_modulus;

        // Create the accumulator
        let mut accumulator_u64 = vec![0_u64; polynomial_size.0];

        // Fill each box with the encoded denoised value
        for i in 0..message_modulus {
            let index = i * box_size;
            accumulator_u64[index..index + box_size]
                .iter_mut()
                .for_each(|a| *a = f(i as u64) * delta);
        }

        let half_box_size = box_size / 2;

        // Negate the first half_box_size coefficients to manage negacyclicity and rotate
        for a_i in accumulator_u64[0..half_box_size].iter_mut() {
            *a_i = (*a_i).wrapping_neg();
        }

        // Rotate the accumulator
        accumulator_u64.rotate_left(half_box_size);

        let accumulator_plaintext = PlaintextList::from_container(accumulator_u64);

        let accumulator =
            allocate_and_trivially_encrypt_new_glwe_ciphertext(
                glwe_size,
                &accumulator_plaintext,
                ciphertext_modulus,
            );

        accumulator
    }

    // Generate the accumulator for our multiplication by 2 using a simple closure
    let accumulator: GlweCiphertextOwned<u64> = generate_accumulator(
        polynomial_size,
        glwe_dimension.to_glwe_size(),
        message_modulus as usize,
        ciphertext_modulus,
        delta,
        |x: u64| 2 * x,
    );

    // Allocate the LweCiphertext to store the result of the PBS
    let mut pbs_multiplication_ct = LweCiphertext::new(
        0u64,
        big_lwe_sk.lwe_dimension().to_lwe_size(),
        ciphertext_modulus,
    );
    println!("Computing PBS...");
    programmable_bootstrap_lwe_ciphertext(
        &lwe_ciphertext_in,
        &mut pbs_multiplication_ct,
        &accumulator,
        &fourier_bsk,
    );

    // Decrypt the PBS multiplication result
    let pbs_multiplication_plaintext: Plaintext<u64> =
        decrypt_lwe_ciphertext(&big_lwe_sk, &pbs_multiplication_ct);

    // Round and remove our encoding
    let pbs_multiplication_result: u64 =
        signed_decomposer.closest_representable(pbs_multiplication_plaintext.0) / delta;

    println!("Checking result...");
    assert_eq!(6, pbs_multiplication_result);
    println!(
        "Multiplication via PBS result is correct! Expected 6, got {pbs_multiplication_result}"
    );
}

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

Specifications

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.

Input constraints:

The sell and buy orders are within the range [1,100].
The maximum number of sell and buy orders is 500, respectively.

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.

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:

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

Plain Implementation

Calculate the total sell volume and the total buy volume.

let total_sell_volume: u16 = sell_orders.iter().sum();
let total_buy_volume: u16 = buy_orders.iter().sum();

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

(total_sell_volume > total_buy_volume) * (total_buy_volume − total_sell_volume) + total_sell_volume

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.

let total_volume = std::cmp::min(total_buy_volume, total_sell_volume);

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

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;
}

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.

Do the fill operation also for the buy orders.

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;
}

The complete algorithm in plain Rust:

fn fill_orders(orders: &mut [u16], total_volume: u16) {
    let mut volume_left_to_transact = total_volume;
    for order in orders {
        let filled_amount = std::cmp::min(volume_left_to_transact, *order);
        *order = filled_amount;
        volume_left_to_transact -= filled_amount;
    }
}

pub fn volume_match(sell_orders: &mut [u16], buy_orders: &mut [u16]) {
    let total_sell_volume: u16 = sell_orders.iter().sum();
    let total_buy_volume: u16 = buy_orders.iter().sum();

    let total_volume = std::cmp::min(total_buy_volume, total_sell_volume);

    fill_orders(sell_orders, total_volume);
    fill_orders(buy_orders, total_volume);
}

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:

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>
server_key is of type tfhe::integer::ServerKey

Now, we can start implementing the algorithm with FHE:

Calculate the total sell volume and the total buy volume.

fn vector_sum(server_key: &ServerKey, orders: &mut [RadixCiphertext]) -> RadixCiphertext {
    let mut total_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    for order in orders {
        server_key.smart_add_assign(&mut total_volume, order);
    }
    total_volume
}

let mut total_sell_volume = vector_sum(server_key, sell_orders);
let mut total_buy_volume = vector_sum(server_key, buy_orders);

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

let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);

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.

fn fill_orders(
    server_key: &ServerKey,
    orders: &mut [RadixCiphertext],
    total_volume: RadixCiphertext,
) {
    let mut volume_left_to_transact = total_volume;
    for order in orders {
        let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, order);
        server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
        *order = filled_amount;
    }
}

fill_orders(server_key, sell_orders, total_volume.clone());
fill_orders(server_key, buy_orders, total_volume);

The complete algorithm in TFHE-rs:

const NUMBER_OF_BLOCKS: usize = 8;

fn vector_sum(server_key: &ServerKey, orders: &mut [RadixCiphertext]) -> RadixCiphertext {
    let mut total_volume = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    for order in orders {
        server_key.smart_add_assign(&mut total_volume, order);
    }
    total_volume
}

fn fill_orders(
    server_key: &ServerKey,
    orders: &mut [RadixCiphertext],
    total_volume: RadixCiphertext,
) {
    let mut volume_left_to_transact = total_volume;
    for order in orders {
        let mut filled_amount = server_key.smart_min(&mut volume_left_to_transact, order);
        server_key.smart_sub_assign(&mut volume_left_to_transact, &mut filled_amount);
        *order = filled_amount;
    }
}

pub fn volume_match(
    sell_orders: &mut [RadixCiphertext],
    buy_orders: &mut [RadixCiphertext],
    server_key: &ServerKey,
) {
    let mut total_sell_volume = vector_sum(server_key, sell_orders);
    let mut total_buy_volume = vector_sum(server_key, buy_orders);

    let total_volume = server_key.smart_min(&mut total_sell_volume, &mut total_buy_volume);

    fill_orders(server_key, sell_orders, total_volume.clone());
    fill_orders(server_key, buy_orders, total_volume);
}

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.

fn vector_sum(server_key: &ServerKey, orders: Vec<RadixCiphertext>) -> RadixCiphertext {
    orders.into_par_iter().reduce(
        || server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS),
        |mut acc: RadixCiphertext, mut ele: RadixCiphertext| {
            server_key.smart_add_parallelized(&mut acc, &mut ele)
        },
    )
}

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

let (mut total_sell_volume, mut total_buy_volume) = rayon::join(
    || vector_sum(server_key, sell_orders.to_owned()),
    || vector_sum(server_key, buy_orders.to_owned()),
);

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

rayon::join(
    || fill_orders(server_key, sell_orders, total_volume.clone()),
    || fill_orders(server_key, buy_orders, total_volume.clone()),
);

Optimized algorithm

fn vector_sum(server_key: &ServerKey, orders: Vec<RadixCiphertext>) -> RadixCiphertext {
    orders.into_par_iter().reduce(
        || server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS),
        |mut acc: RadixCiphertext, mut ele: RadixCiphertext| {
            server_key.smart_add_parallelized(&mut acc, &mut ele)
        },
    )
}

fn fill_orders(
    server_key: &ServerKey,
    orders: &mut [RadixCiphertext],
    total_volume: RadixCiphertext,
) {
    let mut volume_left_to_transact = total_volume;
    for order in orders {
        let mut filled_amount =
            server_key.smart_min_parallelized(&mut volume_left_to_transact, order);
        server_key.smart_sub_assign_parallelized(&mut volume_left_to_transact, &mut filled_amount);
        *order = filled_amount;
    }
}

pub fn volume_match(
    sell_orders: &mut [RadixCiphertext],
    buy_orders: &mut [RadixCiphertext],
    server_key: &ServerKey,
) {
    let (mut total_sell_volume, mut total_buy_volume) = rayon::join(
        || vector_sum(server_key, sell_orders.to_owned()),
        || vector_sum(server_key, buy_orders.to_owned()),
    );

    let total_volume =
        server_key.smart_min_parallelized(&mut total_sell_volume, &mut total_buy_volume);
    rayon::join(
        || fill_orders(server_key, sell_orders, total_volume.clone()),
        || fill_orders(server_key, buy_orders, total_volume.clone()),
    );
}

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:

fn fill_orders(total_orders: u16, orders: &mut [u16], prefix_sum_arr: &[u16]) {
    orders.iter().for_each(|order : &mut u64| {
        let previous_prefix_sum = if i == 0 { 0 } else { prefix_sum_arr[i - 1] };
        
        let diff = total_orders as i64 - previous_prefix_sum as i64;
        
        if (diff < 0) {
            *order = 0;
        } else if diff < order {
            *order = diff as u16;
        } else {
            // *order = *order;
            continue;
        }
    });
};

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


fn fill_orders(total_orders: u16, orders: &mut [u16], prefix_sum_arr: &[u16]) {
    for (i, order) in orders.iter_mut().enumerate() {
        let previous_prefix_sum = if i == 0 { 0 } else { prefix_sum_arr[i - 1] };

        *order = (total_orders as i64 - previous_prefix_sum as i64)
            .max(0)
            .min(*order as i64) as u16;
    }
}

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

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:

fn compute_prefix_sum(server_key: &ServerKey, arr: &[RadixCiphertext]) -> Vec<RadixCiphertext> {
    if arr.is_empty() {
        return arr.to_vec();
    }
    let mut prefix_sum: Vec<RadixCiphertext> = (0..arr.len().next_power_of_two())
        .into_par_iter()
        .map(|i| {
            if i < arr.len() {
                arr[i].clone()
            } else {
                server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS)
            }
        })
        .collect();
    for d in 0..prefix_sum.len().ilog2() {
        prefix_sum
            .par_chunks_exact_mut(2_usize.pow(d + 1))
            .for_each(move |chunk| {
                let length = chunk.len();
                let mut left = chunk.get((length - 1) / 2).unwrap().clone();
                server_key.smart_add_assign_parallelized(chunk.last_mut().unwrap(), &mut left)
            });
    }
    let last = prefix_sum.last().unwrap().clone();
    *prefix_sum.last_mut().unwrap() = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);
    for d in (0..prefix_sum.len().ilog2()).rev() {
        prefix_sum
            .par_chunks_exact_mut(2_usize.pow(d + 1))
            .for_each(move |chunk| {
                let length = chunk.len();
                let temp = chunk.last().unwrap().clone();
                let mut mid = chunk.get((length - 1) / 2).unwrap().clone();
                server_key.smart_add_assign_parallelized(chunk.last_mut().unwrap(), &mut mid);
                chunk[(length - 1) / 2] = temp;
            });
    }
    prefix_sum.push(last);
    prefix_sum[1..=arr.len()].to_vec()
}

fn fill_orders(
    server_key: &ServerKey,
    total_orders: &RadixCiphertext,
    orders: &mut [RadixCiphertext],
    prefix_sum_arr: &[RadixCiphertext],
) {
    orders
        .into_par_iter()
        .enumerate()
        .for_each(move |(i, order)| {
            // (total_orders - previous_prefix_sum).max(0)
            let mut diff = if i == 0 {
                total_orders.clone()
            } else {
                let previous_prefix_sum = &prefix_sum_arr[i - 1];

                // total_orders - previous_prefix_sum
                let mut diff = server_key.smart_sub_parallelized(
                    &mut total_orders.clone(),
                    &mut previous_prefix_sum.clone(),
                );

                // total_orders > prefix_sum
                let mut cond = server_key.smart_gt_parallelized(
                    &mut total_orders.clone(),
                    &mut previous_prefix_sum.clone(),
                );

                // (total_orders - previous_prefix_sum) * (total_orders > previous_prefix_sum)
                // = (total_orders - previous_prefix_sum).max(0)
                server_key.smart_mul_parallelized(&mut cond, &mut diff)
            };

            // (total_orders - previous_prefix_sum).max(0).min(*order);
            *order = server_key.smart_min_parallelized(&mut diff, order);
        });
}

/// FHE implementation of the volume matching algorithm.
///
/// In this function, the implemented algorithm is modified to utilize more concurrency.
///
/// Matches the given encrypted [sell_orders] with encrypted [buy_orders] using the given
/// [server_key]. The amount of the orders that are successfully filled is written over the original
/// order count.
pub fn volume_match(
    sell_orders: &mut [RadixCiphertext],
    buy_orders: &mut [RadixCiphertext],
    server_key: &ServerKey,
) {
    println!("Creating prefix sum arrays...");
    let time = Instant::now();
    let (prefix_sum_sell_orders, prefix_sum_buy_orders) = rayon::join(
        || compute_prefix_sum(server_key, sell_orders),
        || compute_prefix_sum(server_key, buy_orders),
    );
    println!("Created prefix sum arrays in {:?}", time.elapsed());

    let zero = server_key.create_trivial_zero_radix(NUMBER_OF_BLOCKS);

    let total_buy_orders = prefix_sum_buy_orders.last().unwrap_or(&zero);

    let total_sell_orders = prefix_sum_sell_orders.last().unwrap_or(&zero);

    println!("Matching orders...");
    let time = Instant::now();
    rayon::join(
        || {
            fill_orders(
                server_key,
                total_sell_orders,
                buy_orders,
                &prefix_sum_buy_orders,
            )
        },
        || {
            fill_orders(
                server_key,
                total_buy_orders,
                sell_orders,
                &prefix_sum_sell_orders,
            )
        },
    );
    println!("Matched orders in {:?}", time.elapsed());
}

Running the tutorial

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

# 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

Conclusion

In this tutorial, we've learned how to implement the volume matching algorithm described in this paper 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.

Operations

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

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

Radix-based integers.

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

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

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

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.

CRT-based integers.

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

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

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

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.

List of available operations

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

Types of operations

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

operations that take their inputs as encrypted values.
scalar operations take at least one non-encrypted value as input.

For example, the addition has both variants:

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

Each operation may come in different 'flavors':

unchecked: always does the operation, without checking if the result may exceed the capacity of the plaintext space.
checked: checks are done before computing the operation, returning an error if operation cannot be done safely.
smart: always does the operation, if the operation cannot be computed safely, the smart operation will propagate the carry buffer to make the operation possible. Some of those will require a mutable reference as input: this is because the inputs' carry might be cleaned, but this will not change the underlying encrypted value.
default: always compute the operation and always clear the carry. Could be slower than smart, but ensure that the timings are consistent from one call to another.

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

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

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.

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

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:

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

    server_key.checked_small_scalar_mul_assign(&mut ct_1, scalar).unwrap();
    
    server_key.checked_sub_assign(&mut ct_1, &ct_2).unwrap();
    
    let result = server_key.checked_add_assign(&mut ct_1, &ct_3);
    assert!(result.is_err());

    // We use the client key to decrypt the output of the circuit:
    // Only the scalar multiplication could be done
    let output: u64 = client_key.decrypt(&ct_1);
    assert_eq!(output, ((msg1 * scalar) - msg2) % modulus as u64);
}

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.

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

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

sks.smart_add(&mut a.clone(), &mut b.clone());

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.

Using default could slow down computations.

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

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:

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

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:

Start := 'a'

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

Start := 'a' | '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:

Start := Digit+

Digit := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

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:

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

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'

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

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]')
}

With this, we can translate the following basic regexes:

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

enum RegExpr {
    ...
    Seq { re_xs: Vec<RegExpr> },  // matching sequences of RegExpr components (Term.1)
}

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

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

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

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:

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.

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.

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:

to map each character of the content into the u8 ascii value, and then encrypt each bit of these u8 values individually.
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.

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

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.

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.

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:


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

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:

case RegExpr::Char { c } => {
    vec![(sk.eq(content_char, c), c_pos + 1)]
},

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

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

sk.bitor(sk.eq(content[0], a), sk.bitor(sk.eq(content[1], a), sk.eq(content[2], a)))

AnyChar is a no operation:

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)];
}

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

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

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:

eq (tests for an exact character match)
ge (tests for 'greater than' or 'equal to' a character)
le (tests for 'less than' or 'equal to' a character)
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)

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:

content[0] == a && content[1] == a && content[2] == b (we match the a in a?)
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.

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.

Supported regex patterns

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

Components

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

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

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:

SHA256 with Boolean API

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.

Sha256

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

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

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:

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)

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:

Maj(x, y, z) = (x AND (y XOR z)) XOR (y AND z)

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.

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.

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:

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
}

Making it homomorphic

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

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

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

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

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:

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
}

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.

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
}

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.

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
}

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 this paper or this other paper.

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.

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:

Carry = Maj(A, B, C)
Sum = A XOR B XOR C

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.

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

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.

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:

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

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:

./target/release/examples/sha256_bool < input.txt

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.