See an informal description of the result in:
CS 2008 Annual Report.
Circular-Secure Encryption from Decision Diffie-Hellman.
Dan Boneh, Shai Halevi, Michael Hamburg, Rafail 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 (\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.
comment: CRYPTO 2008: 108-125
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |