Solving Small Exponential ECDLP in EC-Based Additively Homomorphic Encryption and Applications
Fei Tang, Guowei Ling, Chaochao Cai, Jinyong Shan, X Liu, Peng Tang, Weidong Qiu
Abstract
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m\in \{0,1\}^{\ell} $ </tex-math></inline-formula> from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$m \ast G$ </tex-math></inline-formula> . Therefore, the decryption of EC-based AHE schemes is inefficient when the plaintext length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell > 32$ </tex-math></inline-formula> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf {FastECDLP}$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell $ </tex-math></inline-formula> is as long as possible in practice. Moreover, we also provide a concrete implementation and apply <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf {FastECDLP}$ </tex-math></inline-formula> to some specific applications. Experimental results show that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf {FastECDLP}$ </tex-math></inline-formula> is far faster than the previous works. For example, the decryption can be done in 0.35 ms with a single thread when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell = 40$ </tex-math></inline-formula> , which is about 30 times faster than that of Paillier. Furthermore, we experiment with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell $ </tex-math></inline-formula> from 27 to 54, and the existing works generally only consider <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell \leq 32$ </tex-math></inline-formula> . The decryption only requires 1 second with 16 threads when <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell = 54$ </tex-math></inline-formula> . 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.