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.
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:
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:
As explained in the introduction, some types (Serverkey
, Ciphertext
) are meant to be shared with the server that performs the computations.
The easiest way to send these data to a server is to use the serialization and deserialization features. tfhe::shortint
uses the framework. Serde's Serialize and Deserialize are then implemented on the tfhe::shortint
types.
To serialize the data, we need to pick a . For our use case, is a good choice, mainly because it is a binary format.