Homomorphic decryption in blockchains via compressed discrete-log lookup tables

International Workshop on Cryptocurrencies and Blockchain Technology (CBT) at ESORICS


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.

Latest Publications

Sustainable AI: Environmental Implications, Challenges and Opportunities

Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga Behram, James Huang, Charles Bai, Michael Gschwind, Anurag Gupta, Myle Ott, Anastasia Melnikov, Salvatore Candido, David Brooks, Geeta Chauhan, Benjamin Lee, Hsien-Hsin S. Lee, Bugra Akyildiz, Max Balandat, Joe Spisak, Ravi Jain, Mike Rabbat, Kim Hazelwood

MLSys - 2022