How is this affine function a pair wise independent permutation? 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$.
A family of functions F is a pairwise independent permutation if:


Each member of the family is itself a permutation, and
For any fixed $A$, $B$ (with $A \ne B$, and both from the input set of the permutation), and $f$ is a random member from the family $F$, then the pair $f(A), f(B)$ is equidistributed over all distinct pairs from the output range of the function.


In particular, if the size of the output range $2^n$, then for any $C \neq D$, then the probability that both $f(A) = C$ and $f(B) = D$ is $(2^{2n} - 2^n)^{-1}$

By applying the above definition, it is easy to see that the function family $f_{(a,b)}$ meets it; each $f_{(a,b)}$ is a permutation (remember, $a=0$ is prohibited), and if $f$ is a random member of that family, then $f(A), f(B)$ is a equistributed distinct pair; that is, given any pair $C \ne D$, then there is a unique $a$, $b$ with $a\ne 0$ such that $f_{(a,b})(A) = C$ and $f_{(a,b)}(B) = D$.  Each such pair $a, b$ occurs with probability $(2^{2n} - 2^n)^{-1}$, and so we have $f(A) = C$ and $f(B) = D$ holding simultaneously with that same probability.