CS276 Lecture 14 (draft)

Summary

Today we show how to construct a pseudorandom function from a pseudorandom generator.

1. Construction of Pseudorandom Functions

Lemma 1 (Generator Evaluated on Independent Seeds) Suppose that {G:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^m} is a {(t,\epsilon)} pseudorandom generator. Fix a parameter {k}, and define {G^k : \{ 0,1 \}^{kn} \rightarrow \{ 0,1 \}^{km}} as

\displaystyle  G^k(x_1,\ldots,x_k) := G(x_1),G(x_2),\ldots,G(x_k)

Then {G^k} is a {(t-O(kn),k\epsilon)} pseudorandom generator.

Let {G:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^{2n}} be a length-doubling pseudorandom generator. Define {G_0 : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n} such that {G_0(x)} equals the first {n} bits of {G(x)}, and define {G_1:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^n} such that {G_1(x)} equals the last {n} bits of {G(x)}.

The the GGM pseudorandom function based on {G} is defined as follows: for key {K\in \{ 0,1 \}^n} and input {x\in \{ 0,1 \}^n}:

\displaystyle  F_K (x) := G_{x_n} (G_{x_{n_1}} ( \cdots G_{x_2} ( G_{x_1} (K) ) \cdots )) \ \ \ \ \ (1)

Theorem 2 If {G: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^{2n}} is a {(t,\epsilon)} pseudorandom generator and {G} is computable in time {r}, then {F} is a {(t/O(nr), \epsilon \cdot n \cdot t)} secure pseudorandom function.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s