导论
第零节：导论
why
I collect these awesome materials here to review them from time to time.
I think it will be helpful to those who share the same interests as me.
简单来说，密码学是一种用来研究如何加密来保护信息，如何解密获取信息的学问。
为什么学密码
可以了解、开创并实现现代密码学的 RSA 算法、未来将抵御量子计算机的格密码等的「后量子密码技术」，
以及学到在特殊情况下我们用现代计算机来破解特定的 RSA 现代密码和后量子密码技术的攻击手段。
密码学基础
- 模运算
- 逆元计算
- RSA 公钥加密算法
- 理解海纳百川的k和无所不能的公因数
密码学导论
相关推荐
密码学领域一直以来有两个非常著名的公开课。一个是斯坦福大学教授Dan Boneh在Coursera上的公开课《Cryptography I》。
另一个著名的公开课就是Jonathan Katz教授的《Cryptography》。
- Dan Boneh 教授的公开课 《Cryptography I》。这门课程已经包含密码学中常见概念的介绍，包括 Stream Cipher、Block Cipher、Message Integrity、Authenticated Encryption、Basic Key Exchange、以及 Public-Key Encryption。
- 哔站的中文翻译版本：《bilibili》。
- Jonathan Katz教授的《Cryptography》。
- Jonathan Katz 教授和 Yehuda Lindell 教授撰写的《Introduction to Modern Cryptography, 2nd Edition》。这本书足够新，写得足够好、论述得足够深。最为重要的是，这本书通俗易懂地讲解了密码学的核心概念，以及安全性证明的核心思路。
- 密码学的基本知识学习， Udacity的公开课《Applied Cryptography》。这门课，一共有10个Lessons，涵盖了古典密码学、对称密码学、非对称密码学、密钥协商、秘密分享及其应用、乃至电子货币、区块链、安全多方计算等前沿密码学研究领域。
- David Evans课程的讲义：crypto-notes.pdf
（公钥）密码学安全性证明
推荐资料
- Victor Shoup 教授的论文《Sequences of Games: A Tool for Taming Complexity in Security Proofs》。这篇论文不会让安全性证明变得简单，但是会讲解怎么更系统地整理证明思路，把细节一步步有调理的放在一串攻击者与仿真者的游戏里。读完里面关于RSA 和 ElGamal 安全性证明的“改写”，会对原先的证明过程有全新认识。
- Fuchun Guo、Willy Susilo、Yi Mu 的著作《Introduction to Security Reduction》。这本书最突出的特点是对几乎所有安全性证明写得非常好的方案进行了完整的讲解，如数字签名中随机预言模型下的 Boneh-Lynn-Shacham方案、标准模型下的 Boneh-Boyen 方案；公钥加密方案中第一个选择密文安全的 Cramer-Shoup 方案、第一个基于身份加密（Identity-Based Encryption，IBE）方案 Boneh-Franklin 方案、标准模型下两个 IBE 方案 Waters 方案和 Gentry 方案。这几个方案所对应原始论文的安全性证明都写得非常清晰，建议精读。
- Cramer-Shoup 方案的论文。相比于近些年来动辄数十页甚至上百页的论文来说，这篇论文的长度会短得多，阅读起来会显得轻松不少。这篇论文的安全性证明堪称范本，应用单个游戏的模式完成了安全性证明，描述非常清晰，很容易理解证明思路。
- Lewko-Waters 方案论文, 有关逐个游戏迭代模式的安全性证明. 这篇论文应用对偶证明方法，在合数阶双线性群下将 Boneh-Boyen-Goh 选择性安全（Selectively Secure）的层次基于身份加密（Hierarchical Identity-Based Encryption，HIBE）方案转换成了适应性安全（Adaptively Secure）的HIBE 方案。对偶证明方法需要以逐个游戏迭代模式完成证明
- 有关通用密码学协议的安全性证明学习，推荐 Yehuda Lindell 的文章《How To Simulate It – A Tutorial on the Simulation Proof Technique》。这是目前为止唯一一个针对密码学协议，以教程
（Tutorial）的形式分析仿真安全性证明方法的文章。全文从半诚实攻击者攻击下安全的不经意传输协议（Oblivious Transfer Secure against Semi-Honest Adversary）这一最基础的协议开始，到混合模型下的证明（Security in Hybrid Model ），再到 顺序 组合 定理（ Sequential Composition Theorem）和针对恶意攻击者攻击的转换方法，最后在结尾简要介绍了通用组合性（Universal Composition）的概念，每一步的讲解都极尽精准和详细。 - Dan Boneh和Vector Shoup 撰写的密码学研究生教材《A Graduate Course in Applied Cryptography》, 这是一本非常全面的密码学教材。
- 新生代密码学家Mike Rosulek的教材《The Joy of Cryptography》。
密码学基础指南
Oded Goldreich 教授是密码学先驱科学家，他的学生们联合起来，
于 2017 年撰写了一本有关高级密码学理论和计算复杂性的研究生教材，
教材名称为《Tutorials on the Foundations of Cryptography》,
教材涵盖了当前密码学的几大分支领域：安全多方计算中的乱码电路、公钥密码学、伪随机函数、单向函数、同态加密、仿真证明技术、
差分隐私，对应的章节名称分别为：《Garbled Circuits as Randomized Encodings of Functions: a Primer》、
《The Complexity of Public-Key Cryptography》、《Pseudorandom Functions: Three Decades Later》、
《The Many Entropies in One-Way Functions》、《Homomorphic Encryption》、
《How to Simulate It: A Tutorial on the Simulation Proof Technique》、
《The Complexity of Differential Privacy》。
细分领域入门材料
密钥协商与密钥交换
推荐 Mihir Bellare、David Pointcheval 和 Philip Rogaway 撰写的论文
《Authenticated Key Exchange Secure against Dictionary Attacks》[8]
和Tibor Jager、Florian Kohlar、Sven Schäge、Jörg Schwenk 撰写的论文
《On the Security of TLS-DHE in the Standard Model》
差分隐私
建议直接阅读 Kunal Talwar 和 Frank McSherry 撰写的论文《Mechanism Design via Differential Privacy》。
这篇论文提出了差分隐私中最重要的机制之一，指数机制（ Exponential Mechanism）。
几乎所有ϵ-差分隐私机制都可以看成指数机制的特例，因此理解指数机制也意味着基本可以理解差分隐私的核心思想。
如果仍然不能很好地理解差分隐私的概念，可以尝试阅读 Ninghui Li、Wahbeh H. Qardaji、Dong Su 等人的论文
《Membership Privacy: A Unifying Framework for Privacy Definitions》。
此篇论文提出了成员隐私（Membership Privacy）的定义。相比差分隐私，
成员隐私应用先验概率和后验概率之间的关系描述隐私保护程度。这篇论文可以帮助我们从更广义的层面理解差分隐私.
不经意随机存取机
建议从 Oded Goldreich 和 Rafail Ostrovsky 的论文《Software Protection and Simulation on Oblivious RAMs》[28]开始。这篇论文首次提出了 ORAM 的概念，虽然篇幅稍长 ， 但无论是RAM模型（RAM Model ）或者是不经意性（Obliviousness），论文中都给出了非常详细的定义和解释.
其它相关材料介绍
其它推荐材料
- 《 An Introduction to Mathematical Cryptography 》， Jeffery Hoffstein、Jill Pipher、Joseph Silverman 著.
- 《 Understanding Cryptography: A Textbook for Students and Practitioners》，Chirstof Paar、Jan Pelzl 等著
- “ A Few Thoughts on Cryptographic Engineering ”， Matthew Green。著名密码学家 Matthew Green 的博客
入门后精读的材料
- 《Foundations of Cryptography》，Oded Goldreich 著。这本书是 Oded Goldreich 撰写的重量级著作，分为两卷，第一卷讲解基础工具，第二卷讲解基础应用。这本书适合资深科研人员，概念密度很大，表述略显精简，需要一句一句精读。这本书是入门时学习的必备辅助材料，尤其研究安全多方计算，这本书是不可或缺的。
- 《The Algorithmic Foundations of Differential Privacy》，CynthiaDwork、Aaron Roth 著。虽然是差分隐私提出者 Cynthia Dwork研究员本人亲自撰写的书籍，书籍的描述非常严谨、准确，但这本书的阅读难度非常大。建议直接阅读相应技术的论文，当在相关公式、引理、定理等的推导过程中遇到困难时，再尝试从这本书找到答案。
- 《 Universally Composable Security: A New Paradigm for Cryptographic Protocols》，Ran Canetti 著。只要研究密码学协议，就一定听说过广义可组合性（Universal Composition）。
由于 UC 安全证明里涵盖环境（Environment）、参与方（Parties）、理想功能模块（Ideal Functionality，记为ℱ）、仿真者（Simulator）和攻击者（Adversary）这 5 类实体，并使用了：（1）多带互动图灵机作为基本计算模型；（2）带有三个限定量词（Quantifier）的两个序列来定义安全性；（3）多重标识（sid、ssid、qid）来标记一个会话（session).