# Universal Re-Encryption (100 pts)¶

## Question:¶

Let $p$ be a prime, and $g$ be an element of $\mathbb{Z}^*_p$ of prime order $q$.

Let $x \in \mathbb{Z}_q$ be the private key, and $h = g^x \pmod p$ be the public key.

To encrypt a message $m \in \mathbb{Z}^*_p$, pick two random values $r, s \in \mathbb{Z}_q$, and compute the ciphertext as follows (all computations are modulo $p$): Download a valid ciphertext $\sigma = (a, b, c, d)$ from here, and compute another valid ciphertext $\sigma' = (a', b', c', d')$ such that:

1. $\sigma$ and $\sigma'$ decrypt to the same message;
2. $a \ne a'$ and $b \ne b'$ and $c \ne c'$ and $d \ne d'$.

## Write-Up:¶

Universal Re-encryption is a cryptographic primitive introduced by Golle et al. in 2004. Given a ciphertext $C$, re-encryption allows producing a new ciphertext $C'$ such that $C$ and $C'$ decrypt to the same plaintext. Re-encryption does not require the private key, and uses the homomorphic properties of the public-key encryption at hand to re-encrypt $C$. However, prior to 2004, all re-encryption primitives used the public key used to generate $C$, thus the anonymity of the receiver of $C$ (i.e., the entity with the corresponding secret key) was not preserved. Golle et al. put forward the notion of Universal Re-encryption (URE), where there is no need to know the public key used to generate $C$ in order to be able to re-encrypt it.

This challenge uses a simple implementation of URE, where the ciphertext is a quadruple consisting of two pairs:

1. The first pair $(a,b)$ is the ElGamal encryption of $1$;
2. The second pair $(c,d)$ is the ElGamal encryption of the actual message $m$.

Using the homomorphic properties of the ElGamal cryptosystem, we can easily compute a re-encryption by picking two (arbitrary1) values $u,v \in \mathbb{Z}_q$,2 and compute:

The following Python code shows how re-encryption is accomplished:

#!/usr/bin/env python3

from random import randint

p = 0x8000048d1d71b57838b7d90ebc63b8c853f3af1af87ce2db5593f3386ae5139d040d3844e31db723d39cdd7717c8cffc26f6f877b5c85ca8e595ca687c07c773

b = 0x436c161645052a76c1f7c976da63f61987f5f9bf7cb810a0e6fb1ea593aa9397c7b7cb0488f0f14cf93c79eef967a4b2a39388da1a357077d30a6f8b2a2c97e7
d = 0x1a50308011b409460d504cc7cddd61cdff1bda0774d1329b59606df274bce81a7e4b15830ddd4e684e3f2422d36bd52220134881db560be0a34c76a9c5bbb6be

u = randint(1, p)
v = randint(1, p)

a_prime = pow(a, u, p)
b_prime = pow(b, u, p)
c_prime = c * pow(a, v, p) % p
d_prime = d * pow(b, v, p) % p

print("a =", hex(a_prime))
print("b =", hex(b_prime))
print("c =", hex(c_prime))
print("d =", hex(d_prime))



The output is:

a = 0x38c7a5e22d1f0fd0273ebb6fc1c404442ccbe80668774976e24b6cba89e439c0475a4df809cd27b700418036503eeeb7e0178462f9c47ed875c0070680d6f6c1

1. Actually, to preserve the desired anonymity properties of mixnets, $u$ and $v$ must be picked uniformly at random. But that's a story for another day, and to solve this challenge, any arbitrary value (except $u=1$) is acceptable.
2. Since we don't know $q$, it suffices to pick $u$ and $v$ from $\mathbb{Z}_p$