Table of contents
Open Table of contents
- What it is
- Security Goals
- Attack Models
- Security Notion
- Semantic Security (IND-CPA)
- IND-CCA implies IND-CPA and NM-CCA implies NM-CPA
- Additional Resources
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.
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:
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 ensures that given a ciphertext that decrypts to a plaintext there should be no way to craft a second ciphertext that decrypts to some plaintext that has a “meaningful” relationship to .
In the literature Non-Malleability is abbreviated as NM.
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):
- Ciphertext Only Attack
- Known Plaintext Attack
- Chosen Plaintext Attack
- Chosen Ciphertext Attack
Ciphertext Only Attack (COA)
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)
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)
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)
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.
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.
- Wikipedia - Attack Model
- Wikipedia - Ciphertext Indistinguishability
- Wikipedia - Malleability
- Wikipedia - Ciphertext Only Attack
- Wikipedia - Known Plaintext Attack
- Wikipedia - Chosen Plaintext Attack
- Wikipedia - Chosen Ciphertext Attack
- Wikipedia - Adaptive Chosen Ciphertext Attack
- Quora - What is the difference between IND-CPA and IND-CCA?
- Cryptography Stack Exchange - Chosen plaintext vs Chosen ciphertext
- Cryptography Stack Exchange - The difference between these 4 breaking Cipher techniques?