Cryptography Reference
In-Depth Information
inverting
f
as follows. On input
y
and 1
n
(supposedly
y
is in the range of
f
(
U
n
)),
algorithm
A
halts with output
B
(
y
10
p
(
n
)
−|
y
|
,
1
n
).
On Dropping the Auxiliary Input 1
|
x
|
.
The reader can easily verify that if
f
is length-
preserving, then it is redundant to provide the inverting algorithm with the auxiliary
input 1
|
x
|
(in addition to
f
(
x
)). The same holds if
f
is length-regular and does not shrink
its input by more than a polynomial amount (i.e., there exists a polynomial
p
(
·
) such
that
p
(
|
f
(
x
)
|
)
≥|
x
|
for all
x
). In the sequel,
we shall deal only with one-way functions
that are length-regular and do not shrink their input by more than a polynomial amount
.
Furthermore, we shall mostly deal with length-preserving functions. In all these cases,
we can assume, without loss of generality, that the inverting algorithm is given only
f
(
x
)
as input
.
On 1-1 One-Way Functions.
If
f
is 1-1, then so is
f
(as defined in Eq. (2.3)), but
not
f
(as defined in Eq. (2.4)). Thus, when given a 1-1 one-way function, we can
assume without loss of generality that it is length-regular, but we cannot assume that
it is length-preserving. Furthermore, the assumption that 1-1 one-way functions exist
seems stronger than the assumption that arbitrary (and hence length-preserving) one-
way functions exist. For further discussion, see Section 2.4.
2.2.4. Candidates for One-Way Functions
Following are several candidates for one-way functions. Clearly, it is not known whether
or not these functions are indeed one-way. These are only conjectures supported by
extensive research that thus far has failed to produce an efficient inverting algorithm
(one having noticeable success probability).
2.2.4.1. Integer Factorization
In spite of the extensive research directed toward the construction of feasible integer-
factoring algorithms, the best algorithms known for factoring integers have sub-
exponential running times. Hence it is reasonable to believe that the function
f
mult
that partitions its input string into two parts and returns the (binary representation of
the) integer resulting by multiplying (the integers represented by) these parts is one-way.
Namely, let
f
mult
(
x
,
y
)
=
x
·
y
where
y
denotes (the string representing) the integer resulting by
multiplying the integers (represented by the strings)
x
and
y
. Clearly,
f
mult
can be com-
puted in polynomial time. Assuming the intractability of factoring (e.g., that given the
product of two uniformly chosen
n
-bit-long primes, it is infeasible to find the prime
factors), and using the density-of-primes theorem (which guarantees that at least
N
log
2
N
of the integers smaller than
N
are primes), it follows that
f
mult
is at least weakly one-
way. (For further discussion, see Exercise 8.) Other popular functions related to integer
factorization (e.g., the RSA function) are discussed in Section 2.4.3.
40
|
x
|=|
y
|
, and
x
·
