"Efficient" encryption scheme that is perfectly secret for two distinct messages

Question

In Katz and Lindell's Introduction to Modern Cryptography, Exercise 2.19 asks to find an encryption scheme that is perfectly secret for two distinct messages*, with the following hint:

The encryption scheme you propose need not be efficient, although an efficient solution is possible.

The solution they offer is to use a key space which consists of all permutations of the message space, and to encrypt by simply applying the permutation to each message, with the following note:

An efficient scheme meeting this definition can be constructed using pairwise-independent permutations (a topic not covered in the book).

Please describe an efficient** scheme that is perfectly secret for two distinct messages. I could not find anything about pairwise-independent permutations through a quick Google search; if your solution uses them please briefly describe them as well.

* An encryption scheme for two distinct messages is characterized by needing to use the same key to encrypt both messages. It's considered perfectly secret if knowing the pair of ciphertexts does not leak any information about the corresponding plaintexts.

** What the authors mean by "efficient" is not clear. I am interested in anything better than a key space of size $|M|!$, but I assume they had a specific solution in mind.

Answer 1

Well, if both messages are fixed to the same length $n$ bits, then here is one solution:

• Pick a representation of $GF(2^n)$

• Define the encryption scheme $E_{a,b}(P) = a \times P + b$ (where $a, b$ are members of $GF(2^n)$ and $a \ne 0$, and $\times$ and $+$ are field operations in $GF(2^n)$).

Then, if $a, b$ are uniformly selected from random (with the constraint that $a \ne 0$), then given the plaintext pair $P_0, P_1$ with $P_0 \ne P_1$, the pair:

$$C_0 = E_{a,b}(P_0),\ \ C_1 = E_{a,b}(P_1)$$

yields no information about $P_0, P_1$. Specifically, for any potential pair of distinct plaintext messages $P'_0, P'_1$, there is exactly one key $a', b'$ with $C_0 = E_{a',b'}(P'_0), C_1 = E_{a',b'}(P'_1)$ (and as $a, b$ were selected uniformly, this leaks no information).

This has the minimal key space of any encryption method that has this 2-message perfect secrecy, specifically, less than $2|M|$