Security goals
A cipher is secure if, even given a large number of plaintext–ciphertext pairs, nothing can be learned about the cipher’s behavior when applied to other plaintexts or ciphertexts.
What can be “learned” and what is a “cipher’s behaviour”? Security goals are descriptions of what is considered a successful attack. Cryptographers define two main security goals that correspond to different ideas of what it means to learn something about a cipher’s behaviour.
Indistinguishability (IND)
Ciphertexts should be indistinguishable from random strings. This is usually illustrated with a hypothetical game: if an attacker picks two plaintexts and then receives a ciphertext of one of the two (chosen at random), they shouldn’t be able to tell which plaintext was encrypted, even by performing encryption queries with the two plaintexts (and decryption queries, if the model is CCA rather than CPA).
Non-malleability (NM)
Given a ciphertext
Surprisingly, the one-time pad is malleable: given a ciphertext
Security goals are only useful when combined with an attack model. The convention is to write a security notion as GOAL-MODEL. For example, IND-CPA denotes indistinguishability against chosen-plaintext attackers, NM-CCA denotes nonmalleability against chosen-ciphertext attackers, and so on.
Semantic security (IND-CPA)
The Semantic security notion captures the intuition that ciphertexts should not leak any information about plaintexts as long as the key is secret. To achieve IND-CPA security, encryption must return different ciphertexts if called twice on the same plaintext; otherwise, an attacker could identify duplicate plaintexts from their ciphertexts, contradicting the definition that ciphertexts shouldn’t reveal any information.
One way to achieve IND-CPA security is to use randomised encryption:With randomised encryption, ciphertexts must be slightly longer than plaintexts in order to allow for more than one possible ciphertext per plaintext. For example, if there are
One of the simplest constructions of a semantically secure cipher uses a deterministic random bit generator (DRBG), an algorithm that returns randomlooking bits given some secret value:
Here,
The proof that this cipher is IND-CPA secure is simple, if we assume that the DRBG produces random bits. The proof works ad absurdum: if you can distinguish ciphertexts from random strings, which means that you can distinguish XOR
Asymmetric encryption
The attack models and security goals for asymmetric encryption are about the same as for symmetric encryption, except that because the encryption key is public, any attacker can make encryption queries by using the public key to encrypt. The default model for asymmetric encryption is therefore the chosen-plaintext attacker (CPA).
Symmetric and asymmetric encryption are the two main types of encryption, and they are usually combined to build secure communication systems. They’re also used to form the basis of more sophisticated schemes.