【讀書筆記】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