ABSTRACT
Modern cryptosystems are invariably based on an assumption that some problem is hard. In Chapters 3 and 4, for example, we saw that private-key cryptography-both encryption schemes and message authentication codescan be based on the assumption that pseudorandom permutations (a.k.a. block ciphers) exist. Recall, roughly, this means that there exists some keyed permutation F for which it is hard to distinguish in polynomial time between interactions with Fk (for a uniform, unknown key k) and interactions with a truly random permutation. On the face of it, the assumption that pseudorandom permutations exist
seems quite strong and unnatural, and it is reasonable to ask whether this assumption is true or whether there is any evidence to support it. In Chapter 6 we explored how block ciphers are constructed in practice. The fact that existing constructions are resistant to attack serves as an indication that the existence of pseudorandom permutations is plausible. Still, it may be difficult to believe that there are no efficient distinguishing attacks on existing block ciphers. Moreover, the current state of our theory is such that we do not know how to prove the pseudorandomness of any of the existing practical constructions relative to any “simpler” or “more reasonable” assumption. All in all, this is not entirely a satisfying state of affairs. In contrast, as mentioned in Chapter 3 (and investigated in detail in Chap-
ter 7) it is possible to prove that pseudorandom permutations exist based on the much milder assumption that one-way functions exist. (Informally, a function is one-way if it is easy to compute but hard to invert; see Section 8.4.1.) Apart from a brief discussion in Section 7.1.2, however, we have not seen concrete examples of functions believed to be one-way. One goal of this chapter is to introduce various problems believed to be
“hard,” and to present conjectured one-way functions based on those problems.1 This chapter can thus be viewed as a culmination of a “top down” approach to private-key cryptography. (See Figure 8.1.) That is, in Chapters 3 and 4 we have shown that private-key cryptography can be based on pseudorandom functions and permutations. We have then seen that the latter
can be instantiated in practice using block ciphers, as explored in Chapter 6, or can be constructed in a rigorous fashion from any one-way function, as shown in Chapter 7. Here, we take this one step further and show how oneway functions can be based on certain hard mathematical problems.
