CRYPTOGRAPHY

This class is intended to provide an introduction to the main concepts of modern cryptography. The main focus will be on definitions and constructions of various cryptographic cryptographic tools, such as encryption schemes, message authentication codes and digital signatures. We will try to understand what properties we expect from these objects, how to formally define these properties and how to construct schemes that realize them. We will also focus on schemes that are widely used in practice. These include, for instance, AES, SHA, HMAC and RSA. However, rather than using these tools as black box, we will show how they are built and the security level they provide. No programming will be required for this class.

1. Introduction to the main ideas of this class.

Source: Cap 1 from [1]

2. Classical Ciphers and One Time Pad. Shift cipher and substitution cipher. Cryptanalysis of the substitution cipher. Perfect Security. The substitution cipher does not guarantee perfect security (with proof). One time pad. One time pad provides perfect perfect security (with proof).

Source: Cap 2 from [1]

3. Block Ciphers: AES

Source: Cap 3 from [1]

4. Pseudorandom Functions and Pseudorandom Permutations. Introduction and definitions. Applications to block ciphers. Examples. PRF security implies key recovery security (with proof). The birthday paradox.

Source: Cap. 4 and Appendix from [1]

5. Symmetric encryption: modes of operation. ECB, CBC$, CTRC and CTR$. Security definitions for symmetric encryption: Indistinguishability against chosen plaintext attack (IND-CPA). Indistinguishability under chosen-plaintext attack (IND-CCA). Proof that any deterministic, stateless scheme is insecure. Proof that IND-CPA security implies security in the sense of plaintext recovery. IND-CPA security does not imply IND-CCA security: the case of the CTR$ mode.

Source: Cap 5 from [1]

6. Hash functions and collision resistance. Universal hash functions, universal one-way hash functions, collision resistant hash functions. Generic attacks to collision resistance. The Merkle-Damgard transform.

Source: Cap 6 from [1]

7. Message Authentication. Notion of security for MACs. The PRF as a MAC paradigm. CBC-MAC. Basic CBC-MAC on variable length messages is insecure. (In)security of randomized CBC-MAC.

Source: Cap 7 from [1]

8. Intro to asymmetric cryptography. One way functions and Trapdoor (one-way) functions. Number theory basics. Groups. Euclid's algorithm, Chinese remainder theorem. Quadratic Residues

Source: Cap 9 from [1], relevant parts from [2]

9. Asymmetric primitives. Discrete logarithms. Computation Diffie Hellman problem and Decisional Diffie Hellman problem. Factoring and RSA. Primality testing. The square and multiply algorithm.

Source: Cap 10 from [1].

10. Asymmetric encryption. Notions of security: security against chosen-plaintext attacks and security against chosen ciphertext attacks. Asymmetric cryptosystems. The El-Gamal encryption scheme. Proof that El Gamal provides IND-CPA security under the Decisional Diffie Hellman assumption. Paillier's Cryptosystem. RSA-OAEP. Identity-based Encryption: the Boneh Franklin IBE

Source: Cap 11 from [1] and slides

11. Digital Signatures. A notion of security for digital signatures. The Hash then invert paradigm for digital signatures.

Source: Cap 12 from [1].

[1] M. Bellare, P. Rogaway “Introduction to Modern Cryptography”

• Scaricabile da http://www.cs.ucsd.edu/~mihir/cse107/classnotes.html

[2] V. Shoup A Computational Introduction to Number Theory and Algebra

• Scaricabile da http://shoup.net/ntb/

[3] J. Katz, Y. Lindell “Introduction to Modern Cryptography” CRC press