Conventional Security Analysis - A Classical Introduction to Cryptography: Applications for Communications Security - page 127

Decorrelation has nice properties which come from its algebraic definition. For
instance we can use the triangular inequality. When D is defined by a matrix norm, 6
decorrelation is multiplicative: if the canonical ideal random function associated with a
random permutation is a uniformly distributed random permutation, then the decorre-
lation of a product of independent random permutations is at most equal to the product
of the decorrelation of each permutation. Let C 1 and C 2 be two independent random
permutations over a set A . They are compared to a uniformly distributed random per-
mutation over A . Because of the independence between C 1 and C 2 ,wehave

C 1 ] d [ C 1 ] d [ C 2 ] d

[ C 2 ◦ = × .

Then we notice that

[ C 1 ] d [ C ∗ ] d [ C ∗ ◦ C 1 ] d [ C ∗ ] d

× = =

and

[ C ∗ ] d [ C 2 ] d C ∗ ] d [ C ∗ ] d × = [ C 2 ◦ =

because C ∗ ◦ C ∗ , and C ∗ have exactly the same distribution. Hence

C 1 , C 2 ◦

[ C 1 ] d

[ C ∗ ] d × [ C 2 ] d [ C ∗ ] d = C 1 ] d [ C ∗ ] d

− −

[ C 2 ◦

−

which leads us to

Dec d ( C 2 ◦ Dec d ( C 1 ) Dec d ( C 2 ) C 1 ) ≤ × .

We now show the relationship between best advantage and decorrelation.

Theorem 4.13 (Vaudenay 2003 [183]). We let ||| . ||| ∞ be the matrix norm associated

to the infinity norm:

y 1 , y 2 ,..., y d |

||| A ||| ∞ = max

x 1 , x 2 ,..., x d

A ( x 1 , x 2 ,..., x d ) , ( y 1 , y 2 ,..., y d ) | .

For any F and its canonical ideal version F ∗ we have

1
2 Dec d

F ∗ )

, = .

BestAdv Cl na ( F ( F )

||| . ||| ∞

|| . || a which provides the same result for Cl a : Similarly, there exists a matrix norm

1
2 Dec d

F ∗ ) BestAdv Cl a ( F , =

|| . || a ( F )

.

6

A matrix norm is a norm such that || A × B ||≤|| A || . || B || .