Paper 2023/988

On the Hardness of Scheme-Switching Between SIMD FHE Schemes

Karim Eldefrawy, SRI International
Nicholas Genise, Duality Technologies
Nathan Manohar, IBM Research - Thomas J. Watson Research Center

Fully homomorphic encryption (FHE) schemes are either lightweight and can evaluate boolean circuits or are relatively heavy and can evaluate arithmetic circuits on encrypted vectors, i.e., they perform single instruction multiple data operations (SIMD). SIMD FHE schemes can either perform exact modular arithmetic in the case of the Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski-Fan-Vercauteren (BFV) schemes or approximate arithmetic in the case of the Cheon-Kim-Kim-Song (CKKS) scheme. While one can homomorphically switch between BGV/BFV and CKKS using the computationally expensive bootstrapping procedure, it is unknown how to switch between these schemes without bootstrapping. Finding more efficient methods than bootstrapping of converting between these schemes was stated as an open problem by Halevi and Shoup, Eurocrypt 2015. In this work, we provide strong evidence that homomorphic switching between BGV/BFV and CKKS is as hard as bootstrapping. In more detail, if one could efficiently switch between these SIMD schemes, then one could bootstrap these SIMD FHE schemes using a single call to a homomorphic scheme-switching algorithm without applying homomorphic linear transformations. Thus, one cannot hope to obtain significant improvements to homomorphic scheme-switching without also significantly improving the state-of-the-art for bootstrapping. We also explore the relative hardness of computing homomorphic comparison in these same SIMD FHE schemes as a secondary contribution. We show that given a comparison algorithm, one can bootstrap these schemes using a few calls to the comparison algorithm for typical parameter settings. While we focus on the comparison function in this work, the overall approach to demonstrate relative hardness of computing specific functions homomorphically extends beyond comparison to other useful functions such as min/max or ReLU.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. PQCrypto 2023
Fully homomorphic encryptionBootstrappingLattice-Based CryptographyPost-Quantum Cryptography
Contact author(s)
karim eldefrawy @ sri com
ngenise @ dualitytech com
nmanohar @ ibm com
2023-06-26: approved
2023-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Karim Eldefrawy and Nicholas Genise and Nathan Manohar},
      title = {On the Hardness of Scheme-Switching Between SIMD FHE Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/988},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.