Design And Implementation Of High-speed Large Integer Multiplier Based On Finite Field NTT

Machine learning based on fully homomorphic encryption scheme can effectively solve the privacy protection and legitimacy problems caused by sharing sensitive data.However,the bit-width of ciphertext will reach millions of bits after the original text is encrypted.The large integer multiplication unit has become the basic tool for encrypted neural network learning and inferencing.Moreover,in high-end applications such as aerospace,using the high-precision arithmetic features of large integers,replacing the mantissa of floating-point data with large integers can effectively solve the problem of insufficient precision.Therefore,it is essential to carry out innovative designs for large integer multiplier to improve the above applications' performance.The main work of this dissertation is as follows:1)A discrete compression method for the twiddle factor of NTT/INTT is designed.The twiddle factor is decomposed into three basic data vectors by analyzing the rule of data,and the storage architecture and corresponding addressing algorithm are designed for three data vectors.They are accessed through the designed addressing algorithm from memory,and all the twiddle factors are obtained by modular multiplication during computation.In the hardware circuit of 768 kbit multiplier proposed in this dissertation,the amount of twiddle factors reduces 98.7%,and the overall on-chip storage reduces51.3%.2)A memory addressing algorithm compatible with NTT/INTT alternate processes is designed.By analyzing the rules of data interaction between NTT and INTT,this dissertation designs an efficient non-conflict address algorithm based on the multi-bank memory architecture of single-port SRAM.The algorithm is compatible with NTT output and INTT input,effectively reducing data reordering during the implementation of the large integer multiplier,accelerating data interaction,and improving the computing speed.3)A 768 kbit multiplier with high-speed pipeline architecture is designed and implemented by FPGA and ASIC.This dissertation uses a single base 16-point NTT is used to realize the critical component 64k-point NTT module.And the pipeline process of 16-point NTT is refined by dichotomy.Using addition and shift to implement modular subtraction units and modular multiplication units,and based on the two innovations proposed,the large integer multiplier design is completed.Under the 64 bit Ubuntu16.04 operating system,the multiplier is modeled and verified and then deployed on Xilinx and Altera FPGA development boards.The experimental results show that hardware design's speed is 36 times better than software.Compared with the existing research results,the working frequency is increased by 12.1%.The number of cycles and computation time decreased by 6 and 7 times,respectively.ATP performance indicator has an average improvement of 73.92%.Finally,based on the SMIC 40 nm,ASIC development of the large integer multiplier is carried out,and the circuit layout is designed.