文献^[8]基于整数上的全同态加密来安全计算内积，首先使用全同态加密(FHE)对向量的每一坐标分别加密得到$\mathbf{{V}'}=({{V}_{1}}^{\prime },{{V}_{2}}^{\prime },\cdots ,{{V}_{l}}^{\prime })$和$\mathbf{{W}'}=({{W}_{1}}^{\prime },{{W}_{2}}^{\prime },\cdots ,{{W}_{l}}^{\prime })$，其中用$\mathbf{{X}'}$表示对X的加密，然后同态计算$＜\mathbf{{V}'},\mathbf{{W}'}＞$。然而，这种方法虽然简单，但存在巨大问题。首先，当向量维数l比较大时，需要传送2l个密文，通信代价很大；在用户端需要计算2l个加密，在云服务器端，为了同态计算内积，服务器需要做l个同态乘和$＜\mathbf{{V}'},\mathbf{{W}'}＞$个同态加，计算量都较大。此外，基于整数的全同态加密的安全性也是值得怀疑的。文献^[9]就给出了基于整数的全同态加密的密码分析。

文献^[10]在基于生物认证的认证中，利用基于理想格的全同态加密来安全计算内积。使用打包的技巧来将一个明文向量的所有坐标打包到一个密文中。但是该方案的计算效率并不高，如对两个2048维的bit向量，为了安全计算内积，其预计计算的时间需要38 s。此外，该方案也不适合计算其他相似性指标，如余弦相似性。

因此，本文提出了一种基于全同态加密的安全计算内积方案，该方案计算量低、通信开销小、针对整数向量而不仅是bit向量，安全性高。

本文使用基于格上的环上错误学习问题(learning with errors over ring,RLWE)的同态加密方法，安全高效地计算两个高维向量的内积。其主要思想是用户首先将明文向量的所有坐标打包到一个密文里，然后云服务器以单指令多数据流(simple instruction multiple data，SIMD)的方式并行计算两个向量的内积。方案具体包括3个部分：基于RLWE的Somewhat同态加密方案的构造、打包和SIMD并行化技术和安全内积计算。

本文基于RLWE来构造Somewhat同态加密方案，该方案基于方案SHE(somewhat homomorphic encryption)^[11]上为多项式时间算法的六元组(Setup,KeyGen,Enc,Dec,Add,Mult)，具体描述如下：

参数设置(SHE.Setup)：根据输入的安全参数$\lambda $，建立多项式环R和离散高斯分布$X$。设多项式${{x}^{n}}+1$的次数$n=n(\lambda )$，离散高斯分布$X=X(\lambda )$，使得RLWE问题对已知格攻击是${{2}^{\lambda }}$级安全的。令$R=\mathbb{Z}[x]/({{x}^{n}}+1)$，明文空间为${{R}_{2}}={{\mathbb{Z}}_{2}}[x]/({{x}^{n}}+1)$，密文空间则为${{R}_{q}}={{\mathbb{Z}}_{q}}[x]/({{x}^{n}}+1)$，输出公共参数$\text{params}=(q,n,X)$。

密钥生成(SHE.KeyGen)：在高斯分布X上随机选择一个元素$s\leftarrow X$作为私钥，然后在${{R}_{q}}$上随机均匀选取一个元素${{a}_{1}}\leftarrow {{R}_{q}}$，同时在高斯分布X上随机选取一个差错$e\leftarrow X$，计算${{a}_{0}}=-{{a}_{1}}s+2e$。令私钥$\text{sk}=s$，公钥$\text{pk}=({{a}_{0}},{{a}_{1}})$。

加密(SHE.Enc)：给定单比特消息$m\in \{0,1\}$，在高斯分布X上分别随机选取元素$u\leftarrow X$和元素$r\leftarrow X$，根据公钥$\text{pk}=({{a}_{0}},{{a}_{1}})$分别计算出密文${{c}_{0}}={{a}_{0}}u+m$与${{c}_{1}}={{a}_{1}}u+2r$，输出密文$c=({{c}_{0}},{{c}_{1}})$。

解密(SHE.Dec)：根据给定的密文$c=({{c}_{0}},{{c}_{1}})$，利用私钥$\text{sk}=s$，计算出${m}'=(({{c}_{0}}+{{c}_{1}}s)\bmod q)\bmod 2$。

求和(SHE.Add)：输入两个密文${{c}_{1}},{{c}_{2}}$，输出这两个密文的和${{c}_{1}}+{{c}_{2}}$。

乘积(SHE.Mult)：输入两个密文${{c}_{1}},{{c}_{2}}$，输出这两个密文的乘积${{c}_{1}}\times {{c}_{2}}$。

文献^[12]在基于理想格的全同态加密方案引入了打包和单指令多数据流(simple instruction multiple data,SIMD)方法，本文将该方法用于上述基于RLWE的SHE方案中，具体过程描述如下。

分解明文空间${{R}_{2}}={{\mathbb{Z}}_{2}}[x]/({{x}^{n}}+1)$：虽然多项式${{x}^{n}}+1$在$\mathbb{Z}$上是不可约的，但可选择合适的n值，使${{x}^{n}}+1$在${{\mathbb{Z}}_{2}}$上是可约的。由此，将其分解为${{x}^{n}}+1={{f}_{1}}(x){{f}_{2}}(x)\cdot \cdot \cdot {{f}_{l}}(x)$，其中${{f}_{i}}(x),i=1,2,\cdots ,l$的次数为$d=n/l$。于是明文空间被分解为l个明文槽：${{\mathbb{Z}}_{2}}[x]/({{x}^{n}}+1)={{\mathbb{Z}}_{2}}[x]/({{f}_{1}}(x))\times {{\mathbb{Z}}_{2}}[x]/({{f}_{2}}(x))\times \cdot \cdot \cdot \times {{\mathbb{Z}}_{2}}[x]/({{f}_{l}}(x))$。即在原来的明文空间中，明文$m(x)$是${{R}_{2}}$上的多项式，有n个比特，通过中国剩余定理(Chinese remainder theorem,CRT)，$m(x)$可被分解为：${{m}_{1}}(x),{{m}_{2}}(x),\cdots ,{{m}_{l}}(x)$，分别对应到l个明文槽${{\mathbb{Z}}_{2}}[x]/({{f}_{1}}(x)),{{\mathbb{Z}}_{2}}[x]/({{f}_{2}}(x)),\cdots ,{{\mathbb{Z}}_{2}}[x]/({{f}_{l}}(x))$，对每个${{m}_{i}}(x),i=1,2,\cdots ,l$，均有d个比特。令明文$m(x)$对应的密文为$c(x)$，通过这种方式，可将l个明文${{m}_{1}}(x),{{m}_{2}}(x),\cdots ,{{m}_{l}}(x)$打包到一个密文$c(x)$。

在对打包后的密文进行操作时，加同态和乘同态能在这些明文槽上并行地执行，这样极大地减轻了计算量。具体过程为：令一个打包后的密文为$c(x)$， 对应在l个明文槽的明文分别为${{m}_{1}}(x),{{m}_{2}}(x),\cdots ,{{m}_{l}}(x)$，令另一个打包后的密文为${c}'(x)$，对应在l个明文槽的明文则分别为${{{m}'}_{1}}(x),{{{m}'}_{2}}(x),\cdots ,{{{m}'}_{l}}(x)$，加同态SHE. Add$(c,{c}')$对应在各个明文槽的明文就分别为：${{m}_{1}}(x)+{{{m}'}_{1}}(x),{{m}_{2}}(x)+{{{m}'}_{2}}(x),\cdots ,{{m}_{l}}(x)+{{{m}'}_{l}}(x)$，可以得到乘同态SHE. Mult$(c,{c}')$对应在各个明文槽的明文为：${{m}_{1}}(x)\times {{{m}'}_{1}}(x)\bmod {{f}_{1}}(x),{{m}_{2}}(x)\times {{{m}'}_{2}}(x),\bmod {{f}_{2}}(x),\cdots ,{{m}_{l}}(x)\times {{{m}'}_{l}}(x)\bmod {{f}_{l}}(x)$。因此同态操作可以看成是在明文槽上使用SIMD并行执行的。

自同构映射能使对应在各个明文槽的明文发生置换：当明文为$m(x)$，其对应在各个明文槽的明文就分别为${{m}_{1}}(x),{{m}_{2}}(x),{{m}_{3}}(x),\cdots ,{{m}_{l}}(x)$，Frobenius自同构映射$m(x)$，使$m(x)\to m({{x}^{{{2}^{i}}}})$明文槽循环移动i个明文槽。如，当$i=1$时，$m(x)$的明文槽就循环移动1个位置，其对应于各个明文槽的明文就发生变化，变更为${{m}_{2}}(x),{{m}_{3}}(x),\cdots ,{{m}_{l}}(x),{{m}_{1}}(x)$。因此，就可以通过操纵相应的密文$c(x)$，并利用密钥更新的技巧 (密钥$s({{x}^{k}})$从更新为$s(x)$)，使各个明文槽中的明文发生置换。

如前所述，基本方案只能对向量中的每一个坐标分别进行加密。本文将向量打包成一个单一的密文，再以SIMD并行的方式计算两个向量的内积。计算内积的过程如下：

1) 系统选择合适的参数n和l，使得明文空间${{R}_{2}}={{\mathbb{Z}}_{2}}[x]/({{x}^{n}}+1)$分解为l个明文槽${{\mathbb{Z}}_{2}}[x]/({{f}_{1}}(x)),{{\mathbb{Z}}_{2}}[x]/({{f}_{2}}(x)),\cdots ,{{\mathbb{Z}}_{2}}[x]/({{f}_{l}}(x))$，其中${{f}_{i}}(x),i=1,2,\cdots ,l$的次数为$d=n/l$；

2) 用户A拥有向量V，对于l维向量$\mathbf{V}=({{V}_{1}},{{V}_{2}},\cdots ,{{V}_{l}})\in {{\mathbb{Z}}^{l}}$，将${{V}_{i}}$分别编码为${{m}_{i}}(x)$，其中，$i=1,2,\cdots ,l$；

3) 通过中国剩余定理将${{m}_{i}}(x)$打包为$m(x)$，并调用加密算法得到$V(x)\leftarrow \text{SHE}\text{.Enc(}pk,m(x)\text{)}$；

4) 类似地，用户B通过同样步骤将l维向量$W=({{W}_{1}},{{W}_{2}},\cdots ,{{W}_{l}})\in {{\mathbb{Z}}^{l}}$打包到$W(x)$，本文以用户A将向量V打包为$V(x)$为例，具体过程如图 1所示；

图  1  用户将明文向量的所有坐标打包到一个密文

5) 云服务器调用SHE.Mult$\text{(}V(x),W(x)\text{)}$，如表 1所示，这一步相当于以SIMD的方式并行计算${{V}_{1}}(x)\times {{W}_{1}}(x)\bmod {{f}_{1}}(x),{{V}_{2}}(x)\times {{W}_{2}}(x)\bmod {{f}_{2}}(x),\cdots ,{{V}_{l}}(x)\times {{W}_{l}}(x)\bmod {{f}_{l}}(x)$；

6) 对上一步的结果调用$\log l$个Frobenius自同构映射以及$\log l$个同态加法，同态评估得到$c(x)$，其对应的明文为$m(x)$；

7) 通过调用算法SHE.Dec$\text{(sk},c(x)\text{)}$，计算出$m(x)$为：$m(x)=\sum\limits_{i=1}^{l}{{{V}_{i}}(x)}\cdot {{W}_{i}}(x)$；

8) 令x=2，代入$m(x)$，得到$＜V,W＞$。

将本文方案和已有的两个基于全同态加密的安全内积计算方案进行比较，结果如表 2、表 3所示。

从表中可以看出，本文方案使用基于RLWE的FHE计算两个向量的内积，不仅针对bit向量，还可以针对一般的整数向量，这一点与文献^[8]的方案相同，而文献^[10]的方案只能针对bit向量，因此，本文方案和文献^[8]的方案在实际应用中更加广泛。而与文献^[8]的方案相比，本文方案在计算中使用了打包技巧，将一个向量的所有坐标打包到一个密文中，同时使用了SIMD技巧以进行并行化处理，使得本文方案有着较高的计算效率。就通信成本而言，两个方案中的明文空间均被划分为l个明文槽，因此本文方案有着较低的通信成本和计算代价。

本文提出一个适合于云计算中top-k检索的安全计算两向量内积相似性的方案，该方案使用基于RLWE的批处理同态加密来保护隐私。与其他方案相比，该方案具有通信开销小和计算代价低的优点。此外，在社交网络中的群体挖掘，以及基于生物特征的认证等场景，也需要用到相似性度量。因此下一步的工作将研究如何将本文提出的方案应用到其他场景。