Cryptography Reference
In-Depth Information
2.
Easy to invert with trapdoor:
There exists a
(
deterministic
)
polynomial-time al-
gorithm, denoted F
−
1
, such that for every
(
i
,
t
)
in the range of I and for every
D
i
, it holds that F
−
1
(
t
x
∈
,
f
i
(
x
))
=
x.
A useful relaxation of these conditions is to require that they be satisfied with over-
whelmingly high probability. Namely, the index-generating algorithm
I
is allowed to
output, with negligible probability, pairs (
i
,
t
) for which either
f
i
is not a permutation or
D
i
. On the other hand, one typically requires
that the domain-sampling algorithm (i.e.,
D
) produce an almost uniform distribution
on the corresponding domain. Putting all these modifications together, we obtain the
following version, which is incomparable to Definition 2.4.4. We take the opportunity
to present a slightly different formulation, as well as to introduce a non-uniformly
one-way version.
F
−
1
(
t
,
f
i
(
x
))
=
x
does not hold for all
x
∈
I
⊆
Definition 2.4.5 (Collection of Trapdoor Permutations, Revisited):
Let
n
.A
collection of permutations
with
indices
in
¯
Iis
a set
{
f
i
:
D
i
→
D
i
}
i
∈
I
such that each f
i
is
1-1
on the corresponding D
i
. Such
a collection is called a
trapdoor permutation
if there exist four probabilistic
polynomial-time algorithms I
,
D
,
F , and F
−
1
such that the following five condi-
tions hold:
}
∗
and I
n
def
=
I
{
0
,
1
∩{
0
,
1
}
1.
Index and trapdoor selection:
For every n,
I
n
×{
}
∗
]
2
−
n
[
I
(1
n
)
Pr
∈
0
,
1
>
1
−
I
n
,
2.
Selection in domain:
For every n
∈ N
and i
∈
2
−
n
.
(a)
Pr
[
D
(
i
)
∈
D
i
]
>
1
−
(b)
Conditioned on D
(
i
)
∈
D
i
, the output is uniformly distributed in D
i
. That is,
for every x
∈
D
i
,
1
Pr
=
|
∈
=
[
D
(
i
)
x
D
(
i
)
D
i
]
|
D
i
|
|
i
|
Thus, D
i
⊆∪
m
≤
poly(
|
i
|
)
{
0
,
1
}
m
. Without loss of generality, D
i
⊆{
0
,
1
}
poly(
)
.
I
n
, and x
3.
Efficient evaluation:
For every n
∈ N
,i
∈
∈
D
i
,
2
−
n
Pr
[
F
(
i
,
x
)
=
f
i
(
x
)]
>
1
−
4.
Hard to invert:
Let I
n
be a random variable describing the distribution of the first
element in the output of I
(1
n
)
, and X
n
def
=
D
(
I
n
)
. We consider two versions:
Standard/uniform-complexity version:
For every probabilistic polynomial-time
algorithm A
, every positive polynomial p
(
·
)
, and all sufficiently large n's,
1
p
(
n
)
Non-uniform-complexity version:
For every family of polynomial-size circuits
[
A
(
I
n
,
Pr
f
I
n
(
X
n
))
=
X
n
]
<
{
C
n
}
n
∈N
, every positive polynomial p
(
·
)
, and all sufficiently large n's,
1
p
(
n
)
Pr
[
C
n
(
I
n
,
f
I
n
(
X
n
))
=
X
n
]
<
