Multiplication matrice-matrice bicyclique dans un cryptage entièrement homomorphe || Mathématiques ∩ Programmation

Dans un article précédent, j’ai abordé la technique de base pour effectuer une multiplication matrice-vecteur dans le cryptage entièrement homomorphique (FHE), connue sous le nom de méthode diagonale Halevi-Shoup. Cet article couvre une méthode plus récente de multiplication matrice-matrice connue sous le nom de méthode bicyclique.

Le code implémentant cette méthode se trouve dans le même référentiel GitHub que l’article précédent, et la méthode bicyclique se trouve dans un fichier appelé bicyclique.py.

L’article précédent lié ci-dessus couvre les concepts généraux derrière « l’emballage FHE », que je considérerai comme connaissances de base pour cet article :

• Le modèle informatique « abstrait » de FHE de style SIMD (CKKS, BGV, BFV) impliquant des textes chiffrés représentés sous forme de vecteurs de fentes de grande largeur, avec des ajouts, des multiplications et des rotations par éléments comme opérations élémentaires.
• Les tâches conjointes consistant à regrouper les données dans des textes chiffrés (semblables à la disposition de la mémoire) et à décider quel circuit d’opérations élémentaires opère sur cet emballage pour implémenter la fonctionnalité équivalente à l’opération en texte clair souhaitée.
• Les paramètres d’efficacité : faible profondeur multiplicative, peu d’opérations de rotation et possibilité de regrouper les rotations sur le même texte chiffré (levage).

La méthode bicyclique

La méthode bicyclique a été introduite dans l’article Homomorphic Matrix Operations under Bicyclic Encoding de Jingwei Chen, Linhan Yang, Wenyuan Wu, Yang Liu et Yong Feng. J’en ai entendu parler pour la première fois via une extension de la technique permettant de prendre en charge la multiplication matrice-matrice par lots dans Tricycle : Private Transformer Inference with Tricyclic Encodings de Lawrence Lim, Vikas Kalagi, Divyakant Agrawal et Amr El Abbadi.

La technique implique également un emballage en diagonale similaire à la méthode Halevi-Shoup et, par conséquent, elle bénéficie de bon nombre des mêmes avantages :

• Une profondeur multiplicative minimale de 1.
• Invariant en termes de mise en page, ce qui signifie que la sortie est compressée selon le même algorithme que l’entrée (différences modulo dans les dimensions de la matrice).
• Un certain nombre de rotations qui évoluent linéairement avec la dimension de la matrice, bien que des astuces de niveau inférieur (Baby-Step-Giant-Step, pour un autre article) réduisent cela à une croissance de racine carrée.

Le packaging d’une matrice est défini comme suit :

Définition: Étant donné une matrice $m \times n$ $A = (a_{i, j})$ et un texte chiffré avec $N$ slots, le emballage bicyclique de $A$ est le vecteur longueur-$N$ $\varphi(A)$ défini par

$$ \varphi(A)_k = a_{k \textup{ mod } m, k \textup{ mod } n} $$

Cet emballage peut être utilisé pour n’importe quelle valeur de $m, n$, mais le noyau de multiplication matricielle n’est valable que si, pour deux matrices $A$ de taille $m \times n$ et $B$ de taille $n \times p$, les tailles d’axe $m, n, p$ sont toutes premières entre elles.

Exemple: Le codage bicyclique avec $N=15$ slots pour la matrice

$$ \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\\ 6 & 7 & 8 & 9 & 10 \\\ 11 & 12 & 13 & 14 & 15 \end{pmatrix} $$

est

$$ (1, 7, 13, 4, 10, 11, 2, 8, 14, 5, 6, 12, 3, 9, 15) $$

Rappelons que la condition de divisibilité du noyau Halevi-Shoup garantissait que, lorsque les diagonales s’enroulaient autour des bords de la matrice, elles ne chevaucheraient pas les autres diagonales. En revanche, la condition de coprimalité bicyclique garantit qu’une longue diagonale d’enroulement traverse chaque entrée de la matrice.

Le code d’emballage ici est simple :

def pack(matrix: list(list(int)), num_slots: int) -> Ciphertext:
    rows, cols = len(matrix), len(matrix(0))
    if gcd(rows, cols) != 1:
        raise ValueError(...)

    data = (matrix(k % rows)(k % cols) for k in range(rows * cols))
    while len(data) < num_slots:
        # duplicate the data until it fills the slots
        data += data
    # truncate to the exact slot size
    return Ciphertext(data(:num_slots))

La réplication à la fin est en fait importante. Deux matrices multiplicandes $A$ de forme $m \times n$ et $B$ de forme $n \times p$ auront en général des tailles différentes, et les rotations utilisées dans le noyau s’étendront au-delà de $mn$ et $np$.

Le déballage utilise naturellement le théorème chinois des restes pour passer de l’entrée matricielle souhaitée à l’index d’emplacement correspondant.

def unpack(encoded: Ciphertext, m: int, n: int) -> list(list(int)):
    if gcd(m, n) != 1:
        raise ValueError(...)

    matrix = ((0) * n for _ in range(m))

    n_inv_mod_m = pow(n, -1, m)  # n^{-1} mod m
    m_inv_mod_n = pow(m, -1, n)  # m^{-1} mod n
    for i in range(m):
        for j in range(n):
            k = (i * n * n_inv_mod_m + j * m * m_inv_mod_n) % (m * n)
            matrix(i)(j) = encoded.data(k)

    return matrix

En particulier (cette formule sera utile à l’étape suivante), pour une matrice $A$ de taille $m \times n$, la valeur en $a_{i, j}$ est dans l’emplacement

$$ a_{i, j} \mapsto \varphi(A)_{in (n^{-1} \textup{ mod } m) + jm (m^{-1} \textup{ mod } n) \textup{ mod } (mn)} $$

Maintenant, étant donné deux matrices $A$ et $B$ compressées à l’aide de la méthode bicyclique, dérivons le noyau de multiplication matricielle. Soit $A$ une taille $m \times n$ et $B$ une taille $n \times p$. Le produit matriciel $C = AB$ a une taille $m \times p$ avec des entrées

$$ c_{i, j} = \sum_{k=0}^{n-1} a_{i, k} b_{k, j} $$

Notre structure générale du noyau sera la suivante :

• Dans une boucle de taille $n$ :
  • Faites pivoter les matrices $\varphi(A)$ et $\varphi(B)$ codées de certains montants (éventuellement différents pour $A$ et $B$)
  • Multipliez les textes chiffrés pivotés par éléments.
• Résumez tous les textes chiffrés résultants.

Cette structure est raisonnablement nécessaire, au moins dans le sens où chaque entrée de la matrice de sortie $c_{i, j}$ a $n$ somme, mais chaque produit par élément ne calcule qu’une seule somme par emplacement. Ainsi, sans répéter les entrées de la matrice plus de $O(1)$ fois, nous aurons besoin de multiplications $\Theta(n)$ de texte chiffré et de rotations $\Theta(n)$ pour collecter tous les termes. La question est de savoir si nous pouvons le faire sans aucun gaspillage.

En effet, nous pouvons, et pour dériver les rotations requises, nous remarquons que, lors du calcul d’une multiplication matricielle, l’indice de contraction interne (le $k$ dans $a_{i, k} b_{k, j}$) se déplace vers la droite sur une rangée de $A$ tout en descendant le long d’une colonne de $B$.

Ainsi, les rotations dont nous avons besoin pour $A$ et $B$ devraient correspondre à la différence entre les positions des emplacements lorsque l’on passe de $(i, k)$ à $(i, k+1)$ pour $A$ et de $(k, j)$ à $(k+1, j)$ pour $B$.

def matrix_multiply(
    packed_matrix_a: Ciphertext,
    packed_matrix_b: Ciphertext,
    m: int,
    n: int,
    p: int,
) -> Ciphertext:
    assert pairwise_coprime(m, n, p), "Dimensions must be pairwise coprime."
    assert len(packed_matrix_a) == len(
        packed_matrix_b
    ), "Both ciphertexts must have the same number of slots"

    result = Ciphertext((0) * len(packed_matrix_a))

    m_inv_mod_n = pow(m, -1, n)
    p_inv_mod_n = pow(p, -1, n)
    for k in range(n):
        a_rot = k * m * m_inv_mod_n % (m * n)
        b_rot = k * p * p_inv_mod_n % (n * p)
        rotated_a = packed_matrix_a.rotate(a_rot)
        rotated_b = packed_matrix_b.rotate(b_rot)
        prod = rotated_a * rotated_b

        # One should accumulate these in a tree-like fashion for optimal
        # noise growth, but this is just a blog post.
        result += prod

    return result