International Association
for Cryptologic Research

We formalise the notion of adaptive proofs of knowledge in the random oracle model,

where the extractor has to recover witnesses for multiple, possibly adaptively chosen

statements and proofs. We also discuss extensions to simulation soundness, as typically

required for the ``encrypt-then-prove\'\' construction of strongly secure encryption

from IND-CPA schemes.

Utilizing our model we show three results:

(1) Simulation-sound adaptive proofs exist.

(2) The ``encrypt-then-prove\'\' construction with a simulation-sound

adaptive proof yields CCA security. This appears to be a ``folklore\'\' result

but which has never been proven in the random oracle model. As a corollary, we

obtain a new class of CCA-secure encryption schemes.

(3) We show that the

Fiat-Shamir transformed Schnorr protocol is _not_ adaptively secure and

discuss the implications of this limitation.

Our result not only separates

adaptive proofs from proofs of knowledge, but also gives a strong hint why

Signed ElGamal as the most prominent encrypt-then-prove example has not been

proven CCA-secure without making further assumptions.