# Composition Does Not Imply Adaptive Security

## Krzysztof Pietrzak

```
```We study the question whether the sequential or parallel composition
of two functions, each indistinguishable from a random function by
non-adaptive distinguishers is secure against adaptive
distinguishers. The sequential composition of F(.) and G(.)
is the function G(F(.)), the parallel composition is
F(.)*G(.) where * is some group operation. It has
been shown that composition indeed gives adaptive security in the
information theoretic setting, but unfortunately the proof does not
translate into the more interesting computational case.
In this work we show that in the computational setting composition
does not imply adaptive security: If there is a prime order cyclic
group where the decisional Diffie-Hellman assumption holds, then
there are functions F and G which are indistinguishable by
non-adaptive polynomially time-bounded adversaries, but whose
parallel composition can be completely broken (i.e. we recover the
key) with only three adaptive queries. We give a similar result for
sequential composition. Interestingly, we need a standard assumption
from the asymmetric (aka. public-key) world to prove a negative
result for symmetric (aka. private-key) systems.