New Key-Recovery Attacks Against FHE

Fully homomorphic encryption (FHE) is a fast-developing field that would enable some interesting privacy-preserving applications. Those schemes allow any computation to be performed on encrypted data without disclosing information about the data itself while producing accurate computation results upon decryption.

Recently, two papers have been published regarding a security definition for FHE. These papers demonstrate that by slightly empowering attackers within a reasonable set of assumptions, practical key-recovery attacks can be constructed. Those attacks are applicable to various established libraries such as SEAL, OpenFHE, Lattigo, TFHE-rs, and TFHELib.

In this post, we will first give a summary of the Learning With Error (LWE) problem to understand the fundamentals of those attacks. A toy implementation is provided to illustrate the concepts of this post. Then we will briefly introduce the general properties and the security models that apply to FHE. The new attacks and their practical results against well-known implementations will be presented. Finally, we will discuss how these papers help understanding the security and pitfalls of FHE schemes in general.

Learning With Error

Nowadays, most of the FHE schemes are based on the Learning With Error↗ (LWE) problem or a variation thereof. Besides FHE, LWE has great importance in cryptography in general and is used to build some post-quantum signature algorithms. To understand the following attacks, we should first introduce some properties of LWE.

In LWE cryptosystems, the secret key $s = (s_0, \dots, s_{n-1}) \in \mathbb{Z}_q^n$ is a randomly generated vector where $q \geq 2$ is a positive integer and $n \geq 1$ is the size parameter. For the sake of simplicity, we assume the message $m \in \{0,1\}$ to be a single bit. The encryption $c = (a,b)$ of $m$ is given by

$b = \langle a,s \rangle + \lfloor \frac{q}{2}\rfloor m + e$

with $a \in \mathbb{Z}_q^n$ randomly generated and $e \in \mathbb{Z}_q$ a small randomly generated error. The operator $\langle , \rangle$ is the standard inner product. A ciphertext $c = (a,b)$ is decrypted with

$m = \lceil\frac{2}{q} (\langle a,s \rangle - b)\rfloor \mod 2$

where $\lceil \cdot \rfloor$ is the rounding function. Since the encryption is linear, it is relatively easy to see that LWE has a homomorphic encryption property. Indeed, adding two ciphertexts $(a_1,b_1)$ and $(a_1,b_1)$ together gives the following:

$(a_1+a_2,b_1+b_2) = \left(a_1+a_2, \langle a_1,s \rangle + \langle a_2,s \rangle + \lfloor \frac{q}{2}\rfloor (m_1 + m_2) + e_1 + e_2\right) = \left(a_1+a_2, \langle a_1 + a_2 ,s \rangle + \lfloor \frac{q}{2}\rfloor (m_1 + m_2) + e_1 + e_2\right)$

This new ciphertext decrypts to $m_1 + m_2 \mod 2$. One thing to notice, which is important for understanding the following attacks, is that the new ciphertext has noise $e = e_1 + e_2$.

We have created a toy example in Sage, available in our GitHub repository↗, allowing to visualize how things work in practice:

sage: from lwe_binary import LWE
sage: lwe = LWE()
sage: s = lwe.keygen()
sage: c1 = lwe.encrypt(1,s)
sage: c1
((19331, 40593, 16415, 19987, 16358, 18642, 47726, 28920, 19322, 60414, 12111, 17241, 18520, 8379, 53280, 10978, 19388, 16743, 45284, 21682, 47339, 39674, 8962, 54166, 47172, 45000, 63534, 34439, 64653, 55681, 4290, 9750, 26215, 7889, 63029, 48475, 24295, 16684, 985, 30639, 61753, 46423, 18752, 33102, 50675, 30985, 23307, 42284, 46957, 19790, 59442, 60157, 59752, 23379, 16232, 12181, 15445, 807, 23396, 50120, 3860, 4103, 40049, 60981),
 96783)
sage: c2 = lwe.encrypt(1,s)
sage: c2
((13517, 22342, 34502, 10213, 59358, 36523, 19179, 41645, 54456, 24418, 52899, 60503, 39366, 8134, 40786, 44523, 9776, 26754, 28382, 24096, 43228, 35122, 41908, 7829, 31890, 45217, 28184, 34849, 53646, 53793, 8464, 4813, 52526, 39710, 20416, 31007, 20280, 47836, 34965, 15035, 48543, 36918, 20897, 21437, 20349, 48825, 5235, 20126, 43955, 15241, 15094, 63494, 15495, 25602, 37324, 5314, 55223, 41252, 54368, 28510, 39219, 9133, 7663, 15206),
 60423)
sage: c = lwe.enc_add(c1, c2)
sage: lwe.decrypt(c, s)
0

Here we encrypt twice the value 1, then we perform a homomorphic addition, and finally we decrypt the result. We have verified the additive homomorphic property of LWE since $1 + 1 = 0 \mod 2$ while working only on the encrypted data. The previous implementation uses very small parameters for experimentation, but it should not be used for sensitive applications.

We have seen that LWE has an additive homomorphic encryption property, or it can be seen as an XOR gate. Most of the current FHE constructions are based on LWE. Nevertheless, building a fully homomorphic encryption from LWE also requires to have a multiplicative homomorphic property, the AND gate. Building it for LWE is more difficult and specific to each scheme construction, so we will not cover it in this post. For more details, the Zama deep dive articles↗ are a very good resource.

Fully Homomorphic Encryption

In this section, we explain from a higher level the properties that satisfy FHE. These properties are unique to FHE schemes and make security definitions harder to verify, as we will see.

Basically, an FHE scheme is composed of algorithms $\mathrm{Enc}$ and $\mathrm{Dec}$ for encryption and decryption as well as an evaluation algorithm $\mathrm{Eval}$ such that for any function $f$ and any plaintexts $m_i$,

$\mathrm{Dec}(\mathrm{Eval}(f, \mathrm{Enc}(m_1, \dots, m_n))) = f(m_1, \dots, m_n)$

Roughly speaking, it means that an FHE scheme allows to compute over encrypted data without knowing their value in clear. In the previous example, the function $f$ was the addition modulo 2. The important thing to notice is that the FHE scheme is not dependent on the function $f$, so any function can be evaluated over the encrypted data.

All FHE schemes so far have noise in their ciphertexts, as mentioned for LWE, and after some operation on ciphertexts, a bootstrapping operation is necessary to reduce the noise. Otherwise, the decrypted plaintext may be wrong. The bootstrapping highly depends on the FHE scheme, but basically it is the operation of applying the homomorphic decryption operation on the ciphertext to reduce the noise still keeping the data encrypted. Since the decryption removes the error term from the message, the noise is reduced. However, the decryption itself also adds some noise; thus, it must ensure that the decryption gives the correct message. This is usually the most time-consuming part of FHE. During later developments, less-consuming bootstrapping operations have been proposed to achieve practical performances.

Security Models for FHE

The last thing we have to cover before moving on to the attacks is how to define the FHE security models.

IND-CPA

Most of the FHE schemes achieve only indistinguishability under chosen plaintext attack (IND-CPA) security. In this scenario, the adversary is able to choose some plaintexts $m_0$ and $m_1$ to ask for their encryption. The challenger chooses a random bit $b$ and sends $c_b$ the encryption of $m_b$ to the attacker. Then an attack is considered successful if the adversary is able to distinguish the ciphertext $c_b$ (i.e., to guess $b$). This security model may be sufficient for certain scenarios, but as soon as an attacker has access to the decryption of some ciphertexts they have chosen, it may be insecure.

IND-CCA2

For a stronger security model, the indistinguishability under adaptive chosen ciphertext attack (IND-CCA2) is often desirable. In this case, the adversary obtains a decryption oracle that can be used at any time, and their goal is to distinguish a ciphertext as before. In this scenario, the adversary can submit ciphertexts and obtain the decrypted plaintexts. Clearly, the attacker is not allowed to ask for the decryption of the plaintexts they have to distinguish. This model is often used to evaluate the security of cryptosystems. For example, Kyber↗, the public-key encryption chosen by the NIST as the new standard↗ for post-quantum cryptography, achieves IND-CCA2.

IND-CPA^D

In the case of FHE, things are more complicated. Under INDA-CCA2, an adversary can ask for the decryption of $c_b+c_b$ and check if the returned value equals or not twice the plaintext value (i.e., $m_0+m_0$ or $m_1+m_1$). Therefore, they can distinguish if the previously received ciphertext $c_b$ was the encryption of which plaintext. Thus, if an encryption scheme has a homomorphic property, it cannot achieve IND-CCA2 security. It means that as soon as an adversary is in a situation where the decryption of some ciphertexts are available to them, they can potentially compromise the encryption. This property has led to some research to define the maximum security achievable by FHE and a situation where there may be weaknesses. This problem is known; for example, the SEAL library↗ developed by Microsoft has a strong warning↗ to users about possible pitfalls when using such schemes in practice.

Understanding the security of the FHE scheme is a main concern, and that’s why the notion of IND-CPA^D has been proposed to study FHE security carefully. In this model, originally proposed by Li and Micciancio↗ in 2021, the adversary is offered to have a little more power compared to IND-CPA. The ^D represents the adversary’s ability to observe some decryption results. As usual, the adversary’s goal is to guess with a high probability a bit $b$ randomly generated by a challenger. The adversary can request encryption of any plaintexts $m_0,m_1$ and get the encryption corresponding to the bit $b$ chosen by the challenger. The adversary can also request function evaluations from previous encryption queries with a function of their choice. The challenger stores the queries on their side. Finally, the adversary can ask decryptions but only for previous queries that are independent of the challenge bit; otherwise, no output is sent. It means that the decryption is sent only if the two corresponding messages in the previous queries are equal. The full description of IND-CPA^D is given in the Li and Micciancio paper.

A given scheme satisfies IND-CPA^D security if any adversary playing the game above has no statistical advantage in guessing the value of $b$. This scheme does not seem to help the adversary compared to the IND-CPA model. On the contrary, when this model was introduced, an FHE scheme, namely CKKS↗, was shown to not be resistant to such model. The two new attacks presented in this post show that this model does not apply to either most current FHE schemes previously presumed to satisfy IND-CPA^D security.

The attacks demonstrated that the IND-CPA^D is not suitable for FHE schemes. Finding a good security model for the security of FHE is still an open problem and an area of ongoing research.

New Attacks Against FHE

The first attack↗ was proposed by a team from the French Atomic Energy Commission (CEA) and the second↗ one from the company CryptoLab↗. Both have been published at the Cryptology ePrint Archive in February 2024.

The attacks from both papers use the fact that the schemes based on LWE have noise after encryption. Applying operations iteratively on ciphertext may amplify the noise until the plaintext itself is not correct once decrypted. Let’s see what happens with our previous example if we repeatedly add the encryption of 0 to itself:

sage: m = 0
sage: c = lwe.encrypt(m,s)
sage: while m == 0:
....:     c = lwe.enc_add(c,c)
....:     m = lwe.decrypt(c,s)
....: 
sage: m
1

After some iterations, the ciphertext, which should always decrypt to 0, is wrongly decrypted to 1. In this scenario, we only follow the rules of the IND-CPA^D game since the evaluations of the plaintexts always output zero. It means that a successful attack built upon this property would break IND-CPA^D security of an FHE scheme.

Let’s see what happens under the hood. We have added a verbose mode to print the value of the decrypted error in binary:

sage: c = lwe.encrypt(0, s, verbose=True)
e = 3 (0000000000000011)
sage: c = lwe.enc_add(c,c)
sage: m = lwe.decrypt(c, s, verbose=True)
e = 6 (0000000000000110)
sage: c = lwe.enc_add(c,c)
sage: m = lwe.decrypt(c, s, verbose=True)
e = 12 (0000000000001100)
sage: m
0

We see that the error term is multiplied by two after each addition operation, which is coherent with the previous formula for ciphertext addition we have seen previously. This continues until the message itself is corrupted by the error. Now that we have a way to recover the error term, we add a ciphertext of zero to itself until the decrypted message is 1. Then, with a dichotomic search↗, we can recover the absolute value of the error $|e|$. The attack presented by the CEA uses this method to recover many values $|e_i|$. However, the attack implementation is not provided, so we implemented the dichotomic search in the script binary_attack.sage from our repository:

sage: attach("binary_attack.sage")
sage: c = lwe.encrypt(0, s, verbose=True)
e = -2 (-000000000000010)
sage: e, last_c = recover_abs_e(c, s)
sage: e
2

We need to pass the secret key $s$ to the function because it needs to request decryption of the plaintext as allowed by the IND-CPA^D model. As anticipated, the function returns the correct absolute value of the error $e$.

Then, the attack uses a trick to ensure that all the recovered values $e_i$ have the same sign and to discard other values with the opposite sign. Finally, when enough values of $e_i$ with the same sign are guessed, a linear system from the decryption formula relations is built:

$\langle a_i,s \rangle = b_i + |e_i|$

The linear system can be solved to recover the secret key $s$. Since the error terms are known up to the sign, there are two possibilities for the value of $s$. Our script implements those steps in the function binary_attack:

sage: s_recovered = binary_attack(s)
sage: s_recovered == s
True

We improved the attack slightly in our script by not discarding the errors with a different sign, but we should adapt the linear system accordingly. When the error signs match, we keep the same linear equation as before:

$\langle a_i,s \rangle = b_i + |e_i|$

When they differ, we add the following equation to our linear system:

$\langle a_i,s \rangle = b_i - |e_i|$

It allows us to divide by two the number of operations needed for the attack.

Then, in the CEA paper, an attack targets Ring LWE (RLWE) schemes. In this variation of LWE, the message bits $m_0, \dots, m_{n-1} \in \mathbb{Z}_2^n$ are seen as coefficients of a polynomial defined over the ring $R_q = \mathbb{Z}_q[X]/(X^n+1)$. The attack is a straightforward adaptation from the above attack against LWE schemes. It targets a single coefficient of $m$ and applies the same method as before. The other attack↗ presented by the CryptoLab team uses a similar approach to build an attack against RLWE. As shown by the following figure taken from the paper, the noise is amplified until the message decryption is changed.

When the error is too high, the result may be wrong, which allows to recover the error value with similar methods as presented before for LWE.

Practical Results

Some practical FHEs have been built upon RLWE. Among them, there are the Brakerski/Fan-Vercauteren↗ (BFV), the Brakerski, Gentry, and Vaikuntanathan↗ (BGV), and the fast fully homomorphic encryption over the torus↗ (TFHE) cryptosystems. They differ in the choice of plaintext and ciphertext encodings and in the way of performing the function evaluation.

Results for BFV

The authors of the first attack claimed to have successfully attacked the BFV cryptosystem implementation of the SEAL, the OpenFHE↗, and the Lattigo↗ libraries with security parameters between 217 bits to 256 bits. Those attacks are reported to take from few minutes up to a couple of hours on a standard machine to fully recover the key. The second paper’s attack was also applied to the BFV implementation of OpenFHE successfully, and the proof-of-concept implementation is provided by the authors in their GitHub repository↗. It allows to easily test the attack against the library.

Results for BGV

The first paper also reports a successful attack against the BGV cryptosystem implementations of SEAL and OpenFHE with similar results as for BFV. The authors also tried to attack HElib↗ with the same idea, but it does not apply. HElib implemented a noise-level–monitoring countermeasure forbidding the decryption of ciphertext with a high level of noise.

Results for TFHE

Finally, both attacks targeted TFHE. In the first paper, the authors applied the attack against TFHElib↗, which allows adding ciphertexts without bootstrapping, and it appeared to be successful in less than one second.

We have copied here the results table from the CEA paper to give a quick overview of the attack requirements for each scheme:

This shows that the attacks are really practical for common security parameters. It also shows that giving access to the decryption of the ciphertext of an FHE leads to key-recovery attacks, which are very practical.

TFHE-rs Proof of Concept

The second paper targeted TFHE-rs↗, the Rust library developed by Zama. The attack here is a bit different because the library performs gate bootstrapping to reduce the noise after each operation. A decryption failure is exploited only after two AND evaluations. In the case of a decryption failure, the error term returned has a statistical distribution that is correlated to the values of the key bits and thus can be recovered. The second paper’s authors also provide an implementation of the attack against TFHE-rs version 0.5.4.

The main part of the code used for the attack is the following:

// --- Evaluation oracle ---
// Homomorphic evaluations
// Obtaining ciphertexts with error after bootstrapping
let ct_bts: Vec<_> = ct_arr.par_iter().map(|x| server_key.and(x, x)).collect();

// Apply Gate AND on the same ciphertext
let ct_out: Vec<_> = ct_bts.par_iter().map(|x| server_key.and(x, x)).collect();

// --- Decryption oracle ---
let res: Vec<_> = ct_out.par_iter().map(|x| client_key.decrypt(x)).collect();

// Outputting ciphertext coefficients of failed ciphertexts
for r in 0..ARRAY_SIZE {
    if res[r] == false {
        nb_failures += 1;
        let ct = &ct_bts[r];
        match ct {
            Ciphertext::Trivial(_b) => { println!("triv;");},
            Ciphertext::Encrypted(lwe_ciphertext) => {
                let (mask, body) = lwe_ciphertext.get_mask_and_body();
                println!("Mask {:#?}", mask);
                println!("body {:#?}", body);
            }
        }
    }
}

The idea is to apply twice the AND evaluations on a ciphertext and collect the decryption failures when they happen. The attack implementation uses a nondefault parameter still targeting a 128-bit security level. In our repository, in the tfhe folder, we have created a copy of the original-paper implementation with minor modifications simplifying the decryption-failure collection. The collection phase can by run with the command

cargo run --release > ../failures.out

The full collection of the failures takes less than four hours and a standard laptop to recover almost 20,000 decryption failures. Then, a Python script main.py is used to perform the statistics on recovering the secret key bits. The script mainplot.py displays the results:

It plots the number of recovered key coefficients in terms of the number of decryption failures obtained. For the parameters chosen before, the full 600 key coefficients are recovered after obtaining about 20,000 decryption failures. This demonstrates the practicality of the attack for this choice of parameters. For the default parameters, the authors explain that the attack would take take more than 300 years. Therefore, in this case, it may be less critical but still something to be concerned about depending on the power available to the attacker.

Impact Regarding Threshold FHE

On top of FHE, a threshold decryption scheme can be constructed. Threshold decryption means that among $n$ users, a ciphertext would be able to be decrypted only if at least $t$ users collaborate together following steps of a protocol resulting in the decryption of the ciphertext. However, a subset of less than $t$ users is not able to decrypt the ciphertext. For example, Zama’s fhEVM↗ uses a set of validators that own secret shares, and when $t$ validator among $n$ agree to decrypt data, they run together the threshold decryption to obtain the data in clear. But the secret decryption key is never accessed by any of the validators. Without such scheme, a node could decide alone to break the smart contract confidentiality by decrypting the data.

In the threshold decryption setup, the ciphertext is decrypted with the decryption secret key that that is unknown to all users. At the end of the collaborative decryption protocol, each user is granted access to the decryption result. In this scenario, the previous attacks described may be applicable to recover the global secret key. Even if the number of decryptions needed to apply the previous attack is huge, they may be a threat in such configuration, and some countermeasures need to be implemented. The CEA paper shows how an attack requiring a large number of decryptions could be applied to the Lattigo implementation and what the mitigation strategies could be. The CryptoLab paper discusses a possible attack against a threshold encryption↗ built upon TFHE. Those attacks need to be taken into account when such schemes are deployed in practice.

Conclusion

This post reviewed the generic concepts used for FHE construction and the main security models. We have also seen that security models for FHE are not yet fully understood. Even if modern FHEs are proven to be IND-CPA, giving access to decryptions to an adversary could lead to disaster as shown by recent attacks targeting the IND-CPA^D security model. Those attacks apply to most of the widely available implementations.

Following a simple toy implementation in Sage, we have shown the inner workings of those attacks. The full implementation for this post’s examples are available on GitHub↗. We hope this helped to understand the risk of disclosing FHE decryptions and to improve the security of such schemes in practice. The field of FHE is moving fast, and we expect new developments around its security to come.

About Us

Zellic specializes in securing emerging technologies. Our security researchers have uncovered vulnerabilities in the most valuable targets, from Fortune 500s to DeFi giants.

Developers, founders, and investors trust our security assessments to ship quickly, confidently, and without critical vulnerabilities. With our background in real-world offensive security research, we find what others miss.

‍Contact us↗ for an audit that’s better than the rest. Real audits, not rubber stamps.