Evaluating Boolean circuits over ciphertexts using Fully
Homomorphic Encryption over the Torus

Kotaro Matsuoka
Novembe/8/2022

Self Introduction• Affiliation: 2nd grade Master’s student atKyoto University• Certified as a ”super creator” at IPA’s MITOU
program 2019.
• Gave lectures about TFHE at IPA’s Security
Camp 2020-2022.
• Today’s talk based on this lecture.

• Won the NHK Robot Contest 2019.
Figure 1: One of the robots we madein NHK Robot Contest.
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

1/32

IntroductionClassification of HEs• Homomorphic Encryption (HE) = A form of encryption that permits encrypted
data to be evaluated by arbitrary functions without decryption.
• Partially Homomorphic Encryption (PHE)• Support addition OR multiplication. (ex.: RSA)

• Somewhat Homomorphic Encryption (SHE)• PHE + a scheme-dependent number of additions or multiplications. (ex.: LiftedElGamal)• Leveled Homomorphic Encryption (LHE)• PHE + a security parameter-depended number of additions or multiplications.
• Sometimes referred to as FHE. (The theoretical upper limit is not known.)• Fully Homomorphic Encryption (FHE)• Supports any operations. (ex.: TFHE)
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

2/32Lineage of HEs

Figure 2:
https://drive.google.com/file/d/1aJCfhIpAk8unQ8BKof3C3cHlVzse1qpD/view,https://nindanaoto.github.io/pdf/IMIKoen.pdf
Kotaro Matsuoka
Added red texts

3/32

What is TFHE?

• TFHE = Fully Homomorphic Encryption over the Torus• Pros:• Suitable for logic circuit evaluations. (Enable to use of existing synthesis tools.)• Fast Bootstrapping operations. (< 10ms on the latest consumer grade CPUs)• Cons:• Relatively slow for linear operations. (Vector additions and multiplications.)

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

4/32

Virtual Secure Platform (USENIX Security 2021)• One of the possible application of TFHE is evaluating a general processor.
• Since the general processor represents a program as data, we can encrypt theprogram.
• Theoretically highest tamper resistant capability.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

5/32

Inside TFHEThe overview of HomNAND

Figure 4: Block diagram of HomNAND

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

6/32

Torus(T, Circle group, 円周群)

• Def.: The group of angles. T = R mod 1 ∈ [−0.5, 0.5)
• The addition is defined but the multiplication is not.
• ex.: 0.8 + 0.6 = 1.4 ≡ 0.4 mod 1, 0.3 − 0.9 = −0.6 ≡ 0.4 mod 1• ex.: 1.2 ≡ 0.2 mod 1, 2.4 ≡ 0.4 mod 1 but, 1.2 · 2.4 = 2.88 ̸≡ 0.2 · 0.4 = 0.08 mod 1

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

7/32

TLWE

• TLWE = Torus Learning With Error• Most Post Quantum Cryptography uses Integer LWE.
• Discretizing Torus by fixed point integer gives the same implementation and security.

• Notations:• The set of Boolean: B = {0, 1} ∈ Z• Security parameters: n ∈ Z+ , α ∈ R+
• Modular Gaussian distribution: DT,α = N (0, α2 ) mod 1, Gaussian dist. over Torus.
• a ∈ Tn , e(error, noise), b ∈ T, s ← U (Bn )(Secret Key), m(plaintext) ∈ T• ←: x ← D means x itself or its entries or coefficients are drawn from D.

• TLWE ciphertext: (a, b) ∈ Tn+1
• a ← U (Tn ), e ← DT,α , s ← U (Bn ), b = a · s + m + e
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

8/32

The idea of 2-input NAND gate evaluation• Since NAND takes Boolean inputs, the plaintext of TLWE should be Boolean.
• Encode Boolean into Torus by − 81 (representing 0) and 18 (1).’• Decryption under this encoded message space uses a sign function.

• c0 , c1 : TLWE input ciphertexts. cy = (0, 18 ) − c0 − c1 : The output.
• The Torus plaintext of cy is in {− 81 , 18 , 38 }.
• Iff both ciphertexts encrypting 18 , cy = − 18 < 0.
• The decryption result of cy becomes 0, iff both inputs are 1.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

9/32

Bootstrapping• Evaluating decryption function over ciphertexts.
• Proposed by Gentry’s Ph.D thesis in 2009.
• By Bootstrapping, we can remove errors in ciphertexts.
• We can evaluate more homomorphic operations after Bootstrapping.

• All widely known FHE uses this idea.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

10/32

The idea of constructing Bootstrapping in TFHE
• TN [X]: The ring of Torus coefficient polynomials modX N + 1.
P −1 1 i• Test Vector (of the sign function): T V [X] = N
i=0 8 X ∈ TN [X]• Figure 5 shows the negacyclic behavior on TN [X].
• The constant term of X ⌈2N ·(b−a·s)⌋ · T V [X] is the plaintext of (a, b).
• Homomorphic evaluation of X ⌈2N ·(b−a·s)⌋ is the key idea.
X −3 · T V [X]1818181818− 18− 81− 18− 18− 81− 18

181818X −N · T V [X]− 18− 81− 18− 18− 18X −(3+N ) · T V [X]− 18− 81− 18− 18− 18

Figure 5: Negacyclic Rotation (N = 8)https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

11/32

The idea of homomorphic exponent evaluation (Blind Rotate)• ⌈2N · (b − a · s)⌋ ≈ ⌊2N · b⌋ −Pn−1

i=0 ⌈2N · ai ⌋ · si = ρ• Now we can evaluate rounding without s.

• Because s ∈ Bn , we can evaluate XPn−1

i=0 ⌈2N ·ai ⌋·siby multiplexers.

• Multiplying X ⌈2N ·ai ⌋·si =Select multiplying X ⌈2N ·ai ⌋ or not.
• The multiplexer can be constructed by multiplication with si .

Algorithm 1 The idea of BlindRotate
Require: (a, b): TLWE, s: the secret key of TLWE, T V [X] ∈ TN [X]
Ensure: crot: X −ρ · T V [X]
1: crot ← X −⌊2N ·cin.b⌋ · T V [X]
2: for i = 0 to n − 1 do
3://crot ← si ?X ⌈2N ·cin.ai ⌋ · crot : crot
4:crot ← ((X ⌈2N ·cin.ai ⌋ · crot) − crot) · si + crot
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

12/32

Necessary components for Bootstrapping

1The ciphertext for a Torus coefficient polynomial.
• crot in algorithm 1 must be encrypted.

2

Homomorphic multiplication between a Boolean and a polynomial.
• si have to be encrypted.

3

Homomorphic extraction of the constant term.
• What we need as a result of Bootstrapping is TLWE.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

13/32

TRLWE• TRLWE: Torus Ring Learning With Error• Security parameters: N ∈ Z+ , αbk ∈ R+
• Secret key for TRLWE: S[X] ← U (BN [X])• Plaintext: m[X] ∈ TN [X]• TRLWE ciphertext:(a[X], b[X]) ∈ (TN [X])2 , a[X] ← U (TN [X]), b[X] = a[X] · S[X] + e[X] + m[X]https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

14/32

TRGSW• TRGSW: Torus Ring Gentry-Sahai-Waters• Supports multiplication with TRLWE as a Leveled HE.
• TFHE uses this ciphertext to encrypt s.
• In general, it can encrypt an integer polynomial.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

15/32

Scaling• All ciphertexts in TFHE use Torus-based message spaces.
• We want to encode si into Torus.

• Parameter (not security related): Bg ∈ Z+• Scaling TRLWE by Bg and rounding into! integer polynomials.
si0Bg(⌈Bg · a[X]⌋, ⌈Bg · b[X]⌋)·= (ar [X], br [X])si0 Bg≈ si · (a[X], b[X])rrb [X] − a [X] · S[X] = si (b[X] − a[X] · S[X] + er [X])https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

16/32

Masking by zero ciphertexts• Adding a vector of TRLWE ciphertexts to encrypt.
• (a1 [X], b1 [X]), (a2 [X], b2 [X]) are encryption of 0.
• The result of the inner product with ciphertexts of 0 is a ciphertext of 0.
• Adding the vector introduces more errors but not changes the result plaintext.

!
a1 [X] b1 [X]+] ≈(⌈Bg · a[X]⌋, ⌈Bg · b[X]⌋) ·si0 Bg
a2 [X] b2 [X]si · (a[X], b[X]) + ⌈Bg · a[X]⌋ · (a1 [X], b1 [X]) + ⌈Bg · b[X]⌋ · (a2 [X], b2 [X])siBg

https://nindanaoto.github.io/pdf/IMIKoen.pdf

0!

Kotaro Matsuoka

17/32

Trade-off in the selection of Bg• The max coefficient value of ⌈Bg · a[X]⌋, ⌈Bg · b[X]⌋ is Bg.
• The bigger Bg means more errors in the resulting ciphertext.

• However, decreasing Bg means bigger rounding errors.
• Decomposition is the idea to avoid this trade-off.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

18/32

Decomposition• Parameter (not security related): l ∈ Z+
• Decomposition takes a TRLWE ciphertext as the input.
• Returns (āi [X], b̄i [X]) ∈ ((Z/Bg)[X])2l , i ∈ (1, l)• The coefficients of (āi [X], b̄i [X]) are ith digits of (a[X], b[X]) in the base Bg.

1Bg
1Bg 2
 ..
 .

 1l

(a[X], b[X]) ≈ (ā1 [X], ..., āl [X], b̄1 [X], ..., b̄l [X])  Bg
 0
 0
 .
 ..
0
https://nindanaoto.github.io/pdf/IMIKoen.pdf

00..
.
0
1 Bg 1 Bg 2 .. . 1Bg l
Kotaro Matsuoka

19/32

The actual form of TRGSW• We assume applying Decomposition to the TRLWE ciphertext to be multiplied.
 
si
0
a1 [X]
b1 [X]
Bg
 si
 Bg20  a2 [X]
b2 [X]   ..
..  ..
..
 
 .
.
.
.
 

  a [X]
 si
0b[X]
  l
 Bgll+si  al+1 [X] bl+1 [X]  0Bg si  0

a[X]
b[X]
l+2l+2
Bg 2 

 .
.
.

.. ..
..
 ..
. sia2l [X]
b2l [X]0l
Bg

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

20/32

Trade-off in the selection of l

• Increasing l exponentially reduces rounding errors but linearly amplifies 0ciphertexts errors.
• Increasing l means more polynomial multiplications.
• The heaviest computation part in TFHE.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

21/32

Breaking down homomorphic constant term extraction• The homomorphic constant term extraction can be divided into 2 parts.
• Notation:• TLWElvl0: The n + 1 degree TLWE ciphertext. (Already introduced one.)• TLWElvl1: The N + 1 degree TLWE ciphertext. (The secret key is different.)
1

Sample Extract Index: Convert TRLWE into TLWElvl1.

2Identity Key Switching: Convert TLWElvl1 into TLWElvl0.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

22/32

Sample Extract Index• Careful look for the decryption of TRLWE gives the idea.
• The minus sign of the third term comes from the negacyclic property of TN [X].
b[X]−a[X]·S[X] =N−1XX

k=0i+j=k,0≤i,j≤N −1[bk −(Xai ·Sj )−(−ai ·Sj )]X ki+j=N +k,0≤i,j≤N −1• The idea is to fix k in the above formula.
• Regard S (the vector of coefficients) as the key.
• By setting k = 0, we can get the constant term.
• (a′ , b′ ): A TLWElvl1 ciphertext encrypting the kth coefficient.

b′ = bkak−i if i ≤ ka′i =−aN +k−i otherwise
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

23/32

IdentityKeySwitching• ”Key Switching” means changing the secret key without decryption.
• In general, ”Key Switching” can evaluate linear function at the same time.
• ”Identity” means we evaluate the identity function in this case.

• The idea is to compute b − a · S directly.
• We can reuse the idea of Scaling and Decomposition.

• Notations:• Parameters: base, t ∈ Z+ (similar to Bg, l respectively.)Si• IKSKij : The TLWElvl1 ciphertext encrypting basej• āij : jth digit of ai in base base.

(0, b) −N−1 XtXāij · IKSKij

i=0 j=1
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

24/32

The overview of HomNAND (again)

Figure 6: Block diagram of HomNAND

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

25/32

Parameter Selection• The security parameter of TFHE affects the performance.
• Unlike conventional ciphers, there is relatively high motivation to cut off the securitymargin.

• Current de facto tool for security estimation is ”lwe-estimator”.
• https://github.com/malb/lattice-estimator/• Supporting dual/hybrid attack (https://ia.cr/2020/515).
• Missing RLWE specific attacks. (AFAIK)• Estimating error rate of decryption after computations is also necessary.
• To reduce n, N , we have to increase α, αbk .
• concrete-npe seems to be best one for TFHE.
https://github.com/zama-ai/concrete-core/tree/main/concrete-npe
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

26/32

Further Optimizations• Using MLWE (Increasing the dimension of TRLWE.) or NTRU.
• Reducing the degree of polynomials. (Ease polynomial multiplications.)• Programmable Bootstrapping.
• Supports more sophisticated non-linear functions than NAND. (ex.: Full Adder,ReLU)• My paper about compound gates. (WAHC2021)
https://doi.org/10.1145/3474366.3486927• TLWE (or TRGSW) to TRGSW bootstrapping (called Circuit Bootstrapping)• We can use TRGSW’s multiplication as a base operation.

• Scheme switching. (Switching between TFHE and other HEs without decryption.)• We can use a suitable scheme for different operations.
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

27/32

The list of open-source TFHE implementations• TFHE: The original implementation. Deprecated.
• https://github.com/tfhe/tfhe• Concrete: The authors’ Rust implementation. Supporting integer operations.
• https://github.com/zama-ai/concrete.git• OpenFHE: Supporting multiple HEs. Aims to support scheme switching.
• https://github.com/openfheorg/openfhe-development• FINAL: NTRU based TFHE.https://github.com/KULeuven-COSIC/FINAL• MOSFHET: Supports key compression and automorphism Blind Rotate.
• https://github.com/antoniocgj/MOSFHET• TFHEpp: My implementation. Supporting Circuit Bootstrapping.
• https://github.com/virtualsecureplatform/TFHEpp.git• cuFHE: CUDA implementation.
• Forked ver.: https://github.com/virtualsecureplatform/cuFHE.git

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

28/32

Boolean Circuit Evaluations

Boolean circuit evaluations• Combinational circuit is the Directed Acyclic Graph(DAG) of logic gates.
• We can use DAG-based job scheduling for evaluations.
• ex.: Taskflow(https://github.com/taskflow/taskflow),
StarPU(https://starpu.gitlabpages.inria.fr/)• Sequential circuits can be divided by registers into combinational circuits.
• Just copy the inputs of registers to the outputs at the end of the cycle.

• The netlist (DAG) of the circuit can be obtained by conventional synthesis tools.
• ex.: Yosys(https://github.com/YosysHQ/yosys.git)

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

29/32

Speed on real environments• As an example, here is the evaluation time for VSP.
• Equipped with 512 bytes ROM and 512 bytes RAM.
• Pipelining degrades performance if the number of worker is not enough.
• At the best case, we achieve around 1.25 Hz evaluation.
Table 1: Performance Evaluation Using Hamming
MachinePipelining?

# of cycles

Runtime [s]sec./cycle

No
Yes
No
Yes

936
1216
936
1216

2342.02773.01440.0
965.9

2.502
2.280
1.538
0.794

AWS c5.metal
AWS p3.16xlarge
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

30/32

The list of open-source Boolean circuit evaluation frameworks• HDL-based ones:• Iyokan: https://github.com/virtualsecureplatform/Iyokan• Supports both CPU and GPU. CMUX Memory is integrated.

• Sudachi: https://github.com/virtualsecureplatform/Sudachi• Taskflow based. Compound gates are supported.

• HLS-based ones:• Cingulta: https://github.com/CEA-LIST/Cingulata• Deprecated.

• FHE Transpiler: https://github.com/google/fully-homomorphic-encryption• Actively developed. Using XLS as a HLS language.

https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

31/32

Conclusion (Open questions)• FHE is the holy grail but not the silver bullet.
• The security only depends on the secret key.
• Efficiency is generally lower than other privacy-preserving computing methods.

• Who is the winner of FHE?
• Currently, CKKS is the mainstream because it is suitable for the private AI.

• How we can extend HE for multi-party settings?
• There are few works about multi-key or threashold HEs.

• How we can resolve malleability?
• Restricting possible computations is difficult.
• Merging with verifiable computation? (Zero-knowledge proof)• How about the hardware acceleration?
• DARPA DPRIVE project
https://nindanaoto.github.io/pdf/IMIKoen.pdf

Kotaro Matsuoka

32/32