tfhe::integer
is dedicated to unsigned 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 an 8-bit integer 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.
integer
does not come with its own set of parameters. Instead, it relies on parameters from shortint
. Currently, parameter sets having the same space dedicated to the message and the carry (i.e. PARAM_MESSAGE_{X}_CARRY_{X}
with X
in [1,4]) are recommended. See here for more details about cryptographic parameters, and here to see how to properly instantiate integers depending on the chosen representation.
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.
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
The first possibility to represent a large integer is to use a Radix-based decomposition on the plaintexts. Let be a basis such that the size of is smaller than (or equal to) 4 bits. Then, an integer can be written as , where each is strictly smaller than . Each is then independently encrypted. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.
The definition of an integer requires a basis and a number of blocks. This is done at key generation. Below, the keys are dedicated to unsigned integers encrypting messages over 8 bits, using a basis over 2 bits (i.e., ) and 4 blocks.
In this representation, the correctness of operations requires the carries to be propagated throughout the ciphertext. This operation is costly, since it relies on the computation of many programmable bootstrapping operations over shortints.
The second approach to represent large integers is based on the Chinese Remainder Theorem. In this case, the basis is composed of several integers , such that there are pairwise coprime, and each has a size smaller than 4 bits. The CRT-based integer are defined modulus . For an integer , its CRT decomposition is simply defined as . Each part is then encrypted as a shortint ciphertext. In the end, an Integer ciphertext is defined as a set of shortint ciphertexts.
In the following example, the chosen basis is . The integer is defined modulus . There is no need to pre-size the number of blocks since it is determined from the number of values composing the basis. Here, the integer is split over three blocks.
This representation has many advantages: no carry propagation is required, cleaning the carry buffer of each ciphertext block is enough. This implies that operations can easily be parallelized. It also allows the efficient computation of PBS in the case where the function is CRT-compliant.
A variant of the CRT is proposed where each block might be associated to a different key couple. Here, a keychain to the computations is required, but this may result in a performance improvement.
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.
Let's try to do a circuit evaluation using the different flavors of already introduced operations. For a very small circuit, the unchecked
flavor may be enough to do the computation correctly. Otherwise, checked
and smart
are the best options.
As an example, let's do a scalar multiplication, a subtraction, and an addition.
During this computation the carry buffer has been overflowed, and the output may be incorrect as all the operations were unchecked
.
If the same circuit is done but using the checked
flavor, a panic will occur:
The checked
flavor permits the manual management of the overflow of the carry buffer by raising an error if correctness is not guaranteed.
Using the smart
flavor will output the correct result all the time. However, the computation may be slower as the carry buffer may be propagated during the computations.
The main advantage of the default flavor is to ensure predictable timings, as long as only this kind of operation is used. Only the parallelized version of the operations is provided.
Using default
could slow down computations.
Operation name | Radix-based | CRT-based |
---|---|---|
Negation
Addition
Scalar Addition
Subtraction
Scalar Subtraction
Multiplication
Scalar Multiplication
Bitwise OR, AND, XOR
Equality
Left/Right Shift
Comparisons <
,<=
,>
, >=
Min, Max