Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$.
share|improve this question
    
Is the first sentence a definition? What is $I_n$? –  Dmitry Khovratovich Jul 8 at 14:54
1  
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? –  fgrieu Jul 8 at 15:24
    
yes i have copied that from the paper, i have mentioned the same –  sashank Jul 8 at 15:30
    
Can you post the definition of pairwise independent permutation? –  mikeazo Jul 8 at 17:31

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
isn't it the probability 1 / (( 2^n ) * (2^(n-1))) ? –  sashank Jul 23 at 9:39
    
@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}$ –  poncho Jul 23 at 12:30
    
oh ok got it ! i miss calculated the $2^n - 1 $ part for $F(B)$ –  sashank Jul 24 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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