Page 85 - ISCI’2017

k
P (2 ,0) (1 2 )= − l − 2 k
k
specifies probability that at N = 2 independent implenmentations of random substitution in i -th
point (in full set of master keys K ()x values) the round key K i ()x = s '( ) will not appear a single
y
i
x
time.
Inverse value

2 k k k
k
−
1 (1 2 ) (5)
li
l −
k
P (2 , 0) 1 P> = − (2 ,0) = ∑ C i k (1 2 ) 2 − i (2 ) = −− l − 2
−
i= 1 2
k
specifies probability of an event when at 2 independent tests the round l- bit length key K ()x will
i
be formed at least once.
l
k
l
Power of different -bit values set is equal to 2 where each of these values in 2 independent
implementations of the vector (2) appears at least once in i -th point of random substitution with
probability (5). I.e. for 2 k different master keys K ()x defining vector (2) implementation by the key
schedule construction it will be formed in average

N ( , ) 2 (2 , 0) 2 (1 (1 2 ) )k l = l P k > = l −− l − 2 k

1
−
−
different round keys K i ()x . Using substitution (1 2 ) ≈ l − 2 l e gives us a simplified formula in the
right side of the expression (3), and, thus, completes the proof.
For the most simple case k = (equality of ciphertext block length to key length) the probability
l
(5) gets the form

2 l l k
l
l −
−
l
l −
2
li
1 P
=− −
P (2 , 0) = ∑ C i l (1 2 ) 2 − i (2 ) =− (2 ,0) 1 (1 2 ) ≈− − 1 0,63
>
1 e ≈
−
i= 1 2
k
and the ratio of the average number N ( , )k l of different round keys K i ()x to the number of 2
different master keys K ()x under k = is determined as
l
k
l
N k 2 (1 P− (2 ,0))
( , ) l
k
l
δ ( , ) l = = = P (2 , 0) 1 e> ≈− − 1 ≈ 0,63 (6)
2 k 2 k
what corresponds to the formula (27) in [15].
Under k ≠ formula (6), as well as formula (27) in [15], is not satisfied, and we need to estimate
l
the ratio ( , )k lδ according to the general formula
( , ) l
N k k   1  2 k l −  ( k l − )
2
k
−
δ ( , ) l = = 2 l k (1 (1 2 ) ) ≈ 2 lk 1     − ≈ 2 l k 1− (0,37 ) 2 . (7).
−
−
−−
l −
2 k   e  
 
Let us concider an example of using these relations.
Fig. 2 and 3 show dependency of the probabilities (5) and the relationships (7) for the blocks of
k
l
length 0 ≤≤ 16 and keys 0 ≤≤ 16. It is obvious that even for such small lengths l and k which
85