# CMux (Controlled Multiplexer)
CMux (pronounced “see-mucks”) is the homomorphic version of a **Mux (multiplexer) gate**: it selects one of two values based on a **selector bit**. In TFHE, CMux is *the* workhorse used repeatedly inside bootstrapping (especially during blind rotation).
***
## 1) What a Mux does in the clear (unencrypted)
A Mux takes three inputs:
* selector bit: `b ∈ {0,1}`
* option 0: `d0`
* option 1: `d1`
It outputs:
* `d0` if `b = 0`
* `d1` if `b = 1`
A common “algebraic” way to write this if-else is: $$b\cdot(d\_1-d\_0)+d\_0 = d\_b$$ So when `b=0`, the output is `d0`, and when `b=1`, the output becomes `d1`.
### Tiny toy example (cleartext)
Let `d0 = 5`, `d1 = 9`.
* If `b=0`: $$0\cdot(9-5)+5 = 5$$
* If `b=1`: $$1\cdot(9-5)+5 = 9$$
That’s the exact behavior we want but **on ciphertexts**.
***
## 2) CMux inputs in TFHE (encrypted)
To evaluate that same formula homomorphically, TFHE encrypts:
* the selector bit `b` as a **GGSW ciphertext** (this is important)
* the two options `d0`, `d1` as **GLWE ciphertexts**
So CMux takes:
* $$\text{GGSW}(b)$$ (selector)
* $$\text{GLWE}(d\_0)$$ (option 0)
* $$\text{GLWE}(d\_1)$$ (option 1)
and returns:
* $$\text{GLWE}(d\_b)$$ (the selected option, still encrypted)
***
## 3) How CMux is computed (homomorphically)
Start from the clear formula: $$b\cdot(d\_1-d\_0)+d\_0$$
Now translate each operation:
1. **Subtract** the two encrypted options: $$\text{GLWE}(d\_1-d\_0) = \text{GLWE}(d\_1) - \text{GLWE}(d\_0)$$
2. **Multiply** by the encrypted bit `b`:
* In TFHE, “multiply a GLWE by an encrypted bit/constant” is done via the **external product**
* External product takes **GGSW × GLWE → GLWE**
So: $$\text{GLWE}(b\cdot(d\_1-d\_0)) = \text{GGSW}(b)\ \boxdot\ \text{GLWE}(d\_1-d\_0)$$
3. **Add back** the encrypted $$d\_0$$: $$\text{GLWE}(d\_b) = \big(\text{GGSW}(b)\ \boxdot\ (\text{GLWE}(d\_1)-\text{GLWE}(d\_0))\big) + \text{GLWE}(d\_0)$$
That’s CMux: one external product + a couple of cheap linear ops (add/sub).
***
## 4) Why the selector must be GGSW
You might wonder: why not encrypt `b` as GLWE too?
Because TFHE wants the “multiplication” part $$b \cdot (\cdot)$$ to be evaluated using the **external product**, which specifically uses a **GGSW ciphertext** as the structured “multiplier” and a **GLWE** as the multiplicand, outputting a **GLWE**. That’s exactly the building block CMux needs.
Beginner way to remember it:
* **GLWE** is a “data container”
* **GGSW** is a “data container + multiplication gadget”
* CMux needs the gadget.
***
## 5) Correctness (why it really outputs the selected ciphertext)
CMux is correct for the same reason the clear formula is correct:
* if $$b=0$$, then $$b\cdot(d\_1-d\_0)=0$$, so result is $$d\_0$$
* if $$b=1$$, then $$b\cdot(d\_1-d\_0)=d\_1-d\_0$$, so result is $$d\_1$$
Homomorphically:
* subtraction and addition on GLWE preserve the corresponding plaintext operations
* the external product evaluates the multiplication piece homomorphically So the output ciphertext decrypts to $$d\_b$$.
***
## 6) Noise / cost: what to expect
CMux’s “expensive part” is the **external product** (because it relies on decomposition + recomposition against many ciphertext components). The add/sub operations are comparatively cheap.
So CMux:
* **increases noise** (mainly due to the external product)
* is **computationally heavier** than linear ops Yet TFHE uses it constantly because it gives you a programmable, branch-like primitive under encryption.
***
## 7) Why CMux matters so much in TFHE bootstrapping
Bootstrapping in TFHE uses **blind rotation**, which repeatedly needs to apply an “if the bit is 1 then rotate, else do nothing” choice.
That choice is *exactly* a CMux:
* selector: a GGSW encryption of a bit $$\pi\_j$$
* option 0: a GLWE encryption of $$M$$ (no rotation)
* option 1: a GLWE encryption of $$M \cdot X^{-2^j}$$ (rotation by a known amount)
Then blind rotation performs a **sequence of CMux operations**, feeding the output of one CMux as the next option.
This is why CMux is often described as one of the main building blocks of TFHE bootstrapping.
***
## 8) ELI5 summary
CMux is an encrypted “**if**” statement:
* You have two encrypted choices: “take this” or “take that”
* You have an encrypted yes/no switch (a bit)
* CMux returns the encrypted choice that matches the switch
* TFHE uses it many times in a row to do bootstrapping tricks like blind rotation
---
# 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/cmux-controlled-multiplexer.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.