Circular-Secure Encryption from Decision Diffie-Hellman

Authors: D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky

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 (PKi, SKi) for i=1,...,n and we encrypt each SKi 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 SKi under PKj 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 proceedings of Crypto 2008, LNCS 5157, pp. 108-125.

Full paper: pdf