When is an encryption scheme secure?

Last week, we saw what public key cryptography is and how it works.

One question you may have had is how do we know if this provides security? In other words, how can we guarantee that if we use public key cryptography no one can intercept our messages and decrypt them?

This week, we will see one way we can define security. To begin, let us introduce some notions about encryption schemes (that use public key cryptography). There are three algorithms that make up an encryption scheme:

1. The key generation algorithm outputs a public and secret key. (pk, sk) ← key gen.
2. The encryption algorithm (E), takes as input the public key and a message and outputs an encrypted message (a ciphertext). c ← E(pk, m).
3. The decryption algorithm (D), takes as input the secret key and the ciphertext and outputs the original message. m ← D(sk, c).

The next question is, how can we know that an encryption scheme is secure? One common way to do this is to set up a game, between an adversary (trying to break the encryption) and the challenger (challenging the adversary to break it). The game runs as follows:

• The challenger generates a public and secret key using the key generation algorithm, and hands the public key to the adversary;
• The challenger asks the adversary to pick two messages, (m0,m1). The challenger then chooses one at random and encrypts it and passes it back to the adversary;
• The adversary’s task is to guess which message it was handed;
• The adversary wins the game if it guesses correctly.

We say the encryption scheme is secure if:

Pr [ adversary winning game] < 1/2 + μ

Where μ is a negligible function (a small quantity). This definition has allowed us to mathematically define a notion of security and thus we can prove whether an encryption scheme is secure or not under this definition.

Questions:

1. Why does the ½ appear in the definition of security?
2. How can we make the definition of security stronger? Hint: think about how we could make the game harder.

This article was written by David Butler, one of the course creators and teachers at Oxbridge Inspire. David is studying for a PhD at the Alan Turing Institute in London.

If you enjoyed this article, you might consider coming to our course in Cambridge this summer on the Mathematics behind Cryptography.