§6 Pseudorandom Functions

Random Functions

• A Random Function corresponds to choosing uniformly at random $f \in \texttt{Func}_n:= \{f | f : \{0,1\}^n \rightarrow \{0,1\}^n\}$.
• Equivalently, for each $x \in \{0,1\}^n$, we choose a bit string $f(x)$ uniformly at random from $\{0,1\}^n$.
• Equivalently, a random function corresponds to choosing uniformly a string of length $n \cdot 2^n$.

Keyed Functions

• A Keyed Function $F : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ is a two-input function, with first input the key $k$. We will be interested in Efficient Keyed Functions, i.e., for which is a polynomial-time algorithm to compute $F(k, x)$ for each given $k, x$.

Pseudorandom Functions

• Definition. Let $F : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ be an efficient, length-preserving, keyed function. $F$ is a Pseudorandom Function if for all probabilistic polynomial-time distinguishers $D$, there is a negligible function $\epsilon$ such that

  $$\left| \operatorname{Pr}_{k \leftarrow\{0,1\}^{n}}\left[D^{F_{k}(\cdot)}\left(1^{n}\right)=1\right]-\operatorname{Pr}_{f \leftarrow \texttt{Func}_{n}}\left[D^{f(\cdot)}\left(1^{n}\right)=1\right] \right| \leq \epsilon(n)$$

  where the first probability is over uniform choice of $k \in \{0,1\}^n$ and over any randomness of $D$, and the second probability is over uniform choice of $f \in \texttt{Func}_n$ and over any randomness of $D$.

Pseudorandom Permutations

• We say that a keyed function $F$ is a Keyed Permutation if $l_{in} = l_{out}$ and if for all keys $k$, the function $F_k : \{0,1\}^{l_{in}(n)} \rightarrow \{0,1\}^{l_{in}(n)}$ is a permutation. We call $l_{in}$ the block length of $F$.

Strong Pseudorandom (Unpredictable) Permutations

• Definition. Let $F : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ be an efficient, length-preserving, keyed permutation. $F$ is a Strong Pseudorandom Permutation if for all probabilistic polynomial-time distinguishers $D$, there exists a negligible function $\epsilon$ such that

  $$\left|\operatorname{Pr}\left[D^{F_{k}(\cdot), F_{k}^{-1}(\cdot)}\left(1^{n}\right)=1\right]-\operatorname{Pr}\left[D^{f(\cdot), f^{-1}(\cdot)}\left(1^{n}\right)=1\right]\right| \leq \epsilon(n)$$

  where the first probability is over uniform choice of $k \in \{0,1\}^n$ and the randomness of $D$, and the second probability is over uniform choice of $f \in \texttt{Perm}_n$ and the randomness of $D$.

Pseudorandom Generators from Pseudorandom Functions

• Define $G(s) := F_s(1) \Vert F_s(2) \Vert \ldots \Vert F_s(l)$ for desired length $l$, where we encode each of the integers $1,\ldots, l$ as an $n$-bit string.

Pseudorandom Functions from Pseudorandom Generators

• Suppose $G$ has expansion factor $n \cdot 2^{t(n)}$ with $t(n) = O(\log n)$.
• Define the keyed function $F : \{0,1\}^n \times \{0,1\}^{t(n)} \rightarrow \{0,1\}^n$ as follows.
• To compute $F_k(x)$ for $k \in \{0,1\}^n$, and $x \in \{0,1\}^{t(n)}$, first compute $G(k)$ and get the output bit string of length $n \cdot 2^{t(n)}$.
• Split the output bit string into $2^{t(n)}$ pieces of $n$ bits each and output the $x$-th piece. Since $t(n) = O(\log n)$, this runs in polynomial time.

— Feb 10, 2023

§6 Pseudorandom Functions by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.