0 概述

全同态加密(Fully Homomorphic Encryption, FHE)能够对密文进行任意运算, 且解密结果等同于对明文进行相同运算后的结果。FHE既具有机密性又能进行密态计算, 在云计算环境下可以提升数据的安全性^[1]。文献[2]构造一种CPA安全的全同态加密方案, 其标志着第一代全同态加密算法的出现, 引起了密码学界的广泛关注。文献[3]基于环上误差学习问题(Ring Learning With Errors, RLWE)构造一种全同态加密算法BV11a, 其成为第二代全同态加密方案的典型代表。文献[4]提出近似特征向量方法并构造基于LWE问题的全同态加密方案GSW, 该方案标志着第三代全同态加密算法的出现。目前, 全同态加密大多需要借助自举过程以对同态计算后的密文进行刷新, 得到噪声较小的密文后重新启动同态运算过程。由于自举过程的计算复杂度较高, 且其使用的计算密钥会占据大量的存储空间, 从而降低了全同态加密方案的效率。文献[5]基于TGSW方案, 构造自举过程小于0.1 s的高效双层全同态加密方案CGGI16。文献[6]对CGGI16进行改进, 得出一种效率更高的全同态加密方案CGGI17。目前, 全同态加密方案的效率不断提升^[7-9], 但其距广泛应用仍有一段距离。因此, 设计高效的全同态加密算法, 并对其编程实例进行优化, 是该领域亟需解决的问题。

密态计算的多数场景均需使用比较操作, 该操作也是安全多方计算、密文检索等协议的基本组成模块。文献[10]基于somewhat同态加密方案构造多比特的密文数值比较器。文献[11]在HElib同态运算库的基础上, 构建一种并行比较多比特明文的同态运算模型。

相对于CPU, GPU硬件具有更强大的浮点计算和并行计算的能力, 可以为全同态加密算法的快速实现提供良好的算力支撑^[12]。目前, GPU已在深度学习^[13-14]、影像数据处理^[15-16]、密码算法加速^[17-18]等领域得到了广泛应用。全同态密码算法的自举技术涉及大量的矩阵乘法和NTT运算, 因此, 可以利用GPU来加速实现这些计算密集型运算。cuFHE库是一个开源的GPU加速全同态密码库^[19], 其借鉴了cuHE^[20]中GPU端的快速数论变换, 实现一种基于CUDA平台的高效CGGI方案。然而, cuFHE仅提供了基本的门电路接口, 并未提供如比较运算等的函数接口。因此, 利用cuFHE提供的接口开发同态运算器, 可以使CGGI等同态加密方案得到更广泛的应用。

本文在cuFHE全同态加密库的基础上, 编写单比特同态比较运算函数, 利用GPU硬件和CPU多线程技术, 设计并实现一种可比较任意长度明文的多比特同态比较运算器。

1 CGGI全同态加密方案

cuFHE软件库的底层方案为CGGI。

定义1(TLWE) 令n≥1为整数, N为2的幂, 噪音参数α≥0, 随机均匀选择私钥s∈$\mathbb{B}$_N[X]^k。消息μ∈$\mathbb{T}$_N[X]被加密为c=(a, b)∈$\mathbb{T}$_N[X]^k×$\mathbb{T}$_N[X], b∈$\mathbb{T}$_N[X]服从高斯分布D_{$\mathbb{T}$N[X], α, s·a+μ}。当向量a中的元素满足均匀分布时, 实例c=(a, b)随机; 当a=0时, 实例称为平凡实例; 当α=0时, 实例称为无噪音实例; 当μ=0时, 实例称为齐次的实例。

搜索问题描述为:给定齐次的TLWE实例, 找到s∈$\mathbb{B}$_N[X]^k, 使噪音分布集中。

判定问题描述为:区分TLWE实例和$\mathbb{T}$_N[X]^k×$\mathbb{T}$_N[X]中的均匀分布实例。

定义2(Phase) 对于c=(a, b)∈$\mathbb{T}$_N[X]^k×$\mathbb{T}$_N[X]和s∈$\mathbb{B}$_N[X]^k, 定义TLWE实例的相位φ_s(c)$\triangleq $b－s·a。相位φ_s(c)与$\mathbb{T}$_N[X]^k+1上的输入(a, b)具有线性关系, 具体而言, 对于l_∞范数φ_s服从(kN+1)-lipschitzian, 即∀x, y∈$\mathbb{T}$_N[X]^k+1, ‖φ_s(x)－φ_s(y)‖_∞≤(kN+1)‖x－y‖_∞。

定义3(TLWE实例) c∈$\mathbb{T}$_N[X]^k+1是一个随机变量。如果存在一个密钥s∈$\mathbb{B}$_N[X]^k, 使得相位的φ_s(c)分布集中, 则定义c是一个合法的TLWE实例。如果c是平凡实例, 则对于所有的密钥s, c都是一个合法的TLWE实例; 如果c服从随机均匀分布, 则s唯一确定。

CGGI方案中的自举过程^[6]描述如下:

算法1   Bootstrapping自举过程

输入   μ₁∈$\mathbb{T}$[X], c=(a, b)∈$\mathbb{T}$_N[X]^k×$\mathbb{T}$_N[X], x∈$\mathbb{B}$, Bookstrapping key=(BK_i)_{i∈[1, n]}

输出   c=(a, b)∈$\mathbb{T}$_N[X]^k×$\mathbb{T}$_N[X]

1.${\rm{ \mathsf{ μ} }}\text{ =}\frac{\text{1}}{\text{2}}{{\rm{ \mathsf{ μ} }}_{\text{1}}}\in \mathbb{T}\left[\text{X} \right]$

2.b=[2Nb], a_i=[2Na_i]∈$\mathbb{Z}$, i∈[1, n]

3. ${\rm{v = (1 + X + \ldots + }}{{\rm{X}}^{{\rm{N}} - {\rm{1}}}}){\rm{\cdot}}{{\rm{X}}^{\frac{{\rm{N}}}{{\rm{2}}}}}{\rm{\cdot \mathsf{ μ} }} \in{{\mathbb{T}}_{\text{N}}} \left[{\rm{X}} \right]$

4.ACC←BlindRotate((0, v), (a₁, a₂, …, a_n, b), (BK₁, BK₂, …, BK_n))

5.Return (0, μ)+SampleExtract(ACC)

CGGI方案中所提供的同态运算以TLWE密文c₁和c₂为输入, 调用自举算法实现同态与非(HomNAND)、同态异或(HomXOR)、同态与(HomAND)、同态或(HomOR)、同态非(HomNOT)门电路, 输出门电路操作对应的密文如下:

$\begin{array}{*{35}{l}} HomNAND\left( {{\boldsymbol{c}}_{1}}, {{\boldsymbol{c}}_{2}} \right)=Bootstrapping(({\bf{0}}, 5/8)-{{\boldsymbol{c}}_{1}}-{{\boldsymbol{c}}_{2}}) \\ HomXOR\left( {{\boldsymbol{c}}_{1}}, {{\boldsymbol{c}}_{2}} \right)=Bootstrapping\left( 2\left( {{\boldsymbol{c}}_{1}}-{{\boldsymbol{c}}_{2}} \right) \right) \\ HomAND\left( {{\boldsymbol{c}}_{1}}, {{\boldsymbol{c}}_{2}} \right)=Bootstrapping(({\bf{0}}, -1/8)+{{\boldsymbol{c}}_{1}}+{{\boldsymbol{c}}_{2}}) \\ HomOR\left( {{\boldsymbol{c}}_{1}}, {{\boldsymbol{c}}_{2}} \right)=Bootstrapping(({\bf{0}}, 1/8)+{{\boldsymbol{c}}_{1}}+{{\boldsymbol{c}}_{2}}) \\ HomNOT\left( \boldsymbol{c} \right)=({\bf{0}}, 1/4)-\boldsymbol{c} \\ \end{array} $

其中, 0表示维度为n的零向量, Bootstrapping为自举过程。

2 同态数值比较器 2.1 单比特同态数值比较器

单比特数值比较器通过比较2个输入端的单比特二进制数的大小, 在输出端输出不同比较结果的逻辑电路, 具体如下。

输入:2个单比特二进制数A、B。

计算:

1) out₁=A·B。

2) out₂=(A·B)$\oplus $(A·B)。

3) out₃=A·B。

其中, ·表示AND运算, $\oplus $表示XNOR运算, ^—表示NOT运算。单比特数值比较器真值表如表 1所示。

逻辑输出为:

1) out₁=1, 表示A小于B。

2) out₂=1, 表示A等于B。

3) out₃=1, 表示A大于B。

在单比特明文数值比较器的设计过程中, 可以抽象出数值比较器的基本特征。对于密文状态下的单比特数值, 只需通过如下同态操作即可实现比较运算:

明文m₀、m₁∈Z₂, 定义密文上的运算AND、XNOR、NOT满足如下同态性质:

1) dec(AND(enc(m₀), enc(m₁)))=AND(m₀, m₁)。

2) dec(XNOR(enc(m₀), enc(m₁)))=XNOR(m₀, m₁)。

3) dec(NOT(enc(m)))=NOT(m)。

结合以上操作, 参照已经实现的单比特明文数值比较器, 设计单比特同态数值比较器, 其运算过程如算法2所示。

算法2  单比特同态比较算法

输入   m₀, m₁, pk, sk

输出   out₁, out₂, out₃

1.M₀=enc(m₀, pk), M₁=enc(m₁, pk)

2.out₁=(NOT(M₀))AND(M₁)

3.out₂=(NOT(M₀)AND(M₁))

XNOR((M₀)AND NOT(M₁))

4.out₃=(NOT(M₀))AND(M₁)

5.return out₁, out₂, out₃

单比特同态数值比较器的真值表如表 2所示, 其中, 方框表示在密文上进行该运算。

对输出结果进行解密:

1) out₁=1, 表示A小于B。

2) out₂=1, 表示A等于B。

3) out₃=1, 表示A大于B。

2.2 并行多比特同态数值比较器

通过逐比特地调用单比特比较器并将结果发回客户端, 可以实现多比特比较运算, 但其涉及过多的解密运算, 通信开销较大, 且未利用硬件的并行优势, 导致复杂度较高, 效率较低。本文在单比特同态比较器的基础上, 利用CPU多线程技术, 通过调用基于GPU的单比特数值比较器来实现并行多比特数值的比较运算, 从而构造一种任意比特长度的多比特数值比较器。因为该过程只需对单比特明文进行加密, 所以其明文空间为Z₂。定义密文上的运算XOR满足如下同态性质:

$ dec(~XOR(~enc\left( {{m}_{0}} \right), enc({{m}_{1}})~)~)=XOR({{m}_{0}}, {{m}_{1}}) $

并行多比特数值的比较运算过程如下:

1) 选取2个二进制明文m=(x₀, x₁, …, x_n), n=(y₀, y₁, …, y_n), 分别对这2个明文逐位使用全同态方案CGGI的加密算法进行加密, 得到对应密文M=enc(m, pk), N=enc(n, pk)。

2) 对上述2个密文使用多线程技术, 并行调用单比特同态数值比较器进行同态比较运算, 并保存结果。

3) 对保存的结果进行相应的AND和XOR门电路操作, 得到最终结果。

对2个输入长度为n比特的二进制字符串, 从高位到低位依次调用单比特同态数值比较器进行运算后可得到OUT, 将OUT解密为out后, 程序结束并输出m≥n或m < n。并行多比特明文同态比较算法描述如下:

算法3  多比特同态比较算法

输入   m=(x₀, x₁, …, x_n), n=(y₀, y₁, …, y_n), pk, sk

输出   OUT

1.parallel for i=0 to n

2.M_i=enc(x_i, pk), N_i=enc(y_i, pk)

3.FLevel_{i, 1}=(NOT(M_i))AND(N_i)

4.FLevel_{i, 2}=(NOT(M_i)AND(N_i))

XNOR((M_i)AND NOT(N_i))

5.SLevel₀=FLevel_{1, 2}, OUT=FLevel_{1, 1}

6.for i=1 to n

7.SLevel_i=(SLevel_i－1)AND(FLevel_{i, 1})

8.OUT=(OUT)XOR(SLevel_i)

9.return OUT

并行多比特同态比较器的真值表如表 3所示。

3 实验结果与分析

本文在cuFHE全同态加密库的基础上, 编写单比特同态比较函数, 利用CPU多线程技术和GPU硬件, 设计一种并行多比特同态比较器。本次实验分别对比较器的加解密时间、自举过程时间、单比特比较器运行时间和多组多比特比较运算时间进行测试。

实验环境:硬件采用Intel(R) Core(TM) i7-8700 3.20 GHz CPU, 8 GB内存, NVIDIA GTX1080 8 GB显卡, 软件系统运行Ubuntu 16.04 LTS 64位操作系统(Linux kernel 4.13), 测试程序基于CUDA 9.2平台, 使用gcc 7.2编译器进行编译。

3.1 加解密与自举过程测试

在实验过程中, 首先对单比特输入进行加解密操作并测试时间, 对于每比特的输入输出, 加密和解密所需平均时间均不足0.01 ms。然后对单比特自举过程的时间进行测试, 结果显示, 自举过程所需时间为3 ms。

3.2 单比特比较算法

在实验过程中, 对多组0、1输入进行加密, 对密文做同态比较运算, 测量总时间后求平均值得到运算时间, 结果显示, 对单比特明文进行同态比较运算所需的时间为10 ms。

3.3 多比特比较算法

在实验过程中, 测量在GPU(CUDA平台)上同态比较器的运行时间。针对不同长度的二进制明文比特串, 同态比较器运算所需的时间如表 4所示。

比较器运算时间与明文长度的关系如图 1所示。

从图 1可以看出, 基于CPU多线程技术与GPU硬件, 在1 s内可完成对100 bit明文的同态比较运算, 且比较器支持对任意比特长度的明文进行同态比较运算。具体应用时对电路规模进行比较的需求通常不大, 本文所设计的同态比较器基本能够满足实际需求。

4 结束语

本文在cuFHE全同态加密库的基础上, 设计一种高效的多比特同态比较器。实验结果表明, 该同态比较器可比较任意比特长度的明文, 且运算速度较高。下一步将降低自举过程的计算量, 以提升该比较器的运算效率。