Course:Introductory:Fall 2009
From CRYPTUTOR
This is the first edition (Fall 2009) of an introductory course in Applied Cryptography.
Instructors: Nikita Borisov and Manoj Prabhakaran
Contents |
Course Objectives
Lectures
Fundamental Concepts
Perhaps the most fundamental, and simplest, concept in modern cryptography is that of (information theoretic) secrecy. This is illustrated by the primitive called secret-sharing. In cryptography based on computational intractability, one relies on problems which are ('assumed' to be) "hard" for computationally bounded parties. Formally, we assume that in certain experiments (parametrized by a security parameter), PPT adversaries have negligible advantage in computing certain values over randomly guessing them. A particularly useful and interesting kind of computational intractability is computational indistinguishability (which concerns with computing a single bit outcome). The most basic kind of computational intractability that has been useful in cryptography is that associated with one-way functions. In many cryptographic constructions using one-way functions, one depends on a hardcore predicate of the one-way function (which yields computational indistinguishability). By means of the Goldreich-Levin predicate, a hardcore-predicate can be associated with any one-way function.
Secure Communication
Broadly, "secure" communication consists of two concepts: message secrecy and message authentication. An important distinction here is whether the communicating parties have a priori shared a secret key or not.
Symmetric Key Cryptography
Message Authentication Code (or MAC) is a symmetric-key primitives which can be used for message authentication. The relevant security notion for MACs is that of existential unforgeability. A fixed input-length MAC can be constructed from a pseudorandom function, and can be converted to a variable input-length MAC using the Merkle-Damgård construction (or alternately, by employing (weak) collision-resistant hash functions).
The security notion of an encryption scheme that is relevant against (only) passive eavesdroppers is that of SIM-CPA security (or, equivalently IND-CPA security). A CPA secure encryption scheme can be constructed from a pseudorandomness generator.
In the presence of active adversaries, CPA security is highly inadequate; instead SIM-CCA (or equivalently, IND-CCA) security is an appropriate notion. In the symmetric-key setting a CCA secure encryption scheme can be easily constructed from a CPA secure scheme, by adding message authentication to the ciphertext: i.e., simply require a MAC on the ciphertext.
Public Key Cryptography
Digital signatures is a public-key primitive for message authentication. Again, the relevant security notion is existential unforgeability, but in the public-key setting (in particular, with adversaries that have access to the public verification key for the signature). In principle digital signatures can be constructed based solely on one-way functions.
For public-key encryption (PKE), as in the case of symmetric-key encryption, CPA security gives security guarantees in the presence of only passive eavesdroppers, while CCA security gives guarantees against active adversaries. Constructing both CPA and CCA secure PKE schemes is significantly more complex than the constructions of SKE: in particular the computational intractability needed for the security of SKE (i.e., existence of one-way functions) is not sufficient for the security of PKE schemes (in a technical sense that can be formalized).
Efficient constructions of PKE schemes often use hybrid encryption.
Secure Communication in Practice
For symmetric-key cryptography Block ciphers and "hash functions" are used.
For public-key cryptography, candidate trapdoor one-way permutations are employed, but for the sake of efficiency, the constructions often also rely on the Random oracle model for security.
