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.