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

for any a and b , thus

2 − m x 1 , x 2
y 1 , y 2

E (DP C ( a [ C ∗ ] ( x 1 , x 2 ) , ( y 1 , y 2 ) + C ∗ ) , b )) ≤ 1 x 2 = x 1 + a

y 2 = y 1 + b

BestAdv Cl a ( C , .

The first term is then E (DP C ∗ ( a

1
2 m

, b )) which is at most

1 .

−

For the ELP result, we first notice that 2 Pr X [ X · a = C ( X ) · b ] − 1 =

E ( 1) X · a + C ( X ) · b , and we express LP C ( a

− , b )as

E ( 1) ( X 1 ⊕ X 2 ) · a + ( C ( X 1 ) ⊕ C ( X 2 )) · b

LP C ( a , b ) = −

where X 1 and X 2 are independent uniformly distributed random variables. We have

2 − 2 m x 1 , x 2
y 1 , y 2

E (LP C ( a 1) ( x 1 ⊕ x 2 ) · a + ( y 1 ⊕ y 2 ) · b [ C ] ( x 1 , x 2 ) , ( y 1 , y 2 ) .

, b )) = ( −

x 2 is equal to 2 − m . Considering that C is a The contribution of terms for which x 1 =

permutation, we can concentrate on x 1 = x 2 and y 1 = y 2 . Then we split the remaining

sum into four groups depending on the two bits ( x 1 · a ⊕ y 1 · b , x 2 · a ⊕ y 2 · b ). Let

b 1 , b 2 be the sum of all probabilities for which the two bits are ( b 1 , b 2 ), x 1 = x 2 , and

y 1 = y 2 .Wehave

E (LP C ( a 2 − m 2 − 2 m 2 − 2 m 2 − 2 m 2 − 2 m , b )) = + 0 , 0 − 0 , 1 − 1 , 0 + 1 , 1 .

As a result of symmetry we have 0 , 1 = 1 , 0 . Furthermore, the sum of the four sums

is 2 m (2 m − 1). Hence

E (LP C ( a 2 − m 2 − 2 m 2 m (2 m 2 − 2 m , b )) = + × − 1) − 4 × 0 , 1 .

We deduce

2 2 − 2 m
x 1 = x 2
y 1 = y 2

E (LP C ( a [ C ] ( x 1 , x 2 ) , ( y 1 , y 2 ) . , b )) = 1 − 1 x 1 · a = y 1 · b

x 2 · a = y 2 · b

Finally, we obtain

[ C ] ( x 1 , x 2 ) , ( y 1 , y 2 ) −

[ C ∗ ] ( x 1 , x 2 ) , ( y 1 , y 2 ) 2 2 − 2 m

x 1 = x 2
y 1 =

E (LP C ∗ ( a

E (LP C ( a

, − , =−

b )) b )) 1 x 1 · a = y 1 · b

x 2 · a = y 2 · b

y 2

C ∗ )

≤ 4BestAdv Cl a ( C , .

which leads us to the stated result by straightforward computations.