nucleation

LIT-1061: Foundations of Cryptography

2 min read

Properties4
StatusActive — read in part 2026-10-15 (Skimmed), and not in its printed form. The text read is the author's 1995 draft, "Foundations of Cryptography (Fragments of a Book)" (23 February 1995, with the "Additional Fragment (Nr. 1)" of 9 February 1996), which Goldreich posted through ECCC (eccc.weizmann.ac.il/static/books/Foundations_of_Cryptography_Fragments_of_a_Book/; PDF at eccc.weizmann.ac.il/resources/pdf/foc.pdf, 305 pp.). The draft's Chapters 1–3 were read in full; its zero-knowledge chapter, the 1989 annotated references and the 1996 addendum were not. The 2001 Cambridge text (DOI 10.1017/CBO9780511546891) is closed: Unpaywall and OpenAlex list no open location. The author's own pages (wisdom.weizmann.ac.il/~oded/foc-book.html and related) and the Internet Archive's capture of foc-book.html could not be reached from this environment. Worth reading as the standard source of the definitions of computational indistinguishability (Def. 3.2) and of a pseudorandom generator (Def. 3.9), and for the result that the first is strictly coarser than statistical closeness. For CASE-083 it confirms each ingredient: the generator definition, the 2⁻ⁿ image count (§3.3.1, stated there only as Δ ≥ ½ with Δ the unhalved sum; the count reappears in the proof of Prop. 3.13), and closure under efficient post-processing, which is set as Exercise 1 of §3.8.4 rather than proved. For CLAIM-302 it shows that the separation itself needs no assumption: Prop. 3.3 gives, by counting, an ensemble on at most 2^(n/2) strings that no polynomial-time test tells from uniform. Generators, or equivalently one-way functions, are needed only for an efficiently samplable pair (Goldreich 1990, cited in §3.8.2). Indistinguishability is defined only for ensembles indexed by n, never for a single pair of distributions. For CLAIM-304 it supplies the definitions; the encoding is the record's own. Section numbers are the draft's; the printed volume (Ch. 3 at pp. 101–183) was not checked.
Tagsmathematics, information-theory
Cited as “paper” byNOTE-863 — Goldreich — Foundations of Cryptography, Vol. 1 (1995 fragments): computational indistinguishability and pseudorandom generators
Cited as “source” byTHEORY-352 — A pseudorandom generator exists if and only if a one-way function exists, where both are secure against uniform adversaries and every reduction is an oracle Turing machine, as statements about ensembles indexed by n; the construction from an arbitrary one-way function is only weak-preserving, so security at one length is bought at a much greater one, THEORY-357 — Computational indistinguishability is strictly coarser than statistical closeness: without any assumption there are ensembles on at most 2^(n/2) strings that no circuit of size 2^(n/8) tells from uniform, though none of them is efficiently samplable, and an efficiently samplable pair of this kind exists if a pseudorandom generator does, since its output covers at most 2^n of the 2^l(n) strings; all of it is about ensembles indexed by n, not single pairs of distributions

Graph View

Goldreich, O. (2001). Foundations of Cryptography, Volume 1: Basic Tools. Cambridge University Press. DOI 10.1017/CBO9780511546891

Key takeaways

Skimmed (NOTE-863). In the 1995 draft of Volume 1, computational indistinguishability is a strictly coarser equivalence than statistical closeness, and the book proves this two ways. Proposition 3.3 does it unconditionally: a counting argument shows there are ensembles supported on at most 2^(n/2) strings that no circuit of size 2^(n/8) tells from uniform with gap 2^(−n/8) or more, but such an ensemble cannot be sampled efficiently. §3.3.1 shows that the output of any pseudorandom generator is statistically far from uniform yet, by definition, indistinguishable from it. That witness is efficiently samplable, and it needs pseudorandom generators, which exist if and only if one-way functions do (Theorem 3.29, stated without proof). That efficient post-processing preserves indistinguishability is set as Exercise 1 of §3.8.4, not proved in the text. All of this is asymptotic, about ensembles indexed by n, not about single pairs of distributions.

Why this is here

A15 drew on Goldreich for the separation of statistical from computational distinguishability. It supplies the definitions CLAIM-302 and CLAIM-304 rest on, and the construction CASE-083 uses. The two claims are the record’s own derivations from the definition of a secure generator, so this is cited for definitions, not read for evidence.

Backlinks