Lattice Part 7: Gadget Decomposition and Fully Homomorphic Encryption

Reading: Peikert’s wide-angle survey for the lattice backbone¹, Brakerski’s FHE survey for the leveled-to-full control argument², and the Gentry / BGV / BV / GSW / FV papers for the actual mechanism³⁴⁵⁶⁷. Beyond Parts 0-3, the only extra objects needed here are introduced locally: noisy LWE-style decryptions, structured ring or module arithmetic, gadget bases, and evaluation keys. Part 7 is where those objects become one controlled evaluation procedure.

The procedure fails at a very specific point. Addition keeps decryption inside the same noisy linear relation. Multiplication does not. It lifts the decryption equation from a linear secret-key basis to a higher-degree basis, enlarges the ciphertext object, and spends decoding margin at the same time. If FHE is to support general evaluation, it needs a control layer exactly at that break.

That control layer is gadget decomposition plus evaluation keys. Once that interface is explicit, key switching becomes a noisy basis change, relinearization becomes the special case that removes post-multiplication secret-key degree, and the leveled-versus-fully-homomorphic split becomes a question of whether the noise budget can be managed forever or only up to a fixed depth.²

Reader State After Part 0-3

This article assumes the reader knows only the first lattice layer:

• Part 0: a lattice is a discrete additive subgroup generated by a basis.
• Part 1: a basis can be usable or unusable; Gram-Schmidt lengths measure how controlled the basis is.
• Part 2: CVP and Babai explain what it means to move a target back toward a lattice or coset.
• Part 3: SIS / ISIS explain short integer witnesses for exact modular relations.

FHE adds one new operational demand. Instead of finding one short witness or decrypting one noisy relation, we want to compute on ciphertexts while keeping the decryption relation valid. So the central invariant is not just hardness:

$$ \text{ciphertext after evaluation must still decrypt under a controlled short relation.} $$

Part 7 therefore reuses Part 0-3 in a specific way. The secret key defines a decryption basis, multiplication pushes the ciphertext into a larger basis, and gadget/key-switching machinery acts like a controlled basis change back to the original form.

Notation For The FHE Layer

The simplified ciphertext convention in this note is:

• $q$ is the ciphertext modulus.
• $t$ is the plaintext modulus.
• $\Delta\approx q/t$ is the plaintext scaling factor.
• $\mathbf{s}$ is the secret key or coefficient vector of a ring/module secret.
• $c=(c_0,\mathbf{c}_1)$ decrypts by evaluating a noisy linear form in $\mathbf{s}$.
• $e$ is the effective error or noise term.
• $B$ is a gadget radix, unrelated to a lattice basis matrix unless explicitly stated.

The minimal correctness template is:

$$ c_0+\langle\mathbf{c}_1,\mathbf{s}\rangle=\Delta m+e\pmod q. $$

The IACR-style discipline for the rest of the article is to track three objects separately: ciphertext shape, secret-key basis, and noise size. Confusing these three is the fastest way to misunderstand FHE.

Why Homomorphic Evaluation Needs A Control Layer

What Addition Preserves

Start from the LWE-style decryption relation. Matrix, ring, and module variants package it differently, but the invariant has the same shape:

$$ \mu = c_0 + \langle \mathbf{c}_1,\mathbf{s}\rangle \pmod q, $$

where the decrypted representative is of the form

$$ \mu = \Delta m + e, \qquad m \in \mathbb{Z}_t, \qquad \Delta \approx q/t, $$

and correctness requires the effective error $e$ to stay inside the decoding interval, e.g. $|e| < \Delta/2$ in the scalar picture or the analogous norm bound in the vector or ring picture.²⁷

So a ciphertext has the linear secret-key form

$$ c=(c_0,\mathbf{c}_1) \in \mathbb{Z}_q \times \mathbb{Z}_q^n. $$

If

$$ \begin{aligned} \mu_i = c_{0,i} + \langle \mathbf{c}_{1,i},\mathbf{s}\rangle &= \Delta m_i + e_i \qquad (i=1,2). \end{aligned} $$

then homomorphic addition stays inside the same template:

$$ \begin{aligned} \mu_1+\mu_2 &= (c_{0,1}+c_{0,2})+\langle \mathbf{c}_{1,1}+\mathbf{c}_{1,2},\mathbf{s}\rangle \\ &= \Delta(m_1+m_2)+(e_1+e_2). \end{aligned} $$

Nothing structural changes.

• The ciphertext is still linear in $\mathbf{s}$.
• The key space is unchanged.
• The new error is just the sum of the old errors.

This is why additive homomorphism is not the hard part of lattice FHE. It lives inside the same noisy affine relation we already know from LWE and RLWE.¹

What Multiplication Breaks

Now multiply two decryptions:

$$ \mu_1\mu_2=\big(c_{0,1}+\langle \mathbf{c}_{1,1},\mathbf{s}\rangle\big)\big(c_{0,2}+\langle \mathbf{c}_{1,2},\mathbf{s}\rangle\big). $$

Expanding gives

$$ \begin{aligned} \mu_1\mu_2 &= c_{0,1}c_{0,2} \\ &\quad + c_{0,1}\langle \mathbf{c}_{1,2},\mathbf{s}\rangle \\ &\quad + c_{0,2}\langle \mathbf{c}_{1,1},\mathbf{s}\rangle \\ &\quad + \langle \mathbf{c}_{1,1},\mathbf{s}\rangle \langle \mathbf{c}_{1,2},\mathbf{s}\rangle. \end{aligned} $$

The last term is the failure point. It is quadratic in the secret key. Writing the post-multiplication ciphertext as

$$ d=(d_0,\mathbf{d}_1,D_2), $$

decryption has the shape

$$ d_0 + \langle \mathbf{d}_1,\mathbf{s}\rangle + \mathbf{s}^\top D_2 \mathbf{s}. $$

The ciphertext is no longer attached to the linear basis

$$ \mathcal{B}_1(\mathbf{s})=\{1,s_1,\ldots,s_n\}, $$

but to the degree-2 basis

$$ \mathcal{B}_{\le 2}(\mathbf{s})=\{1,s_1,\ldots,s_n,s_is_j:1\le i\le j\le n\}. $$

After multiplicative depth $L$, the naive basis becomes

$$ \begin{aligned} \mathcal{B}_{\le L}(\mathbf{s}) &= \left\{ \prod_{k=1}^n s_k^{\alpha_k} : \sum_{k=1}^n \alpha_k \le L \right\}. \end{aligned} $$

whose size is

$$ \left|\mathcal{B}_{\le L}(\mathbf{s})\right|=\binom{n+L}{L}. $$

That combinatorial growth is the algebraic core of ciphertext blow-up. “Ciphertext shape” is not just byte length. It is the degree of the secret-key basis required for decryption.

Ciphertext Shape Is A Secret-Key Basis Problem

In the scalar toy model, a fresh ciphertext decrypts against the basis

$$ (1,s). $$

Multiplication sends it to

$$ (1,s)\otimes(1,s)=(1,s,s,s^2), $$

which merges to

$$ (1,s,s^2). $$

The operational question is therefore:

Can we map a ciphertext expressed against a higher-degree secret-key basis back into the standard linear basis, while controlling the extra noise introduced by that map?

That is the real content of relinearization. It is not “compress the ciphertext because it got longer.” It is “compress the secret-key basis because multiplication moved us into the wrong coordinate system.”

Noise growth arrives at the same moment. If

$$ \mu_i = \Delta m_i + e_i, $$

then raw multiplication gives

$$ \begin{aligned} \mu_1\mu_2 &= \Delta^2 m_1m_2 \\ &\quad + \Delta(m_1e_2+m_2e_1) \\ &\quad + e_1e_2. \end{aligned} $$

So multiplication consumes two budgets simultaneously:

• a basis budget, because the decryption equation is now higher degree in the secret key;
• a noise budget, because the error now has bilinear and quadratic terms.

If the scheme wants to return to the original plaintext scale $\Delta$ rather than stay at $\Delta^2$, an extra renormalization step is also required after multiplication. Part of the later noise accounting will come from exactly that scale-control step.

This is the exact point where FHE stops being “noisy encryption that happens to add” and becomes a controlled lattice-evaluation problem.²⁴

Gadget Decomposition As An Algebraic Interface

The Basic Gadget Identity

Fix a radix $B \ge 2$ and digit length $\ell$ such that $B^\ell > q$. Define the gadget vector

$$ \mathbf{g}=(1,B,B^2,\ldots,B^{\ell-1}) \in \mathbb{Z}_q^\ell. $$

For every $u \in \mathbb{Z}_q$, choose a digit vector

$$ \operatorname{Decomp}_B(u)=(u_0,\ldots,u_{\ell-1}) $$

with small digits $u_i$ such that

$$ \begin{aligned} u &= \langle \operatorname{Decomp}_B(u),\mathbf{g}\rangle \\ &= \sum_{i=0}^{\ell-1} u_i B^i \pmod q. \end{aligned} $$

For a vector or matrix object, the same operation is applied coefficientwise. In block form one often writes

$$ G = I_t \otimes \mathbf{g}, $$

so that

$$ \mathbf{u} = G^\top \operatorname{Decomp}_G(\mathbf{u}). $$

The key algebraic identity is not the reconstruction formula by itself, but the following companion map. For any secret-dependent term $x$,

$$ \operatorname{Pow}_B(x)=(x,Bx,B^2x,\ldots,B^{\ell-1}x). $$

Then

$$ \begin{aligned} \left\langle \operatorname{Decomp}_B(u), \operatorname{Pow}_B(x)\right\rangle &= \sum_{i=0}^{\ell-1} u_i B^i x \\ &= ux. \end{aligned} $$

This is the entire reason gadget decomposition matters. It turns a large coefficient $u$ multiplying some hard-to-handle secret expression $x$ into many small coefficients multiplying public basis weights of $x$.

The cryptographic point of $G$ is not to hide anything. It is to create a canonical public basis against which secret-dependent terms can be addressed linearly.⁶²

A Small Digit Example

Take $q=17$, $B=2$, and $u=13$. Then

$$ 13 = 1 + 0\cdot 2 + 1\cdot 2^2 + 1\cdot 2^3, $$

so

$$ \operatorname{Decomp}_2(13)=(1,0,1,1). $$

If an evaluation key contains encryptions of

$$ s^2,\ 2s^2,\ 4s^2,\ 8s^2, $$

then the digit vector $(1,0,1,1)$ lets us linearly recombine them into an encryption of

$$ 13s^2. $$

This toy example already captures the real mechanism:

1. multiplication produces a coefficient of an unwanted secret term such as $s^2$;
2. gadget decomposition rewrites that coefficient in a fixed digit basis;
3. evaluation-key entries encode the basis-weighted secret term;
4. linear recombination recovers the desired coefficient times the secret term, but under the target ciphertext format.

Nothing in that chain is folklore. It is an explicit algebraic API.

Why Small Digits Matter

If one tried to recombine evaluation-key encryptions using the original coefficient $u$ directly, the extra error from the evaluation key would be multiplied by a potentially large $u$. Gadget decomposition replaces that with many small digits.

There is still a trade-off:

• small base $B$ gives smaller digits but more of them, since $\ell=\lceil \log_B q\rceil$ grows;
• large base $B$ gives fewer digits but larger coefficients in the recombination.

So gadget design is part of noise management, not just notation design.⁷

At a rough level, if each evaluation-key component carries error of size $\eta$, then the switching or relinearization error scales like

$$ \text{digit-count} \times \text{digit-size} \times \eta, $$

up to scheme-specific constants. That is why papers that look “only about relinearization parameters” are in fact about correctness depth.⁴⁷

Why The GSW View Matters

The GSW paper made this point especially explicit by promoting the gadget basis into the native ciphertext syntax itself.⁶ Instead of thinking of the gadget as an auxiliary decomposition tool that appears after multiplication, GSW treats ciphertexts as matrix objects built to act naturally on gadget-expanded secret vectors.

The important conceptual change is this:

• in BGV or BFV-style lines, multiplication first creates a larger secret-key basis and then relinearization switches back;
• in GSW-style lines, the gadget basis is built into the ciphertext representation, so multiplication is expressed as matrix multiplication inside that basis.

The implementation details differ, but the algebraic control argument is the same. Gadget structure is the layer that makes multiplication manageable.

Key Switching And Relinearization

Key Switching As A Noisy Basis Change

Suppose a ciphertext decrypts under a source key $\mathbf{t}$:

$$ \mu = c_0 + \langle \mathbf{c},\mathbf{t}\rangle. $$

We want an equivalent ciphertext under a target key $\mathbf{s}$. For each source-key coordinate $t_j$ and gadget digit $B^i$, publish a switching-key encryption

$$ b_{i,j} + \langle \mathbf{a}_{i,j},\mathbf{s}\rangle = B^i t_j + e_{i,j}^{\mathrm{ks}}. $$

If

$$ c_j = \sum_{i=0}^{\ell-1} c_{i,j} B^i, $$

define

$$ \begin{aligned} c_0' &= c_0 + \sum_j \sum_i c_{i,j} b_{i,j},\\ \mathbf{c}' &= \sum_j \sum_i c_{i,j} \mathbf{a}_{i,j}. \end{aligned} $$

Then

$$ \begin{aligned} c_0' + \langle \mathbf{c}',\mathbf{s}\rangle &= c_0 + \sum_{j,i} c_{i,j}\big(b_{i,j}+\langle \mathbf{a}_{i,j},\mathbf{s}\rangle\big) \\ &= c_0 + \sum_{j,i} c_{i,j}\big(B^i t_j + e_{i,j}^{\mathrm{ks}}\big) \\ &= c_0 + \sum_j c_j t_j + \sum_{j,i} c_{i,j} e_{i,j}^{\mathrm{ks}} \\ &= \mu + e_{\mathrm{ks}}. \end{aligned} $$

So key switching is exactly a noisy basis change:

$$ \text{ciphertext under } \mathbf{t} \longrightarrow \text{ciphertext under } \mathbf{s}. $$

The price is the accumulated switching noise

$$ e_{\mathrm{ks}} = \sum_{j,i} c_{i,j} e_{i,j}^{\mathrm{ks}}. $$

This is why gadget decomposition and key switching cannot be separated conceptually. The decomposition tells the scheme how to address the source-key coordinates through the public evaluation key.²⁶

Relinearization As Post-Multiplication Key Switching

Relinearization is the special case where the source “key” is not another user’s key, but the higher-degree monomial basis introduced by multiplication.

Return to the scalar picture:

$$ \mu = c_0 + c_1 s = \Delta m + e. $$

After multiplication of two ciphertexts, decryption takes the form

$$ d_0 + d_1 s + d_2 s^2=(\Delta m_1 + e_1)(\Delta m_2 + e_2). $$

The ciphertext now lives on the secret basis $(1,s,s^2)$. Relinearization maps it back to $(1,s)$.

Let

$$ d_2 = \sum_{i=0}^{\ell-1} d_{2,i} B^i, $$

and publish evaluation-key encryptions

$$ \operatorname{evk}_i=(a_i,b_i) \quad\text{such that}\quad b_i + a_i s = B^i s^2 + e_i^{\mathrm{evk}}. $$

Define

$$ c_0' = d_0 + \sum_{i=0}^{\ell-1} d_{2,i} b_i, \qquad c_1' = d_1 + \sum_{i=0}^{\ell-1} d_{2,i} a_i. $$

Then

$$ \begin{aligned} c_0' + c_1' s &= d_0 + d_1 s + \sum_{i=0}^{\ell-1} d_{2,i}(b_i+a_i s) \\ &= d_0 + d_1 s + \sum_{i=0}^{\ell-1} d_{2,i}(B^i s^2 + e_i^{\mathrm{evk}}) \\ &= d_0 + d_1 s + d_2 s^2 + \sum_{i=0}^{\ell-1} d_{2,i} e_i^{\mathrm{evk}}. \end{aligned} $$

So the unwanted $s^2$ term has been absorbed into the standard linear ciphertext shape, at the cost of extra error

$$ e_{\mathrm{relin}}=\sum_{i=0}^{\ell-1} d_{2,i} e_i^{\mathrm{evk}}. $$

This is the derivation chain that matters:

$$ \text{multiply} \longrightarrow \text{tensor or quadratic secret basis} \longrightarrow \text{gadget decomposition of the high-degree coefficient} \longrightarrow \text{evaluation-key recombination} \longrightarrow \text{linear ciphertext again}. $$

In higher dimensions, relinearization is key switching from the degree-2 monomial vector

$$ \mathbf{t} = \mathbf{s} \otimes \mathbf{s} $$

back to the linear secret vector $\mathbf{s}$. The algebra is the same, only the indexing gets larger.⁴²

Local invariant: relinearization removes secret-key degree. It does not remove the accumulated error that got us there.

The Ring-LWE Compression Of The Same Story

Ring-LWE and Module-LWE variants move the same relation into quotient rings or module vectors. The same control argument survives there with better packing.

Let

$$ R_q = \mathbb{Z}_q[x]/(f(x)), \qquad c=(c_0(x),c_1(x)) \in R_q^2, $$

and decryption relation

$$ c_0(x) + c_1(x)s(x) = \Delta m(x) + e(x) \pmod q. $$

After multiplication we obtain

$$ d=(d_0(x),d_1(x),d_2(x)) \in R_q^3 $$

with

$$ d_0(x) + d_1(x)s(x) + d_2(x)s(x)^2. $$

Relinearization again publishes encryptions of basis-weighted $s(x)^2$ terms under the original key. In coefficient form, one decomposes $d_2(x)$ coefficientwise into gadget digits and linearly recombines evaluation-key encryptions of

$$ B^i s(x)^2 $$

or the appropriate ring-basis variants.⁵⁷

This is where structured arithmetic and FHE control meet directly:

• ring or module structure makes multiplication regular;
• relinearization explains how that multiplication is brought back into a fixed ciphertext shape afterward.

NTT-friendly ring or module arithmetic is what makes these relinearization or switching recombinations cheap enough to matter in practice. The control layer is still algebraic, but the structured-lattice substrate is what keeps it from collapsing under its own size.

The ring does not eliminate the control problem. It makes the control problem compressible enough to be practical.

Noise Management And Leveled FHE

Noise Is The True Resource

Every lattice FHE scheme has a correctness condition of the form

$$ \lVert e\rVert < \text{decoding-threshold}(q,\Delta,t,\ldots). $$

The notation changes across BGV, BV, FV, and later descendants, but the invariant is the same: the effective error must remain small enough relative to the modulus and scale for decryption or rounding to recover the plaintext.²⁷

For the scaled relation

$$ \mu = \Delta m + e, $$

the rough error transformations are:

$$ e_{\mathrm{add}} = e_1 + e_2, $$

and, after multiplication plus the scheme’s renormalization step,

$$ \begin{aligned} e_{\mathrm{mul}} &\approx m_1 e_2 + m_2 e_1 + \frac{e_1 e_2}{\Delta} + e_{\mathrm{scale}} + e_{\mathrm{relin}}, \end{aligned} $$

where $e_{\mathrm{scale}}$ is the extra rounding or rescaling error needed to bring the plaintext scale back into the expected range.

This formula should not be read as a universal bound with perfect constants. It should be read as the structural reason multiplicative depth is scarce:

• message-noise cross terms appear;
• previous noise multiplies previous noise;
• the control step itself adds evaluation-key noise;
• and the scheme often needs an additional scale-management step after multiplication.

So the real resource of FHE is not just ciphertext size or runtime. It is residual decoding margin.

Shape Control Is Not Enough

A common misunderstanding is: once relinearization has restored ciphertext length, the hard part is over. That is false.

Relinearization controls the secret-key basis. It does not shrink the error that already lives in the ciphertext. In fact it increases error by injecting evaluation-key noise. This is why leveled lattice FHE needs two orthogonal control mechanisms:

1. ciphertext-shape control via key switching or relinearization;
2. noise-to-modulus control via parameter choice, scaling, and often modulus management.

The BGV line made this second axis especially explicit through modulus switching.⁴ If a ciphertext relation modulo $q_i$ is

$$ c_0 + \langle \mathbf{c}_1,\mathbf{s}\rangle = \Delta_i m + e \pmod {q_i}, $$

one can move to a smaller modulus $q_{i+1} < q_i$ by approximately scaling the ciphertext coefficients:

$$ c' = \left\lfloor \frac{q_{i+1}}{q_i} c \right\rceil \pmod {q_{i+1}}. $$

Ignoring scheme-specific bookkeeping, the new error behaves like

$$ e' \approx \frac{q_{i+1}}{q_i} e + e_{\mathrm{round}}. $$

So the absolute error is not removed by relinearization, but its relation to the active modulus can be kept under control. This is the leveled-FHE version of budget management: one spends part of a modulus chain in order to keep the effective decoding ratio viable.²

Why Leveled FHE Is Already A Major Endpoint

A leveled homomorphic scheme is not an unfinished dream. It is a family of schemes parameterized by a target multiplicative depth $L$, such that every admissible circuit of depth at most $L$ can be evaluated correctly without any refresh step.²

To make that leveled guarantee true, the designer must simultaneously close all of the following loops:

• multiplication creates a higher-degree secret basis;
• relinearization or key switching restores the standard basis;
• repeated operations keep error below the decoding threshold;
• modulus or scale management preserves enough remaining margin until depth $L$.

That is already the full algebraic problem for bounded-depth computation.

This is why the BGV and BV lines mattered so much historically.⁴⁵ They made it clear that one can get far beyond toy addition and multiplication by explicit lattice control, even before the final refresh step is inserted.

From Leveled To Fully Homomorphic

What Bootstrapping Refreshes

Fully homomorphic encryption asks for evaluation depth that is not fixed once and for all by the original leveled parameters. The quantity that must be refreshed is not the plaintext. It is the ciphertext’s residual decryption margin.

At a high level, bootstrapping transforms a ciphertext $c$ into a new ciphertext $c^\star$ of the same plaintext but with noise comparable to a fresh encryption:

$$ \operatorname{Dec}_{\mathbf{s}}(c)=m \quad\Longrightarrow\quad c^\star \approx \operatorname{Enc}_{\mathbf{s}}(m). $$

Operationally this means:

1. represent the current noisy ciphertext;
2. homomorphically evaluate the decryption procedure, or an equivalent refresh circuit, on encrypted auxiliary key material;
3. output a new ciphertext of the same message with restored slack.

Gentry’s original blueprint was exactly this observation: if a somewhat homomorphic scheme can evaluate its own decryption circuit, then it can refresh its ciphertexts and iterate forever.³

Why Bootstrapping Reuses The Same Control Layer

Bootstrapping is often described as if it were a separate phase after the “real” scheme. In lattice systems that is the wrong mental model.

To evaluate decryption homomorphically, the scheme still needs to manipulate secret-dependent linear forms, rounding or digit-extraction structure, and key material under encryption. Those are the same families of operations that already forced gadget decomposition, key switching, and noise accounting into the construction.³²

In other words:

• gadget decomposition is still how coefficients are made addressable;
• key switching is still how ciphertexts move between useful secret-key bases;
• modulus and scale management are still how correctness margin is preserved long enough for the refresh to finish.

Fully homomorphic encryption is therefore not a different species from leveled FHE. It is leveled FHE plus a refresh mechanism whose own evaluation cost fits inside the available leveled budget.

Why This Is Still A Lattice Story

Peikert’s survey is useful here because it keeps advanced constructions inside the same lattice-crypto grammar instead of treating them as disconnected exceptions.¹ The construction never stopped being:

1. public noisy linear relations hide secret structure;
2. structured rings or modules make arithmetic regular enough to execute;
3. gadget bases make higher-degree or foreign-key relations linearly addressable;
4. evaluation keys convert that addressability into ciphertext-shape control;
5. bootstrapping refreshes the remaining error margin when the leveled budget runs out.

That continuity matters. It explains why FHE belongs after the introductory lattice geometry rather than in a detached “advanced applications” bucket. FHE is an advanced consequence of the same noisy-linear and structured-lattice framework, not a separate postscript.

Conclusion

Part 7 is where lattice cryptography becomes an algebraic control theory for computation on ciphertexts.

Addition preserves the original noisy linear basis. Multiplication does not: it raises the secret-key degree, enlarges the ciphertext object, and accelerates error growth. Gadget decomposition is the public coordinate system that lets evaluation keys talk to those higher-degree terms. Key switching is the general noisy basis change. Relinearization is the special case that maps post-multiplication secret monomials back into the standard ciphertext shape. Noise management is the separate but equally essential axis that keeps those controlled ciphertexts decryptable.

Leveled FHE is the regime where these controls close for depth $L$. Fully homomorphic encryption is the regime where the remaining margin can also be refreshed. The underlying mechanism stays lattice-native from start to finish.

References

Suggested reading order:

1. Peikert first, for the lattice-wide view of noisy linear relations, gadget tools, and structured assumptions.
2. Brakerski’s survey next, for leveled FHE, modulus management, key switching, and bootstrapping as one control problem.
3. BGV/BV/FV after that, to see how the algebraic control layer becomes concrete in Ring-LWE style schemes.
4. GSW last, to see the gadget basis promoted into the ciphertext syntax itself.

• Chris Peikert. “A Decade of Lattice Cryptography.” Foundations and Trends in Theoretical Computer Science 10(4):283-424, 2016.¹
• Zvika Brakerski. “Fundamentals of Fully Homomorphic Encryption - A Survey.” ECCC TR18-125, 2018.²
• Craig Gentry. “A Fully Homomorphic Encryption Scheme.” PhD thesis, Stanford University, 2009.³
• Zvika Brakerski and Vinod Vaikuntanathan. “Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages.” CRYPTO 2011.⁵
• Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) Fully Homomorphic Encryption without Bootstrapping.” ACM Transactions on Computation Theory 6(3), 2014; conference version ITCS 2012.⁴
• Craig Gentry, Amit Sahai, and Brent Waters. “Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based.” CRYPTO 2013.⁶
• Junfeng Fan and Frederik Vercauteren. “Somewhat Practical Fully Homomorphic Encryption.” IACR ePrint 2012/144.⁷