An Ultra-Highly Parallel Polynomial Multiplier for the Bootstrapping Algorithm in a Fully Homomorphic Encryption Scheme
- PDF / 3,169,943 Bytes
- 14 Pages / 595.224 x 790.955 pts Page_size
- 16 Downloads / 207 Views
An Ultra-Highly Parallel Polynomial Multiplier for the Bootstrapping Algorithm in a Fully Homomorphic Encryption Scheme Weihang Tan1 · Benjamin M. Case2 · Gengran Hu3 · Shuhong Gao2 · Yingjie Lao1 Received: 15 April 2020 / Revised: 11 September 2020 / Accepted: 14 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Fully homomorphic encryption (FHE) is a post-quantum secure cryptographic technology that enables privacy-preserving computing on an untrusted platform without divulging any secret or sensitive information. The core of FHE is the bootstrapping algorithm, which is the intermediate refreshing procedure of a processed ciphertext. However, this step has been the computational bottleneck that prevents real-world deployments among various FHE schemes. This paper, to the best of our knowledge, for the first time, presents a scalable and ultra-highly parallel design for the number theoretic transform (NTT)-based polynomial multiplier with a variable number of reconfigurable processing elements (PEs). Hence, the highest degree of acceleration can be achieved for any targeted hardware platform by implementing as many PEs as possible under the resource constraint. The corresponding addressing and scheduling schemes are also proposed to avoid memory access conflict for the PEs, which yields an extremely high utilization ratio of 99.18% on average. In addition, the latency of the proposed design with the general negative wrapped convolution algorithm is reduced by 59.20% compared to prior works. Keywords Fully Homomorphic Encryption (FHE) · Polynomial multiplication · Number Theoretic Transform (NTT) · VLSI · Ring-Learning with Error (RLWE) · Post-quantum security
1 Introduction The recent development of cloud computing and the Internet of Things (IoT) demands an efficient cryptosystem to Yingjie Lao
[email protected] Weihang Tan [email protected] Benjamin M. Case [email protected] Gengran Hu [email protected] Shuhong Gao [email protected] 1
Department of Electrical and Computer Engineering, Clemson University, Clemson, SC 29634, USA
2
School of Mathematical and Statistical Sciences, Clemson University, Clemson, SC 29634, USA
3
School of Cyberspace, Hangzhou Dianzi University, Hangzhou, 310018, China
protect sensitive data through public networks and computing platforms. To this end, fully homomorphic encryption (FHE) has emerged as a promising secure function evaluation (SFE) scheme that allows operations on encrypted data without decryption. As opposed to conventional encryption methods, data can remain encrypted under the user’s secret key, and hence only the secret key owner has access to the plaintext. In addition, different from partially or somewhat homomorphic encryption that only permits a limited type or a limited number of operations, FHE allows the function to be directly evaluated using the encrypted data for an unlimited number of operations. However, FHE schemes are still computationally expensive, especially for the bootstrapping step, which is the inter
Data Loading...
