All parameter sets provide at least 128-bits of security according to the Lattice-Estimator, with an error probability equal to $2^{-40}$ when using programmable bootstrapping. This error probability is due to the randomness added at each encryption (see here for more details about the encryption process).

Parameters and message precision

shortint comes with sets of parameters that permit the use of the library functionalities securely and efficiently. Each parameter set is associated to the message and carry precisions. Therefore, each key pair is entangled to precision.

The user is allowed to choose which set of parameters to use when creating the pair of keys.

The difference between the parameter sets is the total amount of space dedicated to the plaintext, how it is split between the message buffer and the carry buffer, and the order in which the keyswitch (KS) and bootstrap (PBS) are computed. The syntax chosen for the name of a parameter is: PARAM_MESSAGE_{number of message bits}_CARRY_{number of carry bits}_{KS_PBS | PBS_KS}. For example, the set of parameters for a message buffer of 5 bits, a carry buffer of 2 bits and where the keyswitch is computed before the bootstrap is PARAM_MESSAGE_5_CARRY_2_KS_PBS.

Note that the KS_PBS order should have better performance at the expense of ciphertext size, PBS_KS is the opposite.

This example contains keys that are generated to have messages encoded over 2 bits (i.e., computations are done modulus $2^2 = 4$) 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.

use tfhe::shortint::prelude::*;

fn main() {
    // We generate a set of client/server keys, using the default parameters:
   let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);

    let msg1 = 3;
    let msg2 = 2;

    // We use the client key to encrypt two messages:
    let ct_1 = client_key.encrypt(msg1);
    let ct_2 = client_key.encrypt(msg2);
}

Impact of parameters on the operations

As shown here, the choice of the parameter set impacts the operations available and their efficiency.

Generic bi-variate functions.

The computations of bi-variate functions is based on a trick: concatenating two ciphertexts into one. Where the carry buffer is not at least as large as the message buffer, this trick no longer works. In this case, many bi-variate operations, such as comparisons, cannot be correctly computed. The only exception concerns multiplication.

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.

User-defined parameter sets

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:

use tfhe::shortint::prelude::*;
use tfhe::shortint::parameters::DynamicDistribution;

fn main() {
    // WARNING: might be insecure and/or incorrect
    // You can create your own set of parameters
    let param = ClassicPBSParameters::new(
        LweDimension(656),
        GlweDimension(2),
        PolynomialSize(512),
        DynamicDistribution::new_gaussian_from_std_dev(
            StandardDev(0.000034119201269311964),
        ),
        DynamicDistribution::new_gaussian_from_std_dev(
            StandardDev(0.00000004053919869756513),
        ),
        DecompositionBaseLog(8),
        DecompositionLevelCount(2),
        DecompositionBaseLog(3),
        DecompositionLevelCount(4),
        MessageModulus(4),
        CarryModulus(1),
        MaxNoiseLevel::new(2),
        2.0f64.powi(-40),
        CiphertextModulus::new_native(),
        EncryptionKeyChoice::Big,
    );
}

tfhe::shortint is dedicated to unsigned integers smaller than 8 bits. The steps to homomorphically evaluate a circuit are described below.

Key generation

tfhe::shortint provides 3 key types:

• ClientKey

• ServerKey

• PublicKey

The ClientKey is the key that encrypts and decrypts messages (integer values up to 8 bits here). It is meant to be kept private and should never be shared. This key is created from parameter values that will dictate both the security and efficiency of computations. The parameters also set the maximum number of bits of message encrypted in a ciphertext.

The ServerKey is the key that is used to evaluate the FHE computations. Most importantly, it contains a bootstrapping key and a keyswitching key. This key is created from a ClientKey that needs to be shared to the server (it is not meant to be kept private). A user with a ServerKey can compute on the encrypted data sent by the owner of the associated ClientKey.

Computation/operation methods are tied to the ServerKey type.

The PublicKey is the key used to encrypt messages. It can be publicly shared to allow users to encrypt data such that only the ClientKey holder will be able to decrypt. Encrypting with the PublicKey does not alter the homomorphic capabilities associated to the ServerKey.

Encrypting values

Once the keys have been generated, the client key is used to encrypt data:

Encrypting values using a public key

Once the keys have been generated, the client key is used to encrypt data:

Computing and decrypting

Using the server_key, addition is possible over encrypted values. The resulting plaintext is recovered after the decryption via the secret client key.

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.

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.

#List of available operations

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:

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.

# Cargo.toml

[dependencies]
# ...
bincode = "1.3.3"

// main.rs

use std::io::Cursor;
use tfhe::shortint::prelude::*;


fn main() -> Result<(), Box<dyn std::error::Error>> {
    let (client_key, server_key) = gen_keys(PARAM_MESSAGE_2_CARRY_2_KS_PBS);

    let msg1 = 1;
    let msg2 = 0;

    let ct_1 = client_key.encrypt(msg1);
    let ct_2 = client_key.encrypt(msg2);

    let mut serialized_data = Vec::new();
    bincode::serialize_into(&mut serialized_data, &server_key)?;
    bincode::serialize_into(&mut serialized_data, &ct_1)?;
    bincode::serialize_into(&mut serialized_data, &ct_2)?;

    // Simulate sending serialized data to a server and getting
    // back the serialized result
    let serialized_result = server_function(&serialized_data)?;
    let result: Ciphertext = bincode::deserialize(&serialized_result)?;

    let output = client_key.decrypt(&result);
    assert_eq!(output, msg1 + msg2);
    Ok(())
}


fn server_function(serialized_data: &[u8]) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
    let mut serialized_data = Cursor::new(serialized_data);
    let server_key: ServerKey = bincode::deserialize_from(&mut serialized_data)?;
    let ct_1: Ciphertext = bincode::deserialize_from(&mut serialized_data)?;
    let ct_2: Ciphertext = bincode::deserialize_from(&mut serialized_data)?;

    let result = server_key.unchecked_add(&ct_1, &ct_2);

    let serialized_result = bincode::serialize(&result)?;

    Ok(serialized_result)
}