Understanding TFHE by using Excel (part2/2 Practice-Excel Hands On-)

This note is an english version of the note
https://qiita.com/dkawabe/private/a9996bc3617347cd382a

# Self-Introduction

The author of this note works at a startup specializing in secure computation. At the same time, I am also a beginner to cryptography, having only started learning about it last year. I wrote this note as part of my studies. If you spot any errors — whether typos, omissions, or technical details of cryptographic theory — I would be very grateful for your feedback.

---

## Overview of This Note

This note is Part 2 of a two-part series (Part 1: Theory, Part 2: Practice -Excel Hands On-). The goal of the series is to explain the key points of TFHE using Excel.

**What Is TFHE?**  
TFHE is a type of cryptographic scheme (a fully homomorphic encryption scheme over the torus). Previously, we consider the following question (Question A) to be useful for understanding TFHE:

> **Question A:**  
> “Let m be a plaintext and let Enc(m) be the corresponding ciphertext. 
> In TFHE, how do we compute Enc(m^2) only if Enc(m) is given **(i.e., without decrypting)**?”

Although Question A is simple, its answer is quite complicated.  
Hence, in this series, we considered a simpler Question B to better understand the answer to Question A:

> **Question B:**  
> “In TFHE, how do we compute m^2 from a plaintext m?”

Naturally, in the plaintext domain, we can directly calculate m^2 when a plaintext is m = 0.3. However, this direct calculation approach cannot be applied to the encrypted case — i.e., to computing Enc(m^2) from Enc(m) — because without decrypting Enc(m), you do not know the value of m.

In **Part 1 Theory** of this series, we explained a plaintext method for computing m^2 from m — a method that can be applied to computing Enc(m^2) from Enc(m) in the encrypted state. Using an approach called **Programmable Bootstrapping (PBS)**, we computed m^2 in plaintext.

In **Part 2 Practice,** we provide a hands-on explanation using Excel, showing how to compute m^2 from m with PBS in the plaintext domain.  
I hope this series helps deepen your understanding of TFHE.

---

## A Note on Future Hands-On Sessions

A follow-up session, titled  
**“Using Excel to compute Enc(m^2) from Enc(m) in the encrypted domain,”**  
is *planned* for our company’s second cryptography study event. 
https://connpass.com/event/341101/
If you are interested, please join us. Again, I am *not* a specialist in TFHE cryptography, so for a rigorous understanding, please refer to the original and survey papers.

---

## Hands-On in Excel

Let us now dive into the content of this note (assuming you have read Part 1 of the series). I apologize in advance, but I recommend preparing an Excel sheet and following along in hands-on style if possible. The following text is somewhat cumbersome if you don’t input it into Excel, so I appreciate your understanding.

---

### “Excel Implementation of Computing m^2 from m in Plaintext Using PBS (Toy Model)”

**Purpose**  
We will compare two methods for computing the square:

1. **Direct calculation** of the square (easy to compute but cannot be applied to ciphertext)  
2. **PBS-based** calculation of the square (tedious to compute but can be applied to ciphertext)

Our goal here in Excel is to confirm that for an input m,  
“Result of (1)” = “Result of (2)” = m^2.

Method (1) is just your standard way of squaring a number.  
Most of the work in this Excel implementation will focus on method (2).

---

#### **Step 0. Preparing the Sheet Layout**

- In cell A1, enter **Plaintext**.  
- In cell B1, enter **Index**.  
- In cell C1, enter **Plaintext^2**.  
- In cell D1, enter **PBS**.

You will then have something like this:

|   | A      | B    | C         | D    |
|---|--------|------|-----------|------|
| 1 | Plaintext  | Index | Plaintext^2    | PBS  |
| 2 |        |      |           |      |

Later (from Step 2 onward), we will actually input values into A2, B2, C2, and D2.  
- **C2** will display the square of m via direct calculation,  
- **D2** will display the square of m via PBS.  

Our hands-on objective is to confirm **C2 = D2**.

---

#### **Step 1. Input the Lookup Tables**

- In cell A8, enter **LUT**.  
- In cell A9, enter **m**.  
- In cell B9, enter **m^2**.  
- In cell C9, enter **Rotate**.

Now you have:

|   | A     | B     | C       |
|---|-------|-------|---------|
| 8 | LUT   |       |         |
| 9 | m     | m^2   | Rotate  |
| 10|       |       |         |

Next:

1. In cell A10, type **0.00**.  
2. In cell A11, type **0.01**.  
3. Select cells A10 and A11, then drag the “fill handle” down to A109, so that column A increments by 0.01 all the way down to **0.99**.

4. In cell B10, type `=A10^2`.  
5. Copy cell B10 and paste it into B11 through B109.

As a result, your table looks like this:

|   | A     | B       | C       |
|---|-------|---------|---------|
| 8 | LUT   |         |         |
| 9 | m     | m^2     | Rotate  |
| 10| 0.00  | 0.0000  |         |
| 11| 0.01  | 0.0001  |         |
| 12| 0.02  | 0.0004  |         |
| 13| 0.03  | 0.0009  |         |
| … | …     | …       | …       |
|109| 0.99  | 0.9801  |         |

This completes our **Lookup Tables** input and concludes the setup for PBS.

---

#### **Step 2. Enter the Plaintext m**

We will choose one value of m out of the 100 possible values from 0.00 to 0.99.  
Here we let m = 0.31.  
- In cell A2, enter **0.31**.

---

#### **Step 3. Direct Calculation of m^2**

- In cell C2, enter `=A2^2`.  

This cell, **C2**, now shows the square of m by direct calculation.  
For example, if A2 is **0.31**, then **C2** outputs **0.0961**.

From here on, we will implement PBS so that **D2** eventually shows the square of m via PBS.  
Again, our aim is to confirm **C2 = D2**.

---

#### **Step 4. Enter the Index i**

- In cell B2, enter `=FLOOR(A2*100,1)`.

Now **B2** displays the “index” corresponding to the value of m (the value in A2).  
For instance, if **A2 = 0.31**, then **B2** will be **31**.

Brief explanation of the code in **B2** (feel free to skip this):  
- `FLOOR(--, 1)` returns the integer part of `--` (i.e., truncates decimals).  
- Hence, `FLOOR(A2*100, 1)` returns the integer part (without decimals) of A2 $\cdot$ 100.  
- From Part 1 of this series (or from the table above), that integer corresponds to the index for m.  

Thus, **B2** holds the index corresponding to the input m (the value in A2).

---

#### **Step 5. Implement Rotate**

#### 1. In cell **C10**, enter the following formula:

=MOD(INDEX($B$10:$B$109, MOD($B$2+(ROW()-ROW($B$10)),100)+1),1)

As a result, **C10** will display the value in row “(B2 + 10)” of **column B**.  
For example, if **B2 = 31**, **C10** will show the value in **B41**.

---
##### C10 Cell Code Explanation (Feel Free to Skip Reading)

From now on, we'll explain the code used in **Cell C10**. However, if you’re not interested in the detailed breakdown of the formula, please skip reading.


- **$B$10** refers to the absolutely referenced cell **B10** (apologies for the somewhat confusing notation).  
- **ROW(\-\-)** returns the row number of the cell containing the formula.  
  - For example, **ROW($B$10)** returns **10**.  
- **B2 + (ROW(\-\-) - ROW($B$10))**  
  - This yields: “*(Value in B2)* + *(the row number of the current cell)* - 10.”  
- **MOD(\-\-, 100)**  
  - Returns the remainder when “\-\-” is divided by 100.  
- **INDEX($B$10:$B$109, \-\- + 1)**  
  - Takes the row number “\-\- + 1” to fetch the corresponding value from the range **$B$10:$B$109**.  
  - In this **INDEX** function, row 10 is counted as the 1st entry, row 11 as the 2nd, …, and row 109 as the 100th.  
  - For example, **INDEX($B$10:$B$109, 32)** returns **B41**.  
- Putting it all together:  
  MOD(INDEX($B$10:$B$109, MOD($B$2+(ROW()-ROW($B$10)),100)+1),1)
  ultimately returns the value in column B for the row corresponding to “*(Value in B2) + (the row number of the current cell)*.”

This concludes the code explanation for **Cell C10**.

---

#### 2. copy **Cell C10** and paste it into **Cells C11 through C109**. Using the “fill copy” feature:

- **Cell C11** will output the value in column B for “*(B2 cell’s value) + 11*.”  
- **Cell C12** will output the value in column B for “*(B2 cell’s value) + 12*.”  
- And so on for the subsequent cells.

By doing this, **Column C** becomes a “rotated” version of Column B, effectively shifting each value in **Column B** upwards by an index i.

Now your table might look like this:

|   |  A    |  B      |   C       |
|---|-------|---------|-----------|
| 9 |  m    |  m^2    |  Rotate   |
|10 | 0.00  | 0.0000  |  0.0961   |
|11 | 0.01  | 0.0001  |  0.1021   |
|12 | 0.02  | 0.0004  |  …        |
|13 | 0.03  | 0.0009  |           |
|…  | …     | …       |  …        |
|40 | 0.30  | 0.0900  |           |
|41 | 0.31  | 0.0961  |           |
|42 | 0.32  | 0.1021  |  …        |
|…  | …     | …       |  …        |
|109| 0.99  | 0.9801  |  0.0900   |

---

#### **Step 6. Output m^2 via PBS**

- In cell **D2**, enter `=C10`.

From Part 1 of this series, we know that **D2** will now display the value of m^2 computed by PBS.  
For example, if **m = 0.31**, then **D2** shows **0.0961**.  
Previously, **C2** was **0.0961** from direct calculation, so we can confirm **C2 = D2 = 0.0961**.  
You can test other values of m to see that **C2 = D2 = m^2** holds.

This completes the key points of “using PBS to compute m^2 from m in plaintext” via an Excel hands-on example. Thus, **Part 2 Practice** of this series is concluded.

If you have time, consider how we might apply this plaintext-based calculation method to the computation from **Enc(m)** to **Enc(m^2)** (think about how the “index” might be defined and used in ciphertext calculations).  
Thank you very much for taking the time to read both parts of this series.

Finally, if you are not fully satisfied with this plaintext-based approach, please feel free to join our company’s second cryptography study event!