Foundations of Cryptography: A Primer
Format: PDF / Kindle (mobi) / ePub
Foundations of Cryptography surveys the main paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural cryptographic problems. The author starts by presenting some of the central tools; that is, computational difficulty (in the form of one-way functions), pseudorandomness, and zero-knowledge proofs.
Based on these tools, the emphasis is shifted to the treatment of basic applications such as encryption and signature schemes as well as the design of general secure cryptographic protocols. The author has created a unique overview that includes well over 100 references. The accent is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems.
Foundations of Cryptography is an invaluable resource for all students, researchers and practitioners interested in the foundations that underpin modern cryptography.
all (in a non-trivial sense). The non-triviality of the notion was ﬁrst demonstrated by presenting a zero-knowledge proof system for statements, regarding Quadratic Residuosity, which are believed to be hard to verify (without extra information). Furthermore, contrary to prior beliefs, it was later shown that the existence of one-way functions implies that any NP-statement can be proved in zero-knowledge. Thus, facts that were not known to hold at all (and even believed to be false), were shown
privatekey schemes, because in these schemes the encryption-key must be kept secret (rather than be public as in public-key encryption schemes). We note that a full speciﬁcation of either schemes requires the speciﬁcation of the way in which keys are generated; that is, a (randomized) key-generation algorithm that, given a security parameter, produces a (random) pair of corresponding encryption/decryption keys (which are identical in the case of private-key schemes). Thus, both private-key and
Schemes, and General Cryptographic Protocols. In order to give some feeling of the ﬂavor of the area, we have included in this primer a few proof sketches, which some readers may ﬁnd too terse. We stress that following these proof sketches is not 6 Introduction and Preliminaries 1: Introduction and Preliminaries Part I: Basic Tools 2: Computational Diﬃculty (One-Way Functions) 3: Pseudorandomness 4: Zero-Knowledge Part II: Basic Applications 5: Encryption Schemes 6: Signature and Message
setting their inputs in a way that depends on inputs of honest parties; a more round-eﬃcient method was presented in (45).) (2) Generation of local random tapes: Next, all parties jointly generate a sequence of random bits for each party such 106 General Cryptographic Protocols that only this party knows the outcome of the random sequence generated for it, but everybody gets a commitment to this outcome. These sequences will be used as the randominputs (i.e., sequence of coin tosses) for the
and J. Robert, “Privacy ampliﬁcation by public discussion,” SIAM Journal on Computing, vol. 17, pp. 210–229, 1998. Preliminary version in Crypto85, titled “How to reduce your enemy’s information”.  M. Blum, “Coin ﬂipping by phone,” IEEE Sprig COMPCOM, pp. 133–137, 1982. See also SIGACT News, Vol. 15, No. 1, 1983.  M. Blum, B. Feldman, and T. Micali, “Non-interactive zero-knowledge proof systems,” in 20th ACM Symposium on Principles of Distributed Computing, pp. 103–112, 1988. See (32).