Security Notion

Table of contents

Open Table of contents

What it is

When deciding which cryptographic construction to implement, it’s useful to know its security guarantees given the environment it will be implemented in.

Security notions allow cryptographers to define such security guarantees in a standardized way by encapsulation the security goal as well as the attack model an adversary might operate in.

Security Goals

The first part that’s necessary for a security notion is the security goal we want to achieve. Looking through the lens of an attacker, we need to ask ourselves what we consider a successful attack.

Generally speaking there are two major security goals:

  1. Indistinguishability
  2. Non-Malleability

Indistinguishability (IND)

The property of indistinguishability means that generated ciphertexts should be indistinguishable from “random noise”. To illustrate what this means we can imagine the following scenario where given two plaintexts and a ciphertext that either encrypts the first or the second plaintext, it’s impossible to tell which plaintext the ciphertext encrypts (i.e. there’s a 50% chance that it was the first or the second plaintext).

Practically speaking, this implies that encryptions of plaintexts need to result in ciphertexts that incorporate some form of randomness such that the same plaintext will always map to a different ciphertext when encrypted, therefore being indistinguishable from random noise.

In the literature Indistinguishability is abbreviated as IND.

Non-Malleability (NM)

Non-Malleability ensures that given a ciphertext c1c_1 that decrypts to a plaintext p1p_1 there should be no way to craft a second ciphertext c2c_2 that decrypts to some plaintext p2p_2 that has a “meaningful” relationship to p1p_1.

In the literature Non-Malleability is abbreviated as NM.

Attack Models

A second, necessary aspect we have to define before we can analyze cryptographic constructions is the attack models they should withstand. Attack models define what an attacker can and cannot do / what data an attacker has or doesn’t have access to.

There are various attack models, but the cryptographic literature mostly focuses on the following four (sorted from weakest to strongest):

  1. Ciphertext Only Attack
  2. Known Plaintext Attack
  3. Chosen Plaintext Attack
  4. Chosen Ciphertext Attack

Ciphertext Only Attack (COA)

Type: Passive

Strength: 1 / 4

In a Ciphertext Only Attack the adversary has only access to ciphertexts which are obtained passively through eavesdropping.

This type of attack is the weakest as the only information the attacker has access to are the said ciphertexts.

In the literature a Ciphertext Only Attack is abbreviated as COA.

Known Plaintext Attack (KPA)

Type: Passive

Strength: 2 / 4

The Known Plaintext Attack extends the Ciphertext Only Attack in that the adversary gains access to (plaintext, ciphertext) pairs. This information is also gathered passively through eavesdropping.

In the literature a Known Plaintext Attack is abbreviated as KPA.

Chosen Plaintext Attack (CPA)

Type: Active

Strength: 3 / 4

In a Chosen Plaintext Attack the attacker gains access to an encryption oracle which can be used to encrypt arbitrary plaintexts and therefore get access to the corresponding ciphertext.

This attack mode is active because the adversary needs to query the encryption oracle for the plaintext’s ciphertext.

In asymmetric cryptosystems the attacker can use a public key to get access to an encryption oracle and therefore a plaintext’s ciphertext.

In the literature a Chosen Plaintext Attack is abbreviated as CPA.

Chosen Ciphertext Attack (CCA)

Type: Active

Strength: 4 / 4

A Chosen Ciphertext Attack extends the Chosen Plaintext Attack in that the adversary gains access to a decryption oracle (alongside the encryption oracle) which can be used to get the plaintext for a given ciphertext. Note that the attacker can request decryptions for any kind of ciphertext, whether it’s considered “valid” (i.e. it doesn’t decrypt to some nonsense) or not.

The Chosen Ciphertext Attack is the strongest form of attack given the amount of information and resources the attacker has access to.

In the literature a Chosen Ciphertext Attack is abbreviated as CCA.

Security Notion

As mentioned in the beginning, it’s useful to know what kind of security guarantees a cryptogrpahic construction provides. Given that the real world is a messy place we should consider both, the security goal as well as the attack model when defining and analyzing security guarantees. This is where security notions come into play.

A security notion combines a security goal with an attack model. To reduce verbosity it’s written by taking the capitalized abbreviation of the security goal and combining it with the capitalized abbreviation of the attack model using a hyphen (-) as a separator.

So if you e.g. read IND-CPA it means that the primitive provides resistance against distinguishing ciphertexts using a Chosen Plaintext Attack.

Semantic Security (IND-CPA)

One very important security notion is that of IND-CPA which intuitively means that every generated ciphertext should look like random noise even if the same plaintext is encrypted. So ciphertexts shouldn’t leak any information about the plaintext considering that the key is kept secret.

IND-CPA is oftentimes also called “Semantic Security”.

IND-CCA implies IND-CPA and NM-CCA implies NM-CPA

It’s worth noting that security notions have relationships to each other.

Two of them are that IND-CCA implies IND-CPA and that NM-CCA implies NM-CPA. This is easy to see as a Chosen Ciphertext Attack can be understood as the superset which the weaker Chosen Plaintext Attack is a subset of, meaning that anything a CPA attacker can do a CCA attacker can do as well.

References

The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.