# Foundations of Cryptography, Volume 1: Basic Techniques

# Foundations of Cryptography, Volume 1: Basic Techniques

## Oded Goldreich

Language: English

Pages: 394

ISBN: 2:00220483

Format: PDF / Kindle (mobi) / ePub

Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. This book presents a rigorous and systematic treatment of the foundational issues: defining cryptographic tasks and solving new cryptographic problems using existing tools. It focuses on the basic mathematical tools: computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs. Rather than describing ad-hoc approaches, this book emphasizes the clarification of fundamental concepts and the demonstration of the feasibility of solving cryptographic problems. It is suitable for use in a graduate course on cryptography and as a reference book for experts.

Multi-Agent Machine Learning: A Reinforcement Approach

Advanced Methods in Computer Graphics: With examples in OpenGL

Functional Programming in Scala

Multidimensional Particle Swarm Optimization for Machine Learning and Pattern Recognition

algorithm. Let rn denote a sequence of coin tosses for A maximizing the success probability of A (averaged over input f (Un )). Namely, rn satisfies Pr[Arn ( f (Un )) ∈ f −1 ( f (Un ))] ≥ Pr[A ( f (Un )) ∈ f −1 ( f (Un ))] where the first probability is taken only over all possible values of Un , and the second probability is also over all possible coin tosses for A . (Recall that Ar (y) denotes the output of algorithm A on input y and internal coin tosses r .) The desired circuit Cn

all Un(i) ’s reside in Sn is small. Specifically, we define ∈ g −1 g Un2 p(n) def s1 (n) = Pr B g Un2 p(n) ∧ ∃i s.t. Un(i) ∈ Sn and ∈ g −1 g Un2 p(n) def s2 (n) = Pr B g Un2 p(n) ∧ ∀i : Un(i) ∈ Sn Clearly, s(n) = s1 (n) + s2 (n) (as the events considered in the si ’s are disjoint). We derive a contradiction to the lower bound on s(n) (given in Eq. (2.7)) by presenting upper bounds for both s1 (n) and s2 (n) (which sum up to less). First, we present an upper bound on s1 (n). The key

of length 5000. The following definition is natural for a general discussion of amplification of one-way functions. Definition 2.6.1 (Quantitative One-Wayness): Let T : N → N and ε : N → R be polynomial-time-computable functions. A polynomial-time-computable function f : {0, 1}∗ → {0, 1}∗ is called ε(·)-one-way with respect to time T (·) if for every algorithm A , with running time bounded by T (·) and all sufficiently large n’s, Pr[A ( f (Un )) ∈ f −1 ( f (Un ))] > ε(n) Using this terminology,

arbitrary A can be easily met by a modified A that does not read its last input bit; see Exercise 20). It follows that L A (G (Un )) ∈ {0, . . . , t − 1}, and so Pr[J = L A (G (Un ))] = 1t . Combining all the preceding with Eq. (3.13) (and t = p(n)), we get 1 t −1 1 · Pr[A (1t , G (Un )) = next A (G (Un ))] + · t t 2 1 1 1 1 1 · + ≥ + 1− · p(n) 2 p (n) p(n) 2 1 1 = + 2 p(n) · p (n) Pr[A ( f (Un )) = b(Un )] = for infinitely many n’s, in contradiction to the hypothesis that b is a hard-core of

to further simplify the discussion by setting (n) = n. Generalizations are discussed in Section 3.6.4. Definition 3.6.1 (Function Ensembles): Let : N → N (e.g., (n) = n). An -bit function ensemble is a sequence F = {Fn }n∈N of random variables such that the random variable Fn assumes values in the set of functions mapping (n)-bit-long strings to (n)-bit-long strings. The uniform -bit function ensemble, denoted H = {Hn }n∈N , has Hn uniformly distributed over the set of all functions mapping