(BQ) Part 2 book "Introduction to modern cryptography" has contents: Number theory and cryptographic hardness assumptions, factoring and computing discrete logarithms, private key management and the public key revolution, digital signature schemes,and other contents. | Part III Public-Key ( Asymmetric ) Cryptography 241 Chapter 7 Number Theory and Cryptographic Hardness .Assumptions Modern cryptography, as we have seen, is almost always based on an as sumption that some problem cannot be solved in polynomial time. (See Sec tion for a discussion of this point.) In Chapters 3 and 4, for example, we saw that efficient private-key cryptography- both encryption and message authentication - can be based on the assumption that pseudorandom per mutations exist. Recall that, roughly speaking, this means that there exists some keyed permutation F for which it is impossible to distinguish in poly nomial time between interactions· with Fk (for a randomly-chosen key k) and interactions with a truly random permutation. On the f;;tce of it, the assumption that pseudorandom permutations exist seems quite strong and , and it is reasonable to ask whether this assumption is likely to be true or whether there is any evidence to support it. In. Chapter 5 we explored how pseudorandom permutations (., block ciphers) are constructed in practice. 'The resistance of these constructions to attack at least serves as an indication that Jhe existence of pseudorandom perrimtations is plausible. Still, it is difficult to imagine looking at some F and somehow being convinced on any intuitive level that it is a pseudorandom pernmtation. Moreover, 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 "Il!ore reasonable" assumption. All in all, this is a not entirely satisfying state of affairs. In contrast, as mentioned in Chapter 3 (and investigated in detail in Chap ove ter 6) it is possible to p r that pseudorandom permutations exist based on the much milder assumption that one-way functions exist. (Informally, a func tion is one-wa y if it is easy to compute but hard to invert; see Section .) Apart from a brief .
