In order to be indistinguishable with respect to multiple messages, wouldn't the scheme need to be nondeterministic? How would this then possibly be vulnerable to an adaptive CPA?

  • 2
    $\begingroup$ Are you asking if a cryptosystem that can withstand a non-adaptive chosen plaintext attack must also withstand an adaptive chosen plaintext attack? $\endgroup$ – K.G. Nov 8 '13 at 22:18
  • 1
    $\begingroup$ Exactly -- though I'm really asking for an example rather than just a yes, as I'm aware that being able to withstand an adaptive CPA is theoretically more difficult than a non-adaptive one. $\endgroup$ – Richard James Nov 8 '13 at 22:28

If you're asking about block ciphers. Yes, it's possible. Security against non-adaptive attacks does not imply security against adaptive attacks. A simple example of a block cipher that is secure against non-adaptive attacks but insecure against adaptive attacks would be a random involution. No, it doesn't need to be nondeterministic.

We say that a function $f:X\to X$ is an involution if $f$ is bijective and $f(f(x)) = x$ for all $x \in X$. Suppose we have a block cipher $E:K \times X \to X$ where $E_k(\cdot)$ is an involution for all $k$. Then $E$ is not secure against adaptive chosen-plaintext attack: an attacker can request the encryption of $x$, then request the encryption of that ciphertext, and check whether the result is equal to $x$. However $E$ can be secure against non-adaptive chosen-plaintext attack.

An example construction of such a block cipher would be

$$E_k(x) = \text{AES-Decrypt}_k(\text{AES-Encrypt}_k(x) \oplus 1).$$

This is secure against non-adaptive chosen-plaintext attack (assuming that AES is secure) but insecure against adaptive chosen-plaintext attack.

If you're asking about encryption schemes. Yes, it's possible. Security against non-adaptive attacks does not imply security against adaptive attacks. It's easy to construct counterexamples.

For instance, consider the following encryption scheme. To encrypt a message $m$ under key $k=(k_1,k_2)$, we first check whether $m=k_1$. If $m \ne k_1$, then we pick $r$ randomly (subject to the constraint that $r\ne 0$) and output the ciphertext $c=(r,\text{AES}_{k_2}(r)\oplus m, k_1)$. Otherwise, we output the ciphertext $c=(0,m,k_1)$.

This is a crazy-looking encryption scheme, but it is possible to show that it is secure against non-adaptive attacks: basically, it is just counter-mode encryption of a single-block message (since the attacker has no hope of guessing $k_1$). However, this is completely insecure against adaptive attacks: an attacker who observes one ciphertext can learn $k_1$, from whence they can pose a chosen-plaintext message that lets them build a distinguishing attack.

| improve this answer | |
  • 5
    $\begingroup$ Hm, but if a scheme isn't probabilistic, then any given plaintext will consistently result in a specific ciphertext, failing indistinguishability in the multiple messages case as the pair of messages $1, 1$ will be clearly distinguishable from $0, 1$, right? $\endgroup$ – Richard James Nov 9 '13 at 8:10

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.