36
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ Where have you seen IND-CCA3? $\;$ $\endgroup$ – user991 Jul 3 '15 at 11:04
  • 1
    $\begingroup$ @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. $\endgroup$ – SEJPM Jul 3 '15 at 11:06
  • 2
    $\begingroup$ This paper by Bellare, Desai, Pointcheval and Rogaway from CRYPT'98 provides "canonical" definitions of most of these notions in the context of PKE (except for IND-CCA3) and most importantly, gives implications and separations. $\endgroup$ – cygnusv Jul 3 '15 at 11:24
  • $\begingroup$ If you're looking for signature scheme, we have a Q&A about those here. $\endgroup$ – SEJPM Feb 26 '17 at 16:34
40
$\begingroup$

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 $\operatorname{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 = $ choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time including calls to the encryption oracle.
  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 including calls to the encryption oracle. 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 negligible. 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, especially 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 (a polynomially-bounded number of times): call the encryption or decryption oracle for arbitrary plaintexts or ciphertexts, respectively
  3. Adversary: $m_0, m_1 = $ 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.

IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack

In words: In addition to its capabilities under IND-CCA1, 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 = $ 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.

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 misleading.

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:$ returns 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 a focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

Note that in the case of public-key cryptography the adversary is always given access to the public key $K_E$ as well as the encryption function $E(K_E, \cdot)$.

$\endgroup$
  • 1
    $\begingroup$ IND-CCA3. Does this enable you to add this to the answer? $\endgroup$ – SEJPM Jul 6 '15 at 18:48
  • 1
    $\begingroup$ IND-CCA usually refers to IND-CCA2. See the paper I mentioned in the comments of the question $\endgroup$ – cygnusv Jul 6 '15 at 20:45
  • $\begingroup$ I edited the answer to include the information in the comments. I believe my interpretation of IND-CCA3 to be accurate, but since it is the first time I encounter it, I might have misunderstood it. Feel free to comment or edit. $\endgroup$ – Sergio Andrés Figueroa Santos Jul 6 '15 at 22:13
  • 3
    $\begingroup$ 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) $\endgroup$ – cygnusv Jul 7 '15 at 7:03
  • 2
    $\begingroup$ After about a full year of inactivity, I "fixed" a couple of things with this post. I (unknowingly I have to admit) incorporated the fix suggested by @user2768 and removed the EDIT notes which didn't add any value. I also followed the suggestion by @ b00n12 and added the note on the access to the encryption oracle for IND-CPA. $\endgroup$ – SEJPM Oct 2 '17 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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