Rerandomizable RCCA Encryption

Manoj Prabhakaran and Mike Rosulek. Appeared in CRYPTO 2007.

Abstract

We give the first perfectly rerandomizable, Replayable-CCA (RCCA) secure encryption scheme, positively answering an open problem of Canetti et al. [CRYPTO 2003]. Our encryption scheme, which we call the Double-strand Cramer-Shoup scheme, is a non-trivial extension of the popular Cramer-Shoup encryption. Its security is based on the standard DDH assumption. To justify our definitions, we define a powerful "Replayable Message Posting" functionality in the Universally Composable (UC) framework, and show that any encryption scheme that satisfies our definitions of rerandomizability and RCCA security is a UC-secure implementation of this functionality. Finally, we enhance the notion of rerandomizable RCCA security by adding a receiver-anonymity (or key-privacy) requirement, and show that it results in a correspondingly enhanced UC functionality. We leave open the problem of constructing a scheme that achieves this enhancement.

Downloads

• CRYPTO 2007 proceedings version, via SpringerLink.
• Full version, via Cryptology ePrint Archive.
• Presentation slides from CRYPTO 2007, August 2007.
• Presentation slides from UIUC CS theory seminar, March 2007. Incorrectly claims that our construction achieves anonymity.
• BibTeX entries for the proceedings and full versions.

Notes

• As of August 16, 2007, the full version contains an improved construction of the main encryption scheme (20 group elements instead of 54). The scheme is essentially the same in spirit, but with some redundancy removed.
• We present a generalization of both the definitions and construction in Homomorphic Encryption with CCA Security.