FHE第一代方案

FHE是隐私计算的一个重要领域，但当前阶段在实用性上还面临两个比较大的技术问题：一个是安全信任模型，目前主流FHE框架都是采用公私钥加密方法，这样当多方进行隐私计算时，就存在一个谁负责私钥产生的信任问题，产生私钥方如果和密文数据计算方合谋的话就能够获取其他参与方的明文数据；另外一个问题是性能问题。安全信任模型问题的一个可行解决方案是将私钥产生采用MPC技术进行多方保管，在密文结果解密时需要多方参与才能还原明文数据。性能问题一方面寄希望于加密框架的重大突破，例如未来会否产生格之外的同态加密体制？但当前比较可行的解决方案还是硬件加速。

同态加密技术的大致发展可以分为四代，第一代是以Gentry基于理想格构造的同态加密方案，其安全性依赖于格上Decision BDDP和稀疏子集和难题；第二代是基于LWE/RLWE难题构造的格加密方案,主要包括BGV/BFV等技术；第三代FHE技术主要介绍通过门电路实现任意函数计算的GSW/TFHE方案，第四代是支持小数计算的CKKS方案。

一、基础数学概念

1、环、理想、理想格

1.1、环Ring和理想Ideal

环$R$是一个含有$+和\times$两种运算的集合，且满足：i)$+$运算构成群；ii)$\times$运算满足封闭性、结合率和分配律。例如所有整数构成一个整数环$z$，封闭性：任a和b相乘结果仍然是整数。 环上$\times$运算不是所有元素存在逆元。

理想$I$的定义如下：i)$I$是$R$的一个子环；ii)$\forall a\in I,r\in R,有ar\in I$。

由定义可知，$I$的单位元和$R$的单位元等同。$给定a\in R$, 由$a$生成的理想记为(a)=aR={ ar∣r∈R}( a ) = aR = \{\ ar\mid r \in R\}(a)=aR={ ar∣r∈R}。假定$R$是乘法可交换环，不区分左右理想。

两个理想$I$和理想$J$称为互素当满足$I+J=R$。

以整数环$\mathbb{Z}$为例，所有偶数构成一个理想$(2)$，$(2)$和$(5)$互素，因为{2a+5b∣ a,b∈Z}=Z\{ 2a + 5b |\ a,b \in \mathbb{Z}\} = \mathbb{Z}{2a+5b∣ a,b∈Z}=Z。

1.2、多项式环及理想

有理数多项式环$R$定义如下：

$$R=\frac{\mathbb{Q}[x]}{(f(x))}$$
其中$f(x)$的次数为$n$。$R$上元素$a(x)$生成的理想记为$(a(x))$, $u(x)$多项式的系数可表示为向量$\mathbf{u}=(u_1,u_2\dots u_n)$。$f(x)$不可约时，$R$上理想$I$的逆定义为I−1={x ∈R ∣ ∀ y∈I, 有x×y∈R}I^{- 1} = \{ \mathbf{x}\ \in R\ |\ \forall\ \mathbf{y} \in I,\ 有\mathbf{x} \times \mathbf{y} \in R\}I−1={x ∈R ∣ ∀ y∈I, 有x×y∈R}, $\mathbf{x}\times \mathbf{y}$在多项式环$R$上的乘法运算。

1.3、理想格Ideal Lattice

格$\mathcal{L}(B)的一组基\mathbf{B}可表示为多个向量({\mathbf{b}}_1,{\mathbf{b}}_2\dots {\mathbf{b}}_n),$设$\mathbf{u}=(u_1,u_2\dots u_n)$是整数多项式环上$R$的元素，如果$基\mathbf{B}$上的每个列向量${\mathbf{b}}_i\in (\mathbf{u})$，也就是说格$\mathcal{L}(\mathbf{B})$的基可以由$R$的一个理想$(\mathbf{u})$生成，则称$\mathcal{L}(\mathbf{B})$为理想格。一个常用的理想格基生成方法是rotation basis：${\mathbf{b}}_i=\mathbf{u}\times x^i\mathrm{mod}f(x),i\in [0,n-1]$, 理想格的基如下：

$$\begin{array}{c}{u}_1\\ \begin{array}{c}{u}_2\\ ⋮\end{array}\\ u_n\end{array}\begin{array}{c}{u}_n\\ \begin{array}{c}{u}_1\\ ⋮\end{array}\\ u_{n-1}\end{array}\begin{array}{c}{u}_{n-1}\\ \begin{array}{c}{u}_n\\ ⋮\end{array}\\ u_{n-2}\end{array}\dots \begin{array}{c}{u}_n\\ \begin{array}{c}{u}_{n-1}\\ ⋮\end{array}\\ u_1\end{array}$$
可知，如果L(B)的基由理想(u)生成，则该理想(u)上的元素均在L(B)上。

2、格上运算

2.1、对偶格Dual Lattice

格$L$的对偶格L∗={x ∈Rn ∣ ∀ y∈L, 有<x,y>∈Z}L^{*} = \{ \mathbf{x}\ \in \mathbb{R}^{n}\ |\ \forall\ \mathbf{y} \in L,\ 有 < \mathbf{x},\mathbf{y >}\mathbb{\in Z\}}L∗={x ∈Rn ∣ ∀ y∈L, 有<x,y>∈Z}，$<\mathbf{x},\mathbf{y}>$表示向量$\mathbf{x}$和$\mathbf{y}$的点积。关于对偶格，有以下性质：

• ${(L^{\ast })}^{\ast }=L$；

• 整数向量格满足${({\mathbb{Z}}^n)}^{\ast }={\mathbb{Z}}^n$, ${({2\mathbb{Z}}^n)}^{\ast }={\frac{1}{2}\mathbb{Z}}^n$；

• $L的一组基\mathbf{B}$，则${({\mathbf{B}}^{-1})}^{\text{ T}}$是$L^{\ast }$的一组基。

2.2、格上模运算

格 $\mathcal{L}(B)$ 的一组基记为 $\mathbf{B}=({\mathbf{b}}_1,{\mathbf{b}}_2,\dots ,{\mathbf{b}}_n)$，则其基础区域（parallelepiped）$\mathcal{P}(B)$ 定义如下：$\mathcal{P}(B)=\left\{{\sum }_{i=1}^n{x}_i{\mathbf{b}}_i\mid x_i\in \left[-\frac{1}{2},\frac{1}{2}\right)\right\}$，且 $\mathrm{vol}(\mathcal{P}(B))=\det (L)$。

对任意向量 $t\in {\mathbb{R}}^n$，定义
t mod B={t−t′∣t−t′∈L(B), t′∈P(B)}t \bmod B = \{t - t' \mid t - t' \in \mathcal{L}(B),\ t' \in \mathcal{P}(B)\}tmodB={t−t′∣t−t′∈L(B), t′∈P(B)}。
可以证明，对任意 $t\in {\mathbb{R}}^n$，$t^{\prime }$ 唯一，因此 $t\mathrm{mod}B$ 也是唯一的。

$t\mathrm{mod}B$ 计算方法如下：

$$t\mathrm{mod}B=t-B\lceil B^{-1}t\rfloor ,\lceil v\rfloor \text{ 表示对向量 }v\text{ 系数进行取整}$$

$B$ 是一组优质基时，$t\mathrm{mod}B$ 就是格 $\mathcal{L}(B)$ 中离最近的向量。所以有
$\Vert t\mathrm{mod}B\Vert \ge \mathrm{dist}(L,t)$。

二、第一代FHE方案

1、FHE基本原理

Gentry 在2009年的博士学位论文中给出了第一个理论上可以实现任意函数加密计算的FHE方案，其本人也因为FHE领域的贡献在前不久当选为IACR Fellow。一个完整的FHE方案要具备两点：1）一是要能够实现基本的加法和乘法电路的密文计算，然后通过加法门和乘法门去构造任意函数（四则运算函数/复杂函数等，二进制加法门对应XOR，二进制乘法门对应AND门）。这跟MPC中布尔分享电路构造任意函数电路原理一样；2）二是在基于密文计算中要能够支持任意电路深度。

在Gentry的第一代FHE方案之前，有一些半同态加密方案可以实现加法密文计算或者乘法密文计算，但未出现可以理论上同时支持任意次的加法和乘法密文计算的方案，其根本原因是对密文噪声控制未有突破性进展。在乘法密文计算中，密文噪声随着乘法电路深度增加而指数级增长导致方案不具备可实现性。

2、一个简单的toy FHE

下面是Gentry博士论文里一个简单的密文加法和乘法计算的示例，可以说明噪声是如何增长的。

2.1、 输入数据

输入数据 b∈{0,1}\ b \in \{ 0,1 \} b∈{0,1}，噪声采样$x\in (-\frac{n}{2},\frac{n}{2})$, 密钥$p是一个奇数$。噪声上限$N,且2N<p$。

2.2、 加密过程：

随机选择$x\in (-\frac{n}{2},\frac{n}{2})$，密文$c=b+2x+kp,k值随机选择确保c是偶数$。

2.3、解密过程

$b=(c\mathrm{mod}p)\mathrm{mod}2$。当$b+2x\in (-N,N)$时解密正确。

式 $b+2x$ 是加密引入的噪声，称为密文噪声。因为 $x\gg b$，故密文噪声控制时可近似只考虑 $x$。

2.4、噪声增长

考虑输入$b_1$和$b_2$，对应的密文为$c_1$和$c_2$，密文相乘结果如下：

单次加密的密文噪声为$2x$，相乘一次后的密文噪声为$4x_1{x}_2$。加密参数选择时$N>n$，在多次相乘后，密文噪声总会达到上限$N$。因此为确保解密正确性，密文相乘次数为有限次。

只能进行有限次同态密文计算的FHE方案称为Somewhat FHE。

3、bootstrap

Gentry在第一代FHE方案中的一个创造性贡献是采用bootstrap方法控制密文噪声增长，其基本思想是在密文噪声达到上限之前进行解密操作降低噪声，但是解密操作本身需要通过FHE方案实现。这样可以通过一个somewhat FHE构造出一个完整的FHE方案。举例说明如下：

假设一个 Somewhat FHE 方案能够执行乘法电路深度 $d>2$。各层电路的加密公私钥为 $p{k}_i,s{k}_i,i\in [1,d]$，各层电路的加密/解密算法为 $en{c}_i,de{c}_i,i\in [1,d]$。各层电路的明文和密文分别为 $m_i,c_i,i\in [1,d]$。

则bootstrap过程如下：

3.1、$d-1$层操作

$d-1$ 层密文为 $c_{d-1}$，对应明文为 $m_{d-1}$。使用 $p{k}_d$ 加密 $c_{d-1}$ 得到 $c_d=en{c}_d(c_{d-1})$。

3.2、$d$层bootstrap操作

$d$ 层密文为 $c_d$。此时使用 $s{k}_d$ 进行解密，得到解密结果 $c_d^{\prime }$。则 $c_d^{\prime }$ 是明文 $m_{d-1}$ 在 $p{k}_d$ 下的加密结果，此时 $c_d^{\prime }$ 对应的明文是 $m_{d-1}$，其密文噪声降低到了明文首次加密时的噪声等级。Bootstrap 操作会使用私钥进行解密；为保证私钥安全性，要求解密电路在 Somewhat FHE 方案下可以运行，这样私钥本身也是加密的。

第一代FHE方案细节后面再介绍，基本就是根据前面理想格上的理想向量计算，重点是对bootstrap解密电路进行了加速优化。

参考文献

1. A FULLY HOMOMORPHIC ENCRYPTION SCHEME, Craig Gentry

2. 格理论与密码学，周福才，徐剑

3. Lattices in Computer Science, Oded Regev Tel Aviv University