Paper 2023/1642

A New Perspective on Key Switching for BGV-like Schemes

Abstract

Fully homomorphic encryption is a promising approach when computing on encrypted data, especially when sensitive data is involved. For BFV, BGV, and CKKS, three state-of-the-art encryption schemes, the most costly homomorphic primitive is the so-called key switching. While a decent amount of research has been devoted to optimizing other aspects of these schemes, key switching has gone largely untouched. One exception has been a recent work [26] introducing a new double-decomposition technique. Their contributions are an important addition to the current state-of-the-art with one flaw: They take a limited perspective on key switching parameters and their asymptotic complexity which leads to incorrect conclusions about how effective their approach really is. In our work, we deep dive into key switching and correct, enhance, and improve the current state-of-the-art. We provide a new perspective on key switching parameters for the single- and double-decomposition techniques, respectively, and show that the former outperforms the latter in most scenarios. Additionally, we revisit an idea by Gentry, Halevi, and Smart [17] and reduce the number of multiplications.