Overview of the course:

Cryptography aims at securing communications against malicious parties. This field enjoys numerous links with theoretical computer science (complexity theory, security proofs) but has also a very rich practical counterpart: cryptographic protocols are part of everyday life (electronic commerce, payment cards, electronic voting, etc). This course is an introduction to the different facets of modern cryptography. symmetric encryption, asymmetric encryption, cryptographic hashing, authentication, pseudo-random generators, cryptanalysis, security proofs.

The course will introduce the following notions:

  • Computational indistinguishability and intractability assumptions
  • Pseudorandom generators
  • Pseudorandom functions
  • Symmetric encryption
  • Message authentication codes
  • Cryptographic hash functions
  • Public-key encryption
  • Digital signatures

Course objectives:

  • Understand basic notions of cryptography: Definitions, security requirements, relations between them, and their limitations.
  • Understand how to prove security of primitives via reduction to intractability assumptions, both in the standard and in the random oracle models

Prerequisites:

None, though basic knowledge of algebra, probability, complexity, and information theory are a plus.

Evaluation:

2 homeworks (50%) and 3-hour written exam (50%).

Homework 1 is now available: [pdf] - Due date: Mar. 6
Homework 2 is now available: [pdf] - Due date: Apr. 8

Final exam: Apr. 8, 2pm-5pm, amphi B.

Class Material:

Previous Classes:

  • Class 1 (Jan. 15):
    A brief overview of cryptography: SSL/TLS, perfect security for symmetric encryption, Vernam/One-Time-Pad cipher, pseudorandom generators.
  • Class 2 (Jan. 22):
    A formal definition of computational security, PRG, unpredictability = indistinguishability, hybrid proofs, one-time IND-CPA symmetric encryption.
  • Class 3 (Jan. 29):
    One-time secure symmetric encryption from PRG, Insecurity of WEP, PRG in theory and practice, the discrete logarithm problem, algorithms for DLog.
  • Class 4 (Feb. 5):
    Diffie-Hellman assumptions, the learning with errors (LWE) problems, algorithms for LWE, DDH-based and LWE-based PRGs, pseudorandom functions.
  • Class 5 (Feb. 12):
    Equivalence PRG-PRF, Feistel networks, DES/AES, IND-CPA secure symmetric encryption, IND-CPA-SE from PRFs
  • Class 6 (Feb. 19):
    Message Authentication Codes, MAC from PRFs, CBC-MAC and ECBC-MAC, IND-CCA secure SE from PRFs.
  • Class 7 (Mar. 4):
    Cryptographic hash functions, birthday paradox, Merkle-Damgard construction, HMAC, DLog-based collision-resistant hash function.
  • Class 8 (Mar. 11):
    Limits of symmetric cryptography, public-key cryptography, public-key encryption, KEM/DEM, IND-CPA security, ElGamal PKE, Lyubashevsky-Palacio-Segev PKE.
  • Class 9 (Mar. 18):
    The random oracle methodology, IND-CCA PKE, Fujisaki-Okamoto transform
  • Class 10 (Mar. 25):
    Digital signatures, public-key infrastructure, Schnorr's signature, Katz-Wang signature, Lyubashevsky's signature (LWE variant)

Previous Classes:

Some References: