Cryptography Reference
In-Depth Information
(1)
easy to sample and compute:
On input 1
n
, the output of
(the index selection)
algorithm
I
is distributed over the set
I
n
(i.e., is an
n
-bit long index of some function).
On input (an index of a function)
i ∈ I
, the output of
(the
domain sampling)
algorithm
D
is distributed over the set
D
i
(i.e., over the domain of the function). On input
i
∩{
0
,
1
}
I
and
x ∈ D
i
,
(the evaluation)
algorithm
F
always
outputs
f
i
(
x
).
(2)
hard to invert:
1
For every probabilistic polynomial-time algo-
rithm,
A
, every positive polynomial
p
(
∈
·
), and all suciently
large
n
's
Pr
A
(
i, f
i
(
x
))
(
f
i
(
x
))
<
1
p
(
n
)
f
−
1
∈
i
I
(1
n
)and
x
where
i
←
←
D
(
i
).
The collection is said to be a collection of
permutations
if each of the
f
i
's is a permutation over the corresponding
D
i
,and
D
(
i
)isalmost
uniformly distributed in
D
i
.
For example, in the case of the RSA,
f
N,e
:
D
N,e
→
D
N,e
satisfies
f
N,e
(
x
)=
x
e
mod
N
,where
D
N,e
=
. Definition 2.2 is
also a good starting point for the definition of a trapdoor permuta-
tion.
2
Loosely speaking, the latter is a collection of one-way permuta-
tions augmented with an ecient algorithm that allows for inverting
the permutation when given adequate auxiliary information (called a
trapdoor).
{
0
, ..., N
−
1
}
Definition 2.3.
(trapdoor permutations):
A collection of permutations
as in Definition 2.2 is called a
trapdoor permutation
if there are two aux-
iliary probabilistic polynomial-time algorithms
I
and
F
−
1
such that
(1) the distribution
I
(1
n
) ranges over pairs of strings so that the first
1
Note that this condition refers to the distributions
I
(1
n
)and
D
(
i
), which are merely
required to range over
I ∩{
0
,
1
}
n
and
D
i
, respectively. (Typically, the distributions
I
(1
n
)
and
D
(
i
) are (almost) uniform over
I ∩{
0
,
1
}
n
and
D
i
, respectively.)
2
Indeed, a more adequate term would be a collection of trapdoor permutations, but the
shorter (and less precise) term is the commonly used one.
