Page 87 - ISCI’2017

To estimate probabilistic properties of cyclic keys K ()x sequences we summarize the positions of
рк
the lemma proved above for random, equiprobable and independent values K () x , K () x ,..., K () x . Let us
1 2 t
k
estimate the average number of different sequences K ()x that is generated using all 2 values of
рк
master keys K ()x . The following theorem is true.

Theorem. The average number of different cyclic keys sequences K () x = {K 1 () x ,K 2 () x ,...,K t () x }, that
рк
k
is formed by 2 independent implementations of random homogeneous substitution in i-th point,
i∈ {1,2,..., }t , is defined by:

(
−
  1  2 k tl  k tl
−
k
2
( , , ) =
tl
−−
l
−
N k lt 2 (1 (1 2 ) ) ≈ 2 1  tl    − ≈ 2 1− (0,37 ) 2 ) . (8)
tl
  e  
 
Proof is a generalization of the lemma`s results in the case of K ()x = {K 1 ()x ,K 2 ()x ,...,K t ()x }
рк
sequences formation. Indeed, in accordance with the assumption of K i ()x cyclic keys generating by
the independent implementations of random homogeneous substitution in i -th point, for each
Y
i∈ {1,2,..., }t the probability of K ()x does not depend on y ∈ = { , yy ,..., y } or K ()x . This
i i 1 2 2 l
l −
probability is equal to ( '( )Ps y = K () x ) = 2 . The joint probability of independent events is the
x i i
product of the probabilities of these events, i. e.:
t
tl
( P K () x = {K 1 () x , K () x ,..., K t () x }) = ∏ Ps x y i K i () x ) 2 .
( ' ( ) =
=
−
2
рк
i= 1
Master keys K ()x are selected independently from each other and the corresponding events
K () x = {K 1 () x ,K 2 () x ,...,K t () x } are independent too. Therefore, using the Bernoulli formula just as in the
рк
lemma proof, we obtain the expression
−
tl M
PN , )t = C N M (1 2 )− − tl N M− (2 ) ,
( ,M
which specifies the probability of the case that in N independent implementations the sequence K ()x
рк
would appear exactly M times.

The value

2 k k k
k
tl i
k
−
P (2 , 0, )t> = ∑ C i k (1 2 )− − tl 2 − i (2 ) = 1 P− (2 ,0, ) 1 (1 2 )t = −− − tl 2 (9)
i= 1 2
gives the probability of the case when in 2 independent tests the specific sequence K ()x is formed
k
рк
at least once.

87