### Finding and Evaluating Parameters for BGV

##### Abstract

The BGV scheme is a state-of-the-art fully homomorphic encryption (FHE) scheme. Encryption is based on the Learning with Errors over rings (RLWE) assumption and thus each ciphertext has an associated error that grows with each homomorphic operation. To avoid failure during decryption, the growing error, also called critical quantity, needs to stay below a certain threshold. This requires a trade-off between security and error margin that influences the parameters specific to each use case. Choosing such parameters, for example the polynomial degree or the ciphertext modulus, is a challenge and requires expert knowledge. The main idea of our work is to improve the current state of BGV parameter selection. More specifically, we provide a parameter generator for the leveled BGV scheme using theoretical bounds on the error growth and an empirically derived formula for the security estimate. For the former, we combine previous analysis using the canonical embedding norm and analysis of the residue number system. For the latter, we develop a model based on data from the Lattice Estimator tool and coupled optimization. Finally, we provide the open-source generator which outputs easy-to-use code snippets for the BGV libraries HElib and PALISADE.

Available format(s)
Category
Applications
Publication info
Preprint.
Keywords
Fully Homomorphic Encryption BGV Parameter Generation HElib PALISADE
Contact author(s)
johannes mono @ rub de
chiara marcolla @ tii ae
georg land @ rub de
tim gueneysu @ rub de
najwa aaraj @ tii ae
History
2022-06-09: revised
See all versions
Short URL
https://ia.cr/2022/706

CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2022/706,
author = {Johannes Mono and Chiara Marcolla and Georg Land and Tim Güneysu and Najwa Aaraj},
title = {Finding and Evaluating Parameters for BGV},
howpublished = {Cryptology ePrint Archive, Paper 2022/706},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/706}},
url = {https://eprint.iacr.org/2022/706}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.