Paper 2012/150

Circular chosen-ciphertext security with compact ciphertexts

Dennis Hofheinz


A key-dependent message (KDM) secure encryption scheme is secure even if an adversary obtains encryptions of messages that depend on the secret key. Such key-dependent encryptions naturally occur in scenarios such as harddisk encryption, formal cryptography, or in specific protocols. However, there are not many provably secure constructions of KDM-secure encryption schemes. Moreover, only one construction, due to Camenisch, Chandran, and Shoup (Eurocrypt 2009) is known to be secure against active (i.e., CCA) attacks. In this work, we construct the first public-key encryption scheme that is KDM-secure against active adversaries and has compact ciphertexts. As usual, we allow only circular key dependencies, meaning that encryptions of arbitrary *entire* secret keys under arbitrary public keys are considered in a multi-user setting. Technically, we follow the approach of Boneh, Halevi, Hamburg, and Ostrovsky (Crypto 2008) to KDM security, which however only achieves security against passive adversaries. We explain an inherent problem in adapting their techniques to active security, and resolve this problem using a new technical tool called ``lossy algebraic filters'' (LAFs). We stress that we significantly deviate from the approach of Camenisch, Chandran, and Shoup to obtain KDM security against active adversaries. This allows us to develop a scheme with compact ciphertexts that consist only of a constant number of group elements.

Note: Additional intuition for the main scheme. Update (Oct.2018): fixed problem in LAF construction (see Footnote 9).

Available format(s)
Publication info
Published elsewhere. Full version of Eurocrypt 2013 paper
key-dependent messageschosen-ciphertext securitypublic-key encryption
Contact author(s)
Dennis Hofheinz @ kit edu
2018-10-09: last of 9 revisions
2012-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dennis Hofheinz},
      title = {Circular chosen-ciphertext security with compact ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2012/150},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.