Proving the existence of a pseudorandom function

Question

I've been reading the Introduction to Modern Cryptography book by Katz and Lindell as part of my own learning and have come across this exercise which I am not sure how to approach. The exercise is: (exercise 3.8)

Prove unconditionally the existence of an efficient pseudorandom function $F:\{0,1\}^* \times \{0,1\}^* \mapsto \{0,1\}^*$ where the input-length is logarithmic in the key-length (i.e., $F(k,x)$ is defined only when $|x| = log |k|$, in which case $|F(k,x)| = |k|$).

There is also a hint which states that you should use the fact that any random function is also pseudorandom.

This is my initial train of thought:

We require the pseudorandom function to be indistinguishable from a function chosen uniformly at random from the set of functions that map $log|k|$ bit strings to $|k|$ bit strings (let's say this set is called $Func_{log\,|k|\, \mapsto |k|}$). I'm guessing that we need to work how many functions in this set in order to work out the probability of picking a random function, $f$, from this set.

I know that the set of functions $Func_{n \mapsto n}$ mapping $n$ bit strings to $n$ bit strings contains $2^{n*2^n}$ functions. However my first obstacle is calculating how many functions are in $Func_{log\,|k|\, \mapsto |k|}$ since the functions in this set are not bijective as they are in $Func_{n \mapsto n}$.

If I could calculate this value then I would approach the rest of the problem by calculating the amount of possible pseudorandom functions (clearly given by $|k|$ since $k$ is chosen uniformly at random). I was then hoping, if there was a similar number of functions in $Func_{log\,|k|\, \mapsto |k|}$ (although I speculate there is way more than $|k|$ functions in this set), then eventually try to show that it would be hard for any ppt distinguisher to tell between the pseudorandom function and the randomly chosen one.

I have no idea if this is along the right line and I also don't really know how to bring the hint in to play. All I can think is that it may turn out to be easier to prove that $F$ is indistinguishable from another pseudorandom function which also happens to have been chosen at random.

If anyone could provide a hint as to how to calculate the amount of functions in $Func_{log\,|k|\, \mapsto |k|}$ or pointers for how to approach this then that would be great. As I said, I am doing the exercises for my own good so I'm not massively keen on being given a full solution straight away.

Answer 1

Though this is an 4-year old topic, it seems the following should work:

We can construct a function $F_k(x)$ with output length $l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)}$.

Didivde the key $k$ into $2^{O(\log n)}$ blocks with equal length, denoted by $k_i$ with $i=1,2,\dots, 2^{O(\log n)}$. Because $k$ is uniformly distributed in $\{0,1\}^n$, so is $k_i$.

$F_k(x)= k_x$ is the pseudorandom function.

Answer 2

Preface: of course the following tests alone are not unconditional tests. See below for clarification.

Interesting post Alex. Dan Boneh from Stanford and the Coursera classes Cryptography I and II discusses the statistical test of PRG's which are related to PRF's in terms of an algorithm as the following:

$\{0,1\}^n$ bit strings such that $A(x)$ where $x$ is the input string--outputs $0$ or $1$. Where $0$ = not random and $1$ = random. As Katz discusses too PRF's are indistinguishable from a truly random function.

Examples include $A(x) = 1$ iff (if and only if) the # of $0$'s in the given string $x$ and the number of $1$'s in the string $x$ is not very different. #$0(x)$ - #$1<= 10 * \sqrt n$.

Here is a second example from Boneh: $A(x) = 1$ iff the number of consecutive 0's is the difference between $00x$ and $n/4<= 10*\sqrt n$. $n/4$ just represents the 25% chance from the uniform distribution.

In Boneh's third example we now see logs:

$A(x) = 1$ iff max-run-of-0$(x) <= 10* log_2 (n)$

In order to begin to actually test for a secure PRF/PRG we must look at the concept of advantage:

Where $G:K--> [0,1]^n$ is a PRG and A a statistical test on $[0,1]^n$ then we can define the following:

adv PRG [A,G]= Pr [A(G(k)) = 1 K<--R K - Pr [A(r) = 1] r<-- R {0,1}^n where we are calculating a specific probability of summing to 1 within the seed space and how likely an output from a ST outputed from a generator and 1 from a truly random string.