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:

  1. $\langle f(x_1),f(x_2)\rangle$ where $f$ is distributed according to $F$;
  2. The uniform distribution over sequences of two different elements of $A$.
  • $\begingroup$ Is the first sentence a definition? What is $I_n$? $\endgroup$ – Dmitry Khovratovich Jul 8 '14 at 14:54
  • 1
    $\begingroup$ Are you reading the actual paper, or what appears to be the Nov 1997 preprint, which does contain (nearly) the sentence now in the second paragraph of the question? $\endgroup$ – fgrieu Jul 8 '14 at 15:24
  • $\begingroup$ yes i have copied that from the paper, i have mentioned the same $\endgroup$ – sashank Jul 8 '14 at 15:30
  • $\begingroup$ Can you post the definition of pairwise independent permutation? $\endgroup$ – mikeazo Jul 8 '14 at 17:31

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.

  • $\begingroup$ isn't it the probability 1 / (( 2^n ) * (2^(n-1))) ? $\endgroup$ – sashank Jul 23 '14 at 9:39
  • $\begingroup$ @sashank: no; the probability that $f(A)=C$ is $1/2^n$; $f(B)$ is independent of $f(A)$ except we know that $f(B)\ne f(A)$, hence given the first holds, there are $2^n-1$ possible values that $f(B)$ can take on. It is equidistributed other than that, and hence joint probability that $f(A)=C$ and $f(B)=D$ is $1/2^n \times 1/(2^n-1) = (2^{2n}-2^n)^{-1}$ $\endgroup$ – poncho Jul 23 '14 at 12:30
  • $\begingroup$ oh ok got it ! i miss calculated the $2^n - 1 $ part for $F(B)$ $\endgroup$ – sashank Jul 24 '14 at 2:39

The text quoted in the question:

  1. States that in any (finite commutative) field $(A,+,\cdot)$, the distribution of the permutations $f_{(a,b)}$ defined by $f_{(a,b)}(x)=a\cdot x+b$, where $(a,b)$ is uniformly distributed on $A^*\times A$, is pair-wise independent, per the definition now given in the question.
  2. Observes that because $GF(2^n)$ is such a field, and isomorphic to $I_n=\{0,1\}^n$, this prove by exhibition that there exists a pair-wise independent distribution of permutations of $I_n$.

Proving 1 is easy:

  • With $a\in A^*$, $b\in A$, the function $f_{(a,b)}$ over $A$ defined by $f_{(a,b)}(x)=a\cdot x+b$ is a permutation of $A$.
  • With $a\in A^*$, $b\in A$, $x_1\in A$, $x_2\in A$, if $x_1\ne x_2$ then $a\cdot x_1+b\ne a\cdot x_2+b$, that is $f_{(a,b)}(x_1)\ne f_{(a,b)}(x_2)$.
  • With $x_1\in A$, $x_2\in A$, $u\in A$, $v\in A$, if $x_1\ne x_2$ and $u\ne v$, then $a=(u-v)\cdot(x_1-x_2)^{-1}$ and $b=u-a\cdot x_1$ are such that $u=f_{(a,b)}(x_1)$ and $v=f_{(a,b)}(x_2)$, with $(a,b)\in A^*\times A$.
  • The set $A^*\times A$ and the set $\{(u,v)\in A\times A, u\ne v\}$ both have $n^2-n$ elements, and for any distinct members $x_1$, $x_2$ of $A$ the above transformation from $(a,b)$ to $(u,v)=\big(f_{(a,b)}(x_1),f_{(a,b)}(x_2)\big)$ is a bijection from one set to the other.
  • From which it follows that for distinct members $x_1$, $x_2$ of $A$, if $(a,b)$ is uniformly distributed on $A^*\times A$, then $\big(f_{(a,b)}(x_1),f_{(a,b)}(x_2)\big)$ is uniformly distributed on the set $\{(u,v)\in A\times A, u\ne v\}$; that is, the distribution $F$ of $f_{(a,b)}$ over $A$ with $(a,b)$ uniformly distributed on $A^*\times A$ matches the definition of a pair-wise independent distribution of permutations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.