Paper 2026/811

Efficient Bootstrapping of Matrices in FHE

Abstract

In recent years, Fully Homomorphic encryption (FHE) has proven to be a practical solution to various privacy preserving applications such as neural network inference, private information retrieval, and genome analysis. Industries have started to utilize FHE to enable private computation of user's sensitive data, to protect user privacy. Out of all FHE applications, deep learning inference has been the most popular field of research among FHE researchers and practitioners, as it is incredibly challenging to do encrypted inference under FHE. Matrix multiplication is the fundamental operation that is used in deep learning, and is notoriously challenging to implement efficiently in FHE. Many works utilize CKKS, SotA FHE scheme for deep learning. They introduce novel encoding strategies to enable matrix multiplication, but they require very large evaluation keys, high execution time, and matrix dimension limitations. Fortunately, a recent FHE scheme proposed by Gentry and Lee, called the GL scheme, supports matrix multiplication as a native operation, whilst supporting every operation in CKKS. While very promising, the unique ring structure of the scheme requires prime NTT transforms, 3D DFT encoding of the message, which are not researched enough. Additionally, there is no efficient bootstrapping algorithm introduced by this scheme, as bootstrapping is needed to enable deep computations that is required by large deep learning models. In this work, we introduce the first unique and efficient bootstrapping algorithm of the GL scheme.