第1章 预备知识 1
1.1集合、元组与数制 1
1.1.1集合与元组 1
1.1.2函数 2
1.1.3谓词 3
1.1.4数制与字符串 3
1.2概率基础 5
1.2.1概率的概念 5
1.2.2概率的性质 6
1.2.3常用的概率不等式 7
1.2.4条件概率贝叶斯公式 8
1.3密码学中的证明方法 9
1.3.1归纳法 10
1.3.2反证法 12
1.3.3构造证明 13
1.3.4归约方法 14
1.3.5几种证明方式的总结 16
1.4进一步阅读的建议 18
第2章 理论计算机科学基础 19
2.1基本图灵机 19
2.1.1基本图灵机模型 19
2.1.2基本图灵机的计算 21
2.2图灵机的变形 23
2.2.1非确定图灵机 23
2.2.2多带图灵机 25
2.2.3概率图灵机 26
2.2.4神谕图灵机 27
2.2.5电路计算 29
2.3计算复杂性 30
2.3.1计算复杂性概述 30
2.3.2计算复杂性定义 32
2.3.3计算复杂性类 35
2.4进一步阅读的建议 40
第3章 密码学基础知识 42
3.1数论基础 42
3.1.1因子 42
3.1.2素数 43
3.1.3模运算 43
3.1.4二次剩余 48
3.1.5素数性 49
3.2代数基础 51
3.2.1群的概念 51
3.2.2环及域 53
3.2.3多项式环 54
3.3难解问题 57
3.3.1因子分解假设 58
3.3.2离散对数假设 59
3.3.3Diffie-Hellman问题 60
3.3.4二次剩余问题 61
3.3.5几种难解问题的关系 62
3.4一个小故事 62
3.5进一步阅读的建议 62
第4章 密码学基础 64
4.1对称密码学 65
4.1.1基本概念 65
4.1.2一次一密算法 67
4.2对称密码算法 68
4.2.1对称密码算法简介 68
4.2.2对称密码算法的研究前沿 69
4.3协议 74
4.3.1协议 74
4.3.2协议的分类 76
4.3.3对协议的攻击 78
4.3.4协议设计 78
4.3.5密码学协议的研究前沿 80
4.4进一步阅读的建议 82
第5章 随机性与单向散列函数 84
5.1随机与伪随机 84
5.1.1随机性的概念 84
5.1.2计算不可区分 85
5.1.3采样与计算不可区分 89
5.1.4伪随机性 91
5.2伪随机数生成器 92
5.2.1伪随机数生成器定义 93
5.2.2线性同余发生器 94
5.2.3线性反馈移位寄存器 94
5.2.4混沌序列发生器 95
5.2.5伪随机种子 96
5.2.6伪随机序列应用 96
5.3单向函数与单向散列函数 98
5.3.1单向函数的定义 99
5.3.2弱单向函数 99
5.3.3单向散列函数 101
5.3.4单向散列函数的应用 102
5.3.5陷门单向函数 103
5.4单向散列函数研究前沿 104
5.5进一步阅读的建议 105
第6章 公开密钥算法与数字签名 107
6.1RSA公开密钥算法 107
6.1.1RSA公开密钥算法的构造 107
6.1.2用公开密钥算法通信 108
6.1.3用公开密钥进行密钥分配 108
6.2数字签名 109
6.2.1公开密钥算法用于认证 111
6.2.2DSA数字签名算法 112
6.3研究前沿 113
6.3.1椭圆曲线公开密钥算法 114
6.3.2其他公开密钥算法 118
6.3.3离散对数数字签名 120
6.3.4盲签名 121
6.3.5失败终止签名 122
6.3.6不可抵赖数字签名 125
6.3.7记名签名 126
6.3.8群签名 128
6.4进一步阅读的建议 130
第7章 数字承诺 132
7.1数字承诺的概念 133
7.1.1比特承诺的定义 133
7.1.2完美隐藏的比特承诺 134
7.2数字承诺方案的构造 136
7.2.1用单向置换函数构造比特承诺方案 136
7.2.2用任意单向函数构造比特承诺方案 136
7.2.3用单向置换构造完美隐藏承诺 138
7.3若干种数字承诺方案 139
7.3.1基于对称密码学的承诺 139
7.3.2使用单向函数的承诺 140
7.3.3使用伪随机数生成器的承诺 141
7.3.4一个著名的数字承诺方案 141
7.4承诺的应用 142
7.4.1在零知识证明中的应用 142
7.4.2在硬币抛掷中的应用 143
7.4.3在商业中的应用 144
7.4.4在多方保密计算中的应用 145
7.5承诺技术的研究前沿 145
7.5.1不可关联承诺 145
7.5.2量子比特承诺 153
7.5.3承诺新用途的研究 153
7.6进一步阅读的建议 154
第8章 零知识证明与不经意传输 156
8.1基本概念 157
8.1.1证明者与验证者 157
8.1.2可行性与可靠性 158
8.1.3知识与信息 158
8.2交互证明系统 159
8.2.1交互图灵机 159
8.2.2交互联合计算 160
8.2.3交互证明 160
8.3零知识证明定义 161
8.3.1零知识的含义 162
8.3.2模拟范例 162
8.3.3完美零知识 163
8.3.4计算零知识 163
8.3.5统计零知识 164
8.3.6关于零知识证明的一些结果 171
8.4零知识证明协议举例 172
8.4.1离散对数的零知识证明 173
8.4.2知道某公钥对应的私钥的零知识证明 175
8.4.3n是Blum整数的零知识证明 176
8.4.4哈密尔顿图的零知识证明 177
8.4.5图的三着色的零知识证明 178
8.5零知识证明的研究前沿 180
8.5.1非交互零知识 181
8.5.2顺序零知识 183
8.5.3并行零知识 183
8.5.4寻找零知识的用途 184
8.6不经意传输 185
8.6.1不经意传输的概念 186
8.6.2l-out-of-n不经意传输 190
8.6.3不经意传输的研究前沿 191
8.7进一步阅读的建议 192
第9章 多方保密计算 193
9.1多方保密计算的定义 194
9.1.1定义应考虑的问题 194
9.1.2双方保密计算定义 196
9.2恶意参与者模型 200
9.2.1理想模型 200
9.2.2实际模型 202
9.2.3恶意参与者的安全性定义 204
9.3恶意的参与者 205
9.3.1研究动机与综述 206
9.3.2安全归约 207
9.3.3编译器中使用的函数 208
9.3.4编译器 213
9.3.5编译器的效果 215
9.4一些实际问题的多方保密计算 217
9.4.1百万富翁问题 217
9.4.2两个数相等问题 220
9.4.3计算几何问题 223
9.4.4集合成员判定问题 228
9.4.5集合相交问题 232
9.4.6百万富翁问题高效方案 234
9.4.7多方保密计算的保密性评价 236
9.5研究前沿 240
9.5.1三方以上的保密计算 240
9.5.2恶意参与者的有效计算 242
9.5.3新的多方保密计算问题 242
9.6多方保密计算的应用 243
9.7进一步阅读的建议 244
第10章 量子密码学 246
10.1量子密码 247
10.1.1量子密码简介 247
10.1.2量子密钥分配 250
10.2量子密码与传统密码 253
10.2.1传统密码 253
10.2.2量子密码 255
10.3量子密码研究的前沿问题 255
10.3.1量子信息论 255
10.3.2量子密钥分配 257
10.3.3量子加密 258
10.3.4量子认证 259
10.3.5量子密码安全协议 260
10.3.6量子签名 261
10.4量子密码发展前景 262
10.5进一步阅读的建议 264
参考文献 266