Very interesting work by
@guruvamsip @commonwarexyz to obtain Batch decryption using pairings + high school algebra:
1. Each client chooses a random k_i, encrypts their message under k_i^2 and the validator's pk in the target group. Each client also provides pk.k_i^2, and k_i in group 1 and group 2.
2. The validators decrypt the sum of all the encrypted k_i's (denote it as K) by sending a single decryption share.
3. Given the decryption of K^2 as pk.K^2 one can compute the individual pk.k_i^2 as follows:
(Ignore the pk for now)
K^2 =(k_1 + k_2 + k_3)^2 = k_1^2 + k_2^2 + k_3^2 + cross terms.
(This omits a lot of crucial details for simplicity)
Suppose you want to decrypt the message under k_i^2 using K^2:
1. The cross terms can be removed by combining k_i in g_1 and k_j in g_2 (and vice versa) using pairings for all j!=i. This allows to remove the cross terms.
2. Then the individual pk.k_j^2 can be removed by using the client-provided material.
The brilliance lies in figuring out the optimal amount of information to put into the ciphertext, which allows the cross-term removal (using pairings) while preventing an adversary from decrypting the client ciphertexts without the decryption of the sum K.
Kudos on the great work!