# Does Cramer-Shoup allow re-randomization?

Is it possible to re-randomize a ciphertext with the Cramer-Shoup System? I have some Cramer-Shoup ciphertexts and i want to re-randomize them, so they look different and are unlinkable to there previous form, but still can be decrypted with the original secret-key. Is this possible?

And if it is, would it still be possible using the Camenisch-Shoup System, which calculates a Proof, so someone knows that the "real original value" is encrypted, without decrypting the ciphertext? I hope this is written clear enough Thank you.

Answering only your first question: no, that's not possible. Essentially, if it was possible to randomize the ciphertext of Cramer-Shoup, then it wouldn't be IND-CCA2 secure. However it is IND-CCA2 secure, so it cannot be re-randomizable.

• thank you very much Jun 9 '20 at 16:22

@hakoja correctly points out that what you are asking for is not compatible with CCA security (the security property that Cramer-Shoup satisfies). More specifically, you seem to be looking for a rerandomizable, RCCA-secure encryption scheme. These two properties mean:

• Rerandomizable: Given an encryption of an unknown $$m$$, there is a way to generate fresh samples from $$\textsf{Enc}(k,m)$$.

• Replayable CCA (RCCA): The scheme is non-malleable except for the possibility of modifying a ciphertext $$c$$ into another ciphertext $$c'$$ where $$\textsf{Dec}(k,c) = \textsf{Dec}(k,c')$$. Basically, the scheme is malleable only in ways that preserve the plaintext; otherwise it is non-malleable.

Rerandomizable RCCA means that the randomization feature is the "only malleability" of the scheme. These are not too hard to achieve together, but they become non-trivial when you include another requirement:

• Unlinkability: Given $$c = \textsf{Enc}(k,m)$$ for an unknown $$m$$, it is hard to tell whether some other $$c'$$ is an independent encryption of $$m$$ or a rerandomization of $$c$$. In order to make sense, this property should hold even in the presence of chosen-ciphertext attacks (i.e., against attackers that have access to the decryption function), which makes it difficult. It often means that the rerandomization procedure must refresh all the randomness in a ciphertext.

In the paper below, we were the first to construct a rerandomizable RCCA scheme:

Prabhakaran & Rosulek: Rerandomizable RCCA Encryption, CRYPTO 2007

The scheme is about 5-6x more expensive than Cramer-Shoup, and it relies on DDH holding in some groups with related order. There is a later followup work that gives different constructions of rerandomizable RCCA from pairing-based groups:

Chase, Kohlweis, Lysyanskaya, Meikeljohn: Malleable Proof Systems and Applications. Eurocrypt 2012.

• thanks for the answer and the explanation. Lets say ive got a Ciphertext created with Cramer-Shoup and i want to modify it, so it stays decryptable but changes its appearance, could i just encrypt it with ElGamal over and over again? I know El Gamal isnt secure, but thats not a problem cause the to-be-encrypted Message is already a ciphertext from cramer-shoup Jun 9 '20 at 16:27
• To be clear, you are proposing using $\textsf{ElGamal}(\textsf{CramerShoup}(m))$ as the encryption? The outer layer gives you rerandomizability and the inner layer gives you RCCA. But overall this only satisfies a very weak form of unlinkability. With a chosen ciphertext attack you can test whether two ciphertexts are rerandomizations of the same underlying Cramer-Shoup ciphertext. (I will update my answer to discuss unlinkability) Jun 9 '20 at 17:25
• exactly this nested encryption was my thought. The Problem is, i am kind of bound by Cramer-Shoup because i need some kind of verifiable encryption, to guarantee a third party that the cyphertext actually contains the message that it should contain, without decrypting it (Which should be provided by Camenisch-Shoup mentioned in my quastion). Now i basically want third party to re-randomize those ciphertexts, that they get a new appearance and are not immediatly linkable to there original appearance Jun 9 '20 at 17:51