Universal re-encryption based on ElGamal  

The protocol below is a simple implementation of the universal re-encryption scheme presented by Golle et al. in "Universal Reencryption for mixnets".

In order to find out more about ElGamal itself, please use the menu on the left-hand side to navigate to a different tutorial. 

Prime p and primitive element of modp (generator) g may be parts of the system, thus common for all the users, or they may be different for every user. In this simple example the first approach is taken for clarity:

p= and g=

Example: p= 11, g= 2

Some other good values for p with g equal to 2:
-1073741827
-2147483658
-9223372036854775907

If p and g are written common in a given system, then public keys consist of y values calculated just like the y values in Diffie-Hellman protocol. Let assume that Bob wants to send a message to Alice. Then he will need her public key yB. This kay is created by Alice in the following way:

xA is choosen randomly from the range (0, p - 1)

yA is calculated yA = (g^xA)modp

Example:
      xA= 5
      yA = 2^5mod11 = 32mod11 = 10

Press the generate button to generate this values.

xA becomes Alice's secret key, and yA becomes her public key:

Now Bob can use Alice's public key to send her a message m (), where 0 ≤ m ≤ p - 1. The encryption is berformed in the following way:

k0, k1 are choosen randomly from the range (0, p - 1), new randoms should be choosen for every block of the message

Example: m = 9, k0 = 3, k1 = 7

The ciphertext is stored as two pairs [(alpha0, beta0);(alpha1, beta1)], where:

alpha0 = (m*yA^k0)modp

beta0 = (g^k0)modp

alpha1 = (yA^k1)modp

beta1 = (g^k1)modp
 
Example: 
      alpha0 = 9*10^3mod11 = 9*1000mod11 = 9000mod11 = 2

           beta0 = 2^3mod11 = 8mod11 = 8

      alpha1 = 10^7mod11 = 10000000mod11 = 10

           beta1 = 2^7mod11 = 128mod11 = 7

Press the button below to calculate the ciphertext

In order to decrypt the ciphertext [(alpha0, beta0);(alpha1, beta1)], Alice performs the following steps:

-Makes sure that alpha0, beta0, alpha1, beta1 belong to correct group (in this case they must be values between 0 and 10 exclusive. If this fail a special symbol ⊥ is returned.

- Calculates m1 = [alpha1 * [(beta1^p-1-xA)modp]]modp, if m1 is not equal to 1, then the decryption fails and a special symbol ⊥ is returned.

- If m1 is equal to 1, then Alice calculates m = m0
      m0 = [alpha0 * [(beta0^p-1-xA)modp]]modp.

Example: 
      m1 = [10 * [(7^11-1-5)mod11] = 10*16807mod11 = 1

      m = m0 = [2 * [(8^11-1-5)mod11]mod11 = 2*[32768mod11] = 2 * 10 mod11 = 9

Re-encryption 

The above ciphertext may be then re-encrypted.

The re-encryption function takes the cithertext as an input:

Example: C = [( 2 , 8 ) ; ( 10 , 7 )]

k0', k1' are choosen randomly from the range (0, p - 1), as new randoms should be choosen for every block of the message

Example: k0'= 8, k1' = 2

The reencryption of ciphertext C into C' is performed in the following way:

C' = [(alpha0', beta0');(alpha1', beta1')]

alpha0' = (alpha0 * alpha1^k0')modp

beta0' = (beta0 * beta1^k0')modp

alpha1' = (alpha1^k1')modp

beta1' = (beta1^k1')modp

Example: 
      alpha0' = 2 * 10^8mod11 = 2*100000000mod11 = 2

      beta0' = 8 * 7^8mod11 = 8 *5764801mod11 = 6

      alpha1' = 10^2mod11 = 100mod11 = 1

      beta1' = 7^2mod11 = 49mod11 = 5

Ciphertext C' is decrypted just as the ciphertext C = [(alpha0, beta0);(alpha1, beta1)], Alice performs the following steps:

-Makes sure that alpha0', beta0', alpha1', beta1' belong to correct group (in this case they must be values between 0 and 10 exclusive. If this fail a special symbol ⊥ is returned. Then treats all prime alpha0', beta0', alpha1', beta1' partrs of the ciphertext just like normal alpha0, beta0, alpha1, beta1.

- Calculates m1 = [alpha1 * [(beta1^p-1-xA)modp]]modp, if m1 is not equal to 1, then the decryption fails and a special symbol ⊥ is returned.

- If m1 is equal to 1, then Alice calculates m = m0
      m0 = [alpha0 * [(beta0^p-1-xA)modp]]modp.

Example: 
      m1 = [1 * [(5^11-1-5)mod11] = 1 * 3125mod11 = 1

      m = m0 = [2 * [(6^11-1-5)mod11]mod11 = 2*[7776mod11] = 9

This way the goal of the reencryption was achieved, the ciphertext was rerandomised without the knowleadge of the public key, in a way that it can be decrypted using the original private key.