# Sample Extraction (Need to review) In TFHE bootstrapping, we often end up with a **GLWE ciphertext** (it encrypts a *polynomial* message), but what we ultimately want is an **LWE ciphertext** (it encrypts a *single value*). **Sample extraction** is the bridge: > It takes a GLWE encryption of a polynomial $$M(X)$$ and outputs an LWE encryption of **one chosen coefficient** $$m\_h$$ of that polynomial. *** ## 1) What sample extraction does Given: * a GLWE ciphertext encrypting $$M(X)=\sum\_{j=0}^{N-1} m\_j X^j$$ Sample extraction produces: * an LWE ciphertext encrypting $$m\_h$$ for some $$0 \le h < N$$. And importantly: > **It does not increase the noise** it mostly consists of “copy-pasting” coefficients from the GLWE into the LWE. *** ## 2) The input: A GLWE ciphertext encrypting a polynomial Lets starts with a standard GLWE encryption of $$M$$ under secret key $$\vec S=(S\_0,\dots,S\_{k-1})$$: $$C=(A\_0,\ldots,A\_{k-1},B)\in GLWE\_{\vec S,\sigma}(\Delta M)\subseteq \mathcal{R}\_q^{k+1}$$ where: $$B=\sum\_{i=0}^{k-1} A\_i\cdot S\_i + \Delta M + E$$ and $$E$$ is the (polynomial) noise. Here: * $$A\_i, B$$ are **polynomials** with $$N$$ coefficients * $$M$$ is also a polynomial with coefficients $$(m\_0,\dots,m\_{N-1})$$ *** ## 3) The goal: extract the $$h$$-th coefficient $$m\_h$$ We want an LWE ciphertext that decrypts to (roughly): $$\Delta m\_h + e\_h$$ so that after rescaling/rounding we recover $$m\_h$$. The result LWE dimension becomes: $$n = kN$$ because we “flatten” the $$k$$ polynomials (each with $$N$$ coefficients) into one long LWE vector. *** ## 4) The extracted secret key (this is the key idea) Sample extraction produces an LWE ciphertext under a derived secret key $$\vec s$$ made by concatenating the coefficients of the GLWE secret polynomials: $$\vec{s} = (s\_{0,0}, \ldots, s\_{0,N-1}, \ldots, s\_{k-1,0}, \ldots, s\_{k-1,N-1}) \in \mathbb{Z}^{kN}$$ A GLWE secret key is “$$k$$ polynomials.” An LWE secret key is “one long vector.” So we just line up the polynomial coefficients into a long vector. *** ## 5) The “copy-paste rule” (how to build the LWE ciphertext) We want to extract coefficient $$h$$. The output LWE ciphertext is: $$c=(a\_0,\ldots,a\_{n-1},b)\in\mathbb{Z}\_q^{n+1}$$ and it is built from the GLWE coefficients like this: $$ \begin{cases} a\_{N\cdot i + j} \leftarrow a\_{i,h-j} &\text{for } 0 \leq i < k,\ 0 \leq j \leq h \\ a\_{N\cdot i + j} \leftarrow - a\_{i,h-j+N} &\text{for } 0 \leq i < k,\ h+1 \leq j < N \\ b \leftarrow b\_h & \end{cases} $$ Where: * $$a\_{i,t}$$ means “the $$t$$-th coefficient of polynomial $$A\_i$$” * $$b\_h$$ means “the $$h$$-th coefficient of polynomial $$B$$” ### Why the minus sign appears Because arithmetic is done modulo $$X^N+1$$, we have the **negacyclic property** (e.g., $$X^N \equiv -1$$). When indices “wrap around,” signs flip. *** ## 6) Why this works > Look at the **first step of GLWE/RLWE decryption**, and notice that each coefficient of $$B - A\cdot S$$ is a linear combination of the coefficients of $$A$$, with signs and rotations. That linear combination is exactly what an LWE decryption computes. So sample extraction is basically: * take the coefficient equation you care about (the $$h$$-th one), * rewrite it as a dot product, * and that dot product becomes the LWE structure. *** ## 7) Toy example (RLWE case: $$k=1$$, $$N=4$$) To make the rule feel natural, we uses RLWE ($$k=1$$) with $$N=4$$. Ciphertext: $$C=(A,B)\in RLWE\_{\vec S,\sigma}(\Delta M)$$ with $$A=a\_0+a\_1X+a\_2X^2+a\_3X^3,\quad S=s\_0+s\_1X+s\_2X^2+s\_3X^3,\quad B=b\_0+b\_1X+b\_2X^2+b\_3X^3$$ Since we work mod $$X^4+1$$, the coefficients of: $$B - A\cdot S$$ become (grouped by constant / $$X$$ / $$X^2$$ / $$X^3$$) a set of linear expressions in $$(a\_0,a\_1,a\_2,a\_3)$$ and $$(s\_0,s\_1,s\_2,s\_3)$$. From that observation, it shows you can directly build LWE ciphertexts encrypting each coefficient $$m\_0,m\_1,m\_2,m\_3$$ under the extracted secret $$(s\_0,s\_1,s\_2,s\_3)$$: $$ \begin{cases} (a\_0,\ -a\_3,\ -a\_2,\ -a\_1,\ b\_0) \in LWE\_{\vec s,\sigma}(\Delta m\_0) \\ (a\_1,\ a\_0,\ -a\_3,\ -a\_2,\ b\_1) \in LWE\_{\vec s,\sigma}(\Delta m\_1) \\ (a\_2,\ a\_1,\ a\_0,\ -a\_3,\ b\_2) \in LWE\_{\vec s,\sigma}(\Delta m\_2) \\ (a\_3,\ a\_2,\ a\_1,\ a\_0,\ b\_3) \in LWE\_{\vec s,\sigma}(\Delta m\_3) \end{cases} $$ **What to notice:** * Each output uses the same $$b\_h$$ you want to extract. * The $$a$$-vector is just a rotated (+ sign-flipped) version of $$(a\_0,a\_1,a\_2,a\_3)$$. * Those sign flips come from the negacyclic wraparound. *** ## 8) Where sample extraction appears in TFHE bootstrapping After blind rotation, TFHE gets a **GLWE encryption of a rotated LUT polynomial**. The constant coefficient of that polynomial is (by construction) the value we want. So the *last step* is: > **sample extraction** to extract that constant coefficient into an LWE ciphertext. That’s why sample extraction is listed as one of the three final building blocks of programmable bootstrapping (along with modulus switching and blind rotation). *** ## 9) ELI5 summary * A GLWE encrypts a whole list of numbers (a polynomial’s coefficients). * Sometimes you only want **one number** from that list. * Sample extraction “unwraps” the GLWE into an LWE that encrypts exactly that one coefficient. * It’s mostly rearranging/copying coefficients (with a few minus signs because of wraparound), so it doesn’t add extra noise. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://sabanaku77.gitbook.io/fhe-handbook-for-beginners/sample-extraction-need-to-review.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.