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:
- Direct calculation of the square (easy to compute but cannot be applied to ciphertext)
- 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:
-
In cell A10, type 0.00.
-
In cell A11, type 0.01.
-
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.
-
In cell B10, type
=A10^2. -
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!