Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM SIGSAC Conference on Computer and Communications Security (CCS)

New IND-CPA-D Attacks on BFV and BGV

Hyeongmin Choe, Min-Sik Kang, Damien Stehlé

Published Nov 12, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1145/3830454.3846665

Related papers

A New CRT-based Fully Homomorphic Encryption

Anil Kumar Pradhan, Abhraneel Dutta, Hansraj Jangir +1 more

The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.

IACR Communications in Cryptology•Aug 3, 2026•1 citation

Key Recovery of the Edge-Based Quantum-Secure Fully Homomorphic Encryption Scheme

Jiseung Kim, Hyung Tae Lee

Modern consumer technologies increasingly rely on cloud services and edge computing to process sensitive user data, which must remain private even during computation. Fully homomorphic encryption (FHE) offers a powerful mechanism for enabling such privacy-preserving computation by allowing data to be processed directly in encrypted form. Since Gentry’s breakthrough, all FHE schemes achieving indistinguishability under chosen-plaintext attacks (IND-CPA) have relied on noise-bearing designs. In these constructions, noise plays a central role in ensuring security, but also introduces substantial efficiency overhead. Thus, whether a secure and efficientnoise-freeFHE scheme is possible has remained an open question. A recent work marketed as “edge-based quantum-secure FHE’’ (EB-QFHE) claims to resolve this challenge by proposing a noise-free construction over a prime field and asserting both IND-CPA security and improved efficiency (IEEE Transactions on Consumer Electronics, 2025). In this paper, we present polynomial-time key-recovery attacks against EB-QFHE schemes. Our attacks derive two low-degree univariate polynomials from public information, whose unique common root corresponds to the secret key, and recover it by applying standard polynomial root-finding algorithms. Our theoretical analysis shows that the attacks succeed with overwhelming probability. Furthermore, our SageMath implementation demonstrates that the proposed attacks recover the secret key with a 100% success rate in under one second under the parameter settings recommended in the original paper. Our findings have direct implications for consumer electronics security: edge devices, gateways for the Internet of Things (IoT), and smart appliances that adopt EB-QFHE become completely vulnerable, since an adversary can recover the secret key solely from publicly available parameters.

IEEE Transactions on Consumer Electronics•Jan 1, 2026•0 citations

An efficient multi-key BFV fully homomorphic encryption scheme with optimized relinearization

Sai Hu, Ruwei Huang, Liang Zhou

Abstract Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to $$\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}$$ d + 2 d ~ r ′ / d + 2 l ~ of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.

Cybersecurity•Jun 26, 2025•4 citations

New IND-CPA-D Attacks on BFV and BGV — Artifact

Damien Stehlé, Minsik Kang, Hyeongmin Choe

This artifact backs the three attacks of the paper, Hyeongmin Choe, Minsik Kang, and Damien Stehlé, "New IND-CPA-D Attacks on BFV and BGV," ACM CCS 2026. This project holds the package used for artifact evaluation, including our samples for Section 3. The code is maintained at https://github.com/hmchoe0528/NEW_INDCPAD_HE.

•Nov 2, 2026•0 citations

CCA-Secure Leveled FHE From Multi-Identity Fully Homomorphic Encryption

Weili Wang, Bin Hu, Xiufeng Zhao

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.

Joint International Information Technology, Mechanical and Electronic Engineering Conference (JIMEC)•Jan 1, 2017•0 citations

Efficient fully homomorphic encryption with circularly secure key switching process

Tanping Zhou, Xiaoyuan Yang, Wei Zhang +1 more

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper, the 'special b' variant of the learning with errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearisation process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski's scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.

International Journal of High Performance Computing and Networking•Jan 1, 2016•8 citations
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.
The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.
Modern consumer technologies increasingly rely on cloud services and edge computing to process sensitive user data, which must remain private even during computation. Fully homomorphic encryption (FHE) offers a powerful mechanism for enabling such privacy-preserving computation by allowing data to be processed directly in encrypted form. Since Gentry’s breakthrough, all FHE schemes achieving indistinguishability under chosen-plaintext attacks (IND-CPA) have relied on noise-bearing designs. In these constructions, noise plays a central role in ensuring security, but also introduces substantial efficiency overhead. Thus, whether a secure and efficientnoise-freeFHE scheme is possible has remained an open question. A recent work marketed as “edge-based quantum-secure FHE’’ (EB-QFHE) claims to resolve this challenge by proposing a noise-free construction over a prime field and asserting both IND-CPA security and improved efficiency (IEEE Transactions on Consumer Electronics, 2025). In this paper, we present polynomial-time key-recovery attacks against EB-QFHE schemes. Our attacks derive two low-degree univariate polynomials from public information, whose unique common root corresponds to the secret key, and recover it by applying standard polynomial root-finding algorithms. Our theoretical analysis shows that the attacks succeed with overwhelming probability. Furthermore, our SageMath implementation demonstrates that the proposed attacks recover the secret key with a 100% success rate in under one second under the parameter settings recommended in the original paper. Our findings have direct implications for consumer electronics security: edge devices, gateways for the Internet of Things (IoT), and smart appliances that adopt EB-QFHE become completely vulnerable, since an adversary can recover the secret key solely from publicly available parameters.
Abstract Traditional fully homomorphic encryption(FHE) schemes allow computation only on data encrypted under the same public key. Multi-Key Fully Homomorphic Encryption (MKFHE) enables arbitrary operations on data encrypted with different public keys, allowing all participating users jointly decrypting the final ciphertext. The multi-key BFV FHE scheme inherits BFV’s advantages in ring element encryption and scale invariance. Nonetheless, it also has some disadvantages, such as additional noise generated during the relinearization process, the need for costly transformations during the external product process, and the requirement for a Common Reference String (CRS). In this paper, we investigate the MKFHE scheme for RLWE-based BFV. Firstly, we improve the modulus size of the evaluation key and the public key to construct a modulus enchancement relinearization method, which can significantly reduce the noise generated during the relinearization process. Secondly, we propose to use an inner product via Gadget decomposition in the relinearization based on the MK-BFV scheme instead of the original outer product operation, which can reduce the complexity of the NTT operation to (d+2d~)r′/(d+2)l~\left( {d + 2\tilde{d}} \right)r^{\prime } /\left( {d + 2} \right)\tilde{l}(d+2d~)r′/(d+2)l~ d + 2 d ~ r ′ / d + 2 l ~ of the original one. Finally, we propose a MK-BFV without CRS on the basis of the previous ones, which enhances the user's control over his own key.
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.
Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations are inefficient. In this paper, the 'special b' variant of the learning with errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearisation process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski's scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.