初探全同态加密1 —— FHE的定义与历史回顾

一、加密体系

1、什么是加密体系

 在开始之前，我们先温习一下最最传统的加密体系。
 构建一个 加密系统，往往都需要一个 密钥 Key。通过这个密钥，我们可以一头把明文的信息加密成密文，然后在另一头通过密钥再把密文变回原来的样子。如果没有这个 Key 的话，其他的人很难知道我们到底传递了什么信息。

上文的图例基本展示了所有常见加密体系的全貌。所有的加密体系，如果用比较正式的描述方法，无疑是做了三件事：

1. 通过一个生成算法 $KeyGen(1^{\lambda })$ 来随机生成一对用于加密和解密的密钥 $(EncKey,DecKey)$。
2. 加密方通过 加密密钥 $EncKey$ 和 加密算法 $Encryption$ 来加密 原文 $Plaintext$，最后得到 密文 $Ciphertext$。
3. 随后，在解密的时候，解密方可以通过 解密密钥 $DecKey$ 和 解密算法 $Decryption$ 来解密密文，最后还原回来原来的原文。

 我们这里描述的这三个步骤，其实通用于任何加密体系 (对称加密系统和非对称加密系统)。如果是对称的，那么加密和解密用的密钥就是一样的。如果是非对称的体系的话，那么加密用的就是 公钥 Public Key，然后解密用的是不一样的 私钥 Private Key。

2、加密体系的属性 Properties

 在密码学研究中，每当我们看到一个新的系统的定义之后，接下来往往都要陈述这个系统所应具有的 属性 Properties。

• 正确性，Correctness：
   正确性代表说，如果我拥有一个正确的密钥，那么我就可以通过 解密算法 $Decryption$ 来把密文还原成原文。我们往往都使用概率的方法来表示解密的成功率：
  $$\begin{gathered} \forall pt\in PT,(k_{enc},k_{dec})\leftarrow KenGen(1^{\lambda }) \\ :Pr[Decryption(k_{dec},Encryption(k_{enc},pt))=pt]=1 \end{gathered}$$
  上面的等式代表了，如果我们拥有 正确的密钥，那么解密算法可以 还原 加密算法生成的密文的几率是 100%。
• 语义安全，Semantic Security：
   我们可以理解为，如果我们拥有任意两个不同的原文所对应的密文，那么我们是无法区分到底哪个密文是对应了哪个原文的：
  ∀ m 0 , m 1 : { E n c ( k e n c , , m 0 ) } ≈ c { E n c ( k d e c , m 1 ) } \forall m_0,m_1:\{Enc(k_{enc},,m_0)\}≈_c\{Enc(k_{dec},m_1)\} ∀m0​,m1​:{Enc(kenc​,,m0​)}≈c​{Enc(kdec​,m1​)}
  语义安全的主要意义在于 旁观者 无法区分 两条加密的消息。那么如果有入侵者窃听网络，看到了我发出的加密信息，只要我使用的加密体系是语义安全的，那么我就可以确信入侵者无法从密文中得到关于加密内容的任何信息。

 满足了上述两条属性之后，一个加密体系就变得健全啦。

二、同态加密：偶然的特殊性质

 我们都知道，光看密文本身，我们什么信息都不会得到。但是这是不是就代表，如果没有密钥只有密文，我们什么都不能做了呢？答案我们都知道：其实并不是。
 但是在众多的加密算法当中，有一类算法生成的密文有一种特殊的 同态属性：假如我们使用 加密算法 Enc 得到了 数字1 的 密文 ct1，然后我们又得到了 数字2 的 密文 ct2。这个时候，如果我们把密文相加起来，ct+ct2 恰恰是 1+2=3 的密文！对于这种属性，我们称之为 加法同态。
 同理可得，加法同态之外，还存在着 乘法同态 的加密算法。

 通过同态加密算法，用户 可以与一个 不可信的远程服务器 (云端) 进行某种 安全代理计算 Secure Delegated Computation。用户可以通过 同态加密的技术 来把自己敏感的隐私输入加密后托付给云端，然后云端可以 在加密过后的数据上 进行一定程度的计算，最后得到加密过后的用户想要的结果，并且返还给用户。最后用户就可以用解密密钥来打开得到的结果了。整个协议中，被代理方 云端 始终都 无法看到 任何和私密输入有关的有用信息。

三、同态加密体系的分类

 大致了解了两种最基础的同态性质之后，其他的概念就变得非常容易理解了。如果系统性的来看，同态加密体系大致上被分为四类：部分同态、近似同态、有限级数全同态、完全同态。

四、部分同态加密 Partially Homomorphic Encryption

1、加法同态加密算法 —— ElGamal 加密算法

 同态加密 最初级 的阶段被称为 部分同态加密，定义就是 密文只有一种同态特性。这一阶段就包括了我们上文所描述的 加法同态 与 乘法同态 两种模式。

 如果放到之前说的 安全代理计算 的场景下看，假如我们有 私密输入 $x_1,x_2,...,x_n$，然后我们希望 云端 可以帮我们计算 $f(x_1,x_2,...,x_n)$ ，那么我们可以把云端对于这些输入做的计算使用 函数 F 来表示。

 假如说我们可以通过一个 加法同态加密 的算法来计算 F 的话，那么代表了这个 函数F 肯定就只能包含 私密输入 x_i 的任意线性组合 (加法运算)。一个可行的例子就是把各项私密输入乘以一个常数，然后相加起来：
$$f(x_1,x_2,...,x_n)\to c_1{x}_1+c_2{x}_2+...+c_n{x}_n$$ 但是如果我们想让两个输入 x_i x_j 相乘起来的话，那么上述的加法同态算法就无能为力了。F 只能是所有私密输入的 线性组合。

 常见的 加法同态加密算法 就是 基于循环群 G 的 ElGamal 加密算法。

 ElGamal 是 基于 Diffie-Hellman 密钥交换协议 而产生的一个非常方便的 公钥加密算法，采用的是 循环群 的特性。由于篇幅的原因，这里不详细解释循环群的定义，我们只需要知道 每一个群都可以找到一个生成元 (generator) ，然后这个生成元可以进行幂的计算。

1.1、ElGamal 的大致步骤

 ElGamal 加密实现方法大致如下：

1. 首先我们找到一个 生成元 $g\in G$，然后随机选择一个 整数 x。我们把 g^x 作为 公钥 pk，然后把 x 作为 私钥 sk。
2. 如果要加密一个 消息 m 的话，那么我们就再随机选择一个 整数 y，然后我们就可以输出 密文：
   $$ct\leftarrow (v\leftarrow g^y,e\leftarrow p{k}^y\cdot g^m)$$注意这个密文分为 v, e 两段。
3. 当我们需要解密一个 密文 ct 的时候，我们只需要首先计算 $$w\leftarrow v^x=g^{yx}=p{k}^y$$然后就可以轻松的还原出原文 m 了：$$m\leftarrow lo{g}_g(e/w)$$

1.2、ElGamal 的加法同态特性

 具体 ElGamal 的 正确性 和 安全性 我们就不论证了。但是看到这个加密体系的加密方式之后，由于都是 幂运算，我们可以发现 ElGamal 潜在的 加法同态 的特性。
 假如我们拥有两条消息 m₀，m₁ 的加密，分别为 ct₀，ct₁，展开来就是：
$$\begin{gathered} c{t}_0=(v_0=g^{y_0},e_0=p{k}^{y_0}\cdot g^{m_0}) \\ c{t}_1=(v_1=g^{y_1},e_1=p{k}^{y_1}\cdot g^{m_1}) \end{gathered}$$ 我们可以注意到，如果我们 把两条密文的两个部分各自相乘 的话，我们就可以得到一个 新的密文 $\widehat{ct}$：$$$\widehat{ct}=c{t}_0\cdot c{t}_1=(\hat{v}=g^{y_0+y_1},\hat{e}=p{k}^{y_0+y_1}\cdot g^{m_0+m_1})$$ 我们得到的结果恰恰就是原文 m₀+m₁ 加在一起之后所对应的 加密密文！这样的话，如果我们得到了两条 ElGamal 加密算法的密文，我们就可以通过这样的方法得到密文的 任意线性组合 了。

2、乘法同态加密算法 —— RSA加密

 同理我们也可以应用于 乘法同态加密 的算法上—— F 就只能把所有的私密输入相乘起来，但是没有办法做任何 线性组合 (加法)。乘法同态的例子其实也非常常见，我们大家都熟悉的 RSA 加密就是一个乘法同态的系统。

2.1、RSA 的大致步骤

 RSA 加密的实现方法大致如下：

1. 首先找到一个很大的数字 N = p · q，并且 p, q 为 质数。然后找到一组数字 e, d 使得可以满足 e · d = 1 mod (p-1) (q-1)。我们把 (N, e) 作为 公钥，(N, d) 作为 私钥。
2. 如果要加密一个消息 m，则密文 $ct\leftarrow m^{e}modN$。
3. 如果需要解密一个消息 ct，则原文 $m\leftarrow c{t}^{d}modN$。这里和乘法逆元有关，需要仔细推导

 这个加密的 正确性 就在于 (m^e)^d = m mod N。因为 RSA 加密和解密的过程也就只涉及到了幂的计算，我们又可以观察到同态的性质了。假如说我们有两条加密的消息 ct_0, ct_1 对应 m_0, m_1。那么我们可以把他们相乘起来得到来得到 $\hat{c}$，并且可以观察到：$$\hat{c}=c{t}_0\cdot c{t}_1=m_0^e\cdot m_1^e=(m_0\cdot m_1{)}^e$$ 我们就得到了这两条消息 相乘 之后所对应的密文！这就是 乘法同态性质 了，我们可以接着这条密文继续往上叠加新的密文，这样一来我们就可以得到密文之间 任意的相乘。

五、近似同态加密 Somewhat Homomorphic Encryption

 就如同我们在上一段所说，如果我们又想让私密输入相乘，又想得到它们之间的线性组合的话，单纯的部分同态加密算法 (RSA, ElGamal) 是无法完成的。

 所谓 近似同态加密 指的是 可以同时进行 加法 和 乘法，但是可以做加法和减法的 次数有限，可以计算的函数 F 也在一个有限的范围内。

 近似同态加密这一阶段常见的例子并不多，如果说最好理解的例子的话，那就应该是 基于配对 (Pairing) 的循环群加密算法 了。

 配对 (Pairing) 是 基于某些 特有的椭圆曲线循环群 可以进行的一种特殊运算，用 e(·,·) 来表示。具体 Pairing 做的事情，就是 把两个循环群中的值映射到第三个循环群中：
$$e(g^x\in G,g^y\in G)\to g_T^{xy}\in G_T$$ 这样一来，我们就变相的得到了 前两个值的幂之间的乘积组合！再搭配 ElGamal 加密中可以把两个值的幂做 线性组合 的属性的话，那么我们就得到了一个 全同态的系统 了。

 事实上，现实并没有那么美好，因为 Pairing 这一特殊属性并 不会出现在 所有的循环群当中。所以如果我们把两个可以做 Pairing 的群中的值通过 Pairing 相乘起来，映射到了一个新的群 G_T 当中之后，那么新的群并不一定能找到对应的 Pairing 属性！

 这一局限性证明了这个系统是 近似同态 的，因为我们不能计算 任意逻辑和深度的函数F。

学习一下 循环群 是什么东西。

六、有限级数全同态加密 Fully Leveled Homomorphic Encryption

 在这一阶段的话，我们已经可以对密文进行 任意的加法乘法组合 了，没有任何对于 次数的局限性。

 但是之所以被称之为 有限级数 全同态的原因是，这个阶段的算法会引入一个新的 复杂度上限 L 的概念，这一复杂度上限约束了函数 F 的复杂度。如果我们可以把 F 用 二进制电路 C 来表示的话，那么 C 的深度和大小 一定要在 L 的范围之内，即：
$$|C|\le L$$ 关于这个复杂度的上限 L 是怎么来的。首先，假如有一个全同态加密的算法，可以对密文进行任何的加法与乘法的运算。但是这个算法在加密的时候会在密文里面加入一定的 随机噪音。

 当噪音在可控范围内的时候，那么解密算法就可以很容易从密文还原回原文。但是当我们 叠加密文在一起进行同态计算 的时候，每一个密文里面自带的噪音会被叠加扩大。如果我们只是对密文进行比较简单的逻辑，那么叠加起来的噪音还在一个 可以接受的范围。但是如果我们过于复杂地堆叠密文在一起，那么一旦 噪音的范围超过了临界值，那么就会彻底的覆盖掉原来的原文，从而导致 解密会失败。
 在这个场景中，这个 同态加密系统 可以接受的 噪音上限 转换为 叠加的逻辑的复杂度 的话就是 L 了。这就是为什么我们只可以进行 复杂度小于 L 的计算，因为一旦复杂度超过 L，我们就再也无法还原回原来的原文了。

七、全同态加密 Fully Homomorphic Encryption, FHE

 一个全同态加密的系统 没有任何计算方法的限制，可以在 没有密钥的情况下，把密文任意的组合起来，形成新的密文，并且新的密文，无论计算的复杂度，都可以完美的被 还原成原文。
 当达到这一阶段时，之前提到的 安全代理计算 就变得可行了。如果可以找到一个 效率比较高的全同态加密体系 的话，我们可以安全的把 所有本地的计算 全部 代理到云端，并且不会泄露任何一丁点数据！

1、全同态加密系统的定义

 一个全同态加密系统，一共拥有四个算法：

1. 密钥生成算法 $KeyGen(1^{\lambda })\to sk$：
   生成加密与解密需要用到的 密钥 sk。为了简单表示，我们这里假设这个加密系统是 对称的 (即加密密钥等于解密密钥)。
2. 加密算法 $Enc(sk,m\in 0,1^{|M|})\to ct$：
   把 原文 m 加密成 密文 ct。
3. 解密算法 $Dec(sk,ct)\to m$：
   把 密文 ct 还原为 原文m。
4. 运算算法 $Eval(F,c{t}_1,...,c{t}_l)\to \widehat{ct}$：
   把 l 个密文 组合起来，通过一个 二进制逻辑电路 F，最后得到 组合的密文 $\widehat{ct}$，使得 $Dec(sk,\widehat{ct})=F(m_1,...,m_l)$。

 我们可以看到，最后一步的运算算法 Eval，就是全同态加密的精髓了。回到上文的例子，如果我们想让 云端的服务器 替我们进行一些机器学习的模型分析，那么在这里，我们只需要 把 模型分析预测的过程 转换为 二进制逻辑电路 F，然后我们 提供加密过后的数据样本 ct₁，ct₂，…，ct_l，然后云端就可以通过 Eval(F, ct₁, …, ct_l) 得到加密的最后预测的结果。

2、全同态加密体系的性质

 现在我们来看看这个系统的 属性 (Properties)。

1. 首先，这个体系必须得是 正确的 (Correctness)。
    也就是说，如果我们任意选择一个 电路 F，并且任意选择 一组 原文消息 m₁, m₂, …, m_l。如果我们拥有一开始 KeyGen 算法 生成的 密钥 的话，那么：
   $$Dec(sk,Eval(F,Enc(sk,m_1),...,Enc(sk,m_l)))=F(m_1,...,m_l)$$
2. 其次，这个系统需要达到 语义安全。这一定义我们上文已经阐述过了。
3. 最后，为了让全同态加密体系变得有实际的使用意义，我们必须还得加一条额外的规定：简短性 (Compactness)。
    也就是说 Eval 这个算法输出的结果必须要 在一个限定范围之内。如果要加一个硬性条件的话，就是 Eval 这个算法的 输出结果大小 必须要 独立于 二进制电路 F 的大小。也就是说，就算 F 再大，Eval 的结果大小也不会有所改变：
   $$\begin{gathered} \forall F,sk,c{t}_i\leftarrow Enc(sk,m_i) \\ |Eval(F,ct1,..,c{t}_l)|=poly(\lambda ) \end{gathered}$$ 关于为什么需要加上 简短性，这是因为，如果没有这个要求，我们可以非常轻易的做出一个 毫无意义 (作弊的) 全同态系统：
   1. 密钥生成、加密算法可以任意选择一个语义安全的对称加密算法。
   2. $Eval(F,c{t}_i)\to (F,c{t}_i)$：运算算法 Eval 要做的事情很简单，直接把对于 F 的描述和 原来的密文 ct_i 全部输出到 新的密文 $\widehat{ct}$ 当中。
   3. $Dec(sk,(F,c{t}_i))\to F(Dec(sk,c{t}_1),...,Dec(sk,c{t}_l))$：最后在解密的时候，先把密文里所有的 ct_i 全部依次解密回原文，然后再根据对 F 的描述手动跑一下 F 得到原来的结果。

这个 poly(λ) 是什么东西？？？？
 这里的 poly(λ) 是指一个多项式函数，该函数的输入是安全参数 λ。通常，安全参数 λ 决定了加密方案的安全性级别，例如密钥的长度或密码系统的其他关键参数。poly(λ) 表示这个函数的复杂度是相对于安全参数 λ 的 多项式增长 的，而不是指数、对数或其他更复杂的增长模式。
 在加密方案的分析中，poly(λ) 通常用于描述算法的运行时间、通信复杂度或密文大小等指标，表明这些指标是与安全参数成多项式关系的。保持复杂度在多项式范围内是衡量加密方案可行性的重要标准之一。

如果没有对与 Eval 输出大小的限制的话，那么我们反复叠加多次 Eval 之后，得到的密文大小将会越来越大。最后解密的时候，只需要把所有的原始密文解开，然后算一下 F 就行了。这就好比是一个用户把自己的健康信息加密了，让医院去判断他有没有生病，医院直接原封不动的把密文送回来，然后把自己的整套数据模型加上医疗课本也发回来，跟用户说，你自己去算吧，是一个意思。

 这一类全同态系统还有一个更大的弊端，也就是最后得到的密文并 无法完全掩盖住运算电路 F 的具体细节。在这个医院的使用场景中，有可能医院自己最值钱的就是这套数据分析系统。如果白白的把自己的 F 发回给了用户，那自己的辛苦劳动成果就被别人轻易窃取了。
 综上所述，只要满足 正确、语义安全、简短 这三个要素，我们就拥有一个 有意义 (Non-trivial) 的全同态加密体系了。