[Resource Topic] 2022/1363: Bootstrapping for BGV and BFV Revisited

Welcome to the resource topic for 2022/1363

Bootstrapping for BGV and BFV Revisited

Authors: Robin Geelen, Frederik Vercauteren


We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that BGV and BFV 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.

ePrint: https://eprint.iacr.org/2022/1363

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .