Solving Small Exponential ECDLP in EC-Based Additively Homomorphic Encryption and Applications

Additively Homomorphic Encryption (AHE) has been widely used in various applications, such as federated learning, blockchain, and online auctions. Elliptic Curve (EC) based AHE has the advantages of efficient encryption, homomorphic addition, scalar multiplication algorithms, and short ciphertext length. However, EC-based AHE schemes require solving a small exponential Elliptic Curve Discrete Logarithm Problem (ECDLP) when running the decryption algorithm, i.e., recovering the plaintext <tex-math notation="LaTeX">m∈ \0,1\^ </tex-math> from <tex-math notation="LaTeX">m G </tex-math> . Therefore, the decryption of EC-based AHE schemes is inefficient when the plaintext length <tex-math notation="LaTeX">> 32 </tex-math> . This leads to people being more inclined to use RSA-based AHE schemes rather than EC-based ones. This paper proposes an efficient algorithm called <tex-math notation="LaTeX">FastECDLP </tex-math> for solving the small exponential ECDLP at 128-bit security level. We perform a series of deep optimizations from two points: computation and memory overhead. These optimizations ensure efficient decryption when the plaintext length <tex-math notation="LaTeX"> </tex-math> is as long as possible in practice. Moreover, we also provide a concrete implementation and apply <tex-math notation="LaTeX">FastECDLP </tex-math> to some specific applications. Experimental results show that <tex-math notation="LaTeX">FastECDLP </tex-math> is far faster than the previous works. For example, the decryption can be done in 0.35 ms with a single thread when <tex-math notation="LaTeX">= 40 </tex-math> , which is about 30 times faster than that of Paillier. Furthermore, we experiment with <tex-math notation="LaTeX"> </tex-math> from 27 to 54, and the existing works generally only consider <tex-math notation="LaTeX">≤ 32 </tex-math> . The decryption only requires 1 second with 16 threads when <tex-math notation="LaTeX">= 54 </tex-math> . In the practical applications, we can speed up model training of existing vertical federated learning frameworks by 4 to 14 times. At the same time, the decryption efficiency is accelerated by about 140 times in a blockchain financial system (ESORICS 2021) with the same memory overhead.