A Matter of Correctness: Selecting Optimal BFV Parameters and Preventing Key-Recovery Attacks

Fully Homomorphic Encryption is a form of encryption that, in contrast to traditional cryptography, enables privacy-preserving data processing. A price to pay for this revolutionary feature is that the public parameters of FHE schemes depend on the operations to be performed, making their optimal selection an open challenge. The reason is that the state-of-the-art schemes are built on top of the LWE and RLWE problems, hence introducing some error during the encryption phase. This quantity grows as homomorphic operations are performed, potentially interfering with the plaintext during decryption. To guarantee correctness, and avoid key-recovery attacks, a large ciphertext modulus is required. However, this condition can result in an inadequate level of security or low efficiency. For this reason, it is essential to determine the minimal ciphertext modulus that allows correct decryption, i.e. to track the error growth as accurately as possible.

The prevailing trend in the FHE literature for computing tight upper bounds on the error adopts the average-case analysis. However, the current studies lead to underestimates when applied to the BFV scheme. Moreover, they are limited to the case where ciphertexts are independent. In the abstract, we briefly explain how we successfully performed the first average-case analysis for the BFV scheme and how the method could be extended to the general case where the ciphertexts are computed dependently. We show the results obtained, comparing them with those obtained from experiments and from the state-of-the-art methods. Finally, we point out the differences between the two cases to explain how selecting correct parameters prevents previously proposed key-recovery attacks.