# Why is the re-encryption algorithm in Universal Re-encryption for Mixnets more complicated than apparently necessary?

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?

• 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." Jun 24 '15 at 7:34

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.