【读书笔记】Foundations of Cryptography: A Prime

Foundations of Cryptography (A Primer) 密码学基础（入门书）

作者：Oded Goldreich

链接：http://www.wisdom.weizmann.ac.il/~oded/foc-sur04.html

关于本书

这套 Foundations of Cryptography 是经典的密码学著作，共有三册，分别是 A Primer、Volume 1, Basic Tools 和 Volume 2, Basic Applications，作者 Oded Goldreich 是之前看的 Introduction to Modern Cryptogarphy: Principles and Protocols《现代密码学——原理与协议》作者 Jonathan Katz 的导师。但是看 Jonathan Katz 的书的时候，里面有很多东西没有太明白，原因是他直接使用了 Oded Goldreich 书中的一些内容。这本 A Primer 是入门读本，本着“循序渐进、由浅入深”的原则方法，所以首先选择这本进行研读，然后再次系统地对现代密码学的相关理论进行重新学习。

研读计划

本书英文版共 131 页，计划使用一周的时间完成。

开始时间：2020年8月6日

结束时间：

要点记录

1 Introduction and Preliminaries

1.1 Introduction

现代密码学与“经典”密码学的区别

与复杂理论的关系 Modern cryptography is strongly linked to complexity theory (in contrast to “classical” cryptography which is strongly related to information theory).

应用范围更广，经典密码学主要关注非安全传输媒体上的安全通讯问题 The scope of modern cryptography is very broad, and it stands in contrast to “classical” cryptography (which has focused on the single problem of enabling secret communication over insecure communication media).

敌手计算能力假设 The only assumptions that can be justified refer to the computational abilities of the adversary. Furthermore, the design of cryptographic systems has to be based on firm foundations; whereas ad-hoc approaches and heuristics are a very dangerous way to go.

本书的主要目标和内容

密码学基础：使用模式、方法、技术对自然的安全问题进行概念化、定义、提供解决方案。 This primer is aimed at presenting the foundations for cryptography. The foundations of cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural “security concerns”.

解决密码学问题的两个步骤：定义 + 构造。 Solving a cryptographic problem (or addressing a security concern) is a two-stage process consisting of a definitional stage and a constructional stage.

典型的密码学问题（加密和签名方案）和工具（计算复杂性、伪随机性、零知识证明） This primer focuses on several archetypical cryptographic problems (e.g., encryption and signature schemes) and on several central tools (e.g., computational difficulty, pseudorandomness, and zero-knowledge proofs).

先解决问题，再优化方案。Our focus is on demonstrating the feasibility of solving the problem, not on providing a practical solution. As a secondary concern, we typically discuss the level of practicality (or impracticality) of the given (or known) solution.

计算困难性 Computational difficulty

单项函数的重要意义 The aforementioned tools and applications (e.g., secure encryption) exist only if some sort of computational hardness exists. Specifically, all these problems and tools require (either explicitly or implicitly) the ability to generate instances of hard problems. Such ability is captured in the definition of one-way functions. Thus, one-way functions are the very minimum needed for doing most natural tasks of cryptography.

Prerequisites and structure

Suggestions for further reading

1.2 Preliminaries

Efficient computations and infeasible ones

Randomized (or probabilistic) computations