Cryptography Reference
In-Depth Information
We stress that the output of algorithm
I
on input 1
n
is not
necessarily distributed
uniformly
over
I
∩{
n
. Furthermore, it is not even required that
I
(1
n
) not be entirely
concentrated on one single string. Likewise, the output of algorithm
D
on input
i is not
necessarily distributed
uniformly
over
D
i
. Yet the hardness-to-invert condition implies
that
D
(
i
) cannot be mainly concentrated on polynomially many (in
0
,
1
}
) strings. We
stress that the collection is hard to invert with respect to the distribution induced by the
algorithms
I
and
D
(in addition to depending, as usual, on the mapping induced by the
function itself).
We can describe a collection of one-way functions by indicating the corresponding
triplet of algorithms. Hence, we can say that a
triplet of probabilistic polynomial-time
algorithms
(
I
,
D
,
F
)
constitutes a collection of one-way functions
if there exists a
collection of functions for which these algorithms satisfy the foregoing two conditions.
Clearly, any collection of one-way functions can be represented as a one-way func-
tion, and vice versa (see Exercise 18), yet each formulation has its own advantages. In
the sequel, we shall use the formulation of a collection of one-way functions in order
to present popular candidates for one-way functions.
|
i
|
Relaxations.
To allow a less cumbersome presentation of natural candidates for one-
way collections (of functions), we relax Definition 2.4.3 in two ways. First, we allow the
index-sampling algorithm to output, on input 1
n
, indices of length
p
(
n
) rather than
n
,
where
p
(
·
) is some polynomial. Second, we allow all algorithms to fail with negligible
probability. Most important, we allow the index sampler
I
to output strings not in
I
I
∩{
0
,
1
}
so long as the probability that
I
(1
n
)
∈
p
(
n
)
is a negligible function in
n
. (The
same relaxations can be used when discussing trapdoor permutations and claw-free
functions.)
Additional Properties: Efficiently Recognizable Indices and Domains.
Several ad-
ditional properties that hold for some candidate collections for one-way functions will be
explicitly discussed in subsequent subsections. Here we mention two (useful) additional
properties that hold in some candidate collections for one-way functions. The proper-
ties are (1) having an efficiently recognizable set of indices and (2) having efficiently
recognizable collection of domains; that is, we refer to the existence of an efficient
algorithm for deciding membership in
I
and the existence of an efficient algorithm that
I
and
x
can determine whether or not
x
∈
D
i
. Note that for the non-relaxed
Definition 2.4.3, the coins used to generate
i
∈
given
i
∈
I
(resp.,
x
∈
D
i
) constitute a certificate
I
(resp.,
x
∈
D
i
) may assist in inverting the function
f
i
(resp., always yielding the pre-image
x
).
NP
(i.e., an
-witness) for the corresponding claim; yet this certificate that
i
∈
2.4.3. Examples of One-Way Collections
In this section we present several popular collections of one-way functions (e.g., RSA
and discrete exponentiation) based on computational number theory.
6
In the exposition
6
Obviously these are merely candidate collections for one-way functions; their hardness-to-invert feature
either is a (widely believed) conjecture or follows from a (widely believed) conjecture.
