其他
课程笔记：全同态加密理论与基础
摘要：本文是郁昱老师同态加密暑期班的课程笔记。郁昱老师是上海交通大学计算机科学与工程系教授，主要从事密码学相关的研究。课程首先介绍了一些密码学的基本概念，然后讲了同态加密的一些基础理论。
加密方案和安全概念
1.1 经典加密：One-Time Pad
1.2 Public-key Encryption
非对称加密分为三个过程：密钥生成算法、加密算法、解密算法。
选择明文攻击与选择密文攻击
确定性加密是非语义安全的
确定性加密方案：加密方案是确定的，每一个明文对应一个密文。敌手在进行不可区分性攻击时，只需重新加密消息后与目标密文进行比对即可。如RSA加密。
概率性加密方案：每次加密时首先选择一个随机数，再生成密文。因此同一个明文加密后的结果不一样。如ElGamal加密。
在存在窃听者时，CPA安全和不可区分性加密等价。任何一个确定性加密方案 都不是CPA安全的，存在窃听者时，没有一种确定性的公钥加密方案具有不可区分性加密。
Preliminaries
2.2 统计距离
密码学中常用到的统计距离定义如下：
2.3 哈希函数
且
我们称H是全域的。等式左边表示把x和y映射到同一个槽的哈希函数的数目。这样的话，如果从H中随机选择一个哈希函数，那么x和y发生碰撞的概率就是1/m。
其中A是随机选择，是长度为t, 取值为{0,1}的均匀分布。
Homomorphic Encryptions
3.1（全）同态加密算法理论的发展
部分同态加密(Partially Homomorphic Encryption，PHE)允许对密文进行一种类型的操作被执行无数次。(即对使用次数没有限制)。
例如加法同态：Paillier算法，乘法同态：RSA算法
特定同态加密（Somewhat Homomorphic Encryption，SWHE) 允许对密文完成有限次的任意操作。（对操作没有限制，但是只能进行有限次）
同态加密主要分为四个步骤：
(1) KeyGen：是为非对称版本的HE生成一对秘密和公共密钥的操作，或为对称版本生成一个单一的密钥;(2) Enc：加密; (3)Dec：解密; KeyGen、Enc和Dec与传统加密方案中的经典任务没有区别。(4) Eval：Eval是一个HE特有的操作，它将密码文本作为输入，并输出对应于一个函数的普通文本的密码文本。
3.2 同态加密的应用
3.3 对称与非对称同态加密
对于同态加密，对称加密与公钥加密可以认为是等价的。现在已经有高效的方法将对称同态加密算法转换为公钥同态加密算法。下面说明如何将一个对称加密算法转换为一个公钥加密算法。
公钥生成
加密
（注意：以上是在模2意义上的计算）
第一代同态加密方案[GHDV10]
私钥：一个随机选择的大奇数数 n
同态运算中的噪声问题
加法：c = c1+c2 , 总噪声是每一项噪声的求和。
乘法：c=c1*c2 , 总噪声是每一项噪声的乘积。