Proofs of Security (PRS)


The objective of this cryptographic module is to provide students with fundamental knowledge in the field of theoretical cryptography and in particular of the security of cryptographic primitives such as signatures, encryption schemes, reductions. This course will be useful for anyone interested in formalizing the security of a property.


Cryptography, security models, reductions.


Basic knowledge of reductions between NP-problems and a first course in cryptography can be useful


  • Introduction to Security Proof: Unconditional and Computational Security (Shannon confidentiality, One-Time Pad, Reductions)
  • Security model for public-key encryption scheme (El Gama security)
  • Security Model for Signature and Hash Function (Random Oracle Model, RSA-FDH, and Boneh-Boyen without ROM)
  • Zero-Knowledge Proof and authentication scheme (Guilloux-Quisquater,Schnorr)
  • Advanced Signature schemes based on RSA (PSS, security of FDH by JSCoron)
  • Advanced Encryption Schemes (CCA, RSA -- ROM paper by Bellare-Rogaway for encryption schemes, Cramer-Shoup)
  • Reduction between security models, game-based proof and concrete security (CCA1/CCA2/NM...)
  • Security Proofs in Symmetric Cryptography (Hash-based Signature, security of modes of operations for encryptions and hash functions)

Learning outcomes

The knowledge necessary to understand and create security proof for basic primitives.

Teaching staff

Pierre-Alain Fouque (resp), Adeline Roux-Langlois, Olivier Sanders