Paper 2022/1363

Bootstrapping for BGV and BFV Revisited

Robin Geelen, KU Leuven
Frederik Vercauteren, KU Leuven
Abstract

We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that both schemes can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets. Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in JOC 2023
DOI
10.1007/s00145-023-09454-6
Keywords
Fully homomorphic encryptionBootstrappingBrakerski-Gentry-VaikuntanathanBrakerski-Fan-VercauterenRecryption
Contact author(s)
robin geelen @ esat kuleuven be
frederik vercauteren @ esat kuleuven be
History
2023-11-18: last of 5 revisions
2022-10-11: received
See all versions
Short URL
https://ia.cr/2022/1363
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1363,
      author = {Robin Geelen and Frederik Vercauteren},
      title = {Bootstrapping for BGV and BFV Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1363},
      year = {2022},
      doi = {10.1007/s00145-023-09454-6},
      note = {\url{https://eprint.iacr.org/2022/1363}},
      url = {https://eprint.iacr.org/2022/1363}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.