Paper 2010/144
New Definitions and Separations for Circular Security
David Cash, Matthew Green, and Susan Hohenberger
Abstract
Traditional definitions of encryption security guarantee secrecy for any plaintext that can be computed by an outside adversary. In some settings, such as anonymous credential or disk encryption systems, this is not enough, because these applications encrypt messages that depend on the secret key. A natural question to ask is do standard definitions capture these scenarios? One area of interest is ncircular security} where the ciphertexts E(pk_1, sk_2), E(pk_2, sk_3), ... E(pk_{n1}, sk_n), E(pk_n, sk_1) must be indistinguishable from encryptions of zero. Acar et al. (Eurocrypt 2010) provided a CPAsecure public key cryptosystem that is not 2circular secure due to a distinguishing attack. In this work, we consider a natural relaxation of this definition. Informally, a cryptosystem is nweak circular secure if an adversary given the cycle E(pk_1, sk_2), E(pk_2, sk_3), ..., E(pk_{n1}, sk_n), E(pk_n, sk_1) has no significant advantage in the regular security game, (e.g., CPA or CCA) where ciphertexts of chosen messages must be distinguished from ciphertexts of zero. Since this definition is sufficient for some practical applications and the Acar et al. counterexample no longer applies, the hope is that it would be easier to realize, or perhaps even implied by standard definitions. We show that this is unfortunately not the case: even this weaker notion is not implied by standard definitions. Specifically, we show: 1. For symmetric encryption, under the minimal assumption that oneway functions exist, nweak circular (CPA) security is not implied by CCA security, for any n. In fact, it is not even implied by authenticated encryption security, where ciphertext integrity is guaranteed. 2. For publickey encryption, under a numbertheoretic assumption, 2weak circular security is not implied by CCA security. In both of these results, which also apply to the stronger circular security definition, /we actually show for the first time an attack in which the adversary can recover the secret key of an otherwisesecure encryption scheme after an encrypted key cycle is published./ These negative results are an important step in answering deep questions about which attacks are prevented by commonlyused definitions and systems of encryption. They say to practitioners: if key cycles may arise in your system, then even if you use CCAsecure encryption, your system may break catastrophically; that is, a passive adversary might be able to recover your secret keys.
Note: This paper extends and replaces an earlier draft, "CPA and CCASecure Encryption Systems that are not 2Circular Secure", by Matthew Green and Susan Hohenberger.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. An extended abstract of this work appears in PKC 2012
 Keywords
 EncryptionDefinitionsCircular SecurityCounterexamples
 Contact author(s)
 matthewdgreen @ gmail com
 History
 20120509: last of 4 revisions
 20100318: received
 See all versions
 Short URL
 https://ia.cr/2010/144
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/144, author = {David Cash and Matthew Green and Susan Hohenberger}, title = {New Definitions and Separations for Circular Security}, howpublished = {Cryptology ePrint Archive, Paper 2010/144}, year = {2010}, note = {\url{https://eprint.iacr.org/2010/144}}, url = {https://eprint.iacr.org/2010/144} }