本书介绍了量子算法与量子密码的基础知识,对具有重要密码学应用的Shor算法、Grover算法等典型算法进行具体分析,帮助读者了解这两类量子算法在整数分解、离散对数、SAT、代数方程组等密码数学问题中的具体应用,在此基础上介绍具有理论可证明安全性的密码协议——量子密钥分发协议。本书可作为密码学、信息安全、计算机等专业本科生、研究生的教材,也可作为对量子算法与量子密码感兴趣的计算机学者、数学学者及物理学者的参考书。
马智, 中国科学院信息安全国家重点实验室博士后,信息工程大学教授,工业与应用数学学会编码密码与相关组合理论专委会委员,《信息安全研究》编委,省部级优秀博士学位论文指导教师,省部级优秀硕士学位论文指导教师,获省部级育才奖,行业优秀教师。曾承担国家863课题、国家自然科学基金、国家密码发展基金、省部级重点课题。出版《信息保护:从经典纠错到量子密码》《量子计算数论》。
第1章 绪论 1
1.1 古典密码学 2
1.2 现代密码学 4
1.2.1 私钥密码学 4
1.2.2 公钥密码学 6
1.2.3 安全协议 8
1.3 量子计算对现代密码学的影响 8
1.4 后量子时代密码学 9
第2章 量子力学基础 11
2.1 量子力学革命 11
2.1.1 黑体辐射与量子思想 12
2.1.2 波粒二象性 13
2.1.3 氢原子 15
2.1.4 矩阵力学 16
2.1.5 波动方程 16
2.2 量子力学数学基础 18
2.2.1 线性空间 18
2.2.2 线性算子 27
2.2.3 本征值与本征态 31
2.2.4 张量积 38
2.3 量子力学基本假设 40
2.3.1 波函数假设 40
2.3.2 量子态演化假设 41
2.3.3 算子假设 42
2.3.4 测量假设 43
2.3.5 粒子全同性假设 50
2.4 量子力学基本现象 50
2.4.1 量子力学基本原理 50
2.4.2 量子纠缠及其应用 54
2.4.3 贝尔不等式及其应用 56
习题 60
第3章 量子线路模型 63
3.1 量子门 64
3.1.1 单比特量子门 64
3.1.2 两比特量子门 68
3.1.3 多比特量子门 72
3.1.4 通用量子门组 74
3.2 基于量子线路模型的量子算法 81
3.2.1 量子并行性与黑盒 82
3.2.2 Deutsch-Jozsa算法 83
3.2.3 BV算法 86
3.2.4 量子傅里叶变换 88
3.2.5 Simon算法 92
3.2.6 量子相位估计算法 94
习题 97
第4章 Shor算法及其应用 100
4.1 Shor算法与整数分解问题 100
4.1.1 RSA公钥密码算法 101
4.1.2 经典整数分解算法 105
4.1.3 Shor算法 109
4.1.4 模幂的量子线路实现 117
4.2 Shor算法与离散对数问题 125
4.2.1 离散对数问题 126
4.2.2 DH密钥交换协议和EIGamal公钥密码系统 128
4.2.3 经典离散对数求解算法 133
4.2.4 Shor算法在离散对数问题中的应用 139
习题 145
第5章 量子搜索算法及其应用 148
5.1 搜索算法原理及框架 148
5.1.1 量子Oracle与搜索问题 148
5.1.2 Grover搜索算法框架 151
5.1.3 搜索算法的图形描述 154
5.2 搜索算法分析及示例 156
5.2.1 搜索算法的复杂度 156
5.2.2 搜索算法示例 157
5.2.3 多目标搜索问题 162
5.2.4 搜索算法的最优性 163
5.3 Grover算法与可满足性问题 164
5.3.1 概述 164
5.3.2 可满足性问题 164
5.3.3 量子搜索算法实现 165
5.4 Grover算法求解代数方程组 167
5.4.1 代数方程组问题 167
5.4.2 搜索方程组解的量子线路 169
5.4.3 拓展实例 171
5.5 Grover算法与密钥搜索 172
5.5.1 AES算法简介 172
5.5.2 Grover算法搜索AES密钥框架 173
5.5.3 AES算法的可逆实现 174
5.5.4 Grover算法与Simon算法的结合 182
习题 184
第6章 量子密钥分发技术 186
6.1 经典信息论基础 186
6.1.1 经典香农熵 186
6.1.2 其他经典信息熵 187
6.2 量子信息论基础 188
6.2.1 量子冯·诺依曼熵 189
6.2.2 量子保真度 190
6.2.3 Holevo界 190
6.2.4 典型量子噪声信道模型 192
6.3 QKD协议 193
6.3.1 纠缠光子QKD协议 194
6.3.2 单光子QKD协议 195
6.3.3 连续变量QKD协议 200
6.4 QKD协议理论安全性 203
6.4.1 基于纠缠提纯的安全码率 204
6.4.2 基于信息论的安全码率 205
6.5 QKD系统组成及其实际安全性 207
6.5.1 QKD系统组成 208
6.5.2 QKD系统实际安全性 216
习题 224
后记 225
参考文献 230