Circular chosen-ciphertext security with compact ciphertexts

Dennis Hofheinz

Paper 2012/150

Circular chosen-ciphertext security with compact ciphertexts

Dennis Hofheinz

Abstract

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).

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Full version of Eurocrypt 2013 paper
Keywords: key-dependent messages chosen-ciphertext security public-key encryption
Contact author(s): Dennis Hofheinz @ kit edu
History: 2018-10-09: last of 9 revisions; 2012-03-22: received; See all versions
Short URL: https://ia.cr/2012/150
License: CC BY

BibTeX

@misc{cryptoeprint:2012/150,
      author = {Dennis Hofheinz},
      title = {Circular chosen-ciphertext security with compact ciphertexts},
      howpublished = {Cryptology ePrint Archive, Paper 2012/150},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/150}},
      url = {https://eprint.iacr.org/2012/150}
}