Can anybody explain how the below is true ?
$I_n$ denotes the set of all n-bit strings, ${\{0,1\}}^n$.
(..)
Let $A$ be a finite field then the permutation $f_{(a,b)}(x) = a \cdot x + b$, where $a \ne 0; b \in A$ are uniformly distributed, is pair-wise independent. Thus, there are pair-wise independent permutations over $I_n$ (the permutations $f_{(a,b)}$ with operations over $GF(2^n)$ ).
This is stated in section 2.3 of the below paper, the context is that they use pair wise independent permutation in first and last rounds of Feistel network to get better security guarantees. But they do not mention why the above is true.
[1] Moni Naor and Omer Reingold, "On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited", in Journal of Cryptology January 1999, Volume 12, Issue 1, pp 29-66.
Addition: The question's quote (at least: also) appears in an apparently earlier version of the paper, made available by the first author (pdf).
By definition, a distribution $F$ of permutations over $A$ is pair-wise independent if for all distinct members $x_1, x_2$ of $A$, the following two distributions are identical:
- $\langle f(x_1),f(x_2)\rangle$ where $f$ is distributed according to $F$;
- The uniform distribution over sequences of two different elements of $A$.