We describe a public-key
encryption system that remains secure even encrypting messages that
depend on the secret keys in use. In particular, it remains secure
under a “key cycle” usage, where we have a cycle of
public/secret key-pairs (PK_{i}, SK_{i})
for *i*=1,...,*n*, and we encrypt each SK_{i}
under PK_{(i mod n)+1}. Such usage scenarios
sometimes arise in key-management systems and in the context of
anonymous credential systems. Also, security against key cycles plays
a role when relating “axiomatic security” of protocols
that use encryption to the “computational security” of
concrete instantiations of these protocols.

The existence of encryption systems that are secure in the presence of key cycles was wide open until now: on the one hand we had no constructions that provably meet this notion of security (except by relying on the random-oracle heuristic); on the other hand we had no examples of secure encryption systems that become demonstrably insecure in the presence of key-cycles of length greater than one.

Here we construct an
encryption system that is circular-secure against chosen-plaintext
attacks under the Decision Diffie-Hellman assumption (without relying
on random oracles). Our proof of security holds even if the adversary
obtains an encryption clique, that is, encryptions of
SK_{i} under PK_{j} for all 1 ≤
*i*,*j* ≤ *n*. We also construct a circular
counterexample: a one-way secure encryption scheme that breaks
completely if an encryption cycle (of any size) is published.

In the updated version, we
show how to generalize the system to work under the Decision *k*-Linear
Assumption.