6
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you very much $\endgroup$
    – Crypto Muck
    Commented Jun 9, 2020 at 16:22
7
$\begingroup$

@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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Crypto Muck
    Commented Jun 9, 2020 at 16:27
  • 1
    $\begingroup$ 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) $\endgroup$
    – Mikero
    Commented Jun 9, 2020 at 17:25
  • $\begingroup$ 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 $\endgroup$
    – Crypto Muck
    Commented Jun 9, 2020 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.