Skip to main content
Engineering LibreTexts

6: Pseudorandom Functions

  • Page ID
    7354
  • A pseudorandom generator allows us to take a small amount of uniformly sampled bits, and “amplify” them into a larger amount of uniform-looking bits. A PRG must run in polynomial time, so the length of its pseudorandom output can only be polynomial in the security parameter. But what if we wanted even more pseudorandom output? Is it possible to take \(\lambda\) uniformly sampled bits and generate \(2\lambda\) pseudorandom bits?

    Perhaps surprisingly, the answer is yes. The catch is that we have to change the rules slightly. Since a PRG must run in polynomial time, it does not have time to even write down an exponentially long output (let alone compute it). On top of that, a distinguisher would not have enough running time to even read it.

    To avoid these quite serious problems, we settle for random access to the bits of the very large pseudorandom output. Imagine augmenting a PRG to take an extra input \(i\). Given the short seed \(s \in \{0,1\}^{\lambda}\) and index \(i\), the PRG should output (in polynomial time) the \(i\)th bit of this exponentially-long pseudorandom output. In this way, the short seed implicitly determines an exponentially long output which never needs to be explicitly written down. If F is the function in question, then the key/seed \(k\) implicitly determines the long pseudorandom output:

    \[F(k, \pmzerodot \cdots \pmzerodot \pmzerodot)\|F(k, \pmzerodot \cdots \pmzerodot 1)\| F(k, \pmzerodot \cdots 1 \pmzerodot)\|\cdots\| F(k, 1 \cdots 1 \pmzerodot)\|F(k, 1 \cdots 11)\nonumber\]

    Since we have changed the necessary syntax, we refer to such a function \(F\) as a pseudorandom function (PRF) rather than a PRG.