We examine the relationship between correctness definitions for Fully Homomorphic Encryption (FHE) and the associated security definitions. We show that reactive notions of correctness imply IND-CPA-D and sIND-CPA-D security. But that to obtain both IND-CPA-D and sIND-CPA-D security we need to use a randomized version of the evaluation procedure. Such randomized evaluation procedures cause problems in real life deployments of FHE solutions, so we then go on to show how one can de-randomize the evaluation procedure and still obtain sIND-CPA-D security in the random oracle model for the specific FHE scheme of TFHE.
We examine the relationship between correctness definitions for Fully Homomorphic Encryption (FHE) and the associated security definitions. We show that reactive notions of correctness imply IND-CPA-D and sIND-CPA-D security. But that to obtain both IND-CPA-D and sIND-CPA-D security we need to use a randomized version of the evaluation procedure. Such randomized evaluation procedures cause problems in real life deployments of FHE solutions, so we then go on to show how one can de-randomize the evaluation procedure and still obtain sIND-CPA-D security in the random oracle model for the specific FHE scheme of TFHE.
This paper proposes a generic construction of CCA-secure fully homomorphic encryption (FHE) scheme.First, we introduce a new primitive called multi-identity fully homomorphic encryption, which works in the multi-identity setting; that is, homomorphic evaluation can performed on ciphertexts created with different identities.Then, we propose an IND-sID-CPA secure multi-identity leveled FHE scheme over lattice.Finally, we present CCA-secure FHE from our proposed multi-identity FHE scheme and strongly EUF-CMA secure signature.The security analysis shows that our FHE scheme is CCA2-secure when the evaluation key is unavailable to the adversary, and remains CCA1-secure when the evaluation key is exposed in the standard model.
We consider a setting of two-party computation between a server and a client where every message received by the server is encrypted by a fully homomorphic encryption (FHE) scheme and its decryption key is held by the client only. Akavia and Vald (IACR ePrint Archive, 2021) revisited the privacy problem in such protocols against malicious servers and revealed (as opposed to a naive expectation) that under certain condition, a malicious server can recover the client's input even if the underlying FHE scheme is IND-CPA secure. They also gave some sufficient conditions for the FHE scheme to ensure the privacy against malicious servers. However, their argument did not consider the possibility that a query from a malicious server to a client involves an invalid ciphertext. In this paper, we show, by giving a concrete example, that if such an invalid query is just rejected by the client, then the sufficient conditions in Akavia and Vald's result do not in general ensure the privacy against malicious servers. We also propose another option to handle an invalid query in a way that the client returns a random ciphertext (without explicitly rejecting the query), and show that such a protocol is private against malicious servers if the underlying FHE scheme is IND-CPA secure, sanitizable (in the sense of Ducas and Stehlé, EUROCRYPT 2016), and circular secure.
IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness. We first extend the bootstrapping failure attacks from Cheon et al. [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on skewing the ciphertext noise in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we skew the mask part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game. We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.
Multi-key fully homomorphic encryption (MKFHE), a generalization of fully homomorphic encryption (FHE), enables a computation over encrypted data under multiple keys. The first MKFHE schemes were based on the NTRU primitive, however these early NTRU based FHE schemes were found to be insecure due to the problem of over-stretched parameters. Recently, in the case of standard (non-multi key) FHE a secure version, called FINAL, of NTRU has been found. In this work we extend FINAL to an MKFHE scheme, this allows us to benefit from some of the performance advantages provided by NTRU based primitives. Thus, our scheme provides competitive performance against current state-of-the-art multi-key TFHE, in particular reducing the computational complexity from quadratic to linear in the number of keys.
Abstract. Fully homomorphic encryption (FHE) is a form of public-key encryption that enables arbitrary computation over encrypted data. The past few years have seen several realizations of FHE under differ-ent assumptions, and FHE has been used as a building block in many cryptographic applications. Adaptive security for public-key encryption schemes is an important se-curity notion proposed by Canetti et al. It is intended to ensure security when encryption is used within an interactive protocol and parties may be adaptively corrupted by an adversary during the course of the protocol execution. Due to the extensive applications of FHE to protocol design, it is natural to understand whether adaptively secure FHE is achievable. In this paper we show two contrasting results in this direction. First, we show that adaptive security is impossible for FHE satisfying the (stan-dard) compactness requirement. On the other hand, we show a construc-tion of adaptively secure FHE that is not compact, but that does achieve circuit privacy.
Fully homomorphic encryption (FHE) is a form of public-key encryption that allows the computation of arbitrary functions on encrypted data without decrypting the data. As a result, it is a useful tool with numerous applications. Certificateless encryption (CLE) is a type of public-key encryption that combines the advantages of PKI-based public-key encryption with those of identity-based encryption (IBE). Thus, certificateless fully homomorphic encryption (CLFHE) has aroused considerable research interest. Recently, Chen, Hu, and Lian proposed a leveled certificateless homomorphic encryption (CLHE) scheme and proved its semantic security based on the learning with errors (LWE) problem in the random oracle model. However, their scheme supports only homomorphic addition, but not homomorphic multiplication. In this work, we construct two leveled CLFHE schemes using the approximate eigenvector method presented by Gentry, Sahai, and Waters. Based on the hardness of the LWE problem, we prove that one scheme satisfies adaptive semantic security and anonymity in the random oracle model, whereas the other satisfies selective semantic security and anonymity in the standard model.