Low Complexity VLSI Design of Large Integer Multipliers for Fully Homomorphism Encryption
Abstract : Large integer multiplication has been widely used in fully homomorphic encryption (FHE). Implementing feasible large integer multiplication hardware is thus critical for accelerating the FHE evaluation process. In this paper, a novel and efficient operand reduction scheme is proposed to reduce the area requirement of radix-r butterfly units. We also extend the singleport, merged-bank memory structure to the design of number theoretic transform (NTT) and inverse NTT (INTT) for further area minimization. In addition, an efficient memory addressing scheme is developed to support both NTT/INTT and resolving carries computations. Experimental results reveal that significant area reductions can be achieved for the targeted 786 432- and 1 179 648-bit NTT-based multipliers designed using the proposed schemes in comparison with the related works. Moreover, the two multiplications can be accomplished in 0.196 and 2.21 ms, respectively, based on 90-nm CMOS technology. The low-complexity feature of the proposed large integer multiplier designs is thus obtained without sacrificing the time performance.
? One of the holy grails of modern cryptography is FHE, which allows arbitrary computation on encrypted data.
? A need to perform a binary operation on the plaintext, FHE enables that to be accomplished via manipulation of the ciphertext without the knowledge of the encryption key.
? The brief description above, we can see that the fundamental operations for FHE are large-number addition and multiplication.
? The simplest algorithm is the naive O(N2) algorithm (often called the grade school algorithm).
? This is an efficient grade-school approach, performing the equivalent of two O(N2) multiplications.
? The GPU trial provided significant acceleration, the major problem remains that the power consumption of a high end GPU today is about 200–400 W.
? High precision arithmetic is a primary means of addressing the non-robustness problem in such geometric algorithms.
? One of the major issues in reversible circuit design is garbage minimization to minimise the power dissipation.
? However, existing FHE schemes are currently highly unpractical due to large parameter sizes and highly computationally intensive algorithms amongst other issues.
• In this paper, it is proposed to design an efficient reversible single precision floating point subtractor.
• The proposed floating point subtractor design requires an efficient reversible comparator unit, an 8-bit and a 24-bit reversible subtractor unit, a 24-bit reversible leading zero detector unit and a 24- bit reversible shift register for normalization.
• The paper also focuses on the design of a reversible 1-bit comparator using the two newly proposed reversible gates Reversible Gate1 (RG1) and Reversible Gate2 (RG2).
• The proposed design has been synthesized using 90-nm process technology with an estimated die area of 45.3 mm2.
? High-radix BUs are commonly applied to reduce the number of operation stages, thereby increasing the resulting performance.
? To accelerate FHE operations, various efficient schemes have been presented into tackle large integer multiplication based on the Schönhage–Strassen algorithm (SSA).
? To the multiport memory structures, single-port memory is preferred due to its area efficiency, but it might suffer from the limited bandwidth.
? In, an area-efficient (AE) algorithm was developed by employing SPMB memory to further reduce the memory area in existing memory-based architectures.
|