Circular-Secure Encryption from Decision Diffie-Hellman
Authors: D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky
Abstract:
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
Reference:
In proceedings of Crypto 2008, LNCS 5157, pp. 108-125.
Full paper: pdf