FHE Security for Sparse Keys

Fully Homomorphic Encryption (FHE) allows computation directly on encrypted data. The security of virtually every practical FHE scheme rests on the hardness of a lattice problem called Learning With Errors (LWE), or its ring-structured variant Ring-LWE. Choosing secure parameters requires estimating how hard the underlying problem actually is, and that estimation is non-trivial, especially when the secret key is sparse, as is common in several FHE schemes.

This article covers the key ideas: what LWE security means, how to estimate it, what sparse keys are, and why schemes use them.

The Learning With Errors problem

The LWE problem, introduced by Regev (2005), is defined as follows. Fix integers $n$ (dimension), $q$ (modulus), and a small error distribution $\chi$ (typically discrete Gaussian with standard deviation $\sigma$). The secret $\mathbf{s} \in \mathbb{Z}_q^n$ is drawn once and kept private. An adversary is given many samples

$(\mathbf{a}_i,\ b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \mod q)$

where each $\mathbf{a}_i \in \mathbb{Z}_q^n$ is uniform and $e_i \leftarrow \chi$ is a small error. The hardness assumption is that recovering $\mathbf{s}$ from these samples is computationally infeasible when $n$, $q$, and $\sigma$ are chosen appropriately.

In FHE, ciphertexts are LWE (or Ring-LWE) samples, and the scheme’s security reduces directly to LWE hardness. The three parameters $n$, $q$, $\sigma$ therefore govern the security level. Unlike most cryptographic settings where increasing a parameter always makes the scheme harder to break, the LWE parameters do not all behave the same way: increasing $n$ or $\sigma$ strengthens security, but increasing $q$ weakens it by giving the attacker “more room to work with”. The modulus $q$ needs to grow with the multiplicative depth of the computation being performed (more depth requires more “noise budget”), so in practice the binding constraint is: how large can $\log q$ be while still meeting the security target?

Ring-LWE and the ring dimension

Most practical FHE schemes (BFV, BGV, CKKS to name a few) work over the polynomial ring $\mathbb{Z}_q[X]/(X^n + 1)$ where $n$ is a power of two. This is Ring-LWE: the secret and error are polynomials, and each ciphertext encodes an entire vector of plaintext values (the SIMD “slots”), which dramatically improves throughput.

The ring dimension $n$ is the primary performance lever, but choosing it involves a balancing act. Larger $n$ increases security, which allows a larger $q$ (and therefore deeper circuits) at the same security level, but also means larger ciphertexts, slower operations, and more memory. A typical choice for 128-bit security is $n = 2^{15}$ or $n = 2^{16}$.

Estimating the security

Knowing that LWE is hard in theory does not directly tell you how many bit operations a real attack requires for specific parameters. Concrete security estimation answers this question.

The most commonly used tool for this is the lattice estimator, a SageMath library that models the cost of (most) known lattice attacks and returns the most efficient one for a given parameter set. The reported security $\lambda$ is the base-2 logarithm of the estimated number of operations needed to break the scheme: a scheme is said to have $\lambda$-bit security if the best known attack costs $2^\lambda$ operations. To get a grasp of what this concretely means, you can refer to this video from 3b1b.

The main attack families considered are:

• Primal attacks: reduce the LWE instance to a short-vector problem (SVP) in a lattice, then solve it with the BKZ algorithm.
• Dual attacks: find a short dual vector that distinguishes LWE samples from uniform.
• Hybrid attacks: combine lattice reduction with a meet-in-the-middle or exhaustive guessing phase over a portion of the secret; particularly effective when the secret is sparse or ternary.

For a given $(n, \log q, \sigma)$, the estimator runs all attack variants and returns the minimum security across them. A parameter set is considered to meet $\lambda$-bit security if this minimum is at least $\lambda$.

Sparse keys

In a standard LWE or Ring-LWE instance, the secret $\mathbf{s}$ is drawn uniformly from a ternary distribution $\{-1, 0, 1\}^n$. A sparse secret restricts this further: $\mathbf{s}$ is still ternary, but has exactly $h$ non-zero entries (Hamming weight $h \ll n$).

Several FHE schemes rely on sparse keys:

• DM / CGGI: bootstrapping speed is directly proportional to $h$, so using a small Hamming weight (e.g. $h = 64$ for $n = 2^{10}$) is a key design knob for fast gate bootstrapping.
• CKKS and BFV variants: noise growth, bootstrapping performance, and/or probability of failure can all benefit from sparser secrets.

The appeal is clear: a sparser secret means faster homomorphic operations. The cost is equally clear: a sparser secret is structurally weaker. An attacker who can guess the positions of the $h$ non-zero entries reduces the search space from $3^n$ to $\binom{n}{h} \cdot 2^h$, and hybrid attacks exploit this directly. For small $h$, this is a significant reduction of the search space.

That sparse keys weaken security is not a new observation, and there had been earlier speculation and partial results pointing in this direction. However, the precise impact on concrete security remained unclear for some time. What is now well established is that the standard LWE security estimates, which assume a dense ternary secret, are not valid for sparse keys. A dedicated estimator that accounts for the guessing phase is required.

The rotated primal-hybrid estimator

The paper On the Concrete Hardness Gap Between MLWE and LWE by Tabitha Ogilvie (2026) addresses this directly. It adapts the primal hybrid attack to exploit the ring structure of power-of-two cyclotomic rings, yielding a tighter and more accurate security estimate for sparse Ring-LWE.

The key insight is that the ring structure introduces rotations: a single non-zero coefficient in the secret generates $n$ related samples via the ring automorphisms. The rotated primal-hybrid attack accounts for these rotations in the guessing and decoding steps, which leads to a meaningful improvement in attack efficiency compared to ignoring the structure, and therefore to lower (more conservative) security estimates for the defender.

Three attack variants are modelled:

• primal-without-mitm: pure lattice reduction, no guessing phase.
• primal-mitm-square-root: hybrid attack with square-root meet-in-the-middle.
• primal-mitm-estimator: hybrid attack using the full lattice estimator model for the decoding step.

Concurrent work by Hou and Jiang: Careful with the Ring: Enhanced Hybrid Decoding Attacks against Module/Ring-LWE (2026) proposes a related enhanced hybrid decoding attack that also exploits the ring structure. Their estimates for the FHE parameter sets they consider are broadly consistent with Ogilvie’s, with Ogilvie’s estimates being slightly more conservative (i.e. slightly lower security) for the parameter ranges relevant to FHE. The two works are complementary and both worth reading for a complete picture.

Precomputed tables and the search tool

Running the lattice estimator for sparse-key parameters is expensive: a single evaluation can take from a few seconds to tens of minutes, and locating the exact largest admissible $\log q$ for a given $(n, h, \sigma, \lambda)$ requires a binary search over potentially hundreds of values.

To save this work, I have precomputed the largest admissible $\log q$ for the full grid of parameters commonly used in SIMD FHE schemes, at $\sigma = 3.2$:

• $\log n \in \{12, 13, 14, 15, 16\}$
• $h \in \{32, 64, 128, 192, 256, 512, 1024\}$
• $\lambda \in \{128, 192, 256\}$ bits

The tables are available at github.com/jdumezy/sparse-key-estimate. The 128-bit security table is the most commonly needed.

Each cell gives the largest $\log q$ for which the security estimate, under all three attack variants, is at least $\lambda$ bits. A cell containing -- means no admissible $\log q$ was found in the searched range: the parameter set does not meet the target security level at any practical modulus size.

The repository also includes the search tool itself, in case you need an estimate for parameters not covered by the grid:

git clone https://github.com/jdumezy/sparse-key-estimate
git submodule update --init --recursive PrimalHybrid/lattice_estimator
sage sparse_key_search.py -- --logn 14 --h 128 --sigma 3.2

The tool performs a streaming binary search that supports parallel Sage worker subprocesses and caches all evaluated points, so it can be interrupted and resumed without losing work.

A note on the estimates

The values in the tables are upper bounds on the security achievable by the rotated primal-hybrid attack from Ogilvie (2026). They are not unconditional security guarantees: a stronger attack could lower them. They are however based on the best published attack for sparse Ring-LWE at the time of writing, and the estimates are on the conservative side relative to the concurrent work by Hou and Jiang.

When using these tables for parameter selection, keep in mind:

• The search uses $\sigma = 3.2$, a standard choice for FHE. A different error distribution requires re-running the search.
• The tables cover the Ring-LWE setting (power-of-two cyclotomic rings). Plain LWE or Module-LWE with a different module rank are not directly covered.
• As with all lattice security estimates, improvements in lattice algorithms or new cryptanalytic techniques can change the picture. The lattice estimator is updated regularly; the tables were generated with the version available at the time of computation.

If you find an error or have a question, feel free to contact me or open a GitHub issue.