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 parameter selection challenging. Our work aims to improve 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 a multiplicative depth of only 5, our bounds are up to 25.2 bits tighter than previous analyses and within 1.2 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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Fully Homomorphic EncryptionBFVParameter Generationaverage-case noise analysisPALISADEOpenFHE
- Contact author(s)
-
beatrice biasioli @ tii ae
chiara marcolla @ tii ae
marco calderini @ unitn it
johannes mono @ rub de - History
- 2024-10-24: last of 4 revisions
- 2023-04-27: received
- See all versions
- Short URL
- https://ia.cr/2023/600
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2023/600,
author = {Beatrice Biasioli and Chiara Marcolla and Marco Calderini and Johannes Mono},
title = {Improving and Automating {BFV} Parameters Selection: An Average-Case Approach},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/600},
year = {2023},
url = {https://eprint.iacr.org/2023/600}
}