密码学基础PDF电子书下载

目 录 1

第1章绪论 1

1.1密码学：概述 1

1.1.1加密机制 2

1.1.2伪随机序列发生器 3

1.1.3数字签名 3

1.1.4容错协议和零知识证明 4

1.2概率论基础知识 6

1.2.1符号约定 6

1.2.2 3个不等式 7

1.3计算模型 9

1.3.1 P？NP与NP-完全 9

1.3.2概率多项式时间算法 10

1.3.3 非均匀多项式时间算法 12

1.3.4难处理假设 14

1.3.5预言机（Oracle Machine） 15

1.4严密处理的目的 15

1.4.1严密处理的需要 16

1.4.2严密处理的实际结果 17

1.4.3保守倾向 18

1.5.1 历史记录 19

1.5其他 19

1.5.2关于进一步阅读的建议 20

1.5.3未决问题 21

1.5.4 习题 21

第2章计算复杂性 23

2.1 单向函数：动机（单向函数的意义） 24

2.2 单向函数的定义 25

2.2.1强单向函数 25

2.2.2弱单向函数 27

2.2.3两个有用的长度协议 27

2.2.4单向函数的候选形式 31

2.2.5 非均匀单向函数 32

2.3弱单向函数隐含强单向函数 33

2.3.1定理2.3.2的证明 34

2.3.2一个有趣的例子 37

2.3.3讨论 38

2.4单向函数的多样性 39

2.4.1*通用单向函数 40

2.4.2单向函数类 41

2.4.3单向函数类的实例 42

2.4.4陷门单向置换 44

2.4.5*无爪（claw-free）函数 46

2.4.6*关于推荐候选式 48

2.5核心断言（Hard-Core Predicates） 49

2.5.1 定义 49

2.5.2任意单向函数的核心断言 50

2.5.3*核心函数 56

2.6*单向函数的有效放大 59

2.6.1构造 60

2.6.2分析 62

2.7其他 67

2.7.1历史记录 67

2.7.2关于进一步阅读的建议 68

2.7.3未决问题 69

2.7.4 习题 70

第3章伪随机发生器 77

3.1启发性讨论 78

3.1.1 随机性的计算逼近 78

3.1.2伪随机发生器的一个严格逼近 78

3.2计算不可分辨性 79

3.2.1定义 79

3.2.2统计相关性 80

3.2.3重复实验不可分辨性 81

3.2.4*电路族不可分辨性 84

3.3.1伪随机发生器的标准定义 85

3.2.5伪随机总体 85

3.3伪随机序列发生器定义 85

3.3.2增加扩展因子 86

3.3.3*不定长输出的伪随机发生器 90

3.3.4伪随机发生器的适用性 90

3.3.5伪随机性和不可预测性 91

3.3.6伪随机发生器隐含着单向函数 94

3.4基于单向置换的构造 94

3.4.1基于单一置换的构造 95

3.4.2基于置换集合的构造 100

3.4.3*应用核心函数而不是核心断言 102

3.5.1利用1-1单向函数 103

3.5*基于单向函数的构造 103

3.5.2利用正则单向函数 107

3.5.3在正则单向函数之后的讨论 112

3.6伪随机函数 113

3.6.1 定义 113

3.6.2构造 115

3.6.3应用程序：一个一般的方法论 119

3.6.4*一般化（普遍化） 120

3.7*伪随机置换 124

3.7.1一些定义 125

3.7.2构造 126

3.8其他 128

3.8.1历史记录 128

3.8.2关于进一步阅读的建议 129

3.8.3未决问题 130

3.8.4习题 130

第4章零知识证明系统 140

4.1零知识证明：动机 141

4.1.1证明的概念 142

4.1.2获得知识 144

4.2.1定义 145

4.2交互证明系统 145

4.2.2一个实例（IP中的图非同构问题） 148

4.2.3*IP类的结构 151

4.2.4模型的扩展 152

4.3零知识证明：定义 152

4.3.1 完备零知识和计算零知识 153

4.3.2 一个例子（PZK中的图同构） 157

4.3.3关于辅助输入的零知识 162

4.3.4零知识证明的顺序合成 164

4.4 NP零知识证明 169

4.4.1承诺方案 170

4.4.2图着色的零知识证明 173

4.4.3普遍结论和一些应用 182

4.4.4二级考虑 185

4.5*否定结果 187

4.5.1交互和随机性的重要性 187

4.5.2无条件结果的限制 188

4.5.3统计零知识证明的限制 190

4.5.4零知识和并行合成 190

4.6*证据不可分辨性和隐藏性 192

4.6.1定义 193

4.6.2并行合成 195

4.6.3构造 196

4.6.4应用 198

4.7*知识证明 198

4.7.1定义 198

4.7.2减少知识误差 202

4.7.3 NP知识的零知识证明 203

4.7.4应用 203

4.7.5身份证明（身份认证机制） 204

4.7.6强知识证明 207

4.8*计算合理性证明（参数） 209

4.8.1定义 210

4.8.2完备隐藏承诺方案 210

4.8.3 NP完备零知识理论 215

4.8.4多项式对数效率的讨论 216

4.9*常数轮零知识证明 217

4.9.1使用完全保密的承诺机制 218

4.9.2限定欺骗证明者的能力 222

4.10*非交互零知识证明 225

4.10.1基本定义 225

4.10.2构造 226

4.10.3扩展 230

4.11.1定义 234

4.11*多证明者零知识证明 234

4.11.2两发送者的承诺方案 236

4.11.3 NP完备零知识 239

4.11.4应用 240

4.12其他 241

4.12.1 历史记录 241

4.12.2关于进一步阅读的建议 242

4.12.3未决问题 243

4.12.4 题 244

A.1.1 素数求模的二次剩余 250

A.1.2在素数求模运算中开方 250

附录A计算数论背景 250

A.1素数 250

A.1.3素性检测器 251

A.1.4素数的均匀选择 252

A.2合数 252

A.2.1合数求模的二次剩余 253

A.2.2合数求模的开方运算 253

A.2.3勒让德和雅克比符号 254

A.2.4布卢姆整数和它们的二次剩余结构 254

B.1加密：摘要 256

B.1.1 定义 256

附录B第2卷摘要 256

B.1.2构造 257

B.1.3防窃听安全性 259

B.1.4一些建议 261

B.2签名：摘要 261

B.2.1定义 262

B.2.2构造 262

B.2.3一些建议 264

B.3密码学协议：摘要 265

B.3.1定义 265

B.3.2构造 266

B.3.3一些建议 267

参考文献 268