Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
This library makes it possible to execute homomorphic operations over encrypted data, where the data are either Booleans, short integers (named shortint in the rest of this documentation), or integers up to 256 bits. It allows you to execute a circuit on an untrusted server because both circuit inputs and outputs are kept private. Data are indeed encrypted on the client side, before being sent to the server. On the server side, every computation is performed on ciphertexts.
The server, however, has to know the circuit to be evaluated. At the end of the computation, the server returns the encryption of the result to the user. Then the user can decrypt it with the secret key
.
The overall process to write an homomorphic program is the same for all types. The basic steps for using the TFHE-rs library are the following:
Choose a data type (Boolean, shortint, integer)
Import the library
Create client and server keys
Encrypt data with the client key
Compute over encrypted data using the server key
Decrypt data with the client key
This library has different modules, with different levels of abstraction.
There is the core_crypto module, which is the lowest level API with the primitive functions and types of the TFHE scheme.
Above the core_crypto module, there are the Boolean, shortint, and integer modules, which contain easy to use APIs enabling evaluation of Boolean, short integer, and integer circuits.
Finally, there is the high-level module built on top of the Boolean, shortint, integer modules. This module is meant to abstract cryptographic complexities: no cryptographical knowledge is required to start developing an FHE application. Another benefit of the high-level module is the drastically simplified development process compared to lower level modules.
TFHE-rs exposes a high-level API by default that includes datatypes that try to match Rust's native types by having overloaded operators (+, -, ...).
Here is an example of how the high-level API is used:
Use the --release
flag to run this example (eg: cargo run --release
)
Here is an example of how the library can be used to evaluate a Boolean circuit:
Use the --release
flag to run this example (eg: cargo run --release
)
Here is a full example using shortint:
Use the --release
flag to run this example (eg: cargo run --release
)
Use the --release
flag to run this example (eg: cargo run --release
)
The library is simple to use and can evaluate homomorphic circuits of arbitrary length. The description of the algorithms can be found in the TFHE paper (also available as ePrint 2018/421).
This contains the operations available in tfhe::boolean, along with code examples.
Let ct_1, ct_2, ct_3
be three Boolean ciphertexts. Then, the MUX gate (abbreviation of MUltipleXer) is equivalent to the operation:
This example shows how to use the MUX ternary gate:
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
.
In the first step, the client creates two keys, the client key
and the server key
, with the tfhe::boolean::gen_keys
function:
The client_key
is of type ClientKey
. It is secret and must never be transmitted. This key will only be used to encrypt and decrypt data.
The server_key
is of type ServerKey
. It is a public key and can be shared with any party. This key has to be sent to the server because it is required for homomorphic computation.
Note that both the client_key
and server_key
implement the Serialize
and Deserialize
traits. This way you can use any compatible serializer to store/send the data. To store the server_key
in a binary file, you can use the bincode
library:
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:
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.
Once the encrypted inputs are on the server side, the server_key
can be used to homomorphically execute the desired Boolean circuit:
Once the encrypted output is on the client side, the client_key
can be used to decrypt it:
Some cryptographic parameters will require tuning to ensure both the correctness of the result and the security of the computation.
To make it simpler, we've provided two sets of parameters, which ensure correct computations for a certain probability with the standard security of 128 bits. There exists an error probability due to the probabilistic nature of the encryption, which requires adding randomness (noise) following a Gaussian distribution. If this noise is too large, the decryption will not give a correct result. There is a trade-off between efficiency and correctness: generally, using a less efficient parameter set (in terms of computation time) leads to a smaller risk of having an error during homomorphic evaluation.
The following array summarizes this:
You can also create your own set of parameters. This is an unsafe
operation as failing to properly fix the parameters will result in an incorrect and/or insecure computation:
Since the ServerKey
and ClientKey
types both implement the Serialize
and Deserialize
traits, you are free to use any serializer that suits you to save and load the keys to disk.
Here is an example using the bincode
serialization library, which serializes to a binary format:
tfhe::shortint
is dedicated to unsigned integers smaller than 8 bits. The steps to homomorphically evaluate a circuit are described below.
tfhe::shortint
provides 3 key types:
ClientKey
ServerKey
PublicKey
The ClientKey
is the key that encrypts and decrypts messages (integer values up to 8 bits here). It is meant to be kept private and should never be shared. This key is created from parameter values that will dictate both the security and efficiency of computations. The parameters also set the maximum number of bits of message encrypted in a ciphertext.
The ServerKey
is the key that is used to evaluate the FHE computations. Most importantly, it contains a bootstrapping key and a keyswitching key. This key is created from a ClientKey
that needs to be shared to the server (it is not meant to be kept private). A user with a ServerKey
can compute on the encrypted data sent by the owner of the associated ClientKey
.
Computation/operation methods are tied to the ServerKey
type.
The PublicKey
is the key used to encrypt messages. It can be publicly shared to allow users to encrypt data such that only the ClientKey
holder will be able to decrypt. Encrypting with the PublicKey
does not alter the homomorphic capabilities associated to the ServerKey
.
Once the keys have been generated, the client key is used to encrypt data:
Once the keys have been generated, the client key is used to encrypt data:
Using the server_key
, addition is possible over encrypted values. The resulting plaintext is recovered after the decryption via the secret client key.
The TFHE cryptographic scheme relies on a variant of and is based on a problem so difficult that it is even post-quantum resistant.
In the two proposed sets of parameters, the only difference lies in this error probability. The default parameter set ensures an error probability of at most when computing a programmable bootstrapping (i.e., any gates but the not
). The other one is closer to the error probability claimed in the original , namely , but it is up-to-date regarding security requirements.
Parameter set | Error probability |
---|
As explained in the introduction, some types (Serverkey
, Ciphertext
) are meant to be shared with the server that performs the computations.
The easiest way to send these data to a server is to use the serialization and deserialization features. tfhe::shortint
uses the serde framework. Serde's Serialize and Deserialize are then implemented on the tfhe::shortint
types.
To serialize the data, we need to pick a data format. For our use case, bincode is a good choice, mainly because it is a binary format.
All parameter sets provide at least 128-bits of security according to the Lattice-Estimator, with an error probability equal to when using programmable bootstrapping. This error probability is due to the randomness added at each encryption (see here for more details about the encryption process).
shortint
comes with sets of parameters that permit the use of the library functionalities securely and efficiently. Each parameter set is associated to the message and carry precisions. Therefore, each key pair is entangled to precision.
The user is allowed to choose which set of parameters to use when creating the pair of keys.
The difference between the parameter sets is the total amount of space dedicated to the plaintext, how it is split between the message buffer and the carry buffer, and the order in which the keyswitch (KS) and bootstrap (PBS) are computed. The syntax chosen for the name of a parameter is: PARAM_MESSAGE_{number of message bits}_CARRY_{number of carry bits}_{KS_PBS | PBS_KS}
. For example, the set of parameters for a message buffer of 5 bits, a carry buffer of 2 bits and where the keyswitch is computed before the bootstrap is PARAM_MESSAGE_5_CARRY_2_KS_PBS
.
Note that the KS_PBS
order should have better performance at the expense of ciphertext size, PBS_KS
is the opposite.
This example contains keys that are generated to have messages encoded over 2 bits (i.e., computations are done modulus ) with 2 bits of carry.
The PARAM_MESSAGE_2_CARRY_2_KS_PBS
parameter set is the default shortint
parameter set that you can also use through the tfhe::shortint::prelude::DEFAULT_PARAMETERS
constant.
As shown here, the choice of the parameter set impacts the operations available and their efficiency.
The computations of bi-variate functions is based on a trick: concatenating two ciphertexts into one. Where the carry buffer is not at least as large as the message buffer, this trick no longer works. In this case, many bi-variate operations, such as comparisons, cannot be correctly computed. The only exception concerns multiplication.
In the case of multiplication, two algorithms are implemented: the first one relies on the bi-variate function trick, where the other one is based on the quarter square method. To correctly compute a multiplication, the only requirement is to have at least one bit of carry (i.e., using parameter sets PARAM_MESSAGE_X_CARRY_Y with Y>=1). This method is slower than using the other one. Using the smart
version of the multiplication automatically chooses which algorithm is used depending on the chosen parameters.
It is possible to define new parameter sets. To do so, it is sufficient to use the function new()
or to manually fill the ClassicPBSParameters
structure fields.
For instance:
DEFAULT_PARAMETERS |
TFHE_LIB_PARAMETERS |
The structure and operations related to short integers are described in this section.
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.
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.
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
(*)
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:
Classical arithmetic operations are supported by shortint:
Short homomorphic integer types support some bitwise operations.
A simple example on how to use these operations:
Short homomorphic integer types support comparison operations.
A simple example on how to use these operations:
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.
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:
tfhe::integer
is dedicated to integers smaller than 256 bits. The steps to homomorphically evaluate an integer circuit are described here.
integer
provides 3 basic key types:
ClientKey
ServerKey
PublicKey
The ClientKey
is the key that encrypts and decrypts messages, thus this key is meant to be kept private and should never be shared. This key is created from parameter values that will dictate both the security and efficiency of computations. The parameters also set the maximum number of bits of message encrypted in a ciphertext.
The ServerKey
is the key that is used to actually do the FHE computations. It contains a bootstrapping key and a keyswitching key. This key is created from a ClientKey
that needs to be shared to the server, so it is not meant to be kept private. A user with a ServerKey
can compute on the encrypted data sent by the owner of the associated ClientKey
.
To reflect this, computation/operation methods are tied to the ServerKey
type.
The PublicKey
is a key used to encrypt messages. It can be publicly shared to allow users to encrypt data such that only the ClientKey
holder will be able to decrypt. Encrypting with the PublicKey
does not alter the homomorphic capabilities associated to the ServerKey
.
To generate the keys, a user needs two parameters:
A set of shortint
cryptographic parameters.
The number of ciphertexts used to encrypt an integer (we call them "shortint blocks").
We are now going to build a pair of keys that can encrypt 8-bit integers (signed or unsigned) by using 4 shortint blocks that store 2 bits of message each.
Once we have our keys, we can encrypt values:
Once the client key is generated, the public key can be derived and used to encrypt data.
With our server_key
, and encrypted values, we can now do an addition and then decrypt the result.
The structure and operations related to integers are described in this section.
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
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.
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.
The list of operations available in integer
depends on the type of representation:
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.
Let's try to do a circuit evaluation using the different flavors of already introduced operations. For a very small circuit, the unchecked
flavor may be enough to do the computation correctly. Otherwise, checked
and smart
are the best options.
As an example, let's do a scalar multiplication, a subtraction, and an addition.
During this computation the carry buffer has been overflowed, and the output may be incorrect as all the operations were unchecked
.
If the same circuit is done but using the checked
flavor, a panic will occur:
The checked
flavor permits the manual management of the overflow of the carry buffer by raising an error if correctness is not guaranteed.
Using the smart
flavor will output the correct result all the time. However, the computation may be slower as the carry buffer may be propagated during the computations.
You must avoid cloning the inputs when calling smart
operations to preserve performance. For instance, you SHOULD NOT have these kind of patterns in the code:
The main advantage of the default flavor is to ensure predictable timings, as long as only this kind of operation is used. Only the parallelized version of the operations is provided.
Using default
could slow down computations.
integer
does not come with its own set of parameters. Instead, it relies on parameters from shortint
. Currently, parameter sets having the same space dedicated to the message and the carry (i.e. PARAM_MESSAGE_{X}_CARRY_{X}
with X
in [1,4]) are recommended. See for more details about cryptographic parameters, and to see how to properly instantiate integers depending on the chosen representation.
The first possibility to represent a large integer is to use a Radix-based decomposition on the plaintexts. Let be a basis such that the size of is smaller than (or equal to) 4 bits. Then, an integer can be written as , where each is strictly smaller than . Each is then independently encrypted. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.
The definition of an integer requires a basis and a number of blocks. 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., ) and 4 blocks.
The second approach to represent large integers is based on the Chinese Remainder Theorem. In this case, the basis is composed of several integers , such that there are pairwise coprime, and each has a size smaller than 4 bits. The CRT-based integer are defined modulus . For an integer , its CRT decomposition is simply defined as . Each part is then encrypted as a shortint ciphertext. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.
In the following example, the chosen basis is . The integer is defined modulus . There is no need to pre-size the number of blocks since it is determined from the number of values composing the basis. Here, the integer is split over three blocks.
Operation name | Radix-based | CRT-based |
---|
As explained in the introduction, some types (Serverkey
, Ciphertext
) are meant to be shared with the server that does the computations.
The easiest way to send these data to a server is to use the serialization and deserialization features. TFHE-rs
uses the serde framework, so serde's Serialize and Deserialize are implemented.
To be able to serialize our data, a data format needs to be picked. Here, bincode is a good choice, mainly because it is binary format.
Negation |
Addition |
Scalar Addition |
Subtraction |
Scalar Subtraction |
Multiplication |
Scalar Multiplication |
Bitwise OR, AND, XOR |
Equality |
Left/Right Shift |
Comparisons |
Min, Max |