Paper 2022/706
Finding and Evaluating Parameters for BGV
Abstract
Fully Homomorphic Encryption (FHE) is a groundbreaking technology that allows for arbitrary computations to be performed on encrypted data. State-of-the-art schemes such as Brakerski Gentry Vaikuntanathan (BGV) are based on the Learning with Errors over rings (RLWE) assumption, and each ciphertext has an associated error that grows with each homomorphic operation. For correctness, the error needs to stay below a certain threshold, requiring a trade-off between security and error margin for computations in the parameters. Choosing the parameters accordingly, for example, the polynomial degree or the ciphertext modulus, is challenging and requires expert knowledge specific to each scheme. In this work, we improve the parameter generation process across all steps of its process. We provide a comprehensive analysis for BGV in the Double Chinese Remainder Theorem (DCRT) representation providing more accurate and better bounds than previous work on the DCRT, and empirically derive a closed formula linking the security level, the polynomial degree, and the ciphertext modulus. Additionally, we introduce new circuit models and combine our theoretical work in an easy-to-use parameter generator for researchers and practitioners interested in using BGV for secure computation. Our formula results in better security estimates than previous closed formulas, while our DCRT analysis results in reduced prime sizes of up to 42% compared to previous work.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Fully Homomorphic EncryptionBGV SchemeParameter GenerationRLWE SecurityDCRT Representation
- Contact author(s)
-
johannes mono @ rub de
chiara marcolla @ tii ae
georg land @ rub de
tim gueneysu @ rub de
najwa aaraj @ tii ae - History
- 2023-05-29: last of 4 revisions
- 2022-06-03: received
- See all versions
- Short URL
- https://ia.cr/2022/706
- License
-
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}, url = {https://eprint.iacr.org/2022/706} }