To get an intuitive understanding of why the above definition is useful for cryptographic purposes, let’s look at a simple example taken from [56]. Assume that Alice, Bob, and a trusted third party Trent are playing a game. The game’s objective is for Trent to generate an unbiased bit only with the help of Bob and Alice; that is, Trent himself has no suitable source of entropy he could query.

To achieve the game’s objective, the parties use a probabilistic public-key encryption scheme. Recall that probabilistic encryption offers a provable and very strong level of security because it uses randomness in the encryption process. As a result, given a ciphertext, the adversary cannot compute any information about the plaintext.

A classic example of a probabilistic public-key encryption scheme is the Goldwasser-Micali scheme. A simplified definition of the Goldwasser-Micali scheme can be given using the notion of a trapdoor predicate [117].

A trapdoor predicate is a Boolean function B : {0,1}∗→{0,1} that takes an arbitrary-length bitstring and maps it to either a 0 or a 1. In addition, given a bit v, it is easy to find a random x for which B(x) = v. However, computing B(x) for a given x is computationally feasible only if one knows certain trapdoor information.

In other words, if Alice’s public key is a trapdoor predicate B, then Bob can encrypt the message bit mi by randomly selecting a xi such that B(xi) = mi and send xi to Alice. Because Alice has the trapdoor information, she is able to efficiently compute B(xi) = mi. Eve, however, can do no better than guessing the value of mi.

Using the trapdoor predicate notion, the Goldwasser-Micali probabilistic public-key encryption scheme can be defined as follows:

• Encryption: e(x) = (f(r),x ⊕ B(r))
• Decryption: d(y,z) = B(f−1(y)) ⊕ z

Here, x is a single-bit plaintext, f is a trapdoor function, B is the trapdoor predicate of f, and r is a random string.

Having defined the public-key encryption scheme, we can now describe the game played by Alice, Bob, and Trent:

1. Trent publishes his public key.
2. Alice and Bob each choose a random bit xA and xB, respectively, encrypt it using Trent’s public key, and send the ciphertexts cA and cB to Trent.
3. Trent decrypts the received messages, XORs the bits xA and xB, and announces the result.

Intuitively, because Bob and Alice don’t know each other’s bit values, we would expect the ciphertexts cA and cA to be independent and, therefore, the result of the XOR operation to be unbiased. Surprisingly, however, it turns out to be wrong!