Guidelines for reading FOUNDATIONS OF CRYPTOGRAPHY after COMPLEXITY THEORY

(by Oded Goldreich)

This page augments the guidelines for a reading group on foundations of cryptography (FoC). It is intended at students who take this reading group after having taken a reading group in complexity theory (CC).

As stated in the main guidelines for the FoC reading group, meetings number 1-5 and 7-8 (of the FoC reading group) cover material that was covered in the reading group on CC, although the perspective is different. Hence, students who took the CC reading group can skip these parts and focus on meetings 6 and 9-10 (for the first volume) and on meetings 12-18 and 20-21 (for the second volume). Meetings 11 and 19 are optional; they belong to the first part and are better done one after the other. Details follow.

Evidently, the overlap between the two groups is only in the first part (or first senester) of FoC. This is reflected in the textbooks on which these reading groups are based. Specifically, one-way functions (OWF), pseudorandom generators (PRG), and zero-knowledge proof (ZK) are covered in both textbooks, but the perspecive is different.

More specifically, OWFs are the topic of Section 7.1 of CC and Chapter 2 of FoC, PRGs are the topic of Section 8.2 of CC and Sections 3.1-3.5 of FoC, and ZKs are the topic of Section 9.2 of CC and Chapter 4 of FoC. The perspective in CC is wider: OWFs are viewed as one type of computational hardness, PRGs as one type of a general theory of pseudorandomness, and ZKs are viewed as one type of probabilistic proof systems. In the case of FoC, we pay more attention to specific types of OWFs (see Sec 2.2.4 and 2.4), we consider pseodorandom functions (see Sec 3.6), and we study ZK in a far more extensive manner (see Sec 4.3-4.4, let alone the more advanced sections).

Although meetings number 1-5 and 7-8 (of the FoC reading group) cover material that was covered in the reading group on CC, I would suggest not to skip them completely but rather remind yourself of their contents by reading the corresponding guilines for these meetings and glancing at the corresponding sections of necessay. Specifically, beyond the fact that the perspective is different, some issues that are crucial for FoC are not covered in CC at all. These include:

2.4.2 One-Way Functions as Collections.
2.4.4 Trapdoor one-way permutations. We'll need them in Meeting 11 and 13.
2.4.5 Claw-free Functions. We'll need them in Meeting 16.
3.6 Pseudorandom Functions (Meeting 6).
4.3 Definitions of Zero-Knowledge (Meeting 9). In paricular, note that here (unlike in CC) we consider an arbitrary adversarial verifier (see Sec 4.3.1), and that auxiliary-input ZK is crucial (see Sections 4.3.3 and 4.3.4 (their sequenrtail composition)).
4.4 Construction of Zero-Knowledge (Meeting 10). Here (unlike in CC) we pay more attention to the actual implementtaion, which relies on commitment schemes (Sec 4.4.1).

In addition, I strongly recommend going also over the optional Meetings 11 and 19. Meeting 11 covers the following material (at high level):

Sec 4.10 NIZK ("non-interactive zero knowledge") -- used a lot!
Sec 4.7 POK (Proofs of Knowledge) -- also used a lot and very intriguing.
Sec 4.6 WI (witness indistinguishability) -- also used quite a lot.

Lastly, for the first semester, you may also do Meeting 19 (non-black-box techniques in the design of ZK), which is based on Apdx C.3 (in Vol 2) and Sec 4.6-4.8. Note that meetings 11 and 19 are not mandatory; please consult me in case of doubt.

Back to the two-volume book's webpage.