Cryptography Reference
In-Depth Information
length) many times yields a new algorithm that also has a success probability that is
negligible. Put in other words, events that occur with negligible probability remain
negligible even if the experiment is repeated polynomially many times. This property
is important for complexity-theoretic considerations.
In some literature, a distinction is made between strong one-way functions (as
discussed earlier) and weak one-way functions, and it is then shown that the former
can be constructed from the latter. The major difference is that whereas one only
requires some nonnegligible fractions of the inputs on which it is hard to invert a
weak one-way function, a strong one-way function must be hard to invert on all but
a negligible fraction of the inputs. For the purpose of this topic, we don't delve into
the details of this distinction, and hence we don't distinguish between strong and
weak one-way functions accordingly.
If
X
and
Y
are the same, then a one-way function
f
:
X
X
represents a
one-way permutation
. Hence, one-way permutations are just special cases of one-
way functions, namely ones in which the domain and the range are the same.
Having in mind the notion of a one-way function, the notion of a
trapdoor
function
(or
trapdoor one-way function
) is simple to explain and understand. Ac-
cording to Definition 2.2, a one-way function
f
:
X
→
Y
is a
trapdoor function
if
there exist some extra information—called the
trapdoor
—with which
f
can be in-
verted efficiently—that is, there is a (deterministic or probabilistic) polynomial-time
algorithm
A
that outputs
A
(
f
(
x
)) =
f
−
1
(
f
(
x
)) for all
x
→
X
or
A
(
y
)=
f
−
1
(
y
)
∈
for
y
∈
R
Y
. Consequently, the notion of a trapdoor function can be defined by
prepending the words “unless some extra information (i.e., the trapdoor) is known”
in the second condition of Definition 7.1. More formally, a trapdoor function can be
defined as suggested in Definition 7.2.
Definition 7.2 (Trapdoor function)
A one-way function
f
:
X
Y
is a
trapdoor
function
if there is a trapdoor information
t
and a PPT algorithm
I
that can be used
to efficiently compute
x
=
I
(
f
(
x
)
,t
)
with
f
(
x
)=
f
(
x
)
.
→
Many cryptographic functions required to be one way (or preimage resistant)
output bitstrings of fixed size. For example, cryptographic hash functions are re-
quired to be one way and output strings of 128, 160, or more bits (see Chapter 8).
Given such a function, one may be tempted to ask how expensive it is to invert it
(i.e., one may ask for the computational complexity of inverting the hash function).
Unfortunately, the (complexity-theoretic) answer to this question is not particularly
useful. If the cryptographic hash function outputs
n
-bit values, then 2
n
tries are
always sufficient to invert the function or to find a preimage for a given hash value
(2
n−
1
tries are sufficient on the average). Because 2
n
is constant for any fixed
n
,
the computational complexity to invert the hash function is
O
(1), and hence one
cannot say that inverting it is intractable. If we want to use complexity-theoretic
∈
N
