FPGA Design and Implementation of Large Integer Multiplier

Xing XIE; Xinming HUANG; Ling SUN; Saifei HAN

doi:10.11999/JEIT180836

Volume 41 Issue 8

Aug. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2019 > 41(8): 1855-1860

Xing XIE, Xinming HUANG, Ling SUN, Saifei HAN. FPGA Design and Implementation of Large Integer Multiplier[J]. Journal of Electronics & Information Technology, 2019, 41(8): 1855-1860. doi: 10.11999/JEIT180836

Citation:

Xing XIE, Xinming HUANG, Ling SUN, Saifei HAN. FPGA Design and Implementation of Large Integer Multiplier[J]. Journal of Electronics & Information Technology, 2019, 41(8): 1855-1860. doi: 10.11999/JEIT180836

Citation:

PDF( 1214 KB)

FPGA Design and Implementation of Large Integer Multiplier

doi: 10.11999/JEIT180836

Xing XIE^{1, 2},
Xinming HUANG¹,
Ling SUN^{1
,
,},
Saifei HAN¹

1.
School of Electronic Information, Nantong University, Nantong 226019, China
2.
Engineering Training Center, Nantong University, Nantong 226019, China

Funds: The National Natural Science Foundation of China (61571246), The Postgraduate Research & Practice Innovation Program of Jiangsu Province (KYCX17-1920)

Received Date: 2018-08-27
Rev Recd Date: 2019-02-15

Available Online: 2019-02-25

Publish Date: 2019-08-01

Abstract

Abstract

Large integer multiplication is the most important part in public key encryption, which often consumes most of the computing time in RSA, ElGamal, Fully Homomorphic Encryption (FHE) and other cryptosystems. Based on Schönhage-Strassen Algorithm (SSA), a design of high-speed 768 kbit multiplier is proposed. As the key component, an 64k-point Number Theoretical Transform (NTT) is optimized by adopting parallel architecture, in which only addition and shift operations are employed and thus the processing speed is improved effectively. The large integer multiplier design is validated on Stratix-V FPGA. By comparing its results with CPU using Number Theory Library(NTL) and GMP library, the correctness of this design is proved. The results also show that the FPGA implementation is about eight times faster than the same algorithm executed on the CPU.
- Fully Homomorphic Encryption (FHE),
- FPGA,
- Large number multiplication,
- GMP library

FullText(HTML)

References(18)

References

光炎, 祝跃飞, 顾纯祥, 等. 一种针对全同态加密体制的密钥恢复攻击[J]. 电子与信息学报, 2013, 35(12): 2999–3004. doi: 10.3724/SP.J.1146.2013.00300

GUANG Yan, ZHU Yuefei, GU Chunxiang, et al. A key recovery attack on fully homomorphic encryption scheme[J]. Journal of Electronics &Information Technology, 2013, 35(12): 2999–3004. doi: 10.3724/SP.J.1146.2013.00300

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

陈智罡. 基于格的全同态加密研究与设计[D]. [博士论文], 南京航空航天大学, 2015: 1–5.

CHEN Zhigang. Research and design of fully homomorphic encryption based on lattice[D]. [Ph.D. dissertation], Nanjing University of Aeronautics and Astronautics, 2015: 1–5.

GENTRY C and HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]. The 30th Annual International Conference on Theory and Applications of Cryptographic Techniques: Advances in Cryptology, Tallinn, Estonia, 2011: 129–148.

GENTRY C. A fully homomorphic encryption scheme[D]. [Ph.D. dissertation], Stanford University, 2009.

施佺, 韩赛飞, 黄新明, 等. 面向全同态加密的有限域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

ÖZTÜRK E, DORÖZ Y, SAVAŞ E, et al. A custom accelerator for homomorphic encryption applications[J]. IEEE Transactions on Computers, 2017, 66(1): 3–16. doi: 10.1109/TC.2016.2574340

YE J H and SHIEH M D. Low-complexity VLSI design of large integer multipliers for fully homomorphic encryption[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2018, 26(9): 1727–1736. doi: 10.1109/TVLSI.2018.2829539

POLLARD J M. The fast Fourier transform in a finite field[J]. Mathematics of Computation, 1971, 25(114): 365–374. doi: 10.1090/S0025-5718-1971-0301966-0

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

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

ROY S S, VERCAUTEREN F, VLIEGEN J, et al. Hardware assisted fully homomorphic function evaluation and encrypted search[J]. IEEE Transactions on Computers, 2017, 66(9): 1562–1572. doi: 10.1109/TC.2017.2686385

DORÖZ Y, ÖZTÜRK E, and SUNAR B. Accelerating fully homomorphic encryption in hardware[J]. IEEE Transactions on Computers, 2015, 64(6): 1509–1521. doi: 10.1109/TC.2014.2345388

WANG Wei, HU Yin, CHEN Lianmu, et al. Accelerating fully homomorphic encryption using GPU[C]. 2012 IEEE Conference on High Performance Extreme Computing, Waltham, USA, 2012: 1–5.

HUANG Xinming and WANG Wei. A novel and efficient design for an RSA cryptosystem with a very large key size[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2015, 62(10): 972–976. doi: 10.1109/TCSII.2015.2458033

JOHNSON L G. Conflict free memory addressing for dedicated FFT hardware[J]. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1992, 39(5): 312–316. doi: 10.1109/82.142032

FENG Xiang and LI Shuguo. Accelerating an FHE integer multiplier using negative wrapped convolution and Ping-Pong FFT[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2019, 66(1): 121–125. doi: 10.1109/TCSII.2018.2840108

WANG Wei and HUANG Xinming. FPGA implementation of a large-number multiplier for fully homomorphic encryption[C]. Proceedings of 2013 IEEE International Symposium on Circuits and Systems, Beijing, China, 2013: 2589–2592.

Relative Articles

Supplements(0)

Cited By

Proportional views