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