安全多方计算

安全多方计算作为密码协议的一般性理论研究,取得了非常丰富、深刻的研究成果,是密码学基础理论的重要组成部分;由于实际应用的需求,近年来在实用化方面也取得了显著成果.《安全多方计算》旨在对这一研究领域进行梳理,形成一个完整系统的总结,展现其基本思想与方法.《安全多方计算》以安全多方计算的起源和里程碑式的成果为起点,介绍了Yao混淆电路、GMW、BGW等基础协议,严格论述了安全模型及形式化证明方法,并对实用化技术做了详尽分析与介绍.《安全多方计算》由浅入深,逐步引导读者进入安全多方计算理论研究与技术开发前沿,旨在提供一本系统、完整介绍该领域基础理论与应用技术的著作.

目录
“密码理论与技术丛书”序
前言
第1章　引言1
1.1　现代密码学概述1
1.2　安全多方计算的发展概况2
1.3　安全多方计算实用系统研究4
参考文献5
第2章　安全模型及证明技术8
2.1　现代密码学与可证明安全性8
2.1.1　预备知识9
2.1.2　归约证明技术13
2.1.3　模拟证明技术14
2.2　安全多方计算安全模型14
2.2.1　计算任务的定义14
2.2.2　敌手能力的定义16
2.2.3　运行环境定义17
2.2.4　安全目标的定义18
2.2.5　理想/现实模拟的证明思想19
2.3　半诚实敌手模型20
2.3.1　半诚实敌手模型下理想世界协议运行21
2.3.2　半诚实敌手模型下现实世界协议运行22
2.3.3　半诚实敌手模型下基于模拟的安全性定义22
2.4　恶意敌手模型24
2.4.1　恶意敌手模型下理想世界协议运行25
2.4.2　恶意敌手模型下现实世界协议运行27
2.4.3　恶意敌手模型下基于模拟的安全性定义27
2.5　安全多方计算安全模型的进一步讨论28
2.5.1　功能函数的分类及相互转化28
2.5.2　关于敌手修改输入的讨论31
2.5.3　对安全两方计算协议安全性的讨论32
2.6　组合安全性34
2.6.1　混合模型及模块化顺序组合安全34
2.6.2　通用可组合安全39
参考文献41
第3章　相关基本协议与算法42
3.1　承诺42
3.1.1　承诺的概念42
3.1.2　基于密码学Hash函数的比特承诺44
3.1.3　基于离散对数的Pedersen承诺45
3.2　茫然传输46
3.2.1　茫然传输的概念46
3.2.2　基于公钥加密的2选1 OT协议48
3.3　门限秘密共享49
3.3.1　门限秘密共享的概念49
3.3.2　简单加法(n，n)门限秘密共享方案51
3.3.3　Shamir (t，n)门限秘密共享方案52
3.3.4　可验证的秘密共享54
3.4　同态加密55
3.4.1　RSA与ElGamal加密方案的同态性55
3.4.2　Paillier加密方案57
3.4.3　BGN加密方案59
3.4.4　关于同态加密方案的说明61
参考文献61
第4章　零知识证明63
4.1　Schnorr协议64
4.2　交互证明与零知识证明70
4.3　知识证明与知识的零知识证明79
4.4　Σ-协议82
4.4.1　概念82
4.4.2　Σ-协议的组合性86
4.4.3　由Σ-协议构造零知识证明协议89
4.5　非交互零知识证明92
参考文献95
第5章　安全多方计算基础方案97
5.1　百万富翁问题97
5.2　混淆电路与Yao协议98
5.2.1　混淆电路99
5.2.2　Yao协议102
5.3　GMW协议104
5.3.1　4选1茫然传输105
5.3.2　两方场景106
5.3.3　两方场景示例110
5.3.4　多方场景111
5.3.5　GMW协议整体描述113
5.4　BGW协议114
5.4.1　秘密份额状态下电路计算115
5.4.2　BGW协议的整体描述119
5.5　BMR协议120
参考文献126
第6章　半诚实敌手模型安全性证明127
6.1　证明实例——OT?协议127
6.1.1　一个基于DDH问题的OT协议127
6.1.2　OT协议安全性证明130
6.2　Yao协议安全性证明132
6.2.1　Yao协议描述132
6.2.2　Yao协议安全性证明133
6.3　GMW协议安全性证明138
6.3.1　GMW协议描述139
6.3.2　GMW协议安全性证明140
参考文献142
第7章　恶意敌手模型安全性证明144
7.1　GMW编译器概述144
7.2　恶意敌手模型安全性证明简单示例145
7.2.1　知识的零知识证明——DH四元组146
7.2.2　OT协议描述146
7.2.3　OT协议安全性证明147
7.3　Yao协议的恶意敌手模型安全性证明150
7.3.1　基于cut-and-choose技术的Yao协议150
7.3.2　基于cut-and-choose技术的Yao协议安全性证明159
参考文献167
第8章　基于Beaver三元组的实用性协议168
8.1　半诚实敌手模型下安全的Beaver安全多方计算协议169
8.1.1　Beaver三元组169
8.1.2　Beaver三元组的生成169
8.1.3　半诚实敌手模型下Beaver安全多方计算协议176
8.2　恶意敌手模型下安全的BDOZ安全多方计算协议180
8.2.1　预备知识: MAC方案及其安全性181
8.2.2　BDOZ同态MAC方案182
8.2.3　BDOZ认证秘密共享方案186
8.2.4　BDOZ安全多方计算协议189
8.3　恶意敌手模型下安全的SPDZ安全多方计算协议203
8.3.1　SPDZ MAC方案203
8.3.2　基于SPDZ MAC的认证秘密共享方案205
8.3.3　SPDZ安全多方计算协议214
8.3.4　环上的安全多方计算协议224
参考文献225
第9章　安全多方计算实用化技术227
9.1　OT扩展技术227
9.1.1　半诚实敌手模型下安全的Beaver OT扩展协议227
9.1.2　半诚实敌手模型下安全的IKNP OT扩展协议232
9.1.3　恶意敌手模型下安全的KOS OT扩展协议239
9.2　Yao-混淆电路优化技术244
9.2.1　对混淆XOR门的优化244
9.2.2　对混淆表的优化246
9.3　ABY混合框架248
9.3.1　符号约定249
9.3.2　分享类型249
9.3.3　类型转换253
参考文献256
第10章　量子安全多方计算简介258
10.1　量子力学基础知识259
10.1.1　量子力学的数学框架259
10.1.2　不确定性原理261
10.1.3　未知量子态不可克隆261
10.1.4　非正交量子态不可区分261
10.2　常用量子技术262
10.2.1　量子比特及常用的操作262
10.2.2　d级量子系统263
10.2.3　超密编码265
10.2.4　量子隐形传态267
10.2.5　诱骗态269
10.3　典型量子安全多方计算协议270
10.3.1　量子安全多方求和270
10.3.2　量子安全多方求集合交集势和并集势272
10.3.3　量子隐私比对275
10.3.4　量子匿名投票276
10.3.5　量子密封拍卖278
参考文献280
索引283
“密码理论与技术丛书”已出版书目