Cryptography Reference
In-Depth Information
Evidence to the contrary has been presented ([140] and [133], respectively, where it is
shown that “black-box” reductions are unlikely to provide such transformations).
•
Collections of claw-free function (resp., permutation) pairs yield collections of one-way
functions (resp., permutations), but the other direction is not known.
2.7.1. Historical Notes
The notions of a one-way function and a trapdoor permutation originate from the semi-
nal paper of Diffie and Hellman [63]. Weak one-way functions were introduced by
Yao [210]. The RSA function was introduced by Rivest, Shamir, and Adleman [191],
whereas squaring modulo a composite was suggested and studied by Rabin [187].
Other authors have suggested basing one-way functions on the believed intractability
of decoding random linear codes [29, 108] and on the subset-sum problem [132].
The equivalence of the existence of weak and strong one-way functions (i.e.,
Theorem 2.3.2) is implicit in Yao's work [210], with the first proof appearing in [91].
The efficient amplification of one-way functions presented in Section 2.6 is taken
from Goldreich et al. [104], which in turn uses a technical tool originating in [4]
(see also [55, 135]). The existence of universal one-way functions is stated in Levin's
work [150].
The concept of hard-core predicates originates from the work of Blum and
Micali [36]. They also proved that a particular predicate constitutes a hard-core for
the “DLP function” (i.e., exponentiation in a finite field), provided that the latter func-
tion is one-way. Consequently, Yao showed how to transform any one-way function
into a hard-core predicate (i.e., the result is not stated in [210], but is rather due to oral
presentations of that work). A proof first appeared in Levin's work [150] (see details
in [114]). However, Yao's construction, which is analogous to the construction used in
the proof of Theorem 2.3.2, is of little practical value.
The fact that the inner product mod 2 is a hard-core for any one-way function (of the
form
g
(
x
r
)) was proved by Goldreich and Levin [110]. The proof pre-
sented in this topic, which follows ideas originating in [5], was discovered independently
by Leonid Levin and Charles Rackoff. The improvement captured by Proposition 2.5.4
is due to Levin [151].
Theorem 2.5.6 (hard-core functions of logarithmically many bits based on any one-
way function) is also due to [110]. The Computational XOR Lemma (Lemma 2.5.8)
is due to [208], but the proof presented here is due to Leonid Levin. (An alternative
construction of hard-core functions is presented in [117].)
Hard-core predicates (and functions) for specific collections of permutations have
been suggested [36, 141, 5, 208]. Specifically, Alexi et al. [5] proved that the intractabil-
ity of factoring yields hard-core predicates for permutations induced by squaring mod-
ulo a composite number. A simpler and tighter proof has subsequently been found [82].
,
r
)
=
(
f
(
x
)
,
2.7.2. Suggestions for Further Reading
Our exposition of the RSA and Rabin functions is quite sparse in details. In particular,
the computational problems of generating uniformly distributed “certified primes” and
