Optimizing HE operations via Level-aware Key-switching Framework

Abstract

In the state-of-the-art Homomorphic Encryption (HE) schemes, the key-switching procedure is commonly used as a building block of non-linear operations, but also a major performance bottleneck. Its complexity is primarily determined by the corresponding gadget decomposition, which transforms a ciphertext entry into a vector of small elements to reduce the noise growth from the multiplication with an evaluation key. Prior works such as Cheon et al. (SAC 2018) and Halevi et al. (CT-RSA 2019) fixed a decomposition function in the setup phase which is applied across all ciphertext levels, thus yielding suboptimal performance. In this paper, we introduce a novel key-switching framework for leveled HEs. We aim to allow the use of different decomposition functions during the evaluation phase so that the optimal decomposition method can be utilized at each level to achieve the best performance. A naive solution might generate multiple key-switching keys corresponding to all possible decomposition functions, and sends them to an evaluator. However, our solution can achieve the goal without such communication overhead since it allows an evaluator to dynamically derive other key-switching keys from a single key-switching key depending on the choice of gadget decomposition. We implement our framework at a proof-of-concept level to provide concrete benchmark results. Our experiments show that we achieve the optimal performance at every level while maintaining the same computational capability and communication costs.