理性密码学融合了密码学和博弈论的相关知识，针对密码协议中的安全问题进行研究，是密码学领域一个新的研究方向。本书根据理性密码学的**研究进展和作者在理性密码协议设计领域的科研实践，提出理性密码学设计应遵循的原理、机制和方法，并在此基础上设计一系列理性密码协议。本书有助于理性密码学学习者在掌握基本理论和原理基础上，通过具体的理性密码学模型和协议设计过程，较为全面地理解和掌握理性密码学基本原理及在密码协议设计中的具体应用。本书共13章：第1章介绍密码学基础，第2章介绍理性密码协议预防参与者欺诈模型与原理，第3章介绍理性密码协议预防参与者合谋模型与原理，第4章介绍理性密码协议通信网络模型与原理，第5章介绍理性密码协议云外包模型与原理，第6章介绍可证明安全的理性多秘密共享协议，第7章介绍基于双线性对的可验证的理性秘密共享方案，第8章介绍基于椭圆曲线的可验证的理性秘密共享方案，第9章介绍基于移动互联网络的可验证的理性秘密共享方案，第10章介绍云外包秘钥共享方案，第11章介绍基于社交博弈的云外包隐私集合比较协议，第12章介绍理性的百万富翁协议，第13章介绍基于电路计算的理性安全多方求和协议。

本书可作为网络空间安全、密码学和计算机等相关专业本科生、研究生的参考书，也可作为从事网络空间安全与密码学相关研究的技术人员以及对网络安全和密码学感兴趣的专业技术人员的参考书。

序 言

随着云计算、大数据服务和人工智能的日益普及和广泛部署,网络技术和云计算在给人们带来极大便利的同时,也面临许多安全问题。网络攻击、隐私泄露、病毒传播等安全事件频繁爆发。在保障信息安全的诸多技术中,密码协议和算法是核心技术。随着新型网络的蓬勃发展,密码应用领域也不断扩展,已广泛应用于社会经济、文化、科技和军事等领域,成为国家的重要战略资源。

2016年11月7日由第十二届全国人民代表大会常务委员会第二十四次会议通过了《中华人民共和国网络安全法》,并于2017年6月1日起施行。2019年10月26日第十三届全国人民代表大会常务委员会第十四次会议通过了我国密码领域首部综合性、基础性法律《中华人民共和国密码法》,并于2020年1月1日起施行,标志着我国在密码的应用和管理等方面有了专门性的法律保障。以上法律的颁布和实施为保障网络安全、维护网络空间主权和国家安全、规范密码应用和管理,促进密码事业蓬勃发展指明了方向。

经典密码协议分为两种类型:一种是有可信者参与的协议,优点是简单和高效,缺点是在分布式环境下,很难找到大家都信任的可信者,即使能找到这样的可信者,也会成为黑客攻击的对象和性能的瓶颈;另一种是无须可信者参与,由所有参与者共同完成的协议,优点是符合实际,缺点是虽然协议利用可验证的算法能够发现参与者偏离的行为,但仅能在参与者偏离协议的行为发生之后,而不能事先采取预防措施保证参与者没有偏离协议的动机。以上两类协议的缺陷也是经典密码协议难以解决的困难问题。

近年来,国内外密码学界将博弈论与密码学相结合,用博弈的理论和方法针对经典密码协议中存在的问题进行研究。在密码协议中引入博弈论可以改进经典密码协议中的缺陷和不合理的假设,也开辟了密码学一个崭新的研究方向,即理性密码协议,成为密码学界研究的前沿和热门领域。

理性密码学融合了密码学和博弈论的相关知识,针对密码协议中的安全问题进行研究,是密码学领域一个新的研究方向。本书根据理性密码学的最新研究进展和作者在理性密码协议设计领域的科研实践,提出理性密码学设计应遵循的原理、机制和方法,并在此基础上设计一系列理性密码协议。该书有助于理性密码学学习者在掌握基本理论和原理基础上,通过具体的理性密码学模型和协议设计过程,较为全面地理解和掌握理性密码学基本原理及在密码协议设计中的具体应用。本书共13章:第1章介绍密码学基础;第2章介绍理性密码协议预防参与者欺诈模型与原理;第3章介绍理性密码协议预防参与者合谋模型与原理;第4章介绍理性密码协议通信网络模型与原理;第5章介绍理性密码协议云外包模型与原理;第6章介绍可证明安全的理性多秘密共享协议;第7章介绍基于双线性对的可验证的理性秘密共享方案;第8章介绍基于椭圆曲线的可验证的理性秘密共享方案;第9章介绍基于移动互联网络的可验证的理性秘钥共享方案;第10章介绍基于社交博弈的云外包秘钥共享方案;第11章介绍基于社交博弈的云外包隐私集合比较协议;第12章介绍理性的百万富翁协议;第13章介绍基于电路计算的理性安全多方求和协议。

本书作者博士就读于北京工业大学,并在中国科学院信息工程研究所做博士后研究,长期从事网络安全和密码学方向的科研和教学工作。本书是作者在多年理性密码协议研究和设计基础上撰写完成的学术专著,得到国家自然科学基金(U1604156)、河南省科技攻关项目(172102210045)和河南师范大学优秀学术著作出版基金等项目支持,在此向国家自然科学基金、河南省科技厅和河南师范大学等单位表示衷心的感谢! 在本书编写过程中,得到侯缨盈、朱君哲、李会敏、常键、杨刃林、赵乐、林赛戈、侯淑梅、陈宛桢、秦磊勇等人的协助,他们做了大量细致的工作,在此一并表示衷心的感谢!

本书体系完整、条理清晰、内容全面,能够帮助读者理解和掌握理性密码协议原理与协议设计,以便读者能够更容易进入博弈论和密码学交叉学科领域研究。本书可作为网络空间安全、密码学和计算机等相关专业本科生、研究生的参考书,也可作为从事网络空间安全与密码学相关研究的技术人员以及对网络安全和密码学感兴趣的社会人士的参考用书。

由于时间仓促及作者水平有限,书中难免有不妥之处,恳请读者赐教与指正。

作 者

2021年4月

目    录

目 录

第1章 密码学基础    1

1.1 计算理论基础     1

1.1.1 图灵机模型     1

1.1.2 计算复杂性理论    2

1.1.3 可证明安全性理论   7

1.2 加密算法    12

1.2.1 对称加密     12

1.2.2 对称加密的隐患   14

1.2.3 公钥加密体制    15

1.3 承诺方案    17

1.4 同态加密    19

1.4.1 乘法同态加密    19

1.4.2 加法同态加密    19

1.4.3 门限同态加密    20

1.5 零知识证明     21

1.5.1 交互零知识证明   21

1.5.2 非交互零知识证明    22

1.5.3 批处理非交互零知识证明设计   22

1.6 不经意传输     23

1.7 秘密共享    24

1.7.1 秘密共享系统构成    25

1.7.2 秘密共享的存取结构及信息率   26

1.7.3 Shamir门限秘密共享算法   26

1.7.4 可验证秘密共享   27

1.8 快速傅里叶变换     28

1.8.1 傅里叶变换    28

1.8.2 快速傅里叶变换方法    28

1.9 安全多方计算    30

1.9.1 安全多方计算定义   31

1.9.2 安全多方计算攻击者模型    32

1.9.3 通信模型     32

1.9.4 安全模型     32

1.9.5 混淆电路优化历程   33

1.10 本章小结    40

参考文献     40

第2章 预防欺诈模型与原理    45

2.1 防欺诈方案概述     46

2.2 效用、策略及均衡表示模型    49

2.2.1 静态博弈三要素   51

2.2.2 静态博弈常用策略    51

2.2.3 理性密码协议的纳什均衡求解   52

2.2.4 理性密码协议扩展博弈   53

2.3 预防参与者欺诈的策略和效用模型   57

2.3.1 有限轮博弈最优策略模型    57

2.3.2 预防欺诈的策略模型    61

2.3.3 预防欺诈概率效用模型   64

2.4 预防参与者欺诈的博弈模型   65

2.5 本章小结    67

参考文献     68

第3章 预防合谋模型与原理    71

3.1 防合谋方案概述     71

3.2 预防成员合谋的均衡和策略模型   74

3.2.1 帕累托上策均衡模型   74

3.2.2 参与者合谋动机分析模型    75

3.2.3 预防参与者合谋的效用模型   78

3.2.4 可计算防合谋均衡模型    79

3.3 预防合谋的秘密共享博弈模型    83

3.4 预防合谋的安全多方电路计算博弈模型   84

3.4.1 半诚实模型下电路计算模型   84

3.4.2 理性的电路计算模型   87

3.5 本章小结    95

参考文献      95

第4章 网络通信模型与原理    98

4.1 网络通信方案概述    98

4.2 同时广播通信模型与标准点对点通信模型  99

4.2.1 同时广播通信模型    100

4.2.2 标准点对点通信模型   100

4.3 标准点对点通信网络下理性秘密共享模型  105

4.4 标准点对点通信网络下理性安全多方计算模型  107

4.4.1 标准点对点通信网络下逐步释放模型   108

4.4.2 理性安全多方电路计算模型   110

4.5 本章小结    113

参考文献     114

第5章 云外包模型与原理    123

5.1 云外包方案概述     123

5.2 云外包密钥共享框架与模型   126

5.3 云外包安全多方计算框架与模型   127

5.4 理性密码协议云外包模型    129

5.4.1 云外包密码协议防合谋攻击博弈模型   129

5.4.2 云外包密码协议计算公平性   132

5.5 本章小结    136

参考文献     136

第6章 可证明安全的理性多秘密共享协议   139

6.1 秘密共享概述    139

6.2 基础知识    142

6.3 同时广播通信网络下理性多秘密共享协议  144

6.3.1 系统参数     144

6.3.2 秘密分享阶段    144

6.3.3 秘密重构阶段    145

6.4 点对点通信网络下理性多秘密共享协议   146

6.4.1 系统参数     146

6.4.2 秘密分享阶段    146

6.4.3 秘密重构阶段    148

6.5 协议分析    149

6.5.1 正确性分析    149

6.5.2 安全性分析    151

6.5.3 性能分析     154

6.6 本章小结    158

参考文献     158

第7章 基于双线性对的可验证的理性秘密共享方案   163

7.1 可验证秘密共享方案概述    163

7.2 基础知识    165

7.2.1 双线性映射    165

7.2.2 博弈论相关知识   166

7.2.3 Dodis和Yampolskiy方案简介  167

7.3 方案设计    167

7.3.1 系统参数     167

7.3.2 秘密分享阶段    168

7.3.3 秘密重构阶段    168

7.4 方案分析    169

7.4.1 正确性分析    169

7.4.2 安全性分析    170

7.4.3 性能分析与比较   171

7.5 本章小结    172

参考文献     172

第8章 基于椭圆曲线的可验证的理性秘密共享方案   174

8.1 基础知识    175

8.2 方案设计    177

8.2.1 系统参数     177

8.2.2 秘密分享阶段    177

8.2.3 秘密重构阶段    178

8.3 方案分析    178

8.3.1 方案能检验欺骗   179

8.3.2 方案具有公平的性质   179

8.3.3 方案能容忍至多m -1个参与者的合谋

攻击    179

8.4 本章小结    180

参考文献     181

第9章 基于移动互联网络的可验证的理性秘密共享

方案     183

9.1 基础知识    185

9.1.1 Shamir门限秘密共享算法   185

9.1.2 哈希函数     186

9.1.3 双线性对     187

9.2 方案设计    187

9.3 安全证明    192

9.4 方案比较    193

9.5 本章小结    194

参考文献     195

第10章 云外包密钥共享方案    200

10.1 基于半同态的云外包密钥共享方案  200

10.1.1 初始阶段    201

10.1.2 密钥分发阶段   202

10.1.3 云外包计算阶段    202

10.1.4 验证阶段    203

10.1.5 安全分析    203

10.1.6 性能比较    205

10.2 基于多密钥全同态的云外包密钥共享方案   206

10.2.1 密钥分发阶段   206

10.2.2 云外包计算阶段    207

10.2.3 密钥解密验证阶段   207

10.2.4 安全分析    208

10.2.5 性能比较    209

10.3 本章小结     211

参考文献     212

第11章 基于社交博弈的云外包隐私集合比较协议   214

11.1 隐私集合比较协议概述    214

11.1.1 隐私集合交集计算方法   217

11.1.2 本方案设计协议的优点   220

11.2 基础知识     222

11.3 云外包隐私集合比较协议   224

11.3.1 基于半诚实的服务器的云外包隐私集合交集协议    226

11.3.2 基于社交博弈的云外包隐私集合交集协议     227

11.4 安全分析和比较    229

11.4.1 安全分析    230

11.4.2 性能比较    234

11.5 本章小结     236

参考文献     236

第12章 理性的百万富翁协议    241

12.1 百万富翁协议概述    241

12.2 基础知识     243

12.3 百万富翁问题的经典解决方案   245

12.3.1 经典解决方案解析   245

12.3.2 姚期智构造的两方混淆电路协议  246

12.4 协议设计     247

12.5 协议分析     249

12.6 本章小结     252

参考文献     252

第13章 基于电路计算的理性安全多方求和协议  255

13.1 安全多方求和协议概述    255

13.2 基础知识     256

13.3 协议设计     259

13.4 协议分析     261

13.5 本章小结     262

参考文献     262

本书体系完整、条理清晰、内容全面，能够帮助读者理解和掌

握理性密码协议原理与协议设计,以便读者能够更容易进人博弈

论和密码学交叉学科领域研究。本书可作为网络空间安全、密码

学和计算机等相关专业本科生.研究生的参考书,也可作为从事网

络空间安全与密码学相关研究的技术人员以及对网络安全和密码.

学感兴趣的社会人士的参考用书。