Cryptology ePrint Archive: Report 2021/899

Homomorphic decryption in blockchains via compressed discrete-log lookup tables

Panagiotis Chatzigiannis and Konstantinos Chalkias and Valeria Nikolaenko

Abstract: Many privacy preserving blockchain and e-voting systems are based on the modified ElGamal scheme that supports homomorphic addition of encrypted values. For practicality reasons though, decryption requires the use of precomputed discrete-log (dlog) lookup tables along with algorithms like Shanks's baby-step giant-step and Pollard's kangaroo. We extend the Shanks approach as it is the most commonly used method in practice due to its determinism and simplicity, by proposing a truncated lookup table strategy to speed up decryption and reduce memory requirements. While there is significant overhead at the precomputation phase, these costs can be parallelized and only paid once and for all. As a starting point, we evaluated our solution against the widely-used secp family of elliptic curves and show that we can achieve storage reduction by 7x-14x, depending on the group size. Our algorithm can be immediately imported to existing works, especially when the range of encrypted values is known, such as in Zether, PGC and Solidus protocols.

Category / Keywords: public-key cryptography / discrete log, ElGamal, homomorphic encryption, precomputation

Original Publication (with minor differences): CBT workshop 2021 (ESORICS)

Date: received 30 Jun 2021

Contact author: kostascrypto at fb com, pchatzig at gmu edu, chalkiaskostas at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210701:065209 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]