密码学基础

作者：(以)Odeb Goldreich著；温巧燕，杨义先译

出版社：人民邮电出版社

出版时间：2003-01-01

ISBN：9787115103550

定价：¥35.00

　　密码学涉及解决安全问题的计算系统的概念化、定义以及构造。密码系统的设计必须基于坚实的基础。本书对这一基础问题给出了系统而严格的论述：用已有工具来定义密码系统的目标并解决新的密码问题。本书集中讨论：计算复杂性（单向函数）、伪随机数以及零知识证明。本书的重点在于澄清基本概念并论述解决密码问题的可行性，而不侧重于描述某种具体方法。本书可作为密码学、应用数学、信息安全等专业的教材，也可作为相关专业人员的参考用书。

　　Oded Goldreich是Weizmann学院计算机科学教授，也是Meyer W.Weisgal Professorial Chair的成员。作为一名活跃的学者，他已经发表了大量密码学论文，是密码学领域公认的世界级专家。他还是Journal of Cryptology、SIAM Journal on Computing杂志的编辑，出版了《现代密码学、概率证明与伪随机数》一书。

第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