Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
Loading...
The simplest way of encrypting plaintexts into ciphertexts in Concrete is via LWE encryption.
For simplicity, we use "LWE" and "LWE ciphertext" interchangeably.
An LWE is composed of a vector of integers called a mask and an integer called a body. The size of the mask vector is called the dimension. To achieve a strong level of security, we need to add random gaussian noise to the body. The combination of the mask's dimension and standard deviation of the noise distribution is what we call the LWE security parameters.
Choosing wrong security parameters can lead to weak security, slow computations or insufficient precision to carry the computations.
Parameters are stored in a LWEParams
struct that takes the dimension and standard deviation as parameters. Concrete also comes with predefined sets of parameters for 80 or 128 bits of security. These parameters were secure as of September 15th 2020, and estimated using the LWE estimator.
We can see above that for a given security level, the larger the dimension is, the smaller the noise standard deviation has to be. A larger dimension will lead to more computation and larger ciphertexts, while a larger standard deviation will lead to more noisy ciphertexts and less precise messages. Hence, there is a tradeoff between performance and precision, which is inherent to any FHE program.
A good rule of thumb is to pick secure parameters with the largest possible noise that supports your program's desired precision. By not provisioning unnecessary precision, you can use a smaller mask dimension and thus get better runtime performance.
Once appropriate security parameters have been chosen, we can generate a secret key that will be used to encrypt and decrypt ciphertexts. Concrete currently only implements symmetric uniformly random binary secret keys. Future versions will offer support for public-key cryptography and other key generation methods.
Creating a secret key in Concrete is as easy as using the new
function from the LWESecretKey
struct, and passing it the chosen security parameters:
Secret keys can be saved into json files with the save
method, and recovered using the load
method:
Encrypting messages can be done by either:
using the LWE
struct's factory method encrypt
, which takes a plaintext and a secret key as a parameter.
using the LWE
struct's factory method encode_encrypt
, which takes a message, an encoder and a secret key. This method will encode the messages before encrypting them.
The following code shows how to create an LWE by encoding and encrypting in one step:
In FHE, it is often necessary to manipulate a vector of encrypted values, rather than a single value. Concrete has a convenience struct to simplify working with vectors of LWEs called VectorLWE
, which has the same methods as the LWE struct, but taking a vector of message as input:
Decryption turns a ciphertext into a plaintext and decodes it to yield the final message. The same secret key that was used for encryption must be used for decryption. The decrypt_decode
method exists both for LWE and VectorLWE ciphertexts:
The decrypt_decode
method performs two separate operations:
the decryption, which decrypts the ciphertext using the secret key
the decoding, which removes the noise and decodes the result back to the domain of the original message.
Here is a complete example using a vector of messages:
LWE stands for Learning With Errors and refers to a computational problem conjectured to be hard to solve. With LWE, every computation is performed in a modular integer ring such as where is the modulus (typically 64).
Concrete is a fully homomorphic encryption (FHE) library that implements Zama's variant of TFHE. TFHE is based on Learning With Errors (LWE), a well studied cryptographic primitive believed to be secure even against quantum computers.
Concrete is currently released in alpha. The API is not stable and likely to change short term.
Concrete is an open source library. The code is available on Github.
In cryptography, a raw value is called a message (also sometimes called a cleartext), an encoded message is called a plaintext and an encrypted plaintext is called a ciphertext.
The idea of homomorphic encryption is that you can compute on ciphertexts while not knowing messages encrypted in them. A scheme is said to be fully homomorphic, meaning any program can be evaluated with it, if at least two of the following operations are supported (is a plaintext and is the corresponding ciphertext):
homomorphic univariate function evaluation:
homomorphic addition:
homomorphic multiplication:
Zama's variant of TFHE is fully homomorphic and deals with approximate real numbers () as messages. It implements homomorphic 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 Concrete consists in:
generating a secret key using secure parameters
encoding input messages into fixed-precision plaintexts
encrypting plaintexts using the secret key to produce ciphertexts
operating homomorphically on ciphertexts
decrypting the resulting ciphertexts into plaintexts using the secret key
decoding plaintexts to get the final output messages
Here is an example program that adds two ciphertexts:
Concrete being a library, all functions are wrapped in a Result
to let you manage errors the way you see fit for your program.
This guide will walk you through using the Concrete library to build homomorphic programs, explaining the underlying key concepts as they are encountered.
In FHE, there are two types of operations that can be applied to ciphertexts:
leveled operations, which are faster but increase the noise in the ciphertext
bootstrapped operations, which are slower but reduce the noise in the ciphertext
This section explains the concept of noise and padding in ciphertexts, which are core to how Concrete enables efficient homomorphic operations.
(R)LWE requires random noise to be added to the plaintext at encryption time to be secure. The ''size'' of the noise (or, more precisely, ) is a security parameter, so that larger is the noise, the more secure is the encryption.
In Concrete, the noise is encoded in the least significants bits of a ciphertext. Each leveled computation will increase the noise, and thus if too many computations are done, the noise will eventually overflow onto the significant data bits and lead to an incorrect result.
The figure below illustrates this problem in case of an addition, where an extra bit of noise is incurred as a result.
Concrete enables managing noise in multiple ways:
by emitting a warning when the ciphertext has accumulated too much noise.
by enabling to chose the precision of the encoding to allow for more empty bits between the noise and the message.
by performing a bootstrapping operation to reset the noise to a nominal value.
Since encoded values have a fixed precision, operating on them can sometime produce results that are outside the original interval. To avoid losing precision or wrapping around the interval, Concrete enables storing the additional bits by defining bits of padding on the most significant bits. Padding bits are defined as part of the encoder.
As an example, consider adding two ciphertexts. Adding two values could en up outside the range of either encoders, 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 additional additions would yield correct results.
Concrete enables managing padding in multiple ways:
via methods that enable determining at runtime how many bits of padding are left.
by defining an encoder with enough bits of padding.
by performing a bootstrapping operation that frees up bits of padding.
Make sure to provision enough bits of padding for your program to run correctly, it will be more efficient than bootstrapping too often.
The key-switching allows to convert a ciphertext encrypted with a secret key, to a ciphertext encrypted with another secret key. This requires a special Key-switching key (). Key-switching is used primarily to change the dimension security parameter of a ciphertext, and as part of the bootstrapping procedure.
A Key-switching key is an encryption of the bits of the original secret key (secret_key_before
) under the destination secret key (secret_key_after
). To generate a key-switching key, you can use the structure LWEKSK
with the following parameters:
secret_key_before
: the key under which the ciphertext is encrypted
secret_key_after
: the key under which we want the ciphertext to be encrypted after the key-switch
base_log
: number of bits of the decomposition base
level
: precision of the decomposition
Both the base_log
and the level
parameters are used to managed the noise of the ciphertext and the message precision on the plaintext. They also impact directly the computation cost and the key-switching key size. The level
is usually chosen small to obtain a good tradeoff between all parameters.
Here is a code example:
Performing a key-switch is done by calling the method keyswitch
, which takes a key-switching key as input, and outputs a ciphertext under the new key. Note that in this example, the ciphertext also changes the dimension security parameter, from 1024 to 630.
Operation
Type
Leveled
Side effects
Modifies encryption key
Potentially modifies security parameters
Concrete is built in Rust (💛). Here is how to install it.
Concrete requires Rust 1.46 or above. Run the following to install the latest Rust version, or refer to the rust website for more options.
Concrete uses the FFTW library for fast FFT calculations. Use the following commands to install it:
To install FFTW from source, follow the steps described in FFTW's website.
Create a new Rust project if needed using Cargo:
Then add the Concrete dependency concrete_lib = "0.1.0"
to the Cargo.toml
file. For the code examples in this guide, you will also need to import itertools
. Your configuration should look something like:
To use the Concrete library in your code, simply import the concrete
root module:
Then compile and run to test everything works fine:
Next, we will learn about homomorphic encryption and how to use Concrete to execute a program over encrypted data!
Multiplying a ciphertext by a constant means multiplying a ciphertext by a constant (plaintext value). This is a leveled operation that increases noise, optionally consume padding, and optionally changes the encoding.
By default, LWE ciphertexts can only be multiplied by integer constants. Under the hood, this is done by multiplying the ciphertext's body and mask by the constant. This is only currently implemented statically, i.e. without modifying the encoder, via the mul_constant_static_encoder
method (and its mutable form mul_constant_static_encoder_inplace
).
Because integer constant addition is implemented using a static encoder, the result of the multiplication should be in the interval of the ciphertext's encoder to avoid wrapping around with undefined behavior.
Here is an example using the mutable form:
This operation is also available in vectorized form for VectorLWE
instances, simply by passing a vector of integers to the mul_constant_static_encoder
method:
Multiplying a ciphertext by a real-valued constant is supported in Concrete thanks to the use of padding in the encoder, via the mul_constant_with_padding
method (and its mutable counterpart mul_constant_with_padding_inplace
). The method take 3 arguments:
constant
: the constant to multiply the ciphertext by, as a float64
max_constant
: the maximum value the constant can take. This is necessary to determine the encoding of the result of the multiplication, and particularly useful when multiplying several ciphertexts by different constants (for example when working with VectorLWE
), as the output encoding of the ciphertexts will end up being the same.
nb_bit_padding
: the number of bits of padding to be consumed by the multiplication, which also represents the precision of the constant being multiplied. This cannot be bigger than the remaining bits of padding in the ciphertext being multiplied.
Here is an example code:
And in vectorized form, where all ciphertexts end up with the same encoder interval:
The following functions are implemented:
addition between a ciphertext and a constant
subtraction between a ciphertext and a constant
multiplication between a ciphertext and a constant
addition between two ciphertexts
subtraction between two ciphertexts
multiplication between two ciphertexts
max between two ciphertexts
To compute the opposite of an LWE, simply use the opposite
method, which will return a new ciphertext with the modified value. The method exists in a mutable opposite_inplace
form as well, which modifies the ciphertext itself. All operations in concrete are implemented in immutable and mutable forms, with mutable forms always postfixed with _inplace
.
Here is a complete example for a single LWE:
As for all operations in Concrete, they can be applied to a vector of messages using the VectorLWE
struct instead of LWE
. The vectorized form has an additional method opposite_nth
that enables negating a single value by passing its index to the function.
While you do not need to fully understand RLWE to use Concrete, it is useful to know they exist, as they will be used under the hood to perform bootstrapping (which we will learn about later).
Concrete implements RLWE and VectorRLWE structs, but without the ability to perform SIMD-like operations on them. This will be available in a future release.
Since RLWE is an extension of LWE, you can extract one of the RLWE ciphertext polynomial coefficient as an LWE ciphertext.
RLWE instances are 2-dimensional: they hold a vector of ciphertexts, in which each coefficient is itself a plaintext. Thus, when extracting an LWE, we need to both specify the coefficient we want as well as the ciphertext from which to extract that coefficient. This is done via the extract_1_lwe
function:
Converting an RLWESecretKey
instance into an LWESecretKey
is done using to_lwe_secret_key
function:
Adding a constant to an LWE ciphertext is a leveled operation that does not increase noise and does not consume padding, but can optionally change the interval of the encoder, depending on the method being used.
There are two ways to add a constant to a ciphertext:
using the add_constant_static_encoder
method that adds a constant to a ciphertext without changing the encoding. With this method, the ciphertext itself is changed by adding the constant to its body, while the encoding remains the same.
Both methods also exist in mutable form that modify the current ciphertext: add_inplace
(or its verbose form add_constant_dynamic_encoder_inplace
) and add_constant_static_encoder_inplace
.
The value of the constant being added in the dynamic method does not have to be in the interval of the original encoder.
If the result of adding a constant to a ciphertext using the static method ends up outside the interval of the original ciphertext, the result will wrap around the interval with undefined behavior.
The example below shows how to add a constant to an LWE:
Both dynamic and static methods, as well as their mutable counterparts, exist in vectorized form when operating with a VectorLWE
struct. In this case, constants in the vector are added element wise to the vector of ciphertexts:
Adding or subtracting LWE ciphertexts together is a leveled operation that increases noise and potentially consumer padding and modify the encoding. It is one of the fundamental FHE operation.
The common way to add ciphertexts is to consume bits of padding and update the interval of their respective encoders. This can be achieved using the short form method add
(or add_inplace
) which simply takes another ciphertext as argument. This is an alias for the more verbose add_with_padding
(or add_with_padding_inplace
).
Homomorphic subtraction works exactly the same as addition, using the sub_with_padding
(or sub_with_padding_inplace
) methods.
Here is a code example:
And in vectorized form:
If the interval of the output of the homomorphic addition is known, it is possible to add ciphertexts without consuming padding. To do so, you can use the add_with_new_min
(or add_with_new_min_inplace
) method that takes as arguments the ciphertext to add and the minimum new_min
of the interval of the result.
If the result of the homomorphic addition is outside of the specified range, the behavior is undefined and the result most likely to be incorrect.
Subtracting ciphertexts without consuming padding is not yet implemented in Concrete.
Here is a code example:
Concrete enables operating homomorphically on real-values by encoding them into fixed-precision representation called plaintexts. Encoders have:
Defining the right encoders is important to ensure your homomorphic program runs accurately and efficiently. More precision typically means more internal operations, and thus, a more computationally expensive homomorphic program, while less precision can lead to imprecise results.
Always chose the smallest possible precision that yields the desired output. This will ensure your homomorphic program runs faster!
Concrete simplifies managing precision by providing an Encoder
struct that encodes real messages into plaintexts. An encoder takes three parameters:
the number of bits of precision needed to represent your data
the number of bits of padding to carry on leveled operations (more on that later)
Instead of using the min and max of the interval, an encoder can also be defined using the center value of the interval and a radius:
Concrete only requires that you specify the encoding for your input messages. Once you start operating on the ciphertexts, the encoding will evolve dynamically to represent the range of possible values. When it is not possible to infer the encoding, an output encoder will need to be specified.
Under the hood, a Plaintext instance stores a vector of encoded messages, each with their own encoder. This enables Concrete to better manage performances. Thus, a plaintext in Concrete can be either a single encoded message, or a vector of encoded messages.
Encoding a message into a plaintext is rather simple:
The encode function is versatile, meaning you can pass it a vector of messages instead of a single message. Internally, both are represented in the same way, with single-message plaintexts simply representing the values as a vector of size 1.
The decode method always returns a vector of messages, since this is how the plaintext stores values internally. If you only encoded one value, it will be stored in the decoded vector's first element.
Since encoding reduces the precision of the original message, the decoded message will not always match exactly the original message, but rather the closest value that the encoder can represent.
Here is an example program that specifies and uses an encoder, for a single message and a message vector:
The github project called is using Concrete to implement exact homomorphic computation with 3-bit integers encrypted in LWE ciphertexts.
Negating a value means taking its opposite. The opposite of a ciphertext representing a message in the interval is a ciphertext representing in the interval . This operation does not consume padding nor add noise but it modifies the interval of the encoder.
RLWE stands for and refers to the extension of LWE over the ring of polynomials with coefficients in a modular integer ring. It is also a computational problem conjectured to be hard to solve. RLWE enable packing multiple ciphertexts into a single polynomial, enabling SIMD-like homomorphic operations.
Sometimes, you might need to do the opposite operation, and convert an LWE secret key into an RLWE secret key. This works almost the same, the only difference being that you have to specify the polynomial size when you use the to_rlwe_secret_key
method: This assumes that the LWE dimension is a multiple of (i.e,, the degree of the polynomial).
using the add
method which adds a constant to a ciphertext and shift the interval of the encoder by that constant, thus going from an interval of to an interval of . Note that with this method, the ciphertext itself is not modified, as we only need to change the encoding to get the correct value. This is a convenience alias of the add_constant_dynamic_encoder
method.
The constraint however is that the ciphertexts need to be encoded in the same interval and with the same number of padding bits. The result of adding and will be encoded in the interval with one less bit of padding.
There are constraints when using this method, namely that the ciphertexts must be encoded in intervals of the same size, meaning and have the same precision. The interval of the output ciphertext will then be .
an interval to work in, with size equal to .
a precision in bits, representing the granularity of the interval. The granularity is the smallest increment between two consecutive values, and is equal to .
an interval representing the range of values your messages can take
Here is an example encoder that can represent messages in with 8 bits of precision and 0 bits of padding:
Using the above encoders, values can be represented, with being the smallest value, being the largest, and a granularity of between consecutive values. The granularity of an encoder can be computed with its get_granularity
method.
For example, let and be the messages encoded into the interval and respectively . Then, the range of values of their addition is updated to .
The last parameter, the number of padding bits is required to ensure the correctness of future computations. In a nutshell, they allow to keep the precision and granularity defined in the encoder while taking in account the potential carries. The processes related to the padding are details in the section.
You can decode a plaintext back into a raw message using the method:
Operation
Type
Leveled
Side effects
Increases noise
Potentially consumes padding
Potentially modifies encoding
Operation |
Type | Noiseless |
Side effects | Modifies encoding |
Operation |
Type | Leveled |
Side effects | Potentially modifies encoding |
Operation |
Type | Leveled |
Side effects | Increases noise Potentially consumes padding Potentially modifies encoding |
The issue with manipulating noisy ciphertexts in FHE is that each leveled operation will increase the noise, eventually overflowing on the significant data bits and rendering the resulting computing imprecise. To avoid this from happening and carry on computing forever, ciphertexts need to be "cleaned up" whenever the noise grows too big, using a special procedure called bootstrapping.
The original intuition behind bootstrapping (as introduced by Gentry) is that by homomorphically evaluating the decryption circuit, we can reset the noise in the ciphertext to a nominal level. This requires a public bootstrapping key , which is an encryption under a key of the secret key used to encrypt the input ciphertext.
The bootstrapping operation thus works by taking as input a noisy ciphertext encrypted under some secret key and a bootstrapping key , producing a refreshed ciphertext (i.e., with a reduced amount of noise), encrypted under the secret key . A key-switch can then be performed to obtain a ciphertext encrypted under the original .
A bootstrapping key is a list of RGSW ciphertexts, which are themselves a collection of RLWE ciphertexts. Each RGSW ciphertext composing the bootstrapping key encrypts a bit of the secret key used to encrypt the input ciphertext. This explains why two keys are needed in the generation of a bootstrapping key: the input LWE secret key and a RLWE secret key to produce the RGSW ciphertexts of the bits composing .
The generation of a bootstrapping key involves three parameters, a basis base_log
, a number of levels level
, and a polynomial size . The choice of these parameters is important as they affect the amount of noise and precision of the output ciphertext, as well as the computational cost of performing a bootstrap. They also determine the size of the bootstrapping key. For example, the parameter relates to the discretization used for the bootstrapping, which in turn impacts the output precision. A larger value for increases the output precision but it also increases the bootstrapping time. Thus, finding a set of parameters offering good performance trade-offs is essential.
For example, for an LWE ciphertext with dimension n = 1024
, setting the bootstrapping parameters to N = 1024
, level=4
and base_log=6
will guarantee 3 bits of precision in the output ciphertext, and 4 bits with a probability of 97%.
As a rule of thumb, it is good to try keeping a small value for level
. Generally, a good choice for parameteris 1024 or any other higher power of two.
Bootstrapping keys can be several hundreds of megabytes large and take several minutes to generate using OpenSSL's secure pseudo-random number generator. During development, Rust's faster, but unsafe prng can be used by specifying the cargo flag "--features=unsafe" (never use this in production!).
Here is an example of how to generate a bootstrapping key:
Bootstrapping a ciphertext is done using the bootstrap
method, which takes the bootstrapping key as input. Although bootstrapping can free up padding, it will first need to consume one bit of padding.
There must be at least one available bit of padding in the input ciphertext to perform a bootstrapping operation on it.
Programmable bootstrapping is a powerful technique that enables simultaneously bootstrapping a ciphertext and homomorphically evaluating a function on it. Without programmable bootstrapping, evaluating complex non-linear functions would require evaluating deep arithmetic or boolean circuits, with as many bootstraps as there is noise accumulation. Here, the same function can be evaluated for the cost of a single bootstrap.
A simple way to think of programmable bootstrapping is as a homomorphic table lookup, where the table represents a discretization of the function that needs to be evaluated on the ciphertext.
In TFHE, and thus Zama, we can bootstrap using polynomials modulo , and get as an intermediary step an encryption of a polynomial whose constant term is the input plaintext. Programming the bootstrapping operation then amounts to simply replacing this constant term by a table representing the discretized function being programmed. This table has to be provided with entries of the form with denotes the encoding function of the input and the encoding function of the output.
Just with plain bootstrapping, choosing the right parameters is paramount to get the right tradeoff between performances and precision.
Just as with plain bootstrapping, programmable bootstrapping requires at least one free bit of padding.
To apply a function on a ciphertext, use the bootstrap_with_function
method that takes as arguments:
a bootstrapping key.
the function to be evaluated, as a lambda Fn(f64) -> f64
, which can be any univariate function as long as it does not have side effects.
an output encoder that represents the range and precision of the resulting ciphertext, after the function has been applied to it.
Here is a code example to evaluate the square function:
Operation
Type
Bootstrapped
Side effects
Reduces noise
Modifies padding
Potentially modifies encryption key
Potentially modifies security parameters
Operation
Type
Bootstrapped
Side effects
Reduces noise
Modifies padding
Potentially modifies encryption key
Potentially modifies security parameters