Paper 2023/1642

A New Perspective on Key Switching for BGV-like Schemes

Abstract

Fully homomorphic encryption is a promising solution for privacy-preserving computation, especially involving sensitive data. 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 optimize other aspects of these schemes, key switching has gone largely untouched. One exception has been a recent work by Kim et al. at CRYPTO 2023 [26] introducing a new double-decomposition technique for state-of-the-art key switching. While their contributions are interesting, the authors have a skewed perspective on the complexity of key switching which results in a flawed parameter analysis and incorrect conclusions about the effectiveness of their approach. In this work, we correct their analysis with a new perspective on key switching and provide the new asymptotic bound O(ωℓ). More generally, we take a holistic look at key switching and parameter selection. We revisit an idea by Gentry, Halevi, and Smart [19] improving key switching performance by up to 63% and explore novel possibilities for parameter optimization. We also reduce the number of multiplications in key switching using new constant folding techinques, which speed up execution times by up to 11.6%. Overall, we provide an in-depth analysis of key switching, guidelines for optimal parameter selection, and novel ideas which speed up execution times significantly.