Homomorphic Threshold Decryption

A sketch of one construction is as follows.

Write a value in radix with signed coefficients, i.e., as with . Encode each coefficient as and use ElGamal encryption to form the ciphertext Each ElGamal ciphertext consists of two group elements; if group elements can be encoded in 32 bytes, this gives a 384-byte ciphertext. To decrypt , use ElGamal decryption to obtain the group elements , and then use a lookup table to recover from , or fail if the value is unknown.

This can in principle be done inside of a zkSNARK circuit if the underlying group is an embedded elliptic curve, together with certification that the ciphertext was correctly formed with in-range coefficients.

Addition and subtraction of ciphertexts are done componentwise, using the homomorphic property of ElGamal encryptions, and the fact that .

Adding ciphertexts of values whose coefficients were bounded as results in a sum whose coefficients are bounded as . Choosing and accounting for sign means that a lookup table of size is sufficient to decrypt sums of up to 128 well-formed ciphertexts. Sums of more than 128 ciphertexts can be handled by summing blocks of 128, decrypting the block sum, and summing the plaintexts.

Unfortunately, this method reveals slightly more information about a sum of encrypted summands than would be ideal. Ideally, it would reveal only the sum of the encrypted summands, but in fact it reveals the sum of each radix- chunk, without carrying between them. Carrying collapses information about the summands, but that information is revealed by this scheme. This seems unlikely to be a problem in practice, but it is worth quantifying.

TODO

  • the bounds above are a ballpark estimation; refine them and make them precise
  • work out integration with ABCI++ protocol phases