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.

The goals of this course, in terms of expected results, are

1. Knowledge and understanding. Students will learn the fundamental ideas and the basic principles of modern cryptography. More specifically, students will be able to understand some of the most important cryptographic schemes and primitives used in practice.
2. Applying knowledge and understanding. Students will be able to use, in a secure way, cryptographic schemes such as encryption schemes, authentication schemes and cryptographic hash functions
3. Making judgements. By studying concrete examples of seemingly secure (but wrong) solutions students will learn how to use cryptographic schemes providing high security guarantees.
4. Communication Skills. Students will learn how to properly communicate using the technical language of modern cryptography
5. Learning Skills. A goal of this course is to provide a good theoretical and practical background of modern cryptography. It is expected that students will learn how to autonomously address problems that require the usage of cryptographic primitives such as digital signatures, encryption schemes and cryptographic hash functions.

Lecture-based

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].

12. Introduction to Bitcoin. Blockchain and Merkle Trees. Some simple cryptocurrencies. Consensus. How Bitcoin realizes consensus. Proofs of Work. Mining. Bitcoin and anonymity.

Source: Variuos chapters from [4]

[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

[4] A. Miller, A. Narayanan, E. Felten, J. Bonneau, and S. Goldfeder “Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction”. Princeton University Press.