Operations on encrypted values

The idea of homomorphic encryption is that you can compute on ciphertexts without knowing the messages they encrypt. A scheme is said to be fully homomorphic, if an unlimited number of additions and multiplications are supported ($x$ is a plaintext and $E[x]$ is the corresponding ciphertext):

• homomorphic addition: $E[x] + E[y] = E[x + y]$

• homomorphic multiplication: $E[x] * E[y] = E[x * y]$

Noise and Bootstrap

FHE encrypts data as LWE ciphertexts. These ciphertexts can be visually represented as a bit vector with the encrypted message in the higher-order (yellow) bits as well as a random part (gray), that guarantees the security of the encrypted message, called noise.

Under the hood, each time you perform an operation on an encrypted value, the noise grows and at a certain point, it may overlap with the message and corrupt its value.

There is a way to decrease the noise of a ciphertext with the Bootstrap operation. The bootstrap operation takes as input a noisy ciphertext and generates a new ciphertext encrypting the same message, but with a lower noise. This allows additional operations to be performed on the encrypted message.

A typical FHE program will be made up of a series of operations followed by a Bootstrap, this is then repeated many times.

Probability of Error

The amount of noise in a ciphertext is not as bounded as it may appear in the above illustration. As the errors are drawn randomly from a Gaussian distribution, they can be of varying size. This means that we need to be careful to ensure the noise terms do not effect the message bits. If the error terms do overflow into the message bits, this can cause an incorrect output (failure) when bootstrapping.

Function evaluation

So far, we only introduced arithmetic operations but a typical program usually also involves functions (maximum, minimum, square root…)

During the Bootstrap operation, in TFHE, you could perform a table lookup simultaneously to reduce noise, turning the Bootstrap operation into a Programmable Bootstrap (PBS).

Concrete uses the PBS to support function evaluation:

Let's take a simple example. A function (or circuit) that takes a 4 bits input variable and output the maximum value between a clear constant and the encrypted input:

example:

import numpy as np

def encrypted_max(x: uint4):
    return np.maximum(5, x)

could be turned into a table lookup:

def encrypted_max(x: uint4):
    lut = [5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
    return lut[x]

The Lookup table lut being applied during the Programmable Bootstrap.

PBS management

You should not worry about PBS, they are completely managed by Concrete during the compilation process. Each function evaluation will be turned into a Lookup table and evaluated by a PBS.

See this in action with the previous example, if you dump the MLIR code produced by the frontend, you will see (forget about MLIR syntax, just see the Lookup table value on the 4th line):

module {
  func.func @main(%arg0: !FHE.eint<4>) -> !FHE.eint<4> {
    %cst = arith.constant dense<[5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]> : tensor<16xi64>
    %0 = "FHE.apply_lookup_table"(%arg0, %cst) : (!FHE.eint<4>, tensor<16xi64>) -> !FHE.eint<4>
    return %0 : !FHE.eint<4>
  }
}

The only thing you should keep in mind is that it adds a constraint on the input type, and that is the reason behind having a maximum bit-width supported in Concrete.

Second takeaway is that PBS are the most costly operations in FHE, the less PBS in your circuit the faster it will run. It is an interesting metrics to optimize (you will see that Concrete could give you the number of PBS used in your circuit).

Note also that PBS cost varies with the input variable precision (a circuit with 8 bit PBS will run faster than one with 16 bits PBS).

Development Workflow

Allowing computation on encrypted data is particularly interesting in the client/server model, especially when the client data are sensitive and the server not trusted. You could split the workflow in two main steps: development and deployment.

Development

During development, you will turn your program into its FHE equivalent. Concrete automates this task with the compilation process but you can make this process even easier by reducing the precision required, reducing the number of PBSs or allowing more parallelization in your code (e.g. working on bit chunks instead of high bit-width variables).

Once happy with the code, the development process is over and you will create the compiler artifact that will be used during deployment.

Deployment

A typical Concrete deployment will host on a server the compilation artifact: Client specifications required by the compiled circuits and the fhe executable itself. Client will ask for the circuit requirements, generate keys accordingly, then it will send an encrypted payload and receive an encrypted result.

For more information on deployment, see Howto - Deploy

One of the most common operations in Concrete is Table Lookups (TLUs). TLUs are performed with an FHE operation called Programmable Bootstrapping (PBS). PBS's have a certain probability of error, which, when triggered, result in inaccurate results.

Let's say you have the table:

And you perform a Table Lookup using 4. The result you should get is lut[4] = 16, but because of the possibility of error, you could get any other value in the table.

The probability of this error can be configured through the p_error and global_p_error configuration options. The difference between these two options is that, p_error is for individual TLUs but global_p_error is for the whole circuit.

If you set p_error to 0.01, for example, it means every TLU in the circuit will have a 99% chance of being exact with a 1% probability of error. If you have a single TLU in the circuit, global_p_error would be 1% as well. But if you have 2 TLUs for example, global_p_error would be almost 2% (1 - (0.99 * 0.99)).

However, if you set global_p_error to 0.01, the whole circuit will have 1% probability of error, no matter how many Table Lookups are included.

If you set both of them, both will be satisfied. Essentially, the stricter one will be used.

By default, both p_error and global_p_error is set to None, which results in a global_p_error of 1 / 100_000 being used.

Feel free to play with these configuration options to pick the one best suited for your needs! See to learn how you can set a custom p_error and/or global_p_error.

Supported operations

Here are the operations you can use inside the function you are compiling:

Supported Python operators.

Supported NumPy functions.

Supported ndarray methods.

Supported ndarray properties.

Limitations

Control flow constraints.

Some Python control flow statements are not supported. You cannot have an if statement or a while statement for which the condition depends on an encrypted value. However, such statements are supported with constant values (e.g., for i in range(SOME_CONSTANT), if os.environ.get("SOME_FEATURE") == "ON":).

Type constraints.

You cannot have floating-point inputs or floating-point outputs. You can have floating-point intermediate values as long as they can be converted to an integer Table Lookup (e.g., (60 * np.sin(x)).astype(np.int64)).

Bit width constraints.

There is a limit on the bit width of encrypted values. We are constantly working on increasing this bit width. If you go above the limit, you will get an error.

Concrete is natively supported on Linux and macOS from Python 3.8 to 3.11 inclusive. If you have Docker in your platform, you can use the docker image to use Concrete.

Using PyPI

You can install Concrete from PyPI:

Using Docker

You can also get the Concrete docker image:

📁 | 💛 | 🟨

Concrete is an open source framework which simplifies the use of Fully Homomorphic Encryption (FHE).

FHE is a powerful cryptographic tool, allowing computation to be performed directly on encrypted data without needing to decrypt it. With FHE, you can build services that preserve privacy for all users. FHE also offers ideal protection against data breaches as everything is done on encrypted data. Even if the server is compromised, no sensitive data is leaked.

Organization of this documentation

This documentation is split into several sections:

• Getting Started gives you the basics,

• Tutorials provides essential examples on various features of the library,

• How to helps you perform specific tasks,

• Developer explains the inner workings of the library and everything related to contributing to the project.

Looking for support? Ask our team!

How is Concrete different from Concrete Numpy?

Concrete Numpy was the former name of the Python frontend of the Concrete Compiler. Concrete Compiler is now open source, and the package name is updated from concrete-numpy to concrete-python (as concrete is already booked for a non FHE-related project).

How is it different from the previous version of Concrete?

To compute on encrypted data, you first need to define the function you want to compute, then compile it into a Concrete Circuit, which you can use to perform homomorphic evaluation.

Here is the full example that we will walk through:

Importing the library

Everything you need to perform homomorphic evaluation is included in a single module:

Defining the function to compile

In this example, we compile a simple addition function:

Creating a compiler

To compile the function, you need to create a Compiler by specifying the function to compile and the encryption status of its inputs:

Defining an inputset

An inputset is a collection representing the typical inputs to the function. It is used to determine the bit widths and shapes of the variables within the function.

It should be in iterable, yielding tuples, of the same length as the number of arguments of the function being compiled:

Compiling the function

You can use the compile method of a Compiler class with an inputset to perform the compilation and get the resulting circuit back:

Performing homomorphic evaluation

You can use the encrypt_run_decrypt method of a Circuit class to perform homomorphic evaluation:

If you are trying to compile a regular function, you can use the decorator interface instead of the explicit Compiler interface to simplify your code:

from concrete import fhe

@fhe.compiler({"x": "encrypted"})
def f(x):
    return x + 42

inputset = range(10)
circuit = f.compile(inputset)

assert circuit.encrypt_run_decrypt(10) == f(10)

When you have big circuits, keeping track of which node corresponds to which part of your code becomes difficult. A tagging system can simplify such situations:

def g(z):
    with fhe.tag("def"):
        a = 120 - z
        b = a // 4
    return b


def f(x):
    with fhe.tag("abc"):
        x = x * 2
        with fhe.tag("foo"):
            y = x + 42
        z = np.sqrt(y).astype(np.int64)

    return g(z + 3) * 2

When you compile f with inputset of range(10), you get the following graph:

 %0 = x                            # EncryptedScalar<uint4>        ∈ [0, 9]
 %1 = 2                            # ClearScalar<uint2>            ∈ [2, 2]            @ abc
 %2 = multiply(%0, %1)             # EncryptedScalar<uint5>        ∈ [0, 18]           @ abc
 %3 = 42                           # ClearScalar<uint6>            ∈ [42, 42]          @ abc.foo
 %4 = add(%2, %3)                  # EncryptedScalar<uint6>        ∈ [42, 60]          @ abc.foo
 %5 = subgraph(%4)                 # EncryptedScalar<uint3>        ∈ [6, 7]            @ abc
 %6 = 3                            # ClearScalar<uint2>            ∈ [3, 3]
 %7 = add(%5, %6)                  # EncryptedScalar<uint4>        ∈ [9, 10]
 %8 = 120                          # ClearScalar<uint7>            ∈ [120, 120]        @ def
 %9 = subtract(%8, %7)             # EncryptedScalar<uint7>        ∈ [110, 111]        @ def
%10 = 4                            # ClearScalar<uint3>            ∈ [4, 4]            @ def
%11 = floor_divide(%9, %10)        # EncryptedScalar<uint5>        ∈ [27, 27]          @ def
%12 = 2                            # ClearScalar<uint2>            ∈ [2, 2]
%13 = multiply(%11, %12)           # EncryptedScalar<uint6>        ∈ [54, 54]
return %13

Subgraphs:

    %5 = subgraph(%4):

        %0 = input                         # EncryptedScalar<uint2>          @ abc.foo
        %1 = sqrt(%0)                      # EncryptedScalar<float64>        @ abc
        %2 = astype(%1, dtype=int_)        # EncryptedScalar<uint1>          @ abc
        return %2

If you get an error, you'll see exactly where the error occurred (e.g., which layer of the neural network, if you tag layers).

Big circuits can take a long time to execute, and waiting for execution to finish without having any indication of its progress can be frustrating. For this reason, progressbar feature is introduced:

import time

import matplotlib.pyplot as plt
import numpy as np
import randimage
from concrete import fhe

configuration = fhe.Configuration(
    enable_unsafe_features=True,
    use_insecure_key_cache=True,
    insecure_key_cache_location=".keys",

    # To enable displaying progressbar
    show_progress=True,
    # To enable showing tags in the progressbar (does not work in notebooks)
    progress_tag=True,
    # To give a title to the progressbar
    progress_title="Evaluation:",
)

@fhe.compiler({"image": "encrypted"})
def to_grayscale(image):
    with fhe.tag("scaling.r"):
        r = image[:, :, 0]
        r = (r * 0.30).astype(np.int64)

    with fhe.tag("scaling.g"):
        g = image[:, :, 1]
        g = (g * 0.59).astype(np.int64)

    with fhe.tag("scaling.b"):
        b = image[:, :, 2]
        b = (b * 0.11).astype(np.int64)

    with fhe.tag("combining.rgb"):
        gray = r + g + b
        
    with fhe.tag("creating.result"):
        gray = np.expand_dims(gray, axis=2)
        result = np.concatenate((gray, gray, gray), axis=2)
    
    return result

image_size = (16, 16)
image_data = (randimage.get_random_image(image_size) * 255).round().astype(np.int64)

print()

print(f"Compilation started @ {time.strftime('%H:%M:%S', time.localtime())}")
start = time.time()
inputset = [np.random.randint(0, 256, size=image_data.shape) for _ in range(100)]
circuit = to_grayscale.compile(inputset, configuration)
end = time.time()
print(f"(took {end - start:.3f} seconds)")

print()

print(f"Key generation started @ {time.strftime('%H:%M:%S', time.localtime())}")
start = time.time()
circuit.keygen()
end = time.time()
print(f"(took {end - start:.3f} seconds)")

print()

print(f"Evaluation started @ {time.strftime('%H:%M:%S', time.localtime())}")
start = time.time()
grayscale_image_data = circuit.encrypt_run_decrypt(image_data)
end = time.time()
print(f"(took {end - start:.3f} seconds)")

fig, axs = plt.subplots(1, 2)
axs = axs.flatten()

axs[0].set_title("Original")
axs[0].imshow(image_data)
axs[0].axis("off")

axs[1].set_title("Grayscale")
axs[1].imshow(grayscale_image_data)
axs[1].axis("off")

plt.show()

When you run this code, you will see a progressbar like:

Evaluation:  10% |█████.............................................|  10% (scaling.r)
^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^
Title        Progressbar                                                   Tag

And as the circuit progresses, this progressbar would fill:

Evaluation:  30% |███████████████...................................|  30% (scaling.g)

Evaluation:  50% |█████████████████████████.........................|  50% (scaling.b)

Once the progressbar fills and execution completes, you will see the following figure:

You can convert your compiled circuit into its textual representation by converting it to string:

If you just want to see the output on your terminal, you can directly print it as well:

Terminology

Some terms used throughout the project include:

• computation graph: A data structure to represent a computation. This is basically a directed acyclic graph in which nodes are either inputs, constants, or operations on other nodes.

• tracing: A technique that takes a Python function from the user and generates a corresponding computation graph.

• bounds: Before computation graphs are converted to MLIR, we need to know which value should have which type (e.g., uint3 vs int5). We use inputsets for this purpose. We simulate the graph with the inputs in the inputset to remember the minimum and the maximum value for each node, which is what we call bounds, and use bounds to determine the appropriate type for each node.

• circuit: The result of compilation. A circuit is made of the client and server components. It has methods for everything from printing to evaluation.

Module structure

In this section, we briefly discuss the module structure of Concrete Python. You are encouraged to check individual .py files to learn more.

• concrete

  • fhe

    • dtypes: data type specifications (e.g., int4, uint5, float32)

    • values: value specifications (i.e., data type + shape + encryption status)

    • representation: representation of computation (e.g., computation graphs, nodes)

    • tracing: tracing of python functions

    • extensions: custom functionality (see )

    • mlir: computation graph to mlir conversion

    • compilation: configuration, compiler, artifacts, circuit, client/server, and anything else related to compilation

In this tutorial, we will review how to perform direct table lookups in Concrete.

Direct table lookup

Concrete provides a LookupTable class to create your own tables and apply them in your circuits.

With scalars.

You can create the lookup table using a list of integers and apply it using indexing:

With tensors.

When you apply a table lookup to a tensor, the scalar table lookup is applied to each element of the tensor:

With negative values.

LookupTable mimics array indexing in Python, which means if the lookup variable is negative, the table is looked up from the back:

Direct multi-table lookup

If you want to apply a different lookup table to each element of a tensor, you can have a LookupTable of LookupTables:

In this example, we applied a squared table to the first column and a cubed table to the second column.

Fused table lookup

Concrete tries to fuse some operations into table lookups automatically so that lookup tables don't need to be created manually:

The function is first traced into:

Concrete then fuses appropriate nodes:

Concrete supports native Python and NumPy operations as much as possible, but not everything in Python or NumPy is available. Therefore, we provide some extensions ourselves to improve your experience.

fhe.univariate(function)

Allows you to wrap any univariate function into a single table lookup:

fhe.conv(...)

fhe.maxpool(...)

fhe.array(...)

Allows you to create encrypted arrays:

fhe.zero()

Allows you to create an encrypted scalar zero:

fhe.zeros(shape)

Allows you to create an encrypted tensor of zeros:

fhe.one()

Allows you to create an encrypted scalar one:

fhe.ones(shape)

Allows you to create an encrypted tensor of ones:

During development, the speed of homomorphic execution can be a blocker for fast prototyping. You could call the function you're trying to compile directly, of course, but it won't be exactly the same as FHE execution, which has a certain probability of error (see ).

To overcome this issue, simulation is introduced:

After the simulation runs, it prints the following:

Concrete partly supports floating points. There is no support for floating point inputs or outputs. However, there is support for intermediate values to be floating points (under certain constraints).

Floating points as intermediate values

Concrete-Compile, which is used for compiling the circuit, doesn't support floating points at all. However, it supports table lookups which take an integer and map it to another integer. The constraints of this operation are that there should be a single integer input, and a single integer output.

As long as your floating point operations comply with those constraints, Concrete automatically converts them to a table lookup operation:

In the example above, a, b, and c are floating point intermediates. They are used to calculate d, which is an integer with a value dependent upon x, which is also an integer. Concrete detects this and fuses all of these operations into a single table lookup from x to d.

This approach works for a variety of use cases, but it comes up short for others:

This results in:

The reason for the error is that d no longer depends solely on x; it depends on y as well. Concrete cannot fuse these operations, so it raises an exception instead.

Each integer in the circuit has a certain bit-width, which is determined by the inputset. These bit-widths can be observed when graphs are printed:

However, it's not possible to add 3-bit and 4-bit numbers together because their encoding is different:

The result of such an addition is a 5-bit number, which also has a different encoding:

Because of these encoding differences, we perform a graph processing step called bit-width assignment, which takes the graph and updates the bit-widths to be compatible with FHE.

After this graph processing step, the graph would look like:

Most operations cannot change the encoding, which means that the input and output bit-widths need to be the same. However, there is an operation which can change the encoding: the table lookup operation.

Let's say you have this graph:

This is the graph for (x**2) + y where x is 2-bits and y is 5-bits. If the table lookup operation wasn't able to change the encoding, we'd need to make everything 6-bits. However, since the encoding can be changed, the bit-widths can be assigned like so:

In this case, we kept x as 2-bits, but set the table lookup result and y to be 6-bits, so that the addition can be performed.

This style of bit-width assignment is called multi-precision, and it is enabled by default. To disable it and use a single precision across the circuit, you can use the single_precision=True configuration option.

Table lookups have a strict constraint on the number of bits they support. This can be limiting, especially if you don't need exact precision. As well as this, using larger bit-widths leads to slower table lookups.

To overcome these issues, rounded table lookups are introduced. This operation provides a way to round the least significant bits of a large integer and then apply the table lookup on the resulting (smaller) value.

Imagine you have a 5-bit value, but you want to have a 3-bit table lookup. You can call fhe.round_bit_pattern(input, lsbs_to_remove=2) and use the 3-bit value you receive as input to the table lookup.

Let's see how rounding works in practice:

prints:

and displays:

Now, let's see how rounding can be used in FHE.

prints:

and displays:

Auto Rounders

Rounding is very useful but, in some cases, you don't know how many bits your input contains, so it's not reliable to specify lsbs_to_remove manually. For this reason, the AutoRounder class is introduced.

AutoRounder allows you to set how many of the most significant bits to keep, but they need to be adjusted using an inputset to determine how many of the least significant bits to remove. This can be done manually using fhe.AutoRounder.adjust(function, inputset), or by setting auto_adjust_rounders configuration to True during compilation.

Here is how auto rounders can be used in FHE:

prints:

and displays: