Universal Re-Encryption (100 pts)

Question:

Let be a prime, and be an element of of prime order .

Let be the private key, and be the public key.

To encrypt a message , pick two random values , and compute the ciphertext as follows (all computations are modulo ): Download a valid ciphertext from here, and compute another valid ciphertext such that:

  1. and decrypt to the same message;
  2. and and and .

Write-Up:

Universal Re-encryption is a cryptographic primitive introduced by Golle et al. in 2004. Given a ciphertext , re-encryption allows producing a new ciphertext such that and 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 . However, prior to 2004, all re-encryption primitives used the public key used to generate , thus the anonymity of the receiver of (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 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 is the ElGamal encryption of ;
  2. The second pair is the ElGamal encryption of the actual message .

Using the homomorphic properties of the ElGamal cryptosystem, we can easily compute a re-encryption by picking two (arbitrary1) values ,2 and compute:

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

#!/usr/bin/env python3

from random import randint

p = 0x8000048d1d71b57838b7d90ebc63b8c853f3af1af87ce2db5593f3386ae5139d040d3844e31db723d39cdd7717c8cffc26f6f877b5c85ca8e595ca687c07c773

a = 0x21068b690f5438360063bb80799a95af7bbb83fa399376af9ad21e0cef3d5233aa313fe1960ccfd87e8a4b1dba0e053d89bfebd4bc57170147462fafef44c9c7
b = 0x436c161645052a76c1f7c976da63f61987f5f9bf7cb810a0e6fb1ea593aa9397c7b7cb0488f0f14cf93c79eef967a4b2a39388da1a357077d30a6f8b2a2c97e7
c = 0x7dd53b07c05ea2aca88bcbdd58601fa344918848107431ae7710542ea625abb335c27352c1bd2ef01359adb19b1bee77edc07ab0b41b9766392fc154f7891268
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
b = 0x5ccc00cae177ac8e50f64cb23248b12e075eeb32a9ac40f461db852c50fa36f87ead0c941576a2d89a12b7175f3365c819a68713b45fdcb934e34c9b3b534e0f
c = 0x7815a4229680515d8e73de94a41629cb6777ee4744e71788a169a52171cfd9b2b047b264e113bdf1816838cc063447e20812c4f12df1fc9d7a06fc04b41bad83
d = 0xee8b84463cc93dd1489c2ddc2fc449f0215acada763ff63f5f57fdeecec445cff70285057d4868a383809f1808855b0af2afa98a5a209e1d05f662f508feb76

Source Code

URE_Solve.py.


  1. Actually, to preserve the desired anonymity properties of mixnets, and must be picked uniformly at random. But that's a story for another day, and to solve this challenge, any arbitrary value (except ) is acceptable. 

  2. Since we don't know , it suffices to pick and from