面向全同态加密的有限域FFT算法FPGA设计
|
摘要
大数乘法是全同态加密算法中一个不可或缺的单元模块,也是其中耗时最多的模块,设计一个性能优良的大数乘法器有助于推进全同态加密的实用化进程。针对SSA大数乘法器的实现需求,该文采用可综合Verilog HDL语言完成了一个16×24 bit有限域FFT算法的FPGA设计,通过构建树型大数求和单元和并行化处理方法有效提高了FFT算法的速度。与VIM编译环境下的系统级仿真结果比较,验证了有限域FFT算法FPGA设计的正确性。
Large multiplier is an indispensable module in fully homomorphic encryption, while is also the most time-consuming module. Therefore, design of a large multiplier with good performance is help to promote the practical process of fully homomorphic encryption. Aimed at the demand of SSA(Sch?nhage-Strassen Algorithm) large multiplier, a 16×24 bit finite field FFT based on FPGA is designed by using Verilog HDL language. By constructing the tree type large sum unit and using parallel processing method, the speed of FFT algorithm is improved effectively. And its correctness is proved by comparing with the system level simulation results in VIM compiler environment.
Large multiplier is an indispensable module in fully homomorphic encryption, while is also the most time-consuming module. Therefore, design of a large multiplier with good performance is help to promote the practical process of fully homomorphic encryption. Aimed at the demand of SSA(Sch?nhage-Strassen Algorithm) large multiplier, a 16×24 bit finite field FFT based on FPGA is designed by using Verilog HDL language. By constructing the tree type large sum unit and using parallel processing method, the speed of FFT algorithm is improved effectively. And its correctness is proved by comparing with the system level simulation results in VIM compiler environment.
引文
[1]光焱,祝跃飞,顾纯祥,等.一种针对全同态加密体制的密钥恢复攻击[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].Jounal of Electronics&Information Technology,2013,35(12):2999-3004.doi:10.3724/SP.J.1146.2013.00300.
[2]CAO Xiaolin and MOORE C.Optimised multiplication architectures for accelerating fully homomorphic encryption[J].IEEE Transactions on Computers,2016,65(9):2794-2806.doi:10.1109/TC.2015.2498606.
[3]刘明洁,王安.全同态加密研究动态及其应用概述[J].计算机研究与发展,2014,51(12):2593-2603.doi;10.7544/issn100-1239.2014.20131168.LIU Mingjie and WANG An.The homomorphic encryption research dynamic overview and its application[J].Computer Research and Development,2014,51(12):2593-2603.doi:10.7544/issn100-1239.2014.20131168.
[4]陈智罡,石亚峰,宋新霞.全同态加密具体安全参数分析[J].密码学报,2016,3(5):480-491.CHEN Zhigang,SHI Yafeng,and SONG Xinxia.Estimating concert security parameters of fully homomorphic encryption[J].Journal of Cryptologic Research,2016,3(5):480-491.
[5]GENTRY C.Fully homomorphic encryption using ideal lattices[C].The 41st ACM Symposium on Theory of Computing Proceedings,Bethesda,Maryland,USA,2009:169-178.
[6]吕海峰,丁勇,代洪艳,等,LWE上的全同态加密方案研究[J].信息网络安全,2015,(1):32-38.doi:10.3969/j.issn.1671-1122.2015.01.006.LüHaifeng,DING Yong,DAI Hongyan,et al.Survey on LWE-based fully homomorphic encryption scheme[J].Net Inforamtion Security,2015,(1):32-38.doi:10.3969/j.issn.1671-1122.2015.01.006.
[7]GENTRY C and HALEVI S.Implementing Gentry’s fully homomorphic encryption scheme[C].Annual International Conference on the Theory and Applications of Cryptographic,Tallinn,Estonia,2011:129-148.doi:10.1007/978-3-642-20465-4_9.
[8]GENTRY C.A fully homomorphic encryption scheme[D].[Ph.D.dissertation],Stanford University,2009.
[9]吕金萍.基于LWE的全同态加密的设计与研究[D].[硕士论文],杭州电子科技大学,2014.LüJinping.Design and research of FHE based on LWE[D].[Master dissertation],Hanzhou Electronic Science and Technology University.2014.
[10]吴晓园.基于格的全同态加密方案的研究与设计[D].[硕士论文],西安电子科技大学,2012.WU Xiaoyuan.Study and design of fully homomorphic encryption scheme based on case[D].[Master dissertation],Xidian University,2012.
[11]WANG W,HU Y,CHEN L,et al.Accelerating fully homomorphic encryption using GPU[C].IEEE Conference on High Performance Extreme Computing,Waltham,MA,USA,2012:1-5.doi:10.1109/HPEC.2012.6408660.
[12]EMMART N and WEEMS C.High precision integer addition,subtraction and multiplication with a graphics processing unit[J].Parallel Processing.Letters,2010,20(4):293-306.
[13]WANG Wei,HUANG Xinming,and EMMART N.VLSI desgn of a large-number multiplier for FHE[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2014,22(9):1879-1887.doi:10.1109/TVLSI.2013.2281786.
[14]SCH?NHAGE A and STRASSEN V.Schnelle multiplikation grosser zahlen[J].Computing,1971,7(3):281-292.doi:10.1007/BF02242355.
[15]占席春,蔡费杨,王伟.多路并行FFT算法的FPGA实现技术[J].现代电子技术,2015,38(19):35-39.ZHAN Xichun,CAI Feiyang,and WANG Wei.FPGA-based implementation technologies of multi-channel parallel FFT algorithm[J].Modern Electronics Tchnique,2015,38(19):35-39.
[16]SAID Boussakta.Generalized new mersenne number transforms[J].IEEE Transactions on Signal Processing,2012,60(5):2640-2647.doi:10.1109/TSP.2012.2186131.
[17]EMMART N and WEEMS C.High precision integer multiplication with a GPU using Strassen’s algorithm with multiple FFT sizes[J].Parallel Processing Letters,2011,21(3):293-306.doi:10.1109/IPDPS.2011.336.
[2]CAO Xiaolin and MOORE C.Optimised multiplication architectures for accelerating fully homomorphic encryption[J].IEEE Transactions on Computers,2016,65(9):2794-2806.doi:10.1109/TC.2015.2498606.
[3]刘明洁,王安.全同态加密研究动态及其应用概述[J].计算机研究与发展,2014,51(12):2593-2603.doi;10.7544/issn100-1239.2014.20131168.LIU Mingjie and WANG An.The homomorphic encryption research dynamic overview and its application[J].Computer Research and Development,2014,51(12):2593-2603.doi:10.7544/issn100-1239.2014.20131168.
[4]陈智罡,石亚峰,宋新霞.全同态加密具体安全参数分析[J].密码学报,2016,3(5):480-491.CHEN Zhigang,SHI Yafeng,and SONG Xinxia.Estimating concert security parameters of fully homomorphic encryption[J].Journal of Cryptologic Research,2016,3(5):480-491.
[5]GENTRY C.Fully homomorphic encryption using ideal lattices[C].The 41st ACM Symposium on Theory of Computing Proceedings,Bethesda,Maryland,USA,2009:169-178.
[6]吕海峰,丁勇,代洪艳,等,LWE上的全同态加密方案研究[J].信息网络安全,2015,(1):32-38.doi:10.3969/j.issn.1671-1122.2015.01.006.LüHaifeng,DING Yong,DAI Hongyan,et al.Survey on LWE-based fully homomorphic encryption scheme[J].Net Inforamtion Security,2015,(1):32-38.doi:10.3969/j.issn.1671-1122.2015.01.006.
[7]GENTRY C and HALEVI S.Implementing Gentry’s fully homomorphic encryption scheme[C].Annual International Conference on the Theory and Applications of Cryptographic,Tallinn,Estonia,2011:129-148.doi:10.1007/978-3-642-20465-4_9.
[8]GENTRY C.A fully homomorphic encryption scheme[D].[Ph.D.dissertation],Stanford University,2009.
[9]吕金萍.基于LWE的全同态加密的设计与研究[D].[硕士论文],杭州电子科技大学,2014.LüJinping.Design and research of FHE based on LWE[D].[Master dissertation],Hanzhou Electronic Science and Technology University.2014.
[10]吴晓园.基于格的全同态加密方案的研究与设计[D].[硕士论文],西安电子科技大学,2012.WU Xiaoyuan.Study and design of fully homomorphic encryption scheme based on case[D].[Master dissertation],Xidian University,2012.
[11]WANG W,HU Y,CHEN L,et al.Accelerating fully homomorphic encryption using GPU[C].IEEE Conference on High Performance Extreme Computing,Waltham,MA,USA,2012:1-5.doi:10.1109/HPEC.2012.6408660.
[12]EMMART N and WEEMS C.High precision integer addition,subtraction and multiplication with a graphics processing unit[J].Parallel Processing.Letters,2010,20(4):293-306.
[13]WANG Wei,HUANG Xinming,and EMMART N.VLSI desgn of a large-number multiplier for FHE[J].IEEE Transactions on Very Large Scale Integration(VLSI)Systems,2014,22(9):1879-1887.doi:10.1109/TVLSI.2013.2281786.
[14]SCH?NHAGE A and STRASSEN V.Schnelle multiplikation grosser zahlen[J].Computing,1971,7(3):281-292.doi:10.1007/BF02242355.
[15]占席春,蔡费杨,王伟.多路并行FFT算法的FPGA实现技术[J].现代电子技术,2015,38(19):35-39.ZHAN Xichun,CAI Feiyang,and WANG Wei.FPGA-based implementation technologies of multi-channel parallel FFT algorithm[J].Modern Electronics Tchnique,2015,38(19):35-39.
[16]SAID Boussakta.Generalized new mersenne number transforms[J].IEEE Transactions on Signal Processing,2012,60(5):2640-2647.doi:10.1109/TSP.2012.2186131.
[17]EMMART N and WEEMS C.High precision integer multiplication with a GPU using Strassen’s algorithm with multiple FFT sizes[J].Parallel Processing Letters,2011,21(3):293-306.doi:10.1109/IPDPS.2011.336.