International Association
for Cryptologic Research

Fully homomorphic encryption is a revolutionary technology that allows arbitrary computations on encrypted data, providing privacy and security. State-of-the-art schemes such as the Fan-Vercauteren (FV) scheme are based on the Learning with Errors assumption and its variants. Thus, each ciphertext has an error that increases with each homomorphic operation. To maintain correctness, the error must be kept below a certain threshold, which requires a balance between security and computational efficiency. Therefore, choosing optimal, secure, and efficient parameters can be a challenging task, even for experts in a particular scheme.

In this paper, we present two major contributions to improve the parameter selection in the FV scheme. We perform the first average case analysis to estimate the error growth. Our method significantly improves on previous work in terms of accuracy and tightness of bounds. For a circuit with a multiplicative depth of only 3, our bounds are within 1.2 bits of the experimentally observed values while being up to 19 bits tighter than previous analyses.

In addition, we take advantage of our theoretical advances and propose the first parameter generation tool for the FV 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.