# FHE Attacks

## Obtain error term by repeated squaring

Intuitively it works by repeatedly doubling the zero LWE (or RLWE) ciphertext for $k$ times where $k \approx \log{\Delta}$ such that one obtains the error term $e$ in fresh zero LWE ciphertext in the plaintext space of resulting ciphertext.

If the decryption oracle does not reject decryption request of resulting ciphertext based on exact/heuristic estimation of noise growth, it will return the attacker error $e$ in original zero LWE ciphertext. Given original LWE ciphertext encrypts 0, that is it equals $(b = a \cdot s + e , a)$ the attacker can obtain a linear equation with variable $s$ as $a_0s_0 + ... + a_{n-1}s_{n-1} = b-e$. Repeating the attack $n$ times with $n$ zero LWE ciphertext, the attacker can recover the secret key.

**Countermeasure for FHEW/CGGI**
A way to counteract such attacks without having to track the noise growth in ciphertext during circuit evaluation is to bootstrap the ciphertext before sending it back to the user (or, in case of decryption oracle, the oracle bootstraps and then decrypts). Since noise in bootstrapped ciphertext is independent of noise in input ciphertext, the attack fails.

Check algorithm 4 of eprint 2024/127

ct_i = Enc(0) # (a, b)
k = log(\Delta, 2)
for j in range(0, k):
	ct_i = 2 * ct_i
e_i = Dec(ct_i)
a_times_s = ct_i[1] - e
# given that we know a we can form i^th linear equation for s. Repeating for n times will gives n linear equation to solve and find s

## Exploiting bootstrapping failures in FHEW/CGGI

When we modswitch LWE ciphertext from $q$ to $2N$ where $q >> 2N$ significant error is incurred in the resulting ciphertext due to rounding errors.

$$e_0 = \lfloor \frac{b \times 2N}{q}\rceil - \frac{b \times 2N}{q} $$
$$e_i = \lfloor \frac{a_i \times 2N}{q}\rceil - \frac{a_i \times 2N}{q}$$

The error in resulting LWE ciphertext equals

$$\tilde{b} - \sum \tilde{a}*s = \frac{2N}{q} (b - \sum a_i*s) + e_0 - \sum e_i*s$$

The bootstrapping operation fails if
$$e_0 - \sum e_i * s + e > t$$
for some noise threshold $t$ and where $e = \frac{2N}{q}e_{in}$, $e_{in}$ being noise in input LWE ciphertext.

If bootstrapping fails, then the probability density function of $e_i$ differs vastly based on corresponding secret element $s_i$. And, given $e_i$ is public, it is this property we exploit to correlate $e_j$ with $s_i$ and recover $s_i$.

Check algorithm 5 of eprint 2024/127

**Countermeasure**

Keep bootstrapping failure probability as low as possible. Given that in practice bootstrapping failure is kept really low (for ex, $2^{-40}$), the paper had to change the parameters to increase the bootstrapping failure to show that attack works.

There's really low chance that the attack can be exploited because one will have to gather exponentially more resources to match exponential decrease in failure probability (for ex, reducing failure probability $2^{-40} \to 2^{-41}$ will require to attack to double their resources)

## References
1. https://eprint.iacr.org/2024/127.pdf
2. https://eprint.iacr.org/2024/116.pdf