Paper 2022/1573

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

Fei Tang, Chongqing University of Posts and Telecommunications
Guowei Ling, Chongqing University of Posts and Telecommunications
Chaochao Cai, Beijing Sudo Technology Co., LTD
Jinyong Shan, Beijing Sudo Technology Co., LTD
Xuanqi Liu, Tsinghua University
Peng Tang, Shanghai Jiao Tong University
Weidong Qiu, Shanghai Jiao Tong University

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 $m\in\{0,1\}^\ell$ from $m \ast G$. Therefore, the decryption of EC-based AHE schemes is inefficient when the plaintext length $\ell > 32$. 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 $\mathsf{FastECDLP}$ 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 $\ell$ is as long as possible in practice. Moreover, we also provide a concrete implementation and apply $\mathsf{FastECDLP}$ to some specific applications. Experimental results show that $\mathsf{FastECDLP}$ is far faster than the previous works. For example, the decryption can be done in $0.35$ ms with a single thread when $\ell = 40$, which is about $30$ times faster than that of Paillier. Furthermore, we experiment with $\ell$ from $32$ to $54$, and the existing works generally only consider $\ell \leq 32$. The decryption only requires $1$ second with $16$ threads when $\ell = 54$. 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.

Note: An efficient algorithm called $\mathsf{FastECDLP}$ for solving the small exponential ECDLP at $128$-bit security level.

Available format(s)
Publication info
ECDLP additively homomorphic encryption fast decryption BSGS cuckoo hashing
Contact author(s)
tangfei @ cqupt edu cn
s200201071 @ stu cqupt edu cn
shanjy @ sudoprivacy com
lxq22 @ mails tsinghua edu cn
2022-11-15: revised
2022-11-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fei Tang and Guowei Ling and Chaochao Cai and Jinyong Shan and Xuanqi Liu and Peng Tang and Weidong Qiu},
      title = {Solving Small Exponential {ECDLP} in {EC}-based Additively Homomorphic Encryption and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1573},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.