Suppose we have an encryption scheme that fails the indistinguishability of encryptions test. That is, given messages $m_0, m_1$ and a ciphertext $c_b = Enc_k(m_b)$, where $b \in \{0, 1\}$, the distinguisher $D$ can extrapolate which message was encrypted. Here $D$ has the advantage of knowledge of what the messages are.

In CPA test however, after observing a set of (plaintext, ciphertext) pairs we are presented with a previously unobserved ciphertext. Our task here is not to distinguish (there is nothing to distinguish from...) but rather to decipher.

My question is, does failure of indistinguishability of encryptions imply lack of CPA-security?


1 Answer 1

  1. Faliure of indistinguishablity of encryptions under a eavesdropper does imply faliure of indistinguishablity of encryptions under a chosen-plaintext attack. But the converse is not necessarily true (ex. OTP)

  2. The aim of CPA-secure is not to decrypt previously unobserved ciphertext but to pass the distinguishability test after a set of (plaintext, ciphertext) observations.

Katz's Intro to Modern Crypto

  • $\begingroup$ Yes, except for use of OTP as an example. Let's take the semantic step of considering that the OTP can be subjected to the test while still remaining worth of its name, despite the fact that a single key $k$ is drawn at step 1, and it is shorter than the total (or even individual) size of messages at 2 and 4. We have to admit that this OTP is used with the same pad at each use in 2 and 4 (with the pad a repetition of the key for longer messages). This OTP fails the test of indistinguishablity of encryptions under eavesdropping, and is thus not a proper example of the point discussed. $\endgroup$
    – fgrieu
    May 18, 2015 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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