Paper 2023/600

Improving and Automating BFV Parameters Selection: An Average-Case Approach

Abstract

The Brakerski/Fan-Vercauteren (BFV) scheme is a state-of-the-art scheme in Fully Homomorphic Encryption based on the Ring Learning with Errors (RLWE) problem. Thus, ciphertexts contain an error that increases with each homomorphic operation and has to stay below a certain threshold for correctness. This can be achieved by setting the ciphertext modulus big enough. On the other hand, a larger ciphertext modulus decreases the level of security and computational efficiency, making parameters selection challenging. Our work aims at improving the bound on the ciphertext modulus, minimizing it. Our main contributions are the following. Primarily, we perform the first average-case analysis of the error growth for the BFV scheme, significantly improving its estimation. For a circuit with multiplicative depth of only 3, our bounds are up to 18.6 bits tighter than previous analyses and within 1.1 bits of the experimentally observed values. Secondly, we give a general way to bound the ciphertext modulus for correct decryption that allows closed formulas. Finally, we use our theoretical advances and propose the first parameter generation tool for the BFV scheme. Here we add support for arbitrary but use-case-specific circuits, as well as the ability to generate easy-to-use code snippets, making our theoretical work accessible to both researchers and practitioners.