Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security.

The most common ones are the "IND-" ones, advertising security against specific classes of attackers.
Now these notion may not be that well-understood by many people so I ask hereby for a canonical answer, that explains what the following security notions mean. A (simple) description of the formal attack scenario is preferred.
Please don't restrict the answer to "you can chose this and if you can break it with this it isn't IND-CCA2". Please at least outline the formal attack (like f.ex. real-or-random). Relations between the "IND-" are explained (f.ex. IND-CCA implies IND-CPA).
The notions in question are:

  • IND-CPA
  • IND-CCA
  • IND-CCA1
  • IND-CCA2
  • IND-CCA3
share|improve this question
    
Where have you seen IND-CCA3? $\;$ –  Ricky Demer Jul 3 at 11:04
    
@RickyDemer, not that often. Until now, only every now and then in some papers. The first paper to mention it was this one I think. –  SEJPM Jul 3 at 11:06
    
Another notion is IND-CCA1. $\;$ –  Ricky Demer Jul 3 at 11:08
    
@RickyDemer, added. The answer will have to clarify that it's the same as IND-CCA (AFAIK). –  SEJPM Jul 3 at 11:10
2  
No, I don't think it is a duplicate. You will not necessarily understand the precise meaning of IND-CPA just because you know what is meant by a Chosen Plaintext Attack, etc –  Henrick Hellström Jul 3 at 12:43

1 Answer 1

up vote 2 down vote accepted

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $IND-$ notation provides such definitions in terms of games, where a challenger keeps his key secret, and an adversary has certain capabilities and his target is to break the encryption system.

To keep it general, an encryption scheme will have a key generation algorithm $KG$, which will generate a key pair $K_E$, $K_D$, an encryption algorithm $E$ and a decryption algorithm $D$. Encryption is always revertible, but the encryption and decryption key can be different (covering public key crypto): $D(K_D, E(K_E, M))=M$

IND-CPA: INDistinguishability under Chosen Plaintext Attack

In words: the adversary generates two messages of equal length. The challenger decides, randomly, to encrypt one of them. The adversary tries to guess which of the messages was encrypted.

Algorithm:

  1. Challenger: $K_E, K_D$ = KG(security parameter)
  2. Adversary: $m_0, m_1 = $ randomly choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time. (edited to include polynomial operations also at the beginning)
  3. Challenger: $b=$ randomly choose between 0 and 1
  4. Challenger: $C:=E(K_E, m_b)$. Send $C$ to the adversary.
  5. Adversary: perform additional operations in polynomial time. Output $guess$
  6. If $guess=b$, the adversary wins

Further comment: the main concept introduced by this scenario is the polynomial bound. Now, our expectations from crypto are weakened from probability of winning is negligible to probability of winning within a reasonable timeframe is neglible. The restriction for the messages to be of the same length aims to prevent the adversary to trivially win the game by just comparing the length of the ciphertexts. However, this requirement is too weak, specially because it assumes only a single interaction between the adversary and the challenger.

IND-CCA1: INDistinguishability under Chosen Ciphertext Attack

In words: the target of the game is the same as in IND-CPA. The adversary has an additional capability: to call an encryption or decryption oracle. That means: the adversary can encrypt or decrypt arbitrary messages before obtaining the challenge ciphertext.

Algorithm:

  1. Challenger: $K_E, K_D$ = KG(security parameter)
  2. **Adversary (as many times as he wants): call the encryption or decryption oracle for an arbitrary **
  3. Adversary: $m_0, m_1 = $ randomly choose two messages of the same length
  4. Challenger: $b=$ randomly choose between 0 and 1
  5. Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
  6. Adversary: perform additional operations in polynomial time. Output $guess$
  7. If $guess=b$, the adversary wins

Further comment: IND-CCA1 considers the possibility of repeated interaction, implying that security does not weaken with time. Edited to remove: Another consequence of IND-CCA1 is non-malleability: the ciphertext cannot be tampered to be decrypted into a $M' \neq M$.

IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack

In words: In addition to its capabilities under IND-CCA2, the adversary is now given access to the oracles after receiving $C$, but cannot send $C$ to the decryption oracle.

Algorithm:

  1. Challenger: $K_E, K_D$ = KG(security parameter)
  2. Adversary (as many times as he wants): call the encryption or decryption oracle for an arbitrary plaintext/ciphertext
  3. Adversary: $m_0, m_1 = $ randomly choose two messages of the same length
  4. Challenger: $b=$ randomly choose between 0 and 1
  5. Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
  6. Adversary: perform additional operations in polynomial time, including calls to the oracles, for ciphertexts different than $C$. Output $guess$.
  7. If $guess=b$, the adversary wins

Further comment: IND-CCA2 suggests that using the decryption oracle after knowing the ciphertext can give a reasonable advantage in some schemes, since the requests to the oracle could be customized depending on the specific ciphertext.

EDIT: Based on the comments, I changed every appearance of IND-CCA for IND-CCA1. There seems to be disagreement regarding if IND-CCA is equivalent to IND-CCA1 or IND-CCA2. The notion of IND-CCA3 is added based on the reference provided by @SEJPM. I add it for completeness, but it seems important to point out that there are few resources about it, and my interpretation could be mislead.

IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

In words: It is not possible to create a valid forgery with non-negligible probability. The adversary is given two pairs of encryption/decryption oracles. The first pair performs the intended encryption and decryption operations, while the second one is defined as follows: $\mathcal{E}_K$: returns encryptions of random strings. $\mathcal{D}_K:$ return INVALID. Instead of being presented as a game, it is presented using the mathematical concept of advantage: the improvement of the probability of winning by using the valid oracle against the probability of success under the "bogus" oracle.

Formula: $\mathbf{Adv}^{ind-cca3}_{\pi}(A)=Pr\left[K\overset{\$}{\leftarrow}\mathcal{K}:A^{\mathcal{E}_K(\cdot),\mathcal{D}_K(\cdot)}\Rightarrow 1\right] - Pr\left[A^{\mathcal{E}_K(\$|\cdot|),\perp(\cdot)}\Rightarrow 1\right] $

Further comment: the paper where IND-CCA3 is introduced focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

share|improve this answer
1  
IND-CCA3. Does this enable you to add this to the answer? –  SEJPM Jul 6 at 18:48
    
I quickly edited your answer. I've made the IND-CCA2 italic and moved the (adaptive) in the phrase, so it now reads "IND(...) under adaptive CCA" –  SEJPM Jul 6 at 18:58
    
Indeed IND-CCA is the same as IND-CCA1 (the 1 is somewhat unneeded but added to put it in-line with IND-CCA2 and IND-CCA3), you may want to add it as a second line after your IND-CCA line. –  SEJPM Jul 6 at 19:02
    
IND-CCA usually refers to IND-CCA2. See the paper I mentioned in the comments of the question –  cygnusv Jul 6 at 20:45
2  
Several comments: (1) Since you want to cover both symmetric and asymmetric crypto, you have to specify that the adversary has access to an encryption oracle (redundant in the asymmetric case). (2) Between steps 1 and 2 of the IND-CPA game, the adversary can also perform operations in polynomial time. (3) IND-CCA1 does not imply non-malleability (at least for the asymmetric case, Bellare et al. proved that IND-CCA1 does not imply NM-CPA) –  cygnusv Jul 7 at 7:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.