Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption

Siliang HUA; Huiguo ZHANG; Shuchang WANG

doi:10.11999/JEIT200174

Volume 43 Issue 5

May 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(5): 1381-1388

Siliang HUA, Huiguo ZHANG, Shuchang WANG. Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(5): 1381-1388. doi: 10.11999/JEIT200174

Citation:

Siliang HUA, Huiguo ZHANG, Shuchang WANG. Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(5): 1381-1388. doi: 10.11999/JEIT200174

Citation:

Siliang HUA, Huiguo ZHANG, Shuchang WANG. Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(5): 1381-1388. doi: 10.11999/JEIT200174

PDF( 2137 KB)

Optimization and Implementation of Number Theoretical Transform Multiplier Butterfly Operation for Fully Homomorphic Encryption

doi: 10.11999/JEIT200174

Changshu Institute of Technology, Suzhou 215500, China

Funds: The Natural Science Foundation of Jiangsu Province (BK20191027)

Received Date: 2020-03-17
Rev Recd Date: 2020-10-21

Available Online: 2020-11-19

Publish Date: 2021-05-18

Abstract

Abstract

Fully Homomorphic Encryption (FHE) allows data to be encrypted and out-sourced to commercial cloud environments for processing, while encrypted which diminishes privacy concerns. For the optimization requirements of large integer multiplication operations in fully homomorphic encryption, an operand merge algorithm of a Number Theory Transform (NTT) multiplier butterfly operation unit is proposed. By using a fast algorithm of modulo operation, the operands of the Radix-16 and Radix-32 units are reduced to 43.8% and 39.1%. The hardware architecture of the NTT Radix-32 unit is designed and implemented. The proposed design is synthesized using 90 nm process technology. The results show that the maximum frequency of the circuit is 600 MHz with die area 1.714 mm². The results also show that the optimization algorithm improves the computational efficiency of NTT multiplier butterfly operation.
- Fully Homomorphic Encryption (FHE),
- Large integer multiplier,
- Number Theoretical Transform (NTT),
- Butterfly operation

FullText(HTML)

References(15)

References

[1]	ALBRECHT M, CHASE M, CHEN Hao, et al. Homomorphic encryption standard[R/OL]. http://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf, 2018.
[2]	陈克非, 蒋林智. 同态加密专栏序言[J]. 密码学报, 2017, 4(6): 558–560. doi: 10.13868/j.cnki.jcr.000207 CHEN Kefei and JIANG Linzhi. Preface on homomorphic encrpytion[J]. Journal of Cryptologic Research, 2017, 4(6): 558–560. doi: 10.13868/j.cnki.jcr.000207
[3]	李增鹏, 马春光, 周红生. 全同态加密研究[J]. 密码学报, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208 LI Zengpeng, MA Chunguang, and ZHOU Hongsheng. Overview on fully homomorphic encryption[J]. Journal of Cryptologic Research, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208
[4]	ARCHER D, CHEN L, CHEON J H, et al. Applications of homomorphic encryption[EB/OL]. http://homomorphicencryption.org/white_papers/applications_homomorphic_encryption_white_paper.pdf, 2017.
[5]	GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The 41st Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–178. doi: 10.1145/1536414.1536440.
[6]	ABOZAID G, EL-MAHDY A, and WADA Y. A Scalable multiplier for arbitrary large numbers supporting homomorphic encryption[C]. 2013 Euromicro Conference on Digital System Design, Los Alamitos, USA, 2013: 969–975. doi: 10.1109/DSD.2013.110.
[7]	RAFFERTY C, O’NEILL M, and HANLEY N. Evaluation of large integer multiplication methods on hardware[J]. IEEE Transactions on Computers, 2017, 66(8): 1369–1382. doi: 10.1109/TC.2017.2677426
[8]	VAN METER R and ITOH K M. Fast quantum modular exponentiation[J]. Physical Review A, 2005, 71(5): 052320. doi: 10.1103/PhysRevA.71.052320
[9]	GARCÍA L. Can Schönhage multiplication speed up the RSA encryption or decryption?[EB/OL]. https://www.informatik.tu-darmstadt.de/cdc/home_cdc/index.de.jsp, 2005.
[10]	FÜRER M. Faster integer multiplication[C]. The 39th Annual ACM Symposium on Theory of Computing, San Diego, USA, 2007: 57–66. doi: 10.1145/1250790.1250800.
[11]	WANG Wei, HUANG Xinming, EMMART N, et al. VLSI design of a large-number multiplier for fully homomorphic encryption[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014, 22(9): 1879–1887. doi: 10.1109/TVLSI.2013.2281786
[12]	FENG Xiang and LI Shuguo. Design of an area-effcient million-bit integer multiplier using double modulus NTT[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2017, 25(9): 2658–2662. doi: 10.1109/TVLSI.2017.2691727
[13]	施佺, 韩赛飞, 黄新明, 等. 面向全同态加密的有限域FFT算法FPGA设计[J]. 电子与信息学报, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312 SHI Quan, HAN Saifei, HUANG Xinming, et al. Design of finite field FFT for fully homomorphic encryption based on FPGA[J]. Journal of Electronics &Information Technology, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312
[14]	谢星, 黄新明, 孙玲, 等. 大整数乘法器的FPGA设计与实现[J]. 电子与信息学报, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836 XIE Xing, HUANG Xinming, SUN Ling, et al. FPGA design and implementation of large integer multiplier[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836
[15]	Project Nayuki. Number-theoretic transform (integer DFT)[EB/OL]. https://www.nayuki.io/page/number-theoretic-transform-integer-dft, 2017.