Paper 2007/119

Rerandomizable RCCA Encryption

Manoj Prabhakaran and Mike Rosulek


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.

Note: Updated version includes an improved construction for the main encryption scheme

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. To appear in CRYPTO 2007
Contact author(s)
mmp @ cs uiuc edu
2007-08-17: last of 4 revisions
2007-04-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Manoj Prabhakaran and Mike Rosulek},
      title = {Rerandomizable RCCA Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2007/119},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.