Cryptology ePrint Archive: Report 2004/317
Adaptively-Secure, Non-Interactive Public-Key Encryption
Ran Canetti and Shai Halevi and Jonathan Katz
Abstract: Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure.
Impossibility holds even if secure data erasure is possible.
We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about
the frequency of communication between parties. Using this approach,
we construct adaptively-secure, completely non-interactive encryption
schemes supporting secure encryption of arbitrarily-many messages from
arbitrarily-many senders. Our schemes additionally provide
forward security and security against chosen-ciphertext attacks.
Category / Keywords: foundations / adaptively-secure encryption
Publication Info: An extended abstract will appear at TCC '05
Date: received 22 Nov 2004, last revised 23 Nov 2004
Contact author: jkatz at cs umd edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20041124:031924 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]