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.

  • $\begingroup$ Is this the exact wording of the exercise? $\endgroup$
    – Guut Boy
    Dec 24 '14 at 0:49
  • 1
    $\begingroup$ Btw. let $n = |k|$ then there are $2^{n^2}$ functions from $log(n)$ to $n$ bits (where log is taken to be base 2). To see this note that all elements in $\{0,1\}^{log(n)}$ can be mapped to $2^n$ different values (all the strings in $\{0,1\}^n$). There are $n$ distinct elements in $\{0,1\}^{log(n)}$ so you have $\Pi^{n}_{i = 1}2^n = (2^n)^n = 2^{n^2}$ possible functions. $\endgroup$
    – Guut Boy
    Dec 24 '14 at 1:09
  • $\begingroup$ @Guut Boy - Thanks that makes sense! Yes it is the exact wording. $\endgroup$
    – Alex
    Dec 24 '14 at 9:47

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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.