Foundations of Cryptography Basic Tools

第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 其他 19

.1.5.1 历史记录 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.2.5 伪随机总体 85

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

3.3.1 伪随机发生器的标准定义 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* 基于单向函数的构造 103

3.5.1 利用1-1单向函数 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 交互证明系统 145

4.2.1 定义 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* 多证明者零知识证明 234

4.11.1 定义 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 计算数论背景 250

a.1 素数 250

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

a.1.2 在素数求模运算中开方 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 第2卷摘要 256

b.1 加密：摘要 256

b.1.1 定义 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