How can an encryption scheme be indistinguishable with multiple messages but vulnerable to an adaptive chosen-plaintext attack?

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?

-
Are you asking if a cryptosystem that can withstand a non-adaptive chosen plaintext attack must also withstand an adaptive chosen plaintext attack? – K.G. Nov 8 '13 at 22:18
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. – 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.

-
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? – Richard James Nov 9 '13 at 8:10