For a long time, the arguments that members of the cryptographic community used to exhibit in favor of the security of cryptosystems were deficient and weak (eg empiric validations, wrong proofs). On the contrary, provable security aims to provide the users with more rigorous arguments in favor of cryptographic schemes’ security.

The concept of provable security was introduced by Goldwasser and Micali in their seminar paper Probabilistic Encryption in 1984. It heavily relies on the “computational model”. In this talk we will present the computational model of security and the keys ideas underlaying provable security. This encompasses describing the sort of attackers it considers, how “security” is broadly defined and which proof techniques are used. Regarding proof methodologies, we will specially focus on the “game-playing” technique and (if not running out of time) we will present a proof of ElGamal IN-CPA security using this framework.