课程笔记：全同态加密理论与基础

摘要：本文是郁昱老师同态加密暑期班的课程笔记。郁昱老师是上海交通大学计算机科学与工程系教授，主要从事密码学相关的研究。课程首先介绍了一些密码学的基本概念，然后讲了同态加密的一些基础理论。

1


加密方案和安全概念

1.1 经典加密：One-Time Pad

这是对称加密，两边共享了一个对称的秘钥。优点：信息论意义上的安全性。即c和m的互信息为0。缺点：效率低，需要一个安全通道共享秘钥；为了实现完美安全性，消息与秘钥的长度要相同。

1.2  Public-key Encryption 

非对称加密分为三个过程：密钥生成算法、加密算法、解密算法。

选择明文攻击与选择密文攻击

选择明文攻击（CPA）是指由敌手选择明文并且可以得到对应的密文。选择密文攻击（CCA）是指敌手不仅可以选择明文获得密文，还能选择有限次的密文，获得对应的明文。CCA比 CPA 描述敌手的能力更强。

CPA 安全。我们把选择明文攻击（CPA）描述成一个游戏以方便我们更好的理解。首先声明一点，这个游戏的目的是在选择明文攻击的前提下攻破系统的不可区分性（Indistinguishablity），所以下面简称这个游戏为 IND-CPA。其次，还要定义两个角色挑战者 C 和敌手 A。挑战者（challenger）的任务相当裁判，主持游戏并且对敌手的行为进行反馈。敌手顾名思义，就是去攻击当前系统，而且对于这个游戏来说是采用选择明文攻击的方法进行攻击。游戏的描述如下：

A. 初始化：挑战者 C 创建 IND-CPA 系统，并且将公钥发送给敌手 A。

B. 敌手 A 选择两个长度相同的明文 m0，m1发送给挑战者 C。挑战者 C 随机选择 b∈｛0,1｝，并将 mb加密记作 cb，然后将密文cb发送给敌手 A。

C. 敌手 A 猜测挑战者 C 上一步进行加密的明文是 m0还是 m1，并且将猜测结果输出，输出结果记为 。若 ，那么敌手攻击成功。

确定性加密是非语义安全的

确定性加密方案：加密方案是确定的，每一个明文对应一个密文。敌手在进行不可区分性攻击时，只需重新加密消息后与目标密文进行比对即可。如RSA加密。

概率性加密方案：每次加密时首先选择一个随机数，再生成密文。因此同一个明文加密后的结果不一样。如ElGamal加密。

在存在窃听者时，CPA安全和不可区分性加密等价。任何一个确定性加密方案 都不是CPA安全的，存在窃听者时，没有一种确定性的公钥加密方案具有不可区分性加密。

2

Preliminaries

2.1 不可区分性

对于两个分布X和Y，我们定义他们是-不可区分的 ，如果对于,以及任意时间t :

我们定义完美不可区分、统计意义上不可区分、以及计算安全性如下：

2.2 统计距离

密码学中常用到的统计距离定义如下：

2.3 哈希函数

全域哈希函数

设U为键的全域，H是哈希函数的有限集，H中的哈希函数将U映射到哈希表的槽0, 1, ⋯, m-1里。如果满足
且
我们称H是全域的。等式左边表示把x和y映射到同一个槽的哈希函数的数目。这样的话，如果从H中随机选择一个哈希函数，那么x和y发生碰撞的概率就是1/m。

剩余哈希公式

对于,有t+d比特的min-entropy,

其中A是随机选择，是长度为t, 取值为{0,1}的均匀分布。

3


Homomorphic Encryptions

3.1（全）同态加密算法理论的发展

同态加密的类型

部分同态加密(Partially Homomorphic Encryption，PHE)允许对密文进行一种类型的操作被执行无数次。(即对使用次数没有限制)。
例如加法同态：Paillier算法，乘法同态：RSA算法

特定同态加密（Somewhat Homomorphic Encryption，SWHE) 允许对密文完成有限次的任意操作。（对操作没有限制，但是只能进行有限次）

完全同态加密（Fully Homomorphic Encryption，FHE）允许对密文进行无限次的任意操作。（操作和次数都没有限制）

同态加密主要分为四个步骤：
(1) KeyGen：是为非对称版本的HE生成一对秘密和公共密钥的操作，或为对称版本生成一个单一的密钥;(2) Enc：加密; (3)Dec：解密; KeyGen、Enc和Dec与传统加密方案中的经典任务没有区别。(4) Eval：Eval是一个HE特有的操作，它将密码文本作为输入，并输出对应于一个函数的普通文本的密码文本。

3.2 同态加密的应用

同态加密可以被应用于健康数据、政务数据、金融数据等数据保护场景中。一方面希望保护数据隐私、数据安全，同时又可以将计算任务外包给计算服务商。

3.3 对称与非对称同态加密

对于同态加密，对称加密与公钥加密可以认为是等价的。现在已经有高效的方法将对称同态加密算法转换为公钥同态加密算法。下面说明如何将一个对称加密算法转换为一个公钥加密算法。

1. 公钥生成

生成l个随机比特，以及他们的密文，（l 的长度要远大于密文的长度）

1. 加密

为了加密一比特值, 选择一个随机比特串r，使得, 输出：
（注意：以上是在模2意义上的计算）

4


第一代同态加密方案[GHDV10]

私钥：一个随机选择的大奇数数 n

公钥：整数 这里就是噪声

加密：取集合的一个子集，然后加上消息

解密：这里最低位就是消息m. (这里的计算是先模n , 再模2)

同态运算中的噪声问题

加法：c = c1+c2 , 总噪声是每一项噪声的求和。

乘法：c=c1*c2 , 总噪声是每一项噪声的乘积。

由此我们可以看到，噪声是指数级别增长的，噪声过大会影响最后的解密结果。

END

作者简介：庄智廉：重庆大学大数据与软件学院一年级研究生。主要研究兴趣包括隐私保护机器学习、联邦学习。语雀：阿柴 。知乎：acai

往期精选

联邦学习前沿 | 基于图神经网络的联邦推荐系统研究

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群