Commutative encryption based on ElGamal  

The protocol below is a simple implementation of the commutative encryption by Weis base on universal re-encryption scheme presented by Golle et al. in "Universal Reencryption for mixnets", which in turn is based on ElGamel.

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

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.

x1 becomes 1-st party's secret key, and y1 becomes its public key:

Now this party can use the public key to encrypt its message m (), where 0 ≤ m ≤ p - 1. The encryption is berformed in the following way:

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

Example: m = 9, kA = 3, kB = 7

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

alpha1 = (m*y1^kA)modp

beta1 = (g^kA)modp

gamma1 = (y1^kB)modp

delta1 = (g^kB)modp
 
Example: 
      alpha1 = 9*10^3mod11 = 9*1000mod11 = 9000mod11 = 2

          beta1 = 2^3mod11 = 8mod11 = 8

        gamma1 = 10^7mod11 = 10000000mod11 = 10

          delta1 = 2^7mod11 = 128mod11 = 7

Press the button below to calculate the ciphertext

Commutative re-encryption by the (n+1) party

The re-encryption function takes n cithertexts as an input, each four tuples in size. In this case we are going to perfrom the commutative encryption by 2 parties only, thus n = 1. Thus the input ciphertext n1 is as follows:

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

The encryptor selects n+1 values rj such that their product is equal 1. In this case n+1=2, thus r1 * r2 shuld equal 1.

Example: r1= 8,  r2 ≡ r1^(-1) modp; r2 = 7

rj values are multiplied with the coresponding alphaj tuples. To form new part of commutative ciphertext.

n1 becomes as follows:

Example: C1 = [( (8 * 2)mod11 , 8 ) ; ( 10 , 7 )] = [(5 , 8 ) ; ( 10 , 7 )]

Then all n ciphertext are reencrypted with new random values. kA, kB are choosen randomly from the range (0, p - 1)

Example: k0'= 8, k1' = 2

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

C1' = [(alpha1', beta1');(gamma1', delta1')]

alpha1' = (alpha1 * gamma1^kA)modp

beta1' = (beta1 * delta1^kA)modp

gamma1' = (gamma1^kB)modp

delta1' = (delta1^kB)modp

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

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

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

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

Then the encypting party n+1, encrypts the rn+1 randomnes using the oridinary encryption method from the re-encryption protocol:

- choose x2 and generate y2
- choose two random numbers kA, kB
- perform encryption according to the re-encryption algorithm
 
Press the button to encypt r2 into ciphertext C2.

Example: X2 = 7, y2 = 7

Example: kA = 1, kB = 7

 
Example: C2 =

At this stage the commutative ciphertext consist of n+1 ciphertexts of form [(alpha0, beta0);(alpha1, beta1)]. This ciphertexts get permutated, in order to provide maximum privacy. In this form they may be send to another party for decryption.

Commutative Decryption by any of the n parties involved

Since all the ciphertexts are permutatet if a party wants to remove its lock from the secret, then it scans through ciphertexts for one encrypted with coresponding public key y. To do so it calculates gammak/(deltak^x) until it finds one ciphertext where this value is equal 1.

Below ciphertexts have not been permutated for simplicty:

Party 1 uses x1 to calculate gammak/(deltak^x) in order to find the ciphertext encrypted by y1:

Then alphak/(betak^x) is calculated from the choosen ciphertext and (n-1) random seeded values ri (for i not equal k) are choosen so that their product is equal to alphak/(betak^x).

Example: n is equal 2, thus (n - 1) leaves only one value ri required for this step.

These values ri are multipled into each corresponding ci's aphai values.

and the remaining ciphertexts are rerandomized, each witch new randoms kA and kB:

Commutative Decryption by the last of the n parties involved

The last party performs an oridinary decryption as described in the re-encryption protocol