Attacks
CKKS faces three families of attacks:
- against the underlying RLWE assumption,
- against the sparse-secret-key encapsulation used during bootstrapping, and
- against the residual noise on decrypted values.
Each family informs different parameters of the deployment:
- Given the ring dimension $N$, the hardness of RLWE determines an upper bound on the largest modulus the scheme uses, $q_0 q_1 \cdots q_L \cdot p_0 p_1 \cdots p_k$ (where the $p_i$ are the auxiliary primes added during key switching), the standard deviation $\sigma$ of the error distribution added to fresh encryptions, and the Hamming weight of the main secret key.
- Sparse secret key attacks determine the minimum Hamming weight of the sparse secret used in bootstrapping encapsulation, and hence the degree of the interpolating polynomial in the bootstrap circuit.
- The analysis of information leakage from noise determines how much noise flooding must be added to partial decryptions.
RLWE attacks
Each attack below targets the following problem.
Fix the ring $R = \mathbb{Z}_q[X]/(X^N + 1)$ with $N$ a power of two. An RLWE sample is a pair $(a, b) \in R^2$ of the form $a = b\,s + e$, where $b$ is drawn uniformly at random from $R$, $e$ is an error polynomial with coefficients drawn from a discrete Gaussian of standard deviation $\sigma$, and $s \in R$ is a fixed secret polynomial. Given $m$ independent RLWE samples sharing the same secret $s$, recover $s$.
The hardness of the problem depends on the distribution of $s$. Several common choices:
- Fixed Hamming weight. Uniform over polynomials with exactly $h$ coefficients equal to $\pm 1$ and the rest zero. CKKS uses this distribution for the secret key $s$ in Section 3.2, with $h = 1024$ at $N = 65536$.
- Discrete Gaussian. Coefficients drawn independently from a discrete Gaussian of small standard deviation. CKKS uses this distribution for the encryption mask $v$ in Section 3.2, whose security argument treats $v$ as the secret of a fresh RLWE sample.
This is the search version of RLWE; the decision version, which asks to distinguish RLWE samples from uniformly random pairs in $R^2$, is the form Section 3.2's RLWE assumption uses, and the two are equivalent up to polynomial factors.
For the parameter regime CKKS cares about — $N = 2^{16}$ and $\sigma = 3.2$ — this problem is believed to provide $128$-bit security as long as $\log_2 q \le 1721$.
More generally, the maximum $\log_2 q$ that still yields $128$-bit security at each ring dimension $N$ is approximately:
| $N$ | Max $\log_2 q$ |
|---|---|
| $2^{10}$ | [TODO] |
| $2^{11}$ | [TODO] |
| $2^{12}$ | [TODO] |
| $2^{13}$ | [TODO] |
| $2^{14}$ | [TODO] |
| $2^{15}$ | [TODO] |
| $2^{16}$ | $1721$ |
| $2^{17}$ | [TODO] |
| $2^{18}$ | [TODO] |
These bounds are the largest moduli currently considered safe, and they may shrink as new attacks are discovered.
Algebraic attack
[WORK IN PROGRESS]
Recovers $s$ by treating the bounded coefficients of each error polynomial $e_i$ as roots of a polynomial of bounded degree, which yields a system of nonlinear polynomial equations in the coefficients of $s$ that can be solved by linearization.
Ramified prime attack
[WORK IN PROGRESS]
Uses a ring homomorphism to project the RLWE samples into a smaller subfield, where the noise collapses. Only effective for very small $\sigma$, so it does not apply at $\sigma = 3.2$.
Primal attack
[WORK IN PROGRESS]
Embeds the RLWE samples into a single high-dimensional lattice and uses lattice reduction to find the exceptionally short vector that encodes $s$ and the errors.
Dual attack
[WORK IN PROGRESS]
Recovers $s$ by finding short vectors in the dual of the lattice associated with the RLWE samples.
Combinatorial / BKW attack
[WORK IN PROGRESS]
Reduces the dimension of the problem by combining a large number of RLWE samples to cancel out coefficients of $s$. Mostly theoretical at the parameters above, since it requires far more samples than are usually available.
Hybrid attack
[WORK IN PROGRESS]
Interpolates between a combinatorial (BKW-style) reduction and a primal or dual lattice-reduction attack.
Sparse secret key attacks
[WORK IN PROGRESS]
Dedicated attacks against the sparse secret key used by the sparse-secret-key encapsulation in bootstrapping, which the dense secret key isn't vulnerable to, and how the parameters keep them out of reach.
Information leakage from noise
[WORK IN PROGRESS]
Specific attacks that recover information about the secret key from the residual noise on decrypted values — the failure mode that IND-CPAD security models — and how noise flooding defends against them.