Matrix Multiplication

Since a ciphertext encodes a vector, matrix–vector multiplication can be performed with basic homomorphic encryption operations by multiplying the ciphertext with each row of a matrix, and then by adding all the products. However, this naive method consumes a tremendous amount of time and memory, so the DESILO FHE library provides an optimized way to perform matrix multiplication. This document explains how to utilize the provided operations to perform matrix multiplication more efficiently.

Setting the engine slot count

To use optimized matrix multiplication, the input matrix must be square. For efficient computation in the encrypted state, the engine requires the input matrix to be a slot_count by slot_count matrix. The computational time and memory usage grows quadratically (or worse) with the slot count. Therefore it is important to configure the engine's slot_count according to the matrix size.

from desilofhe import Engine

engine = Engine(slot_count=64)  # Supports matrices of size 64x64

Matrix Multiplication Methods

There are two methods for performing the same matrix multiplication: one that uses a rotation key, and another that utilizes both a matrix multiplication key and a plain matrix. The multiplication with a rotation key is more memory-efficient but slower, while the multiplication with both a matrix multiplication key and a plain matrix is faster but consumes more memory.

Rotation Key

A matrix multiplication can be performed on various input types with just a rotation key. Below are examples for lists, NumPy arrays, and PyTorch tensors.

import torch
import numpy as np

from desilofhe import Engine

engine = Engine(slot_count=64)
secret_key = engine.create_secret_key()
rotation_key = engine.create_rotation_key(secret_key)

matrix = [[i * 64 + j for j in range(64)] for i in range(64)]
numpy_matrix = np.arange(64 * 64).reshape(64, 64)
tensor_matrix = torch.arange(64 * 64).reshape(64, 64)

message = [2] * 64
ciphertext = engine.encrypt(message, secret_key)

multiplied1 = engine.multiply_matrix(matrix, ciphertext, rotation_key)
multiplied2 = engine.multiply_matrix(numpy_matrix, ciphertext, rotation_key)
multiplied3 = engine.multiply_pytorch_tensor_matrix(
    tensor_matrix, ciphertext, rotation_key
)

Note that when using a PyTorch tensor, the API name is slightly different. For clarity, the library appends the suffix pytorch_tensor to all PyTorch tensor-related APIs.

Matrix Multiplication Key & Plain Matrix

Although basic matrix multiplication is convenient, it involves many rotation operations internally, making it slow. To improve efficiency, the DESILO FHE library provides two additional data structures: MatrixMultiplicationKey and PlainMatrix. Note that while this method improves computation speed, it consumes much more memory because additional data structures are created preemptively.

Matrix Multiplication Key

A matrix multiplication key is a precomputed set of fixed rotation keys optimized for a specific matrix size. Using it allows matrix multiplication with far fewer rotation operations than the basic method.

from desilofhe import Engine

engine = Engine(slot_count=64)
secret_key = engine.create_secret_key()
matrix_multiplication_key = engine.create_matrix_multiplication_key(secret_key)

Plain Matrix

A plain matrix is a set of plaintexts optimally prepared for matrix multiplication. It enables faster matrix multiplication than simply encoding a matrix in Plaintext.

import numpy as np

from desilofhe import Engine

engine = Engine(slot_count=64)

message = np.arange(64 * 64).reshape(64, 64)
plain_matrix = engine.encode_to_plain_matrix(message)

Matrix multiplication that uses both structures looks like the following:

import numpy as np

from desilofhe import Engine

engine = Engine(slot_count=64)
secret_key = engine.create_secret_key()
matrix_multiplication_key = engine.create_matrix_multiplication_key(secret_key)

matrix = np.arange(64 * 64).reshape(64, 64)
plain_matrix = engine.encode_to_plain_matrix(matrix)

message = [2] * 64
ciphertext = engine.encrypt(message, secret_key)

multiplied = engine.multiply_matrix(
    plain_matrix, ciphertext, matrix_multiplication_key
)

Plain Matrix with given diagonal indices

In this library, matrices divided into diagonals and each diagonal is separately encoded. A diagonal is defined as a set of elements that share the same circular row offset pattern. For example, in a 4x4 matrix, the diagonal index for each element is as follows:

[[0, 3, 2, 1],
 [1, 0, 3, 2],
 [2, 1, 0, 3],
 [3, 2, 1, 0]]

When a diagonal consists entirely of zeros, the multiplication result for that diagonal is also zero. Encoding such zero-filled diagonals is unnecessary. If you know which diagonals in your matrix are non-zero, you can specify the diagonals to encode use the diagonal_indices parameter. This can reduce memory usage.

Consider a 4x4 sparse matrix where only diagonals 2 and 3 contain non-zero values.

An original matrix would be:

[[0, 1, 2, 0],
 [0, 0, 3, 4],
 [5, 0, 0, 6],
 [7, 8, 0, 0]]

Extracting each diagonal from the original matrix gives: - Diagonal 0: [0, 0, 0, 0] - Diagonal 1: [0, 0, 0, 0] - Diagonal 2: [5, 8, 2, 4] - Diagonal 3: [7, 1, 3, 6]

Since diagonals 0 and 1 contain only zeros, we can encode only diagonals 2 and 3. This reduces the memory size to half.

import numpy as np

from desilofhe import Engine

example_matrix = np.array(
    [[0, 1, 2, 0], [0, 0, 3, 4], [5, 0, 0, 6], [7, 8, 0, 0]]
)

engine = Engine(slot_count=4)
secret_key = engine.create_secret_key()
matrix_multiplication_key = engine.create_matrix_multiplication_key(secret_key)

diagonal_indices = [2, 3]
plain_matrix = engine.encode_to_plain_matrix(
    example_matrix, engine.max_level - 1, diagonal_indices
)

message = [1, 2, 3, 4]
ciphertext = engine.encrypt(message, secret_key)

multiplied = engine.multiply_matrix(
    plain_matrix, ciphertext, matrix_multiplication_key
)