基于同态加密实现的矩阵乘法算法及卷积运算

前言

我是研究隐私计算方向的， 主要学习的领域是应用全同态加密对已有机器学习模型进行重写，即设计基于全同态加密的机器学习算法。在阅读论文的过程中，发现许多大佬应用SIMD型全同态加密技术实现了一系列的密态卷积运算、密态矩阵向量乘法运算和密态矩阵乘法运算），然后也算是随着这些算法的提出而逐渐成长起来的，所以这里对这些算法进行一些总结。

本文不介绍这些算法的性能，且需要实现掌握CKKS同态加密算法。

长期更新中。。。。。。

1. 符号说明

2. Introduction

隐私保护计算可以在保护数据隐私的同时充分利用数据的价值，是一种格外流行的领域。在众多同态加密支持的隐私保护应用中，矩阵操作和卷积操作成为了核心。

3. 矩阵向量乘法与矩阵乘法

设计密态矩阵（向量）乘法算法的核心即尽量减少同态旋转（自同构）的数量，尽量减少乘法深度的消耗。

3.1 双循环编码下的FHE矩阵乘法算法

本算法来自论文：《Homomorphic Matrix Operations under Bicyclic Encoding》

该论文发表位置: IEEE Transactions on Information Forensics and Security （CCF-A类）

Abstract

同态加密矩阵操作已经被广泛用于各种隐私保护应用。在这种背景下，本文提出了一种新颖的矩阵编码算法，称其为"双循环编码"。基于该编码算法，本文提出两种密态矩阵运算算法，分别称为"BMM-I"和"BMM-II"。且双循环编码的另一个优势即，密态矩阵转置操作完全免费。

1. 双循环编码

(1) 双循环编码

给定矩阵$A=(a_{i,j})\in R^{n\times m}$。定义映射${\phi }_R:R^{n\times m}\to R^r$为${\phi }_{n,m,r}(A)=(a_{[0{]}_n},[0{]}_m,a_{[1{]}_n},[1{]}_m,...,a_{[r{]}_n},[r{]}_m)$，其中$r\le n\cdot m$。特别地，当$gcd(n,m)=1$时，取$r=1$，则称${\phi }_{r=nm}$为双循环映射，此时${\phi }_{n,m,nm}(A)\in R^{n\cdot m}$会讲矩阵$A$​​中的每一个元素遍历到。

双循环映射证明，这里可以通过中国剩余定理（CRT）来证明：若$gcd(n,m)=1$，则有$\mathbb{Z}/(nm\mathbb{Z})$与$\mathbb{Z}/(n\mathbb{Z})\otimes \mathbb{Z}/(mZ)$同构。

我们称${\phi }_{n,m,n\cdot m}(A)$为矩阵$A$的双循环映射，表示为$d(A)$​。

(2) 双循环解码

给定一个向量$x\in R^l$，我们想要将其解码为一个$n\times m$大小的矩阵$gcd(n,m)=1$，其中$l\ge n\cdot m$。定义映射${\psi }_{l,n,m}:R^l\to R^{n\times m}$，该映射可将向量$x\in R^l$映射为一个矩阵$X=(X_{i,j})$，其中$X_{i,j}=x_k,k=[i\cdot t\cdot m+j\cdot s\cdot n{]}_{n\cdot m}$，$(s,t)$是$(n,m)$的Bezout系数，即满足$s\cdot n+t\cdot m=1$。特别地，矩阵$A\in R^{n\times m}$的双循环编码$d(A)$的解码映射${\psi }_{n\cdot m,n,m}(d(A))=A$，我们称此为双循环解码。

下边，我们介绍双循环编码算法的相关性质：

---

(1) 在双循环编码中，矩阵$A\in R^{n\times m}$的行和列的遍历过程形成了两种不同的循环：行遍历模n，列遍历模m。这也是双循环编码名字的由来。很明显，双循环编码可以很容易推广到d维循环编码算法用于d维张量$A\in R^{n_1\times n_2\times ...\times n_d}$，其中$n_1\times n_2\times ...\times n_d$之间两两互素。

(2) 矩阵的双循环编码算法可以看作为对角线编码算法的一种扩展。其主要区别为对角线编码算法适用于方阵，且对于d-维方阵，需要创建d个对角线向量。而双循环编码算法对于维度互素的矩阵有效，并且，只需要创建一个双循环向量即可。

(3) 对于矩阵$A\in R^{n\times m}$，且$gcd(n,m)=1$。默认情况下向量$d(A)$的第一个元素对应于矩阵$A$的第$(0,0)$个元素，这里需要指出，实际上，$d(A)$的首元素可以从矩阵$A$​的任一元素开始。

2. 双循环编码下的两种矩阵乘法算法

这里我们先描述明文状态下的算法，之后在描述加密状态下对应的算法。

2.1 算法1描述

算法1注意事项：

(1) 在步骤4a和4b中， 旋转操作的步长应该分别模$nm$和$mp$​。

(2) 在步骤4b中，旋转操作的步长表示为$i(rm-n)$而不是$ip$。该表示在证明算法1的正确性时扮演关键的作用。

算法1证明见原论文，这里我证明过确实是可以的。

2.2 算法2描述

在描述算法2之前，需要先引入segment-sum算法

给定向量$c=(c_i)\in R^n$和整数$k$，其中$k|n$，则定义向量$c$的k长segment-sum算法为：$s=(s_i)\in R^k$，其中$s_i={\sum }_{0\le j<n/k}{c}_{j\cdot k+i}$。即长为$n$的向量，k长segment-sum算法，会输出一个k长的向量，其中$k|n$​。

下面我们描述算法2：

算法2证明见原文，这里我证明过确实是可以的。

3. 双循环编码下的基础加密矩阵操作

这里描述在双循环编码下的加密矩阵操作，暂时还不会描述加密矩阵乘法操作。

3.1 加密状态下矩阵的双循环编码和行(列)编码的转换

由于行编码和列编码在原理上是相同的，故这里仅描述行编码和双循环编码的转换。对于矩阵$A=(a_{i,j})\in R^{n\times m}$，其中$(n,m)$互素。定义$A$的行编码为$r(A)$，定义$A$的双循环编码为$d(A)$，则在$r(A)$和$d(A)$之间存在线性变换$T$。满足$d(A)=T\cdot r(A)$，且$r(A)=T^{\prime }\cdot d(A)$。

3.2 加密状态下矩阵的双循环编码的转置操作，

很容易证明对于$(n,m)$互素的矩阵，其转置的双循环编码$d(A^T)$和其本身的双循环编码$d(A)$是完全相同的，即$d(A)=d(A^T)$。故$ct.d(A)=ct.d(A^T)$​。

3.3 密文的Repeat操作

3.4 密文的segment-sum操作

4. 基于双循环编码的加密矩阵乘法算法

(1) 现在提出算法1的加密版本：

(2) 算法2的加密版本：

容易看到，BMM-II算法中，两个向量相乘后的结果存储了矩阵相乘结果的全部信息，因此其密文操作数量明显小于BMM-I算法。
(3) 双循环编码算法的改进

很明显，现在的双循环编码算法仅适用于$(n,m,p)$互素的情况，然而为了处理$(n,m,p)$不互素的情况，就成了问题，这里我们可以通过填充0的方式来改进，构造新的矩阵使得其满足$(n^{\prime },m^{\prime },p^{\prime })$互素，从而完整矩阵乘法操作。

代码实现：

3. 卷积运算

3.1 论文：《Encrypted Image Classification with Low Memory Footprint using Fully Homomorphic Encryption》

3.2 论文：《Optimized Privacy-Preserving CNN Inference With Fully Homomorphic Encryption》