Paper 2022/706

Finding and Evaluating Parameters for BGV

Johannes Mono, Ruhr-University Bochum
Chiara Marcolla, Technology Innovation Institute
Georg Land, Ruhr-University Bochum, DFKI GmbH
Tim Güneysu, Ruhr-University Bochum, DFKI GmbH
Najwa Aaraj, Technology Innovation Institute
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.

Metadata
Available format(s)
PDF
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
2022-06-03: received
See all versions
Short URL
https://ia.cr/2022/706
License
Creative Commons Attribution-NonCommercial-ShareAlike
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.