Encrypted Matrix Inversion

[aquint-zama]

Winners

🥇 1st place: A submission by Lcressot

---

Overview

Matrix inversion is a mathematical operation that is vital for many use-cases: numerical optimization, solving systems of equations, learning regression models, principal-component analysis. In this bounty we would like you to implement an algorithm for inverting encrypted matrices using Concrete-Python.

Description

Many algorithms exist for matrix inversion but they require modification when applied to FHE. For example, you will need to handle convergence criteria which are not directly translatable to FHE circuits but also to introduce quantization in the inversion algorithm.

Implementation guide

We expect the algorithm to produce results with a high level of correctness for matrices that have a realistic dynamic range (i.e. the values in the matrix have similar range and can be quantized to 8-10 bits). Solutions that do not produce sufficient correctness will be rejected. The rankings of the bounty submissions will be based on the speed of the solutions and we recommend that you use tensorized TLUs (applying TLUs on tensors instead of single scalars) as much as possible.

Your should start from this template:

import time
from typing import Tuple

import numpy as np
from concrete import fhe

def invert_matrix(x):
    return x

class EncryptedMatrixInversion:
    shape: Tuple[int, int]
    circuit: fhe.Circuit

    def __init__(self, n, sampler):
        self.shape = (n, n)

        inputset = [sampler() for _ in range(100)]
        for sample in inputset:
            assert isinstance(sample, np.ndarray)
            assert np.issubdtype(sample.dtype, np.floating)
            assert sample.shape == self.shape

        quantized_inputset = [self.quantize(sample) for sample in inputset]
        for quantized_sample in quantized_inputset:
            assert isinstance(quantized_sample, np.ndarray)
            assert np.issubdtype(quantized_sample.dtype, np.integer)
            assert quantized_sample.shape == self.shape

        compiler = fhe.Compiler(invert_matrix, {"x": "encrypted"})
        self.circuit = compiler.compile(quantized_inputset)

    def quantize(self, matrix: np.ndarray) -> np.ndarray:
        return matrix.astype(np.int32)

    def encrypt(self, quantized_matrix: np.ndarray) -> fhe.PublicArguments:
        return self.circuit.encrypt(quantized_matrix)

    def evaluate(self, encrypted_quantized_matrix: fhe.PublicArguments) -> fhe.PublicResult:
        return self.circuit.run(encrypted_quantized_matrix)

    def decrypt(self, encrypted_quantized_inverted_matrix: fhe.PublicResult) -> np.ndarray:
        return self.circuit.decrypt(encrypted_quantized_inverted_matrix)

    def dequantize(self, quantized_inverted_matrix: np.ndarray) -> np.ndarray:
        return quantized_inverted_matrix.astype(np.float32)

    def run(self, matrix: np.ndarray) -> np.ndarray:
        assert np.issubdtype(matrix.dtype, np.floating)
        assert matrix.shape == self.shape

        quantized_matrix = self.quantize(matrix)
        encrypted_quantized_matrix = self.encrypt(quantized_matrix)
        encrypted_quantized_inverted_matrix = self.evaluate(encrypted_quantized_matrix)
        quantized_inverted_matrix = self.decrypt(encrypted_quantized_inverted_matrix)
        inverted_matrix = self.dequantize(quantized_inverted_matrix)

        assert np.issubdtype(inverted_matrix.dtype, np.floating)
        assert inverted_matrix.shape == self.shape

        return inverted_matrix


normal_sampler = ("Normal", lambda: np.random.randn(n, n) * 100)
uniform_sampler = ("Uniform", lambda: np.random.uniform(0, 100, (n, n)))

for name, sampler in {normal_sampler, uniform_sampler}:
    for n in {3, 5, 10}:
        print()

        title = f"Sampler={name}, N={n}"
        print(title)
        print("-" * len(title))

        print(f"Compiling...")
        start = time.time()
        encrypted_matrix_inversion = EncryptedMatrixInversion(n, sampler)
        end = time.time()
        print(f"(took {end - start:.3f} seconds)")

        print()

        print(f"Generating Keys...")
        start = time.time()
        encrypted_matrix_inversion.circuit.keygen()
        end = time.time()
        print(f"(took {end - start:.3f} seconds)")

        print()

        sample_input = sampler()
        expected_output = np.linalg.inv(sample_input)

        print(f"Running...")
        start = time.time()
        actual_output = encrypted_matrix_inversion.run(sample_input)
        end = time.time()
        print(f"(took {end - start:.3f} seconds)")

        print()

        error = np.abs(expected_output - actual_output)

        print(f"Average Error: {np.mean(error):.6f}")
        print(f"    Max Error: {np.max(error):.6f}")
        print(f"    Min Error: {np.min(error):.6f}")
        print(f"  Total Error: {np.sum(error):.6f}")
        
        print()

Your main goal is to minimize errors and make running as performant as possible. Here are a few tips that might be useful:

• You should implement invert_matrix function.
• You are free to change the function signature to include additional information (e.g., quantization parameters)
• If you do that, don't forget to change compilation from fhe.Compiler(invert_matrix, {"x": "encrypted"}) to fhe.Compiler(lambda x: invert_matrix(x, additional, arguments, ...), {"x": "encrypted"})
• You are also free to change any other function signature and implementation (e.g., add more parameters to init such as quantization bit-width target)
• The only part that you can't change is this:

sample_input = sampler()
expected_output = np.linalg.inv(sample_input)

print(f"Running...")
start = time.time()
actual_output = encrypted_matrix_inversion.run(sample_input)
end = time.time()
print(f"(took {end - start:.3f} seconds)")

print()

error = np.abs(expected_output - actual_output)

print(f"Average Error: {np.mean(error):.6f}")
print(f"    Max Error: {np.max(error):.6f}")
print(f"    Min Error: {np.min(error):.6f}")
print(f"  Total Error: {np.sum(error):.6f}")

print()

Reward

• 🥇 1st place: €10,000
• 🥈 2nd place: €3,500
• 🥉 3rd place: €1,500

Rewards are attributed based on speed performance on the Amazon EC2 M6i instances.

Related links and references

• Concrete documentation

Submission

Apply directly to this bounty by opening an application here.

Questions?

Do you have a specific question about this bounty? Join the live conversation on the FHE.org discord server here. You can also send us an email at: bounty@zama.ai

[aquint-zama]

description updated