Technical Perspective: What Does Provable Security Mean for Cryptographic Schemes?

In the early ages of cryptography, cryptographic schemes were considered secure until an attack could break them. But such an attack may take time to be discovered, and it might be too late. In the 1980s, a new paradigm emerged with the notion of provable security, with three important steps: the security model, the computational assumptions, and the proof by reduction.

The most important step is the formalization of a security model, which precisely states what security should mean, or alternatively, which attacks one wants to withstand. With public-key encryption, as studied in the following paper, one could simply expect the one-wayness, which basically requires that from a ciphertext, without the decryption key, it is difficult to recover the plaintext. But this is a very weak security notion. It has thereafter been improved into semantic security, which can be seen as a computational variant of perfect privacy: no adversary can recover one bit of information of the plaintext, still from the ciphertext and without the decryption key.