全同态加密入门

前言

大数据浪潮下的隐私保护已经成为无数网民亟待解决的问题，由此21世纪初出现了全同态加密的多种方案。本博客旨在梳理全同态加密的发展脉络，结合陈智罡老师的《全同态加密——从理论到实践》记录自己的学习历程

引言

为什么需要全同态加密

结合网络通信中数据的生命周期异或是存在形式，大致分为三种形态：传输、存储和计算。数据在传输过程中可以用AES进行加密，再用RSA对密钥进行加密。数据存储也可以加密，比如windows里面的bitlocker对磁盘加密。唯一亟待解决的就是数据在计算时怎么加密。传统的密码在对密文进行计算的时候，必须先对密文进行解密，再进行运算。密文解密了就有泄漏的风险，于是密码学家就开始想能不能直接在密文上面进行运算而无需解密。如果能解决这个问题，就能够解决数据计算时隐私保护的问题，从代数角度来看就是同态性。

1978年，Rivest、Adleman和Shamir（即RSA提出者）提出了隐私同态加密，也就是现在所说的全同态加密。当时RSA只满足乘法同态性，实现全同态加密成为当时的一个开放难题。

什么是全同态加密

根据上面的例子不难得出，全同态加密指在不解密的情况下，能够对密文执行任意计算。对任意有效函数$f$和明文$m$，用符号定义为：

$\forall f,m\ E(f(m))=f(E(m))$

同态加密发展历程

全同态加密入门

概念定义

首先要认识几个名词，如果不能理解，请先认为它是正确的~~(至少我是这样做的)~~：

1、噪声：是密文中的一部分，初始同态加密后，这个噪声是比较小的。它是基于格密码引出的概念，其有利有弊。算法的安全性大多数是基于一个困难的数学问题，最初引入噪声是基于LWE问题，引入一个小的噪声就能使整个密文解密起来非常困难，保障算法的安全性。但是由于同态加密运算，尤其是乘法运算，会导致密文中的噪声大大增加，若密文的噪声淹没了明文部分，就会导致解密出来的结果出现问题。如下图所示：

2、传统加密算法主要由三个部分组成：密钥生成、加密算法和解密算法。全同态加密算法增加了密文计算算法，该算法是同态加密算法的核心。目前提出的同态加密算法都是基于公钥的同态加密，有没有基于私钥的同态加密算法呢？2011年Rothblum在TCC会议上提出了任一基于私钥的同态加密算法都可以转化为基于公钥的同态加密算法。

• 密钥生成算法(KeyGen)：生成公钥(Public Key,pk)和私钥(Secret Key,sk)，公钥用于加密数据，私钥用于解密数据。同态加密除了生成公钥和私钥之外，密钥生成算法还要生成一个密文计算公钥(Evaluate Key,Evk)，该公钥用于进行密文计算，最主要的作用是为了降低噪声。保证密文能进行无限制的运算。
• 加密算法(Enc)：和传统的密码一样，用于加密明文，使用加密算法得到的密文叫做"新鲜"密文，即该密文是一个初始密文，没有和其他密文进行运算过。"新鲜"密文的噪声称作初始噪声。
• 解密算法(Dec)：和传统的密码一样，用于解密密文，它不仅能对初始密文进行解密，也能对计算后的密文进行解密。若噪声超过上限，解密可能会失败。
• 密文计算算法(Evaluate)：该算法是同态加密的核心，该算法有三个输入：密文计算公钥Evk、密文之间运算函数$f$ 和执行密文运算的密文$C$。

3、部分同态加密(Partially Homomorphic Encryption,PHE)：指只满足加法或者乘法一种运算的加密算法。如加法同态加密Paillier算法，乘法同态加密Elgamal、RSA算法等。

4、近似同态加密(Somewhat Homomorphic Encryption,SHE)：这一阶段距离想要实现的全同态更近了一步。如果有近似同态加密算法的话，那么就可以在密文上同时计算加法与乘法了。但是需要注意的是，正因为这一阶段是近似同态（Somewhat Homomorphic）的，所以可以做的加法和乘法次数非常有限，可以计算的函数 F 也在一个有限的范围内。

5、层级全同态加密(Leveled Fully Homomorphic Encryption,LFHE)：已经可以对密文进行任意的加法乘法组合了，没有任何对于次数的局限性。

但是之所以被称之为层级全同态的原因是，这个阶段的算法会引入一个新的复杂度上限$L$的概念，这一复杂度上限约束了函数$F$ 的复杂度。如果我们可以把$F$ 用二进制电路$C$ 来表示的话，那么$C$ 的深度和大小一定要在$L$的范围之内，即：$|C|\leq L$

6、全同态加密(Fully Homomorphic Encryption，FHE)：千呼万唤始出来，顾名思义，FHE支持对密文任意次数的运算。

电路模型

上述谈到LFHE的时候提及了二进制电路$C$，事实上2009年Gentry提出的全同态加密方案就是基于电路模型提出的。为什么要采用电路模型呢？传统的密码学都是基于数论观点，但是密码学真正的落脚点应该是计算复杂度。密码学所有方案都应该依赖于一个数学难题，这是安全性的根本。电路观点是一中计算复杂度的模型，用途是衡量问题所需要的资源，例如时间、存储量等。在电路模型下，可以通过门电路的深度、数量来衡量。而且电路模型在计算的时候需要电路**“接触”**到运算的数据，因此不会泄露任何信息。

构造框架

密码学的安全性是基于困难问题之上，全同态加密亦是如此：理想格(ideal lattice)、LWE(Learning With Errors)问题和RLWE(Ring Learning With Errors)问题，还有一种是基于近似GCD问题。

全同态加密的发展大致分为三代：

• 2009年Gentry提出了基于理想格的全同态加密方案，我们通常称之为第一代全同态加密方案。构造思想如下：
  先构造一个SHE方案，其安全性基于最近向量问题(closest vector problem, CVP).由于噪声增长的原因，该方案只能执行有限次同态加法和乘法。
  其次当噪声快淹没明文的时候，采用**自举(Boostrapping)**技术来削减噪声，其本质是对密文进行一次同态解密。由于此处是构造全同态加密方案的核心，因此值得再用一篇文章来深入理解这个技术。参照深入理解Boostrapping技术
• 第二代全同态加密方案是基于LWE问题，该问题是由Regev在2005年提出。对于两个LWE密文向量$(c_{11},c_{12})$和$(c_{21},c_{22})$，私钥$(s_{11},s_{12})$