A collaborative team of researchers has released a new study addressing one of the most persistent optimization challenges in Fully Homomorphic Encryption (FHE). In a paper titled "From Dependent Ciphertexts to Sharp Bounds for Polynomial Evaluation in BGV," authors Chiara Marcolla of the Technology Innovation Institute, Nadir Murru of the University of Trento, and Matilda Urani of the Polytechnic University of Turin introduce an advanced average-case framework for estimating noise growth. Their findings allow for tighter selection of ciphertext moduli in the BGV encryption scheme, resulting in tangible performance boosts that outperform parameters currently used in major FHE software libraries.
Fully Homomorphic Encryption represents a transformative paradigm in modern cryptography, allowing computations to be performed directly on encrypted data without requiring decryption. This capability enables secure cloud computing, privacy-preserving machine learning, and confidential data processing across untrusted environments. However, the practical deployment of FHE schemes remains constrained by performance overheads. Chief among these engineering obstacles is the precise management of noise growth during homomorphic operations.
Every ciphertext in lattice-based FHE schemes carries an associated noise component. As data undergoes homomorphic additions and multiplications, this noise inevitably accumulates. Choosing ciphertext moduli that are excessively large undermines the overall efficiency, computational speed, and scalability of the cryptographic scheme. Conversely, underestimating noise growth carries severe consequences, including decryption failures and potential security vulnerabilities. Consequently, accurate noise estimation is vital for determining the optimal parameter sets that balance security margins with computational performance.
Traditionally, average-case analyses have provided researchers and engineers with probabilistic estimates of noise expansion in practical FHE computations. Yet, recent studies have demonstrated that reliable estimation requires accounting for intricate dependencies among ciphertext errors. Neglecting these underlying correlations can cause analytical models to systematically underestimate the true accumulation of noise, leading to risky parameter choices.
Addressing this gap, the newly published research presents the first comprehensive average-case analysis for the BGV scheme that accounts for both the correlations induced by secret and public keys and the dependencies that emerge between ciphertexts. By formulating new variance estimates tailored specifically for the noise coefficients involved in homomorphic additions and multiplications with dependent ciphertexts, the authors have established a rigorous mathematical foundation for tracking error propagation.
Crucially, the research team extended their theoretical framework beyond basic arithmetic operations to encompass the homomorphic evaluation of polynomial functions. Polynomial evaluation is a ubiquitous building block in FHE applications, frequently utilized to approximate non-linear functions, implement activation functions in privacy-preserving neural networks, and execute complex data analytics. By modeling noise dynamics through polynomial evaluations, the authors achieved theoretical estimates that align exceptionally closely with empirical, experimental observations, exhibiting discrepancies of less than 1.2 bits.
These sharp theoretical bounds carry immediate practical implications for parameter selection in real-world cryptographic deployments. By adopting these refined estimates to configure the initial parameters of the BGV scheme, the researchers successfully engineered significantly smaller ciphertext moduli compared to those currently embedded in widely utilized FHE software frameworks.
When benchmarked against established implementations, the performance improvements are substantial. Compared to OpenFHE, the new parameter selection approach yields an average reduction of approximately 11.5% in ciphertext modulus size. Furthermore, relative to HElib, the framework successfully reduces the ratio between consecutive moduli by up to 23 bits per level in practical operational settings. These reductions directly translate to lower memory footprints, faster arithmetic operations, and enhanced scalability for applications relying on the BGV homomorphic encryption scheme.






