This note is an english version of the note
https://qiita.com/dkawabe/private/06195c94c434106f8cc5
Self-Introduction
The author of this note works at a startup company specializing in secure computation. At the same time, I am also a beginner who only started learning about cryptography last year. I wrote this note as part of my studies. If you spot any errors, from typos and misspellings to technical details in cryptography theory, I would be grateful for your feedback.
Note Overview
This note is the first of a two-part series (Part 1: Theory, Part 2: Practice—Hands-On). The goal of the series is to provide a key-point explanation of TFHE using Excel.
What Is TFHE?
TFHE is a type of cryptosystem (a fully homomorphic encryption over the torus). Although it may seem sudden, the following Question A is quite useful for understanding TFHE. (Question A was suggested by @0917laplace, and the idea to use Excel was suggested by @daikumatan):
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)*?”
Question A is simple, but its answer is complicated.
Therefore, in this series, to understand the answer to Question A, we will consider a simpler Question B:
Question B
“In TFHE, how do we compute m^2 from a plaintext m?”
For example, if a plaintext is m = 0.3, then we can calculate m^2 = 0.09 directly. However, this direct calculation approach cannot be applied to computing Enc(m^2) from Enc(m) in the encrypted state, because without decrypting Enc(m), we do not know the value of m.
In this series, I will explain a method of computing m^2 from m (in the plaintext domain) that can be applied to computing Enc(m^2) from Enc(m) (in the encrypted domain).
- Part 1: Theory uses mathematics at roughly high school level to explain.
- Part 2: Practice uses Excel in a hands-on demonstration.
I hope this series will help deepen your understanding of TFHE.
A Note on Future Hands-On Sessions
There is also a follow-up to this Excel-based series, titled
“Using Excel to compute Enc(m^2) from Enc(m) in the encrypted domain”, which will be featured at our company’s second cryptography study session—planned, at least.
https://connpass.com/event/341101/
You are welcome to join us.
Once again, I am not an expert in TFHE cryptography; therefore, peoples who wish to understand it rigorously should refer to the original or survey papers.
Note Roadmap
Let us begin Part 1 of this series. Here is the flow of this note:
- Basics of Cryptography (plaintext, ciphertext, encryption, decryption)
- Homomorphic Encryption (HE) and Fully Homomorphic Encryption (FHE)
- Key Points of TFHE
- TFHE’s Calculation Approach
Section 4 is the most important (it answers Question B).
You can read and understand Section 4 even without reading Sections 1–3.
Although this series deals solely with plaintext calculations, Sections 1–3 will cover general ideas in cryptography so that you can better understand the features of TFHE.
1. Basics of Cryptography
We will keep the explanations to the bare minimum.
“Cryptography is a mechanism by which an information (plaintext) is transformed using special information (key) into something that others cannot easily read (ciphertext), and then the original information (plaintext) can be recovered by using special information (secret key).”
In this series, you may assume that the set of possible plaintexts and ciphertexts are real numbers or subsets of real numbers. Also:
- Encryption: plaintext → ciphertext
- Decryption: ciphertext → plaintext
While encryption and decryption involve keys, we will omit any description of the keys in this series, as our goal is to answer Question B. (For similar reasons, we also omit encode/decode, LWE cryptography, RLWE cryptography, RGSW cryptography, etc.)
2. Homomorphic Encryption (HE) and Fully Homomorphic Encryption (FHE)
2.1. Homomorphic Encryption
Let Enc be a cryptosystem. In other words, for a plaintext m, Enc(m) denotes the corresponding ciphertext.
-
Additively Homomorphic Encryption
For all plaintexts m, n:
Enc(m) + Enc(n) = Enc(m + n). -
Multiplicatively Homomorphic Encryption
For all plaintexts m, n:
Enc(m) × Enc(n) = Enc(m × n).
2.2. Fully Homomorphic Encryption (FHE)
Let Enc be a cryptosystem.
Enc is called a Fully Homomorphic Encryption scheme if it satisfies the following two conditions:
- Enc is both additively and multiplicatively homomorphic.
- You can perform addition and multiplication on ciphertexts arbitrarily many times.
3. Key Points of TFHE
3.1. Literal Translation of TFHE
According to the original paper (e.g., TFHE: Fast Fully Homomorphic Encryption Over the Torus, Journal of Cryptology, (2020) 33:34–91) TFHE means a fully homomorphic encryption over the torus.
Following this, we begin by explaining the definition of “torus.” From my personal perspective, the torus is more of a means than a goal. In other words, understanding “how the torus is used to achieve the objective (Section 3.3(2) below)” is more important than merely grasping “the definition of the torus.”
3.2. Definition of the Torus
“The torus T is the set of real numbers from 0 (inclusive) to 1 (exclusive),
where the integer part is ignored (i.e., adding or subtracting 1 is disregarded).”
Strictly speaking, the torus is the quotient module R/Z of the set of real numbers R by the set of integers Z. We denote the torus by T. For instance, in T:
0.1 = 1.1 = 2.1 = 3.1 = ... (since we ignore adding 1 in T).
Moreover, in T, addition, subtraction, and scalar multiplication are defined as follows:
0.3 + 0.8 = 1.1 = 0.1 (since we ignore adding 1 in T),
0.3 - 0.7 = -0.4 = -0.4 + 1 = 0.6 (since we ignore adding 1 in T),
3 $\cdot$ 0.4 = 0.4 + 0.4 + 0.4 = 1.2 = 0.2 (since we ignore adding -1 in T).
In T, at least in the manner described above, you cannot define multiplication or division. Please consider the reason. This concludes our basic explanation of the torus.
3.3. Properties of TFHE
Let Enc be the TFHE cryptosystem. Then Enc satisfies:
- Enc is a fully homomorphic encryption system.
- Let f: T → T be an arbitrary single-variable function (it could be multiplication by n, raising to the n-th power, a single-variable polynomial, an absolute value function, sine function, or anything else!). If m is a plaintext (where m and f(m) are in T), then you can compute Enc(f(m)) only if Enc(m) is given (i.e., without decrypting).
Point (2) is the defining feature of TFHE.
The following sections offers key-point explanations.
For simplicity, we focus on the case f(x) = x^2. Among functions that require the so-called PBS (Programmable Bootstrapping), squaring is the simplest. In contrast, for simpler operations like scalar multiplication (e.g., f(x) = 2x), PBS is not needed (as seen in Section 2.1).
4. TFHE’s Calculation Approach
4.1. Programmable Bootstrapping
Let us restate Questions A and B from the beginning:
Question A
In TFHE, how do we compute Enc(m^2) only if Enc(m) is given (i.e., without decrypting)?”
Question B
“In TFHE, how do we compute m^2 from a plaintext m?”
Both Question A and Question B share the same answer:
They are computed via an operation called Programmable Bootstrapping (PBS).
In more detail, PBS is the combined operation of the following four steps (performed from right to left):
Programmable Bootstrap
= (Key Switch) $\circ$ (Sample Extract) $\circ$ (Blind Rotate) $\circ$ (Rescale).
The most important part of PBS is Blind Rotation. In this series, to understand “how to compute Enc(m^2) from Enc(m) using PBS,” we will explain “how to compute m^2 from m using PBS” in plaintext.
Of course, if m = 0.3, you can get m^2 = 0.09 directly; however, this direct computation method cannot be applied to computing Enc(m^2) from Enc(m). Below, we illustrate the plaintext-based method for computing m^2 that can be extended to ciphertext-based computation Enc(m^2).
4.2. Computing m^2 from m Using PBS (A Toy Model)
Let us assume our plaintext space is limited to the 100 values: 0.00, 0.01, 0.02, …, 0.99.
Step 1. Create Lookup Tables
Before inputting a specific plaintext m, prepare a table listing (m, m^2) for all possible plaintext values. This table is called the lookup table:
| i | m | m^2 |
|---|---|---|
| 1 | 0.00 | 0.0000 |
| 2 | 0.01 | 0.0001 |
| 3 | 0.02 | 0.0004 |
| 4 | 0.03 | 0.0009 |
| … | … | … |
| 30 | 0.30 | 0.0900 |
| 31 | 0.31 | 0.0961 |
| 32 | 0.32 | 0.1024 |
| … | … | … |
| 100 | 0.99 | 0.9801 |
Step 2. Input a Plaintext
Input a plaintext m into PBS. Here, suppose m = 0.31.
Step 3. Determine the Index
In the second column of the table, find the row matching your input m.
The value in the first column of that row is the index i.
For m = 0.31, that index is i = 31.
Step 4. Rotate
Using the index i determined in Step 3, you create a fourth column by shifting (or “rotating”) each value in the third column up by i rows.
Performing this step on ciphertext is called Blind Rotation.
For example, for m = 0.31, i = 31. Rotation proceeds as follows:
| i | m | m^2 | Rotate (shifted up by 31) |
|---|---|---|---|
| 1 | 0.00 | 0.0000 | 0.0961 |
| 2 | 0.01 | 0.0001 | 0.1021 |
| 3 | 0.02 | 0.0004 | … |
| 4 | 0.03 | 0.0009 | |
| … | … | … | … |
| 30 | 0.30 | 0.0900 | |
| 31 | 0.31 | 0.0961 | |
| 32 | 0.32 | 0.1024 | … |
| … | … | … | … |
| 100 | 0.99 | 0.9801 | 0.0900 |
(The table above is a conceptual illustration showing how the third column’s values are rotated so the row with index i moves up to the row with index 1, etc.)
Step 5. Sample Extract
Take the value at row i = 1 of the newly created fourth column (this corresponds to Sample Extract).
For m = 0.31, the value in that row is 0.0961. This becomes the output of PBS.
Putting it all together, if you input 0.31 into PBS, the output is 0.0961. Indeed, (0.31)^2 = 0.0961. The same applies to other values as well. Although the procedure is a bit cumbersome, we can see that PBS effectively functions as a squaring operation.
That concludes this key-point explanation (using math) of how to compute m^2 from m with PBS. This also marks the end of Part 1 (Theory) of this series. Thank you for reading!
Closing and Next Steps
In Part 2 (Practice), we will offer a hands-on demonstration of all the above steps using Excel.