基于Benes网络的SIMD同态密文任意重排

摘要

RLWE的密文使用了SIMD后极大的增加的同态加密的效率。同态加密通过加密一个向量，实现对明文的快速加法和乘法。然而，加密为一个密文的向量的内部元素之间，无法高效的操作。
如一个密文加密了$[a,b,c]$，想要计算$a+b$并不是简单的。同态密文的重排指的是，在密文域将加密为同一个密文的向量进行置换重排。本文介绍Gentry等人在2012年提出的，基于Benes网络的明文重排方法。

同态加密的基本操作

基于RLWE的同态加密方案通常加密一整个向量，从而使得均摊的加密和运算时间大大降低，实现单指令多数据（SIMD）的加密。然而，加密一个向量使得向量内部元素的操作不灵活。于是，研究者们通过利用自同态和密文转化技术，提出了同态密文的旋转操作，增加了SIMD密文的灵活性。下面介绍基于RLWE的同态加密方案的基本运算。

SIMD向量加密

假设向量为$\mathbf{a}=[a_1,a_2,\cdots ,a_n]$表示$n$维的向量，$a_i$表示其第$i$个元素。

SIMD的密文，通常是将$\mathbf{a}$作为一整个明文，加密为一个密文。我们使用$\mathbf{A}$表示向量$\mathbf{a}$的密文。同时，我们也说$\mathbf{A}$有 n 个槽 （slot），第$i$个槽中加密的数据为$a_i$.

则同态加法得到的密文$\mathbf{A}+\mathbf{B}$表示向量$[a_1+b_1,a_2+b_2,\cdots ,a_n+b_n]$的密文。

同态乘法得到的密文$\mathbf{A}\times \mathbf{B}$则表示$[a_1\times b_1,a_2\times b_2,\cdots ,a_n\times b_n]$的密文。

旋转

SIMD的密文相对于其他的密文，多了一个旋转操作。通常说的旋转是指的向左循环旋转。比如密文$\mathbf{A}$向左旋转 $k$ 步，则结果为 $[a_{k+1},\cdots ,a_n,a_1,a_2,\cdots ,a_k]$.

向右旋转 $k$ 步，也称为向左旋转 $-k$ 步。

提取

我们通过 0，1 掩膜向量和密文的乘积来提取出特定槽的密文。比如可以通过将$\mathbf{A}$乘以 $[0,0,1,0,\cdots ,0,1]$（即第3个和第$n$个为1，其他全为0的明文向量），提取出 $a_3$和$a_n$的密文。

这里乘的密文向量，可以叫做选择向量。被选择的维度为1，其他维度为0的明文向量，可以根据需要提取出需要的密文。

基于Benes网络的SIMD密文重排

我在https://blog.csdn.net/watqw/article/details/142356306 中给出了如何利用Benes进行置换重排的方法。

构建一个Benes网络，根据需要重排的目标位置填充路由信息，然后使用同态加密的基本操作实现Benes交换网络。

每一层的交换，只需要常数次的旋转、提取和加法，就可以完成。

假设原来密文中的明文为$[1,2,3,4,5,6,7,8]$，需要将其重排为向量$[2,6,5,8,4,7,1,3]$的密文。

下图是一个已经填好路由信息的Benes网络。

我们以第一次交换为例子，说明如何进行密文交换。

假设原始密文为${\mathbf{C}}_0^1$，其明文为$[1,2,3,4,5,6,7,8]$.

将${\mathbf{C}}_0^1$向左旋转4步，得到${\mathbf{C}}_1^1$，其明文为$[4,5,6,7,8,1,2,3,4]$。

将KaTeX parse error: Expected 'EOF', got '}' at position 14: \mathbf[C_0^1}̲向右旋转4步，得到${\mathbf{C}}_2^1$，其明文为$[4,5,6,7,8,1,2,3,4]$。注意，这里由于周期是8，所以${\mathbf{C}}_1^1$和${\mathbf{C}}_2^1$的明文是相等的。

然后，根据路由信息，构造选择向量

${\mathbf{C}}_0^1$的选择向量为${\mathbf{a}}_0^1=[0,1,0,0,0,1,0,0]$. 位置没有变化的维度为1，其他维度为0.

${\mathbf{C}}_1^1$的选择向量为${\mathbf{a}}_1^1=[1,0,1,1,0,0,0,0]$. 向上交换的维度为1，其他为0.

${\mathbf{C}}_2^1$的选择向量为${\mathbf{a}}_2^1=[0,0,0,0,1,0,1,1]$. 向下交换的维度为1，其他为0.

然后计算${\mathbf{C}}_0^2={\mathbf{C}}_0^1\times {\mathbf{a}}_0^1+{\mathbf{C}}_1^1\times {\mathbf{a}}_1^1+{\mathbf{C}}_2^1\times {\mathbf{a}}_2^1$.

每一层的计算开销都是一样的，需要2次旋转，3次乘法和2次加法。

由Benes网络的特性，只需要$2\log (n)-1$层的交换，就可以得到任意重排后的密文。

参考文献

[1] Gentry, Craig, Shai Halevi, and Nigel P. Smart. “Fully homomorphic encryption with polylog overhead.” Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.