Optimizations of Large Multipliers for Integer-Based Fully Homomorphic Encryption

The presence of the Internet of Things (IoT) creates a major change in data storing method as data is now stored digitally. For this reason, cloud storage is now dominantly chosen for storing the data. Therefore, a mechanism that can secure the data is essentially important. In addition to that, the attribute of encrypted data is now shifted from static to dynamic, thus allow arbitrary computations on the encrypted data without the need for decryption. For these reasons, a Fully Homomorphic Encryption (FHE) is developed. However, the nature of FHE requires a huge key that prolongs the encryption time; thusly, impractical for real deployment. By far, the variant of Integer-based FHE is protected with the smallest key, while the security is maintained at the optimum level. Inspired by these features, this thesis is aimed to further optimise Integer-based scheme from the hardware perspective. In particular, it is focused on optimising the computations during the encryption, involving large size operands. The first optimization is proposed based on the frequency domain multiplier, Number Theoretic Transform (NTT). An optimisation is emphasized on NTT kernel which results in stretched NTT length; thus, to offer larger multiplier. Significant speed-up improvement is achieved with 92% faster than software. The second proposed multiplier is Weighted-NTT, targeted for Digital Signal Processing (DSP) embedded multiplier implementation; thusly, a small moduli is selected. The convolution properties of Weighted-NTT are exploited to fill the NTT length entirely with operand; thus, expand the multiplier size. It performs 93.2% faster encryption than software implementation for Toy group. Lastly, Karatsuba multiplier optimization is proposed. Also targeting for DSP implementation, the ultimate optimization is suggested on the hardware arrangement to produce high Throughput vs Area. It significantly speed-up the Integer-based FHE encryption with 99% better speed than the benchmark software implementation. This research has shown that the optimised multipliers on a hardware platform can significantly improve Integer-based FHE encryption’s performance with at least 92% improvement than the same scheme implemented on software.