IMC: Introduction to Modern Cryptography

Welcome to Introduction to Modern Cryptography

Learning Outcomes

On successful completion of this course, you should be able to: 

1. apply basic number theory, group theory and discrete probability to analyze cryptographic algorithms.
2. understand the notions of pseudorandom functions/generators and their connection with encryption schemes.
3. develop the ability to model security problems and to write security proofs.
4. understand fundamental cryptographic primitives including Key Exchange, Digital Signatures, Oblivious Transfer, Public-Key Encryption, Commitment, and critique or prove the security of candidate cryptographic schemes that are supposed to realize the above primitives
5. understand basic computational problems that are important for cryptography such as the factoring problem, the RSA problem, the discrete-logarithm problem, and develop the ability to reduce the security of cryptographic schemes to computational problems

The course is divided in two parts: private key and public key. Topics covered in the private key part are: classical ciphers (Caesar, Vigenere), one-time pad and perfect secrecy, computational secrecy, pseudorandom functions and permutations, CPA security, CCA security and proofs by reduction. The following topics are also briefly discussed: block ciphers, modes of operation, message integrity, hash functions and MACs. In the public key part we cover: hard computational problems such as factoring and discrete log, the Diffie-Hellman key exchange protocol, ElGamal and digital signatures. Other topics that may also be discussed (depending on time) are: zero-knowledge proofs, Schnorr Identification, commitment schemes and oblivious transfer protocols. A tentative outline of the material is given below.

Part 1: Private Key

- Classical ciphers: Shift cipher, Vigenere
- Perfect secrecy
- One-time pad (OTP)
- Computational secrecy
- Pseudorandom generators (PRG)
- Pseudo-OTP
- Security against chosen-plaintext attacks (CPA)
- Pseudorandom functions / permutations (PRF / PRP)
- CPA-secure encryption using PRF/PRP: block ciphers
- Modes of operation: block ciphers, stream ciphers
- Malleability
- Security against chosen-ciphertext attacks (CCA)
- Secrecy vs. integrity: message authentication codes (MAC)
- Hash functions

Part 2: Public Key

- Digital Signatures
- Trapdoor One-Way functions
- Random oracles
- Cyclic groups
- The discrete logarithm/Diffie-Hellman assumptions
- Key exchange and the Diffie-Hellman protocol
- Public Key Encryption
- Security against chosen-plaintext attacks
- ElGamal Encryption
- Zero-Knowledge proofs