Welcome to the resource topic for 2022/1573
Title:
Solving Small Exponential ECDLP in EC-based Additively Homomorphic Encryption and Applications
Authors: Fei Tang, Guowei Ling, Chaochao Cai, Jinyong Shan, Xuanqi 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 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.
ePrint: https://eprint.iacr.org/2022/1573
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .