Cryptography: PRG, PRF and PRP

The main purpose of this post is to show that the three fundamental cryptographic primitives PRG, PRF and PRP are in fact equivalent in the sense of (semantic) security. We shall do this by showing that

• PRG to PRF: using GGM PRF construction
• PRF to PRP: by the Luby-Rackoff Theorem (ie., a 3-round Feistel cipher) 
• PRP to PRG: using counter mode

PRG to PRF

Since PRF is somewhat a "random access" version of PRG, one may want to simulate a PRF $F(k,i)$ by enumerating a PRG $G(k)$ to its $i$th value. However, this design takes exponential time and is thus not satisfactory. There are many method to build an efficient secure PRF out of a secure PRG, and here we present the arguably most intuitive one (which is also the first one): the Goldreich-Goldwasser-Micali construction [GGM'84]. Given a PRG $G:\{0,1\}^m\rightarrow\{0,1\}^{2m}$, let $G_0,G_1$ be the left and right halves of $G$, ie., $G(k)=G_0(k)||G_1(k)$. A PRF $F:\{0,1\}^m \times \{0,1\}^n\rightarrow \{0,1\}^m$ is defined by $$F(k, x_1...x_n) = G_{x_n}(G_{x_{n-1}}(...(G_{x_2}(G_{x_1}(k))...)).$$ The security of the construction can be easily proven by induction on $n$. Its fixed parameter security is given by the following theorem, though we omit the proof due to its technicality:

Theorem. If $G$ is a $(t,\epsilon)$-PRG then $F$ is a $(t-cn,\epsilon q n,q)$-PRF for some constant $c$.

Note that the PRF expansion lemma also implies that one can build a secure PRF out of a secure PRG.

PRP to PRG

Counter mode.

Example. (OTP vs PRF) A one-bit PRF defined by $E(k,m)=k\oplus m$ is secure, since its distribution is exact the set of all one-bit PRPs. However, an $n$-bit PRF defined in similar way is no longer a secure PRF, since $E(k,m_1)\oplus E(k,m_2) = m_1\oplus m_2$ is obviously not random.

Example. (PRP vs PRF) A secure invertible PRF is clearly a secure PRP. A secure PRP, however, may not be a secure PRF, since a PRP must be invertible, and thus is not random when looked upon as a PRF. On the other hand, the PRF Switching Lemma tolds as if the input length is sufficiently large, then a secure PRP is indeed a secure PRF by thr PRF Switching Lemma: Let $E$ be an secure PRP over $(\mathcal K, \mathcal M)$. For an adversary that makes at most $q$ queries, then $$|Adv_{PRF}(A,E)-Adv_{PRP}(A,E)|\le q^2/|\mathcal M|.$$

Exhaustive search attacks

Ideal ciphers

A block cipher is a function $E:\mathcal K \times \mathcal M \rightarrow \mathcal C$. Here we shall let $|\mathcal K| = n$ and $|\mathcal M| = |\mathcal C| = poly(n)$, where $n$ is called the security parameter. A block cipher $E$ is called an ideal cipher if for any $m\in \mathcal M$, $Adv(E(k,m),r)$ is negligible for $r \in_r \{0,1\}^{poly(n)}$ and $k \in_r \mathcal K$. Another characterization of an ideal block cipher $E$ is $\{E(k,m)\} \approx_p \{f_k(m)\}$ for any $m\in \mathcal M$, where ${f_k}$ are a random subset of the family of all invertible functions from $\mathcal M$ to $\mathcal C$. The second characterization is especially helpful, because it allows us to approximate an ideal cipher by a random invertible functions.

Fact. Let $E:\mathcal K\times\mathcal M\rightarrow \mathcal C$ be an ideal cipher. For all $c,m$, the probability that a cipher-text can only be decrypted by the encryption key is $$P\{k'\neq k, E(k',m)=c\} \le \sum_{k'\in\mathcal K,k'\neq k} P\{E(k',m)=c\} \le \frac{|\mathcal K|}{|\mathcal M|}.$$ Assuming that DES is ideal, the probability that one can recover a unique key from $N$ input-output pairs is larger than $1-N2^{56-64N}$. When $n=1$, the probability is roughly 99.5% --- already high enough for an exhaustive search attack to be reasonable.

Attacks on block ciphers

To attack a block cipher $(E,D)$, we are given a few input-output pairs $(m_i, c_i=E(k,m_i))$, $i=1,...,n$ to find the key $k$. The ciphers we are interested here are DES and some of its strengthened versions
DES:   $E(k,m)$ for $k\in \{0,1\}^{56}$, $m\in \{0,1\}^{64}$
2DES: $E^2((k_1,k_2),m) = E(k_2,E(k_1,m))$
3DES: $E^3((k_1,k_2,k_3),m) = E(k_3,D(k_2,E(k_1,m)))$
DX:     $E^x((k_1,k_2,k_3),m) = k_3\oplus E(k_2, k_1\oplus m)$

DES Challenge: Broken by exhaustive search attack since 1997.

2DES Challenge: Given $c,m$, find $k_1,k_2$ such that $E(k_2,E(k_1,m))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1$, check whether $D(k_2,c)$ is in the table.

Both steps take $O(56 \cdot 2^{56})=O(2^{62})$ time and $O(2^{56})$ space, which turns out to be the total cost of the attack (called the meet-in-the-middle attack). This complexity is considered tractable with technology of nowadays.

3DES Challenge: Given $c,m$, find $k_1,k_2,k_3$ such that $E(k_3,D(k_2,E(k_1,m)))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1,k_2$, check whether $E(k_2,D(k_3,c))$ is in the table.

The first step takes $O(56\cdot 2^{56})$ time and the second step takes $O(56\cdot 2^{56}\cdot 2^{56})=O(2^{118})$ time. Both steps take $O(2^{56})$ space. In practice, we regard a cipher as sufficiently secure if it takes $\omega(2^{90})$ time to compromise. This is why 3DES is widely used today while DES and 2DES are not.

Security of stream ciphers

Perfect Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called perfectly secure if for all $c\in \mathcal C$, $k \in_r \mathcal K$, and $m_1,m_0\in \mathcal M$ with $|m_1| = |m_0|$, $$P\{ E(k,m_0)=c \} = P\{E(k,m_1)=c \}.$$ The canonical example of perfectly secure cipher is the one-time pad (OTP). This definition of security, however, turns out to be too strict for practical ciphers: It is clear that a necessary condition for perfect security is $|\mathcal K| \ge |\mathcal M|$, since for any $c \in\mathcal C$ and any $m \in\mathcal M$ there must exist $k \in\mathcal K$ such that $E(k,m)=c$. Hence perfect security can be guaranteed only if $|k|=\omega(|m|)$, which made perfectly secure ciphers hard to use in practice. (Recall that a stream cipher uses symmetric key. If we have a secure channel to transfer a key as long as a message, why not using it to transfer the message in the first place?)

Semantic Security. A cipher $(E,D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is called semantically secure if for $k \in_r \mathcal K$ and all $m_0,m_1\in \mathcal M$ with $|m_0| = |m_1|$, there is no efficient algorithm that can distinguish $E(k,m_0)$ from $E(k,m_1)$ with non-negligible probability. This fact can also be written as $\{E(k, m_0)\} \approx_p \{E(k, m_1)\},$ which means the two distributions are computationally indistinguishable.

Recall that a PRG is secure if it is computational indistinguishable from a true RNG. The following theorem connects the definition of secure PRGs and and the definition of semantic security.

Theorem. A stream cipher derived from a secure PRG is semantically secure.

The intuition of behind the theorem is as follows. It is clear that any stream cipher derived from a true RNG is semantically secure. Therefore, if a PRG derives a stream cipher that is not semantically secure, then there exists an efficient way to distinguish the PRG from a true RNG (i.e., by deriving a stream cipher and then testing the semantic security of the derived cipher), which would imply that the PRG is not secure.

Before we proceed to a formal proof, we need to make the statement ‘‘distinguish A from B’’ more precise. We define the advantage of an adversary $A$ over an algorithm $G$ with respect to $G'$ as $$Adv(A,G,G')=|P\{A(G(X))=1\} - P\{A(G'(Y))=1\}|,$$ where $X$ and $Y$ and random variables. The larger the advantage is, the more capable $A$ can distinguish $G$ from $G'$. With this definition, we see that $G(X) \approx_p G'(Y)$ if and only if $Adv(A,G,G')$ is negligible for all efficient adversaries $A$. We shall write $Adv(A,G)$ for simplicity when $G'$ is clear from the context.
Now suppose that $E$ is a stream cipher derived from PRG $G$.

Proof of the theorem. It suffices to show that for any adversary $A$ for the cipher, there is an adversary $B$ for the PRG such that $Adv(A,E) \le 2Adv(B,G).$ Our approach, which is quite standard in proving results concerning strength of security, is to build adversary $B$ using $A$ as an oracle. Formally, we define $B_i(X)=A(m_i\oplus G(X))$ for $i\in \{0,1\}$ and let $B=B_j$ where $j=\arg\max_i\{Adv(B_i,G) \}$. The construction of $B_0$ is illustrated as follows.

When $Y$ is uniformly random, there is no way to tell $m_0\oplus Y$ from $m_1 \oplus Y$, and thus $P\{A(m_0\oplus Y)=1\} = P\{A(m_1 \oplus Y)=1\}$. Now, note that

$Adv(A,E)=|P\{A(m_0 \oplus G(X))=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ = |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\} + P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ \le |P\{A(m_0 \oplus G(X))=1\} - P\{A(m_0 \oplus Y)=1\}| + |P\{A(m_1 \oplus Y)=1\} - P\{A(m_1 \oplus G(X))=1\}| \\ =Adv(B_0,G) + Adv(B_1,G) \le 2Adv(B,G).$

This completes the proof. $\square$

A predictable PRG is exactly an insecure PRG

Let $A(x)$ be an algorithm and $n=|x|$ denote the length of the binary encoding of its input $x$. We say that an event regarding $A$ and $x$ holds with negligible probability if it holds with probability $O(1/poly(n))$. We say the event holds with significant probability if it holds with probability $1-O(1/poly(n))$. Note that the property of being negligible or significant is closed under polynomial additions and multiplications. That is, the probability of the union and the interception of a polynomial number of negligible (resp.$\ $significant) events is still negligible (resp.$\ $significant).

We say that a PRG $G$ is predictable if given a random seed $k$,  there is an efficient algorithm that can predict some $i$th bit of the output according to first $i-1$ bits with non-negligible probability.

We say that a PRG $G$ is insecure if given a random seed $k$, there is an efficient algorithm that can distinguish it from a true random number generator with non-negligible probability.

Static abstract methods in Java

In Java 6 and earlier, you can't define an abstract static method. For example,

abstract class foo {
    abstract void bar( );        // this is ok
    abstract static void bar2(); // this gives a compile-time error
}

Abstract static methods work fine and are commonly used in many other languages, e.g., @classmethod in Python. Indeed, some methods just don't make sense as instance methods, and it would be much more effective to call directly a static abstract method than creating an instance just for using that abstract method. If Java supported abstract static methods, one could expect that the method (i) must be implemented by subclasses, and (ii) is a class method of the subclass. In Java, however, a static method cannot be inherited or overridden. If a subclass has a static method with the same signature as a static method in the superclass, the former shadows the latter instead of overriding it. (See this document for rules of overriding and shadowing in Java.)
On the other hand, some languages do support static inheritance, just like the way they support instance inheritance. From a syntax perspective, those languages usually require the class name to be included in the statement. For example, in Java, assuming you are writing code in ClassA, where methodA is a static method and there is no instance method with the same signature. Then methodA() and ClassA.methodA() are equivalent statements. In SmallTalk, however, the class name is not optional, so the syntax is (note that SmallTalk does not use the . to separate the "subject" and the "verb", but uses it as the statement terminator): ClassA methodA. Because the class name is always required, the correct "version" of the method can always be determined by traversing the class hierarchy.
Since a Java static method defined in an abstract class would belong to that very class, an abstract static method could not be used anyway. Fortunately, an abstract class can have static fields and static methods starting from Java 7 (see this document). These static members can be invoked with a class reference as you would do with a non-abstract class.

A note on omega automata

$\omega$-automata are finite state automata interpreted on infinite words. Non-deterministic $\omega$-automata are quintuples $(Q,\Sigma,I,T,\mathcal F)$, where $Q$ is a finite set of states, $I$ is a non-empty set of initial states, $T:Q\times\Sigma\times Q\to Q$ is a transition relation, and $\mathcal F$ is an acceptance condition.
The Rabin condition is in form of $\mathcal F=\{(A_i,R_i):i\in J\}$, and run is accepting iff there exists $j\in J$ such that it visits $A_j$ i.o. but visits $R_i$ only finitely many times.
The Streett condition is $\mathcal F=\{(A_i,R_i):i\in J\}$ such that a run is accepting iff there exists $j\in J$ such that it visits $A_j$ i.o. or visits $R_i$ only finitely many times.
The parity automata are $\omega$-automata with a priority function $p:Q\to [c]$ for some $c\in\mathbb N.$ A run $\pi$ is accepting iff $\lim\sup p(\pi(n))$ is even. Parity automata can be simulated by $\omega$-automata with the Rabin acceptance conditions: just define $J:=\mathbb N$, $A_n:={s\in S: p(s)\le 2n\}$, and $R_n:={s\in S: p(s)\le 2n-1\}$.


Parity Automata.