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

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)
PDF
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
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},
      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.