Computational FHE Circuit Privacy for Free

Circuit privacy is an important notion in Fully Homomorphic Encryption (FHE), well-illustrated by the Machine Learning-as-a-Service scenario. A scheme is circuit private (first defined in Gentry’s PhD Thesis) if an adversary cannot learn the circuit evaluated on a ciphertext from the computation result. In this work, we first show that the BGV FHE scheme by Brakerski, Gentry and Vaikuntanathan (ITCS’12) is computationally circuit private in a semi-honest context, and then present an extended construction to make it computationally circuit private against a malicious adversary. We achieve this without resorting to expensive mechanisms such as noise flooding. Instead, we argue carefully about the ciphertext and noise distributions that are encountered in BGV. In more detail, we consider the notion of circuit privacy along four dimensions: whether the adversary is internal or external (i.e. does the adversary hold the secret key or not), and in a semi-honest and malicious setting. Our starting point is Gentry’s definition, which we change from statistical to computational indistinguishability. Doing so allows us to prove that the BGV scheme is computationally circuit-private in a semi-honest setting to an external adversary out of the box. We then propose a new definition by extending Gentry’s definition to an internal adversary. This is appropriate since the scenario that the client is the adversary (and therefore has access to the decryption key) is a realistic one. Further, we remark that our definition is strictly stronger than Gentry’s – our definition requires that a scheme be circuit private according to Gentry’s definition and additionally, the distribution of the ciphertext noise in all ciphertexts to be computationally indistinguishable. Given this new definition, and using previous results of Costache, Nürnberger and Player (CT-RSA’23), we show that slight modifications to the BGV scheme will make it fulfill this new definition. Finally, we show how to extend these results to a malicious setting if we require that the client attaches proofs of well-formedness of keys and ciphertexts