Advanced Examples

This page is dedicated to more complex FHE use-cases. It introduces a few key concepts, such as data rotation or data extraction. You can run all the codes in Google Colab.

A. Sum All Elements

As explained before, it is possible to encrypt a vector in a ciphertext, for instance data = [1, 2, 3, 4, 5, 6, 7, 8]. In this advanced example, we want to sum all those eight elements together. This use-case requires to rotate data and compute an homomorphic addition in order to build the desired result at the 8-th element of the output encrypted vector.

from desilofhe import Engine

engine = Engine()

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
rotation_key = engine.create_rotation_key(secret_key)

data = [1, 2, 3, 4, 5, 6, 7, 8]
encrypted = engine.encrypt(data, public_key)

rotated_data = encrypted
added = rotated_data
for i in range(7):
    rotated_data = engine.rotate(rotated_data, rotation_key, delta=1)
    added = engine.add(added, rotated_data)

decrypted = engine.decrypt(added, secret_key)

# read the result in the 8-th coefficient
print(decrypted[7])  # ~36

Optimized Strategy

Here we propose an optimized version of the previous example. Indeed, in the previous example we performed 7 homomorphic rotations of 1 position to the right, and 7 homomorphic additions in order to get the desired result (i.e. adding the first 8 encrypted elements together). However, the same operation can be performed in a more efficient way, by simply performing 3 rotations (of 1, 2, and 4 positions to the right) and 3 additions.

from desilofhe import Engine

engine = Engine()

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
rotation_key = engine.create_rotation_key(secret_key)

data = [1, 2, 3, 4, 5, 6, 7, 8]
encrypted = engine.encrypt(data, public_key)

added = encrypted

# rotate by 1 and add
rotated_data = engine.rotate(added, rotation_key, 1)
added = engine.add(added, rotated_data)

# rotate by 2 and add
rotated_data = engine.rotate(added, rotation_key, 2)
added = engine.add(added, rotated_data)

# rotate by 4 and add
rotated_data = engine.rotate(added, rotation_key, 4)
added = engine.add(added, rotated_data)

decrypted = engine.decrypt(added, secret_key)

# read the result in the 8-th coefficient
print(decrypted[7])  # ~36

B. Data Extraction and Reorganization

A ciphertext encrypts a vector of numbers, and thanks to the SIMD feature of the scheme, it is pretty easy to add vectors together or to compute coefficient-wise multiplications between two encrypted vectors.

The previous example described a non-SIMD use-case where one adds all the elements of the encrypted vector in the first coefficient of the output ciphertext. The other coefficients around are filled with partial sums of the original vector's elements which are values we do not want to keep.

Let's see how to extract some pieces of data from ciphertexts and recombine them into a new clean vector only filled with needed values and zeros everywhere else.

In particular, in this example we extract pieces of information form 4 encrypted vectors and re-organize them to obtain the vector [1, 2, 3, 4, 5, 6, 7, 8] as result. This is be done by performing multiplications between the encrypted vector and a cleartext mask allowing to extract the right element, followed by an homomorphic rotation to bring the extracted element in the right position. A final homomorphic addition allows to merge all the information into a single ciphertext.

from desilofhe import Engine

engine = Engine()

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
rotation_key = engine.create_rotation_key(secret_key)

# values to extract is marked by its index
# index         0         1
data1 = [12, 7, 1, 15, 9, 2, 11, 10]
# index  2  3
data2 = [3, 4, 20, 11, 17, 6, 9, 16]
# index         5     4
data3 = [9, 18, 6, 9, 5, 11, 13, 8]
# index                  6          7
data4 = [20, 19, 18, 17, 7, 14, 15, 8]

encrypted1 = engine.encrypt(data1, public_key)
encrypted2 = engine.encrypt(data2, public_key)
encrypted3 = engine.encrypt(data3, public_key)
encrypted4 = engine.encrypt(data4, public_key)

# Extract the 3rd element in data1
mask = [0, 0, 1, 0, 0, 0, 0, 0]
multiplied = engine.multiply(encrypted1, mask)
# Rotate to bring it in 1st position
rotated1 = engine.rotate(multiplied, rotation_key, -2)

# Extract the 6th element in data1
mask = [0, 0, 0, 0, 0, 1, 0, 0]
multiplied = engine.multiply(encrypted1, mask)
# Rotate to bring it in 2nd position
rotated2 = engine.rotate(multiplied, rotation_key, -4)

# Extract the 1st and 2nd elements in data2
mask = [1, 1, 0, 0, 0, 0, 0, 0]
multiplied = engine.multiply(encrypted2, mask)
# Rotate to bring them in 3rd and 4th position
rotated34 = engine.rotate(multiplied, rotation_key, 2)

# Extract the 3rd element in data3
mask = [0, 0, 1, 0, 0, 0, 0, 0]
multiplied = engine.multiply(encrypted3, mask)
# Rotate to bring it in 6th position
rotated6 = engine.rotate(multiplied, rotation_key, 3)

# Extract the 5rd element in data3
# (it is already in the right position so no rotation is needed)
mask = [0, 0, 0, 0, 1, 0, 0, 0]
rotated5 = engine.multiply(encrypted3, mask)

# Extract the 5th element in data4
mask = [0, 0, 0, 0, 1, 0, 0, 0]
multiplied = engine.multiply(encrypted4, mask)
# Rotate to bring it in 7th position
rotated7 = engine.rotate(multiplied, rotation_key, 2)

# Extract the 8th element in data4
# (it is already in the right position so no rotation is needed)
mask = [0, 0, 0, 0, 0, 0, 0, 1]
rotated8 = engine.multiply(encrypted4, mask)

# Add together all the rotated elements to obtain the expected result
added = engine.add(rotated1, rotated2)
added = engine.add(added, rotated34)
added = engine.add(added, rotated5)
added = engine.add(added, rotated6)
added = engine.add(added, rotated7)
added = engine.add(added, rotated8)

# decrypt and print the result
decrypted = engine.decrypt(added, secret_key)
print(decrypted[:8])  # [~1 ~2 ~3 ~4 ~5 ~6 ~7 ~8]

C. Polynomial Evaluation

In this example we want to evaluate in an SIMD fashion the following polynomial: x^3 - x^2 + sqrt(2)*x + 1. The input values for x will be stored in a ciphertext encrypting [1, 2, 3, 4, 5, 6, 7, 8]. It is very easy to evaluate any polynomial with the DESILO FHE library. We can use the function evaluate_polynomial to evaluate the polynomial.

from desilofhe import Engine
import math

engine = Engine()

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)

data = [1, 2, 3, 4, 5, 6, 7, 8]
encrypted = engine.encrypt(data, public_key)

# Polynomial evaluation p(x) = x^3 - x^2 + sqrt(2)*x + 1
coefficients = [1, math.sqrt(2), -1, 1]
polynomial = engine.evaluate_polynomial(encrypted, coefficients, relinearization_key)

decrypted = engine.decrypt(polynomial, secret_key)
print(decrypted[:8])
# [~2.4142 ~7.8284 ~23.2426 ~54.6569 ~108.0711 ~189.4853 ~304.8995 ~460.3137]

Otherwise we can evaluate the polynomial manually using homomorphic addition, subtraction and multiplication.

from desilofhe import Engine
import math

engine = Engine()

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)

data = [1, 2, 3, 4, 5, 6, 7, 8]
encrypted = engine.encrypt(data, public_key)

# Polynomial evaluation p(x) = x^3 - x^2 + sqrt(2)*x + 1
coeff0 = 1
sqrt2 = math.sqrt(2)
# compute x^2
x2 = engine.square(encrypted, relinearization_key)
# compute x^3
x3 = engine.multiply(encrypted, x2, relinearization_key)
# compute sqrt(2)*x
x1 = engine.multiply(encrypted, sqrt2)
# compute the polynomial
polynomial = engine.subtract(x3, x2)
polynomial = engine.add(polynomial, x1)
polynomial = engine.add(polynomial, coeff0)

# decrypt and print the result
decrypted = engine.decrypt(polynomial, secret_key)
print(decrypted[:8])
# [~2.4142 ~7.8284 ~23.2426 ~54.6569 ~108.0711 ~189.4853 ~304.8995 ~460.3137]

D. Sign Function Approximation

In this example we want to homomorphically compute a polynomial approximation of the sign function in the interval [-1,1]. The polynomial approximation consumes a total of 8 multiplicative levels as described in the following piece of code. In this case, we want is to return -1 when the input is negative, 1 when the input is positive, and 0 when the input is 0. The following strategy comes from this paper. Note that the difference between the actual value and its approximation is smaller than 0.008, and can be reduced at the price of a heavier homomorphic polynomial approximation.

Indeed here we want to compute Q(P(X)) with Q(X)'s coefficients given in p72 and P(X)'s coefficients given in p71.

def sign(x, relinearization_key):
    # Polynomial approximation p(x) = p_{7,2}(p_{7,1}(x))
    p71 = [
        3.60471572275560 * 10**-36,
        7.30445164958251,
        -5.05471704202722 * 10**-35,
        -3.46825871108659 * 10,
        1.16564665409095 * 10**-34,
        5.98596518298826 * 10,
        -6.54298492839531 * 10**-35,
        -3.18755225906466 * 10,
    ]
    p72 = [
        -9.46491402344260 * 10**-49,
        2.40085652217597,
        6.41744632725342 * 10**-48,
        -2.63125454261783,
        -7.25338564676814 * 10**-48,
        1.54912674773593,
        2.06916466421812 * 10**-48,
        -3.31172956504304 * 10**-1,
    ]

    # compute y = p_{7,1}(x)
    y = engine.evaluate_polynomial(x, p71, relinearization_key)

    # compute p_{7,2}(p_{7,1}(x))
    return engine.evaluate_polynomial(y, p72, relinearization_key)

E. Homomorphic Artificial Neuron

In this example we want to compute an artificial neuron in an SIMD fashion. The neuron we consider takes as input 4 real numbers, and computes an inner-product with a weight vector (size 4 as well) plus a bias. The last operation is the computation of the ReLU function on the result of the inner-product. The ReLU function takes as input a real number x and outputs x if it is positive, and zero otherwise. This function will be computed homomorphically through a polynomial approximation as described above.

Inner Product and Bias

Let's start with the homomorphic inner-product and the addition of the bias.

def inner_product_bias(encrypted_data, weight, bias):
    inner_product = bias
    for encrypted_data, weight in zip(encrypted, weights):
        product = engine.multiply(encrypted_data, weight)
        inner_product = engine.add(inner_product, product)
    return inner_product

ReLU

Now we can write a function computing a polynomial approximation of ReLU in the interval [-1,1]. The idea of the polynomial approximation of the function ReLU is to evaluate a polynomial approximation of the sign function, and then build ReLU by computing ReLU(x) = 0.5 * (x + x*sign(x)). In Example D we already defined an homomorphic sign function, so let's use it for ReLU (as mentioned before, this strategy comes from this paper).

def relu(x, relinearization_key):
    # Polynomial approximation p(x) = 0.5 * (x + x * sign(x))

    # Compute sign(x)
    sign_evaluation = sign(x, relinearization_key)

    # compute x * sign(x)
    multiplied = engine.multiply(sign_evaluation, x, relinearization_key)

    # compute x + x * sign(x)
    added = engine.add(multiplied, x)

    # finally compute 0.5 * (x + x * sign(x))
    result = engine.multiply(added, 0.5)
    return result

Artificial Neuron

Now we can write the final piece of code which will call the two functions we wrote in the previous steps. Let's use an engine with more multiplicative levels and a parallel CPU implementation to make the homomorphic computation faster.

from desilofhe import Engine
import math

# engine with more multiplicative levels and a parallel CPU implementation
engine = Engine(max_level=17, mode="parallel")

secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
rotation_key = engine.create_rotation_key(secret_key)

# data stores enough data to evaluate 8 times our neuron in the SIMD fashion (i.e. at once)
# the first input is the first column [0.1, 0.9, 1.5, 0.8], the second is [0.2, 1.0, 0.3, 1.0] and so on.
data = [
    [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8],
    [0.9, 1.0, 1.1, 1.2, 1.3, 1.4, 0.7, 1.6],
    [1.5, 0.3, 0.0, 0.7, 1.1, 1.3, 0.2, 0.8],
    [0.8, 1.0, 1.6, 1.2, 0.3, 0.7, 0.1, 1.1],
]

# encrypt
encrypted = [engine.encrypt(d, public_key) for d in data]

# inner-product between the input data and the weights plus the bias
weights = [-0.4, -1.2, 0.6, 1.0]
bias = 0.34
inner_product = inner_product_bias(encrypted, weights, bias)
# [~0.92 ~0.24 ~0.5 ~0.36 ~-0.46 ~-0.1 ~-0.56 ~-0.32]

# ReLU homomorphic evaluation
neuron_output = relu(inner_product, relinearization_key)

# decrypt and print the result
decrypted = engine.decrypt(neuron_output, secret_key)
print(decrypted[:8])  # [~0.92 ~0.24 ~0.5 ~0.36 ~0.0 ~0.0 ~0.0 ~0.0]

F. Argmax Evaluation

In this example we want to homomorphically compute an argmax function over a table of values. For example if the input is [0.1, 0.6, 0.2, 0.3] we want the output to be [0.0, 1.0, 0.0, 0.0]. We will start by defining a function to compute the maximum between two encrypted values inside the same ciphertext.

The strategy in this section comes from this paper.

Max Function Between two Values

Here we want to write a function computing an homomorphic SIMD max between two encrypted list of values, i.e. between two ciphertexts. In Example D we wrote an SIMD function computing the homomorphic sign function, and we will use it to build an SIMD max function now. Indeed, the max function between two values a and b can be computed as 0.5 * (a + b + (a - b) * sign(a - b)). The max function consumes 10 multiplicative levels, which means that we need to have an input ciphertext at least at level 10 for this implementation.

def max(a, b, relinearization_key):
    # max(a, b) = 0.5 * (a + b + (a - b) * sign(a - b))

    # compute a - b
    subtracted = engine.subtract(a, b)

    # compute sign(a - b)
    subtracted_sign = sign(subtracted, relinearization_key)

    # compute (a - b) * sign(a - b)
    multiplied = engine.multiply(
        subtracted, subtracted_sign, relinearization_key
    )

    # compute a + b + (a - b) * sign(a - b)
    added = engine.add(multiplied, engine.add(a, b))

    # compute 0.5 * (a + b + (a - b) * sign(a - b))
    result = engine.multiply(added, 0.5)

    return result

Max Function for a Table of Values

The goal is to compute the max value of a table and fill the entire table with this value before outputting it. For example, if we have [0.1, 0.2, 0.3, 0.4] we want to output [0.4, 0.4, 0.4, 0.4].

Our strategy is to compute at once those four 0.4 consecutive values. In order to do so we start by doubling the size of the table and fill it with 2 copies of the original data. For example [0.1, 0.2, 0.3, 0.4] becomes [0.1, 0.2, 0.3, 0.4, 0.1, 0.2, 0.3, 0.4]. Then we will divide and conquer in log2(size) iterations of rotating the current ciphertext and computing an SIMD max between the current ciphertext and the rotated version of it.

Observe that if the level of ciphertext before max is smaller than 10, we need to perform a bootstrapping. Indeed, max needs 10 levels to be computed, and a bootstrap brings back 10 multiplicative levels. It is possible to see the level of ciphertext ct with ct.level. Observe that we could have call the bootstrap function inside the max function when needed.

In the paper the authors use a left rotation but for efficiency reasons we will use right rotations in the for-loop and compute only one final left rotation in the end. We also reset to zero all the values that we do not need anymore by multiplying with the mask.

def quick_max(
    a, n, rotation_key, relinearization_key, conjugation_key, bootstrap_key
):  # n power of 2, with 2n < N
    log2n = int(math.log2(n))

    right_rotated = engine.rotate(a, rotation_key, n)
    added = engine.add(a, right_rotated)

    mask = [1] * n

    for i in range(log2n):
        left_rotated = engine.rotate(added, rotation_key, -(2**i))
        temp = max(added, left_rotated, relinearization_key)

        # bootstrap
        temp = engine.bootstrap(
            temp, relinearization_key, conjugation_key, bootstrap_key
        )
        added = temp

    # multiply times the mask to keep only n elements
    multiplied = engine.multiply(added, mask)
    return multiplied

Argmax Function for a Table of Values

The idea of the argmax computation is to subtract the original data with the result of the quick_max and finally figure out where the zero(s) are with a sign evaluation. For example [0.1, 0.2, 0.3, 0.4] becomes [0.4, 0.4, 0.4, 0.4], and the difference between the two is [-0.3, -0.2, -0.1, 0.0]. If we apply the sign function we end up with [-1.0, -1.0, -1.0, 0.0], which we can easily convert to the desired result [0.0, 0.0, 0.0, 1.0] by simply adding 1.

def argmax(
    a, n, rotation_key, relinearization_key, conjugation_key, bootstrap_key
):  # n power of 2, with 2n < N
    # compute the quick_max
    a_max = quick_max(
        a, n, rotation_key, relinearization_key, conjugation_key, bootstrap_key
    )

    # compute differences between the elements in a and the a_max (containing the max value)
    diff_values = engine.subtract(a, a_max)

    # then compute their sign (0 if 0, 1 if positive, -1 if negative)
    # in our case we only have 0 and -1 values
    sign_values = sign(diff_values, relinearization_key)

    # finally convert -1 into 0, and convert 0 into 1, by computing (sign + 1)
    # use a mask so the trash values after the n-th coefficient remain equal to 0
    mask = [1] * n
    output = engine.add(sign_values, mask)

    return output

Let's Run our Code

We can now try our argmax function on encrypted data!

from desilofhe import Engine
import math

engine = Engine(use_bootstrap=True)
secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
rotation_key = engine.create_rotation_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
conjugation_key = engine.create_conjugation_key(secret_key)
bootstrap_key = engine.create_bootstrap_key(secret_key, stage_count=3)

# data
data = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8]
n = len(data)

# encrypt
encrypted = engine.encrypt(data, public_key)

# compute argmax
encrypted_argmax = argmax(
    encrypted,
    n,
    rotation_key,
    relinearization_key,
    conjugation_key,
    bootstrap_key,
)

# decrypt and print the result
decrypted = engine.decrypt(encrypted_argmax, secret_key)
print(decrypted[:16])  # [~0 ~0 ~0 ~0 ~0 ~0 ~0 ~1 ~0 ...]