This is the paper.

On page 6, the paper describes a variant of El Gamal and a way of re-encrypting ciphertexts.

I thought an easier way to do encryption is to output $(m(g^x)^y,g^y)$, and universal re-encryption can be done by $(m(g^x)^y(g^x)^z,g^yg^z)$ for randomly chosen $z$. Instead the paper used a ciphertext with four components. Why?

Does it have something to do with CCA security?

  • 2
    $\begingroup$ The answer from @Habib is perfectly fine, but note also that this scheme does not achieve CCA security, as stated in this quote from the paper (End of Section 5): "In fact, we cannot achieve CCA security in the strictest sense in our system: In order to permit re-encryption, ciphertext must be malleable." $\endgroup$
    – cygnusv
    Jun 24, 2015 at 7:34

1 Answer 1


Actually no, it is not related to CCA security.

The re-encryptor mix server needs all of the four components for performing a correct re-encryption since it does not know the public key of the receiver $g^x$. Mix server only knows $\alpha_0, \beta_0, \alpha_1, \beta_1$ and two re-encryption factors it generates $k''_0, k''_1$

The encrypted message mix server receives:

$$[(my^{k_0}, g^{k_0}); (y^{k_1}, g^{k_1} )] = [(\alpha_0, \beta_0); (\alpha_1, \beta_1)]$$

The re-encrypted message it sends:

$$[(my^{k'_0}, g^{k'_0}); (y^{k'_1}, g^{k'_1} )]= [(\alpha_0\alpha_1^{k''_0}, \beta_0\beta_1^{k''_0}); (\alpha_1^{k''_1}, \beta_1^{k''_1})]$$

The scheme is designed in a way that not only it does not require the public key, the ciphertexts and the re-encryption procedure do not yield any information about the public key. As a result, it could be used in applications that require "receiver-anonymity" in situations that we have multiple receivers.

Page 2 of the paper:

The novelty in our proposal is that re-encryption neither requires nor yields knowledge of the public key under which a ciphertext was computed.


Your Answer

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

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