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.
Category / Keywords: key-dependent messages, chosen-ciphertext security, public-key encryption Publication Info: Full version of Eurocrypt 2013 paper Date: received 22 Mar 2012, last revised 19 Jan 2013 Contact author: Dennis Hofheinz at kit edu Available format(s): PDF | BibTeX Citation Note: Additional intuition for the main scheme. Version: 20130119:141253 (All versions of this report) Discussion forum: Show discussion | Start new discussion