Cryptography Reference
In-Depth Information
error due to the fact that we simplify the problem by replacing the random
permutation π with a random function. The last term arise because at each
query to π (resp. π 1 ) which is in some input set A i (resp. output set B j )there
are at most 2 c I points in A i whose image under π is already defined (resp. at
most 2 c O points in B j whose image under π 1 is already defined), thus occupying
at most 2 c I out of the 2 n−c O output sets (resp. at most 2 c O out of the 2 n−c I
input sets).
We first show that (1) implies the claimed expected complexity bound. In
game G 0 ,let T denote the random variable defined as the number of oracle
queries until the event E 0 occurs. We lower bound the expected value Q =E( T )
as follows. Let p ( q ) denote the right hand side of (1), and let q
be such that
p ( q )= 2 .SincePr( T
q )
p ( q ), we have
q
2 .
q ·
Pr( T>q )
Q
Pr( T = q )
·
q
(2)
q>q
Now, for i
,let q i denote the value of q such that the i th term on the
right hand side of (1) is equal to
∈{
1 , 2
}
1
4 . Since there are 2 terms in (1), we may take
min( q 1 ,q 2 ) as lower bound for q .Since q 1 =2 2 1
and q 2 =2 n− ( c I + c O ) 2 ,the
claimed lower bound on Q follows.
It remains to prove (1). We will do this by building a chain of games, starting
with G 0 , which are similar until bad is set (for further details of this methodology
see for example [2]).
First define a game G 1 to be similar to G 0 except that the permutation π
is replaced by a relation P ⊂{ 0 , 1 }
n that is injective and functional,
but not necessary defined in whole domain. According to naming convention
in [2] relation P is called partial permutation, whereas injectivity and functional
conditions together are named “permutation constraint”. Initially P is empty
and through execution of G 1 its values are being sampled randomly with respect
to “permutation constraint”. Whenever P ( x )(resp. P 1 ( y )) is needed first it is
checked if P (resp. P 1 ) is defined on x (resp. y ). If this is the case then appro-
priate value is returned, otherwise P ( x )(resp. P 1 ( y )) is sampled uniformly at
random from img ( P )(resp. img ( P 1 )), where img ( P ) is complement of image
of P . Because the sampling is the same as in Game G 0 ,wehave
n
×{ 0 , 1 }
Pr( E 0 )=Pr( E 1 ) .
(3)
Next we define game G 2 which is the same as G 1 except “permutation con-
straint” for P does not need to be fulfilled. That means the values P ( x )(resp.
P 1 ( y )) are sampled at random from
n , but the game stops immediately
when the “permutation constraint” is not satisfied. Unless the “permutation
constraint” is violated by the occurrence of a collision between a new output
value returned by P and a previous output value of P or input value queried
to P 1
{
0 , 1
}
(resp. a collision between a new output value returned by P 1
and an
previous output value of P 1
or input value queried to P ), the games G 1 and
 
Search WWH ::




Custom Search