《公钥加密的设计方法》聚焦现代密码学核心——公钥加密, 以可证明安全为经纬, 系统阐释公钥加密方案的设计原理与构造范式, 深度解析易被忽视却至关重要的设计与证明细节. 《公钥加密的设计方法》结构清晰、 内容自洽: *先回顾公钥加密的发展历程; 进而介绍必要的准备知识, 在审视**方案的基础上, 详细介绍基 于各类密码组件的通用设计方法; 随后分别从安全性增强与功能性扩展两 个维度展示公钥加密的重要成果和前沿进展; *后简介标准化与工程实践, 架起理论与实践的桥梁. **成果与现代理论的交织, 为读者呈现了一幅完整的公钥加密领域全景图.

第1章 概述
　　章前概述
　　内容提要
　　公钥密码学的背景与起源
　　公钥加密的研究进展综述
　　本章的1.1节以极简的方式介绍公钥密码学的背景与起源，1.2节综述公钥加密的研究进展.
　　1.1 公钥密码学的背景与起源
　　密码几乎与文字一样古老，并随着时代的变革、技术的进步而持续不断地发展，其发展历程大致可以分为以下两个阶段[1].
　　古典阶段：该阶段密码的内涵局限于加解密，主要应用于军事行动中的保密通信.在古典密码早期，加密方案的安全性依赖于对方案本身的保密，代表性的方案有公元前1世纪出现的Caesar（凯撒）密码，其本质是将字母循环后移三位进行简单的单表代换加密.在古典密码中期，加密方案的安全性摆脱对于系统保密性的依赖，转向对密钥的保密，代表性的方案是1586年出现的多表代换加密的Vigenère（维吉尼亚）密码，其不断重复密钥并与明文进行相加.在古典密码后期，Caesar、Vigenère等密码中蕴含的代换/置换设计思想得到进一步发展，集大成者是**次世界大战时期出现的Enigma（恩尼格玛）密码，其代换规则是动态的，每加密一个字母的消息后，代换规则随内部诸多转子的位置变化动态地改变，从而使代换、置换关系更为复杂.总的来说，古典阶段的密码缺少系统的设计与分析方法，更类似于一种“艺术”而非“科学”，一旦加密方案暴露后，容易受到密码分析而被攻破，陷入“攻破-修复”的循环.
　　现代阶段：随着信息化进程的加速，密码逐渐从军用扩展到商用和民用.1945年，Shannon在著名论文《密码学的数学理论》[2]中*次使用概率论的方法对密码系统的安全性进行了精准的刻画，奠定了现代密码学的基础，使得密码学从“艺术”逐渐走向“科学”. 1973年，Feistel[3]提出了著名的Feistel网络，催生出数据加密标准（data encryption standard，DES），对称密码的设计与分析逐渐系统化. 20世纪70年代后，计算设备的算力遵循摩尔定律持续提升、计算环境由集中式迁移到分布式，信息技术的迅猛发展对密码学提出了新的挑战. 1976年，Diffie与Hellman在划时代的论文《密码学的新方向》[4]中将非对称的思想引入密码学，开创了公钥密码学. 1978年，Rivest，Shamir和Adleman[5]基于数论中的困难问题设计出*个公钥加密方案和数字签名方案. Goldwasser和Micali[6]给出了公钥加密的合理安全性定义——语义安全，同时开创了可证明安全的方法（即采用计算复杂性理论中的归约技术将密码方案的安全性严格归结为计算困难问题的复杂性），并基于二次剩余假设构造出*个满足语义安全的概率公钥加密方案——Goldwasser-Micali PKE.此后，在公钥密码学的推动下，密码学科迅猛发展、内涵加深、外延丰富，从加密、签名和密钥交换扩展到零知识证明[7]、安全多方计算[8]等.总的来说，区别于古典阶段密码设计的随意，现代密码学与复杂性理论结合紧密，具备严谨的可证明安全，各类密码组件/方案与困难问题之间以归约为桥梁，形成精密的归约网络.
　　1.2 公钥加密的研究进展综述
　　自Diffie和Hellman发表划时代论文[4]后，公钥密码学的发展一日千里、日新月异，热潮持续至今，始终是现代密码学的核心和重要技术的摇篮.公钥加密又是公钥密码学的核心，它的发展有两条主线[1]：一条是安全性的增强，从*初的直觉安全演进到严格健壮的语义安全，再到不可区分选择密文安全和各类超越传统安全模型的高级安全，如选择打开安全、抗泄漏安全、抗篡改安全和消息依赖密钥安全;另一条是功能性的丰富，从*初不具有密钥委派功能的一对一加解密到能委派身份密钥的身份加密，再到具有细粒度访问控制功能的属性加密乃至极致泛化的函数加密以及可对密文进行公开计算的（全）同态加密等.本书将按照这两条主线（如图1.1所示）梳理公钥密码学的发展历程，介绍重要的成果.
　　图1.1 公钥加密的两条发展主线
　　1.2.1 安全性增强
　　对于密码方案，给出恰当的安全性定义至关重要，安全性定义必须足够强以刻画现实中存在的攻击.但是通常很难直接构造满足强安全性的密码方案，强安全性的公钥加密方案的构造往往建立在弱安全性的公钥加密方案之上.对应到公钥加密的发展历程，公钥加密的安全性定义亦是从弱到强逐渐演化的.
　　1982年，Goldwasser和Micali[6]发展了可证明安全的技术框架：建立安全模型以准确刻画敌手的攻击行为和攻击效果，将密码方案的安全性归约到计算困难问题的困难性上. Goldwasser和Micali指出单向安全并不是加密方案的合理安全性，他们提出了语义安全性（semantic security）以及等价的另一个定义——选择明文攻击下的不可区分性（indistinguishability against chosen-plaintext attack，IND-CPA）. IND-CPA安全要求密文在计算意义下不泄漏明文的任何一比特信息.相比基于模拟方式定义的语义安全，IND-CPA安全基于安全游戏定义，在归约证明中更容易使用，因此应用广泛.随着密码分析技术的发展，研究人员发现IND-CPA安全无法抵御现实世界中存在的新型攻击，进而陆续提出了多种增强的安全性.以下简介公钥加密的几种重要的增强安全性质.
　　选择密文安全. IND-CPA安全仅考虑被动敌手，即敌手只窃听信道上的密文. 1990年，Naor和Yung[9]指出敌手有能力发起一系列主动攻击，比如重放密文、修改密文等，进而提出选择密文攻击（chosen-ciphertext attack，CCA）刻画这一系列主动攻击行为，即敌手可以自适应地访问解密谕言机，获取密文对应的明文.对应的安全性称为选择密文攻击下的不可区分性（indistinguishability againstchosen-ciphertext attack，IND-CCA），即IND-CCA安全.若限制敌手只可在观测到挑战密文之前访问解密谕言机，对应的安全性弱于标准的IND-CCA安全，称为IND-CCA1安全. 1998年，Bleichenbacher[10]展示了针对PKCS #1标准中公钥加密方案的有效选择密文攻击，实证了关于IND-CCA安全的必要性.从此，IND-CCA安全成了公钥加密方案的事实标准.获得IND-CCA安全的公钥加密方案有以下主流路线.
　　随机谕言机模型下：
　　基于陷门置换构造IND-CCA安全的PKE. Bellare和Rogaway[11]提出了随机谕言机模型（random oracle model，ROM），而后在文献[12]提出了一种基于陷门置换构造IND-CCA安全的PKE方案的方法，即*优非对称加密填充（optimal asymmetric encryption padding，OAEP）. Shoup[13]指出OAEP并不适用于所有的陷门置换. Fujisaki等[14]明确了OAEP的适用条件，并提出了基于RSA类型陷门置换的RSA-OAEP方案.
　　基于IND-CPA安全的PKE构造IND-CCA安全的PKE. Fujisaki和Okamoto[15]提出了在ROM下利用混合加密将IND-CPA安全的PKE方案提升为IND-CCA安全的PKE方案的通用转换，其核心思想是引入哈希函数绑定密文的各部分使得密文不可延展. Fujisaki和Okamoto随后[16]进一步弱化了底层PKE方案的安全性，将其从IND-CPA安全减弱为单向安全，这一通用转换也被称为FO转换[16，17].类似的通用转换还有许多，但就蕴含的思想而言，其核心思想均与FO转换相似，如Okamoto和Pointcheval[18]提出的快速强化安全的非对称密码转换（rapidenhanced-security asymmetric cryptosystem transform，REACT）通用转换.后续工作着力于提升FO转换的效率[19-21]及扩展应用范围[22].
　　标准模型下：
　　使用非交互式零知识证明将任意IND-CPA安全的PKE方案强化为INDCCA安全. Naor和Yung[9]*次提出双密钥加密策略结合非交互式零知识证明（non-interactive zero-knowledge proof，NIZK）将任意IND-CPA安全的PKE方案强化为IND-CCA1安全; Dolev，Dwork和Naor[23]设计出矩阵式加密结构，结合一次性签名（one-time signature，OTS）和NIZK将任意IND-CPA安全的PKE方案提升至IND-CCA安全;受上述两个工作启发，Sahai[24]展示如何用OTS将普通NIZK强化为具有模拟可靠性（simulation soundness，SS）的NIZK，以此为工具应用Naor-Yung双重加密范式，将任意IND-CPA安全的PKE方案强化为INDCCA安全. Biagioni等[25]和Cramer等[26]分别给出了Naor-Yung双重加密范式的两个变体，前者对加密随机数进行了安全的重用，后者使用了新的加密重复策略和消息一致性证明方法.
　　基于弱化的非交互式证明系统构造IND-CCA安全的PKE. Cramer和Shoup[27]提出了一种特殊的指定验证者非交互式零知识证明（designatedverifierNIZK，DV-NIZK）——哈希证明系统（hash proof system，HPS），并基于HPS给出了一类基于判定性困难问题的IND-CCA安全的PKE方案的通用构造. Wee[28]提出了一种特殊的指定验证者非交互式零知识知识证明系统——可提取哈希证明系统（extractable HPS，EHPS），并基于EHPS给出了一类基于搜索性困难问题的IND-CCA安全的PKE方案的通用构造.
　　基于结构更丰富的加密方案构造IND-CCA安全的PKE. Boneh等[29]以身份加密（identity-based encryption，IBE）为底层方案，结合OTS或消息验证码（message authentication code，MAC）构造出IND-CCA安全的PKE方案. Kiltz[30]将IBE弱化为基于标签的加密（tag-basedencryption，TBE），结合OTS构造出IND-CCA安全的PKE方案.基于更强的陷门函数. Peikert等[31]提出了陷门函数及其构造IND-CCA安全的PKE方案的方法.后续工作进一步减弱了有损陷门函数的结构性质[32，33].*近的突破性结果是Hohenberger等[34]展示了如何仅基于单射陷门函数构造IND-CCA安全的PKE方案.
　　基于iO的编译器. Sahai和Waters[35]引入了可穿孔伪随机函数，借助不可区分混淆（indistinguishability obfuscation，iO）构造出IND-CCA安全的PKE方案.该构造实现了Diffie和Hellman自1976年起的愿景，展示了如何将对称加密编译为公钥加密.
　　基于可公开求值伪随机函数. Chen等[36]提出了可公开求值伪随机函数，并基于此给出了PKE方案的通用构造.该构造不仅从更抽象的层次阐释了**的GM加密方案[6]和ElGamal加密方案[37]的设计思想，还统一了基于（可提取）哈希证明系统、陷门函数、可穿孔伪随机函数与iO的构造.
　　选择打开安全. IND-CPA安全模型和IND-CCA安全模型刻画了两方分布式场景下的安全性.然而在现实世界中，PKE方案也常会应用于多方分布式场景中，此时需要抵御更强有力的攻击.例如，在多方协议的某轮执行过程中，n 1个参与方使用某用户的公钥对某轮协议中相

目录
“密码理论与技术丛书”序
前言
第1章概述1
1.1公钥密码学的背景与起源1
1.2公钥加密的研究进展综述2
1.2.1安全性增强3
1.2.2功能性丰富12
第2章准备知识20
2.1符号、记号与术语20
2.2可证明安全方法22
2.2.1基于归约的安全性证明22
2.2.2安全性证明的组织方式24
2.3复杂性理论初步28
2.3.1计算性困难问题28
2.3.2判定性困难问题29
2.4困难问题30
2.4.1整数分解类假设30
2.4.2离散对数类假设34
2.4.3格类假设36
2.5信息论工具39
2.5.1熵的概念39
2.5.2随机性提取41
2.6密码组件42
2.6.1数字签名方案42
2.6.2身份加密方案43
2.6.3非交互式密钥协商方案46
2.6.4伪随机函数及其扩展48
2.6.5非交互式零知识证明52
第3章**公钥加密方案回顾55
3.1公钥加密的定义与基本安全模型55
3.1.1公钥加密方案55
3.1.2密钥封装机制60
3.1.3两类混合加密范式的比较64
3.2基于整数分解类难题的**方案65
3.2.1Goldwasser-Micali PKE65
3.2.2Rabin PKE67
3.3基于离散对数类难题的**方案68
3.3.1ElGamal PKE68
3.3.2Twisted ElGamal PKE70
3.4基于格类难题的**方案73
3.4.1Regev PKE73
3.4.2GPV PKE76
第4章公钥加密的通用构造方法79
4.1非交互式零知识证明类.79
4.1.1Naor-Yung范式79
4.1.2Dolev-Dwork-Naor范式85
4.1.3Sahai范式90
4.2陷门函数类92
4.2.1基于陷门函数的构造92
4.2.2基于有损陷门函数的构造97
4.2.3基于相关积陷门函数的构造106
4.2.4基于自适应陷门函数的构造109
4.3哈希证明系统类123
4.3.1哈希证明系统的起源释疑125
4.3.2哈希证明系统的实例化126
4.3.3基于哈希证明系统的构造129
4.4可提取哈希证明系统类136
4.4.1可提取哈希证明系统的起源释疑137
4.4.2可提取哈希证明系统的实例化138
4.4.3基于可提取哈希证明系统的构造139
4.5程序混淆类148
4.5.1程序混淆的定义与安全性148
4.5.2基于不可区分程序混淆的构造152
4.6可公开求值伪随机函数类157
4.6.1可公开求值伪随机函数的定义与安全性158
4.6.2基于可公开求值伪随机函数的构造161
4.6.3可公开求值伪随机函数的构造162
第5章公钥加密的安全性增强170
5.1抗泄漏安全170
5.1.1抗泄漏安全模型172
5.1.2基于哈希证明系统的构造173
5.1.3基于有损函数类的构造179
5.1.4基于不可区分程序混淆的构造207
5.2抗篡改安全216
5.2.1抗篡改安全模型216
5.2.2基于自适应陷门关系的构造217
5.2.3基于不可延展函数的构造221
5.3消息依赖密钥安全233
5.3.1消息依赖密钥安全模型234
5.3.2基于输入同态哈希证明系统的构造236
5.3.3基于密钥同态哈希证明系统的构造241
第6章公钥加密的功能性扩展248
6.1可搜索公钥加密248
6.1.1可搜索公钥加密的定义与性质250
6.1.2基于匿名身份加密的构造254
6.1.3公钥加密与可搜索公钥加密的功能结合257
6.1.4可搜索公钥加密的安全性增强268
6.2代理重加密280
6.2.1代理重加密的定义与性质282
6.2.2基于公钥加密的构造288
6.2.3基于双线性映射的构造291
6.3可托管公钥加密302
6.3.1基于公钥加密和非交互式零知识证明的构造304
6.3.2基于三方非交互式密钥协商和对称加密的构造305
第7章公钥加密与身份加密312
7.1基于程序混淆的升级313
7.2基于随机谕言机模型的升级316
第8章公钥加密的标准化及工程实践322
8.1公钥加密的标准化322
8.1.1国内外标准化组织简介322
8.1.2公钥加密标准化方案324
8.2公钥加密的工程实践.326
8.2.1重要方案的优秀开源实现326
8.2.2重要的开源密码库326
8.3公钥加密的工程实践经验327
参考文献330
索引359
“密码理论与技术丛书”已出版书目361