Loading...
Please wait, while we are loading the content...
Similar Documents
Cryptography ( Winter 2006 ) Lecture 9 : Pseudorandom Function Families and Permutations 1 February 2006
| Content Provider | Semantic Scholar |
|---|---|
| Author | Beame, Paul |
| Copyright Year | 2006 |
| Abstract | Recall our definitions from last time: Definition 1.1. An infinite keyed function family F is an infinite sequence {F }k≥1 where F k : {0, 1} × {0, 1} → {0, 1}(k). We call the ` the length of the family. We write FK for the function F |K|(K, ·) : {0, 1} → {0, 1}. Note that we can equivalently view F as an ensemble {Fk}k≥1 where Fk is the distribution on the Func(`(k), `(k)) induced by choosing K ← Uk and returning FK . We can then write our definition of a pseudorandom function family as follows: Definition 1.2. A function ensemble F of length ` is a pseudorandom function family (PRFF) if and only if 1. F is polynomial-time computable; i.e. the function that computes F (K, x) = FK(x) = F |K|(K, x) for x ∈ {0, 1}`(|K|) is computable in deterministic polynomial time. 2. For all (oracle) PPT A, AdvF A (k) = Pr[A Fk(1k) = 1]− Pr[AFunc(`(k),`(k))(1k) = 1] is negligible. We stated the following theorem last time which we will now prove. Theorem 1.3 (Goldreich, Goldwasser, Micali). If PRNGs with factor 2 stretch exist then PRFFs exist with length `(k) = k. Proof. Let G : {0, 1}∗ → {0, 1}∗ be a PRNG such that G : {0, 1} → {0, 1} for each k. Define G0 : {0, 1} → {0, 1} and G1 : {0, 1} → {0, 1} by G(y) = G0(y)G1(y). That is G0 gives the left half of the output of G and G1 gives the right half. We can extend this definition for all subscripts x ∈ {0, 1}∗ by Gλ(y) = y (λ is the empty string) Gx0(y) = Gx(G0(y)) Gx1(y) = Gx(G1(y)). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://courses.cs.washington.edu/courses/cse599b/06wi/lecture9.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
