Paper 2010/144

New Definitions and Separations for Circular Security

David Cash, Matthew Green, and Susan Hohenberger


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 n-circular security} where the ciphertexts E(pk_1, sk_2), E(pk_2, sk_3), ... E(pk_{n-1}, sk_n), E(pk_n, sk_1) must be indistinguishable from encryptions of zero. Acar et al. (Eurocrypt 2010) provided a CPA-secure public key cryptosystem that is not 2-circular secure due to a distinguishing attack. In this work, we consider a natural relaxation of this definition. Informally, a cryptosystem is n-weak circular secure if an adversary given the cycle E(pk_1, sk_2), E(pk_2, sk_3), ..., E(pk_{n-1}, 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 one-way functions exist, n-weak 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 public-key encryption, under a number-theoretic assumption, 2-weak 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 otherwise-secure 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 commonly-used definitions and systems of encryption. They say to practitioners: if key cycles may arise in your system, then even if you use CCA-secure 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 CCA-Secure Encryption Systems that are not 2-Circular Secure", by Matthew Green and Susan Hohenberger.

Available format(s)
Publication info
Published elsewhere. An extended abstract of this work appears in PKC 2012
EncryptionDefinitionsCircular SecurityCounterexamples
Contact author(s)
matthewdgreen @ gmail com
2012-05-09: last of 4 revisions
2010-03-18: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.