FHE Op. Data Type Bootstrapping BGV [3] mult, add integer ∼ 800𝑠 BFV [9] mult, add integer > 1000𝑠 CKKS [5] mult, add fixed point ∼ 500𝑠 FHEW [8] Boolean binary < 1𝑠
TFHE [6] Boolean binary 13ms
a cloud server that can directly evaluate homomorphic functions, e.g., encrypted neural inferences [4] or encrypted general-purpose computing [14], on the ciphertexts. When all computations are completed, the server returns the encrypted results to the client without learning any intermediate or final output, due to the endto-end encrypted data flow. Only the client can decrypt the results by her secret key. Among all FHE cryptosystems, FHE over the Torus (TFHE) [6] is the most efficient scheme supporting arbitrary operations with an unlimited computation depth, as shown in Table 1. First, TFHE supports arbitrary operations by various homomorphic Boolean logic gates. Traditional FHE schemes such as BGV [3], BFV [9], and CKKS [5] can perform only homomorphic additions and multiplications, while both FHEW [8] and TFHE [6] can enable homomorphic Boolean algebra, e.g., NAND, XOR, and XNOR gates. Second, TFHE obtains the fastest bootstrapping. Each FHE operation inevitably introduces a certain amount of noise into the ciphertext. If there are too many FHE operations on the computational critical path, the accumulated noise in the ciphertext may exceed a threshold, and thus the ciphertext cannot be decrypted successfully. To support an unlimited computation depth, a FHE scheme has to periodically invoke a bootstrapping operation to decrease the amount of noise in the ciphertext. The bootstrapping operation is extremely expensive for BGV, BFV, and CKKS. For example, a BGV bootstrapping typically costs several hundred seconds [11]. Therefore, these FHE schemes can support only a limited computation depth by designing a large enough noise budget. Although a bootstrapping of FHEW takes only 1𝑠, TFHE can obtain a even faster bootstrapping, i.e., a TFHE bootstrapping requires only 13𝑚𝑠 on a CPU. By fast bootstrapping, TFHE allows an unlimited computation depth.
Unfortunately, a TFHE-based complex circuit consisting of multiple TFHE gates is still extremely slow. For instance, a TFHE-based simple RISC-V CPU [14] comprising thousands of TFHE gates can run at only 1.25𝐻𝑧. In order to realize practical TFHE-based computing, it is critical to accelerate TFHE gates by specialized hardware. However, TFHE is only well-implemented on CPUs [16] and GPUs [7]. Although a recent work [10] accelerates TFHE gates on a FPGA, the TFHE gate latency on the FPGA is much longer than that on a GPU. To the best of our knowledge, there is no ASIC-based hardware accelerator for TFHE.
In this paper, we propose a fast and energy-efficient accelerator, MATCHA, to process TFHE gates. We find that the bootstrapping dominates the latency of all TFHE logic operations. The kernels of fast Fourier transform (FFT) and inverse FFT (IFFT) are the bottlenecks in a bootstrapping operation. MATCHA is designed to accelerate the TFHE bootstrapping using approximate multiplication-less integer FFTs and IFFTs. We also propose a pipelined datapath for MATCHA to support aggressive bootstrapping key unrolling [2,22] that invokes FFTs and IFFTs less frequently. Our contributions can be summarized as follows. [𝑋 ], which are the ring of polynomials of variable 𝑋 with quotient 𝑋 𝑁 + 1 and real coefficients modulo 1. B {0, 1} is a set, and we write vectors in bold. Given a set S, we write s $ ← -S to indicate that s is sampled uniformly at random from S. We write 𝑒 ← X to denote that 𝑒 is sampled according to X.
In TFHE [6], we assume 𝑚 ∈ B is a plaintext. The encryption scheme works as follows:
can be XOR, NAND, AND, and OR. A TFHE logic operation involves an addition between 𝑐 0 and 𝑐 1 , and a bootstrapping. TLWE. TLWE is a torus analogue of the learning with error (LWE) problem [3]. 𝑘 is a positive integer. 𝑁 is a power of 2, and X is a probability distribution over R 𝑁 [𝑋 ]. A TLWE secret key s is a vector of 𝑘 polynomials over Z 𝑁 [𝑋 ] with binary coefficients, denoted as s
TGSW. TGSW is the matrix extension of TLWE. Each row of a TGSW sample is a TLWE sample. An external product that maps : 𝑇𝐺𝑆𝑊 ×𝑇𝑊 𝐿𝐸 → 𝑇 𝐿𝑊 𝐸 can be defined by TFHE [6]. The product of the TGSW ciphertext of a polynomial message 𝜇 𝑇𝐺𝑆𝑊 ∈ T 𝑁 [𝑋 ] and the TLWE ciphertext of a polynomial message 𝜇 𝑇 𝐿𝑊 𝐸 ∈ T 𝑁 [𝑋 ] becomes a TLWE ciphertext of a polynomial message 𝜇 𝑇𝐺𝑆𝑊 • 𝜇 𝑇 𝐿𝑊 𝐸 ∈ T 𝑁 [𝑋 ] Bootstrapping. Each TFHE logic operation inevitably introduces a certain amount of noise into the resulting ciphertext. A bootstrapping has to be performed to remove the noise at the end of each TFHE logic operation. In various TFHE logic operations, the bootstrapping step is the largest performance bottleneck. The details of a TFHE bootstrapping can be viewed in [6]. The bootstrapping procedure is shown in Algorithm 1. The dimension of the TLWE sample is set as 𝑘 = 1 [6], which means that the TLWE sample is simply the Ring
The most computationally intensive step of a bootstrapping is the homomorphic decryption in line 7, where the message of 𝐴𝐶𝐶 becomes a polynomial 𝑋 b -ās • 𝑡𝑒𝑠𝑡𝑣. Particularly, homomorphically computing 𝑋 -ās = 𝑋 𝑛 𝑖=1 -ā𝑖 s 𝑖 = 𝑛 𝑖=1 𝑋 -ā𝑖 s 𝑖 involves a great number of polynomial multiplications. Naïvely multiplying two degree 𝑁 polynomials has the complexity of O(𝑁 2 ). FFT and IFFT are used to reduce the complexity of a polynomial multiplication to O(𝑁 log(𝑁 )) [7], where 𝑁 is the degree of polynomials.
Torus Implementation. Theoretically, the scale invariant scheme of TFHE is defined over the real torus T, where all operations are modulo 1. But TFHE rescales the elements over T by a factor 2 32 , and maps them to 32-bit integers [6], since it can work with approximations. Therefore, TFHE does not have to actively perform modular reduction, since all operations on 32-bit integers implicitly x i (n)
x j (n) call a native and automatic mod 2 32 operation. To maintain high conversion accuracy, TFHE uses 64-bit double-precision floating point FFT and IFFT kernels [6].
Related Work. Except some TFHE implementations on CPUs [6], GPUs [7], and FPGAs [10], there is no specialized hardware accelerator that can process TFHE. A TFHE accelerator is different from the accelerators designed for other FHE schemes such as BGV, BFV, and CKKS in two points. First, although few prior accelerators [19] support BGV and CKKS bootstrapping along a tiny multiplicative depth datapath, most prior works [15,18,20] design hardware accelerators to process leveled BFV or CKKS homomorphic operations without bootstrapping. However, a TFHE accelerator must perform bootstrapping at the end of each TFHE gate. Second, BGV, BFV, and CKKS require NTT and INTT kernels, while TFHE needs only FFT and IFFT kernels without modular reduction.
Motivation. A TFHE gate performs not only polynomial additions but also a bootstrapping (FFT+IFFT+other) that costs 99% of the gate latency on a CPU, as shown in Figure 1. Therefore, in order to shorten the latency of TFHE gates, we need to accelerate the bootstrapping step in TFHE gates. Moreover, FFTs and IFFTs consume 80% of the bootstrapping latency in various TFHE gates. In order to accelerate TFHE gates, MATCHA adopts approximate multiplication-less integer FFTs and IFFTs, and uses a pipelined datapath to support aggressive bootstrapping key unrolling [2,22].
Despite the fact that elements over T are mapped to 32-bit integers, TFHE still uses 64-bit double-precision floating point FFT and IFFT kernels, since 32-bit integer or single-precision floating point FFT and IFFT kernels are not accurate enough to guarantee the correct decryption of a ciphertext [6]. However, processing 64-bit double-precision floating point FFT and IFFT kernels incurs significant hardware overhead and power consumption.
Novelty. We first identify the opportunity to use approximate integer FFTs and IFFTs to accelerate TFHE without decryption errors for MATCHA. It is difficult to apply approximate NTTs and INTTs in accelerating other FHE schemes, e.g., BGV, BFV, and CKKS, which do not include a bootstrapping step after each homomorphic multiplication or addition. The errors introduced by approximate NTTs and INTTs will be quickly accumulated in the ciphertext and result in a decryption error, if a bootstrapping step cannot be performed in time. On the contrary, TFHE keeps the approximation errors of integer FFTs and IFFTs in check by performing a bootstrapping step at the end of each TFHE gate.
Depth-first FFT. Most prior FHE accelerators [18][19][20] perform NTTs and INTTs by the Cooley-Tukey data flow that introduces irregular memory accesses particularly in its bit-reversal stage. In order to remove the bit-reversal overhead, a prior ideal-latticebased cryptographic accelerator [13] uses the Cooley-Tukey flow for NTTs and the Gentlemen-Sande flow for INTTs. These cryptographic accelerators store a polynomial mod 𝑋 𝑁 + 1 as a list of 𝑁 coefficients. For each multiplication between two polynomials, they execute two NTT kernels on two polynomials respectively, perform element-wise multiplications, and then run an INTT kernel on the result. The invoking frequency ratio between NTTs and INTTs is 2 : 1. These FHE accelerators have are many opportunities (i.e., switchings from NTT to INTT) to reduce the bit-reversal overhead. In contrast, TFHE saves a polynomial mod 𝑋 𝑁 + 1 as either a list of 𝑁 coefficients or the Lagrange half-complex representation consisting in the complex evaluations of the polynomial over the roots of unity 𝑒𝑥𝑝 (𝑖 (2𝑗 + 1)𝜋/𝑁 ) for 𝑗 ∈ 0, 𝑁 2 . FFT and IFFT kernels are required only during the conversion between these two representations. The invoking frequency ratio between FFTs and IFFTs in a TFHE gate is 1 : 4. As Figure 1 shows, the latency of IFFT kernels is much longer than FFT kernels. TFHE does not have many opportunities to reduce the bit-reversal overhead. Instead, for MATCHA, we focus on decreasing the computing overhead of a single FFT or IFFT kernel. We adopt the depth-first iterative conjugate-pair FFT (CPFFT) algorithm [1]. Unlike the Cooley-Tukey or Gentlemen-Sande flow, the CPFFT requires only a single complex root of unity read per radix-4 butterfly. Two butterflies in the same block can share the same twiddle factor, further halving the number of reads to the twiddle-factor buffer [1]. Moreover, the Cooley-Tukey and Gentlemen-Sande flows process FFTs/IFFTs stage by stage in a breadth-first manner, as shown in Figure 2(a). To capture the spatial locality, as Figure 2(b) shows, CPFFT traverses the FFT flow in a depth-first fashion by completing a sub-transform before moving to the next.
A Multiplication-less Butterfly. The lifting structure [17], a special type of lattice substrate implemented by cascading identity matrices with a single nonzero off-diagonal element, is proposed to approximate multiplications in FFT and IFFT kernels by additions and binary shifts. The basic lifting step shown in Figure 3(a) can be expressed by 𝑦 𝑗 (𝑛) = 𝑥 𝑗 (𝑛), 𝑦 𝑖 (𝑛) = 𝑥 𝑖 (𝑛) + 𝑇 𝑥 𝑗 (𝑛) , 𝑧 𝑗 (𝑛) = 𝑦 𝑗 (𝑛), and 𝑧 𝑖 (𝑛) = 𝑦 𝑖 (𝑛) -𝑇 𝑦 𝑗 (𝑛) , where 𝑇 is a lifting coefficient. And thus, the lifting structure with the rounding operation can achieve integer-to-integer transform. Also, the lifting and its inverse matrices in this case are represented as 1 𝑇 0 1 and 1 𝑇 0 1
, respectively. A floating-point lifting coefficient can be quantized as an approximate dyadic-valued coefficient 𝛼/2 𝛽 , and hence computed with only adders and shifters, where we allocate 𝛽 bits to the lifting coefficient, and 𝛼, 𝛽 ∈ N. For example, a coefficient 9/128 can be operated as 9 128 = 2 3 +2 0 2 7 = 1 2 4 + 1 2 7 . Hence, the lifting with its coefficient 9/128 and a rounding operation is replaced to
for i=1 to do n 2 the summation of 4 and 7 bit-shifters illustrated in Figure 3(b). The perfect reconstruction in lifting is always kept if floating-point coefficients are approximated to dyadic-valued coefficients.
Bootstrapping Key Unrolling. A TFHE bootstrapping needs to compute external produces, i.e., 𝑋 -as = 𝑋 𝑛 𝑖=1 -a 𝑖 s 𝑖 sequentially, thereby becoming the performance bottleneck of a TFHE gate. Instead, bootstrapping key unrolling (BKU) [2,22] is proposed to compute 𝑋 𝑛/2 𝑖=1 -a 2𝑖 -1 s 2𝑖 -1 -a 2𝑖 s 2𝑖 in each external product, so that the number of homomorphic additions can be reduced from 𝑛 to 𝑛/2. The secret key s is sampled from B 𝑛 , so 𝑠 𝑖 ∈ {0, 1}, where 0 ≤ 𝑖 ≤ 𝑛. Based on the values of 𝑠 2𝑖 and 𝑠 2𝑖+1 , the truth table of 𝑋 𝑛/2 𝑖=1 -a 2𝑖 -1 s 2𝑖 -1 -a 2𝑖 s 2𝑖 can be shown in Figure 4. So BKU rewrites 5 shows, BKU encrypts 𝑠 2𝑖 -1 𝑠 2𝑖 , 𝑠 2𝑖 -1 (1 -𝑠 2𝑖 ), and (1 -𝑠 2𝑖 -1 )𝑠 2𝑖 as TGSW ciphertexts, and builds a bootstrapping key bundle to unroll the orginal bootstrapping key for two times.
Aggressive BKU Performing Badly on CPUs. BKU can be further generalized as
where 𝑚 ∈ [2, 𝑛]. So it is possible to more aggressively unroll the bootstrapping key by increasing 𝑚. Although unrolling the bootstrapping key for two times (𝑚 = 2) reduces the bootstrapping latency by 49%, we find that further enlarging 𝑚 beyond 2 even prolongs the bootstrapping latency on a CPU, as explained in Section 6. Our experimental methodology is described in Section 5.
The reason can be summarized as follows.
• The limited number of cores on a CPU. With an enlarged 𝑚, there are more terms in the exponent part of Equation CPU baseline has only 8 physical cores. Mapping each terms to a core, and summing the results from all cores introduce significant communication overhead.
• More cache conflicts. The size of bootstrapping key increases exponentially with an enlarged 𝑚. For example, as Figure 5 shows, instead of a single bootstrapping key, BKU with 𝑚 = 2 requires three bootstrapping keys. Each TGSW scale-and-add operation happening on a term fetches its corresponding bootstrapping key to the shared last level cache, generating more cache conflicts. • The lack of a pipelined design. As Figure 5 highlights, in each iteration, the construction of the bootstrapping key bundle BKB and the external product operation are executed sequentially.
Although it is possible to start the computation of BKB for the next iteration and perform the external product operation of this iteration at the same time, the current BKU implementation [22] cannot do this, due to the lack of a pipelined design. MATCHA for Aggressive BKU. In this paper, we propose a pipeline flow for MATCHA to support aggressive BKU with a larger 𝑚. Compared to our CPU baseline, our pipeline flow can be easily accelerated by a large number of specialized hardware components including TGSW clusters and External Product (EP) cores. As Figure 6(a) shows, we divide the bottleneck of a TFHE bootstrapping into two steps, i.e., the construction of the bootstrapping key bundle, and the EP operation. A TGSW cluster is used to construct the bootstrapping key bundle, while an EP core processes EP operations between the bootstrapping key bundle and 𝐴𝐶𝐶. A TGSW cluster consists of a TGSW adder tree and multiple TGSW scale units, each of which computes one term in the bootstrapping key bundle, e.g., when 𝑚 = 2, (𝑋 -𝑎 2𝑖 -1 -𝑎 2𝑖 -1) • BK i,0 , where BK i,0 is the TGSW ciphertext of 𝑠 2𝑖 -1 𝑠 2𝑖 . And then, the TGSW adder sums all terms and generates the bootstrapping key bundle. With the bootstrapping key bundle (BKB i ), an EP core computes 𝐴𝐶𝐶 ← BKB i 𝐴𝐶𝐶. The TGSW cluster and the EP core have their separated register file banks to reduce on-chip memory conflicts. Moreover, these two steps of a TFHE bootstrapping can be deployed on a TGSW cluster and an EP core in a pipelined manner, as shown in Figure 6(b). In each time step, the EP core computes the EP operation with the bootstrapping key bundle generated by the TGSW cluster in the previous time step. When 𝑚 is increased, the workload of the bootstrapping key bundle construction becomes larger. connected to 32 scratchpad memory (SPM) banks by crossbars. MATCHA also employs a memory controller to manage the offchip memory requests issued to HBM2 DRAMs. The polynomial unit is in charge of performing polynomial additions/subtractions for each TFHE logic operation, initializing bootstrapping operations, extracting samples, and conducting key-switching operations that consist of additions, logic comparisons, and Boolean logic operations. One TGSW cluster and an EP core can support one bootstrapping pipeline. As Figure 7(b) shows, a TGSW cluster 16 32-bit integer multipliers and 16 32-bit integer adders to support TGSW scale operations. Each TGSW cluster has only two register banks, since the memory accesses during a TGSW scale operation have strong spatial locality. The TGSW cluster can read a register bank while write the other bank concurrently. An EP core consists of an FFT core and four IFFT cores to accelerate the FFT and IFFT kernels during an EP operation, as shown in Figure 7(c). It has 8 register banks to serve the irregular memory accesses in FFT and IFFT kernels. An EP core also has four 32-bit integer multipliers and four 32-bit integer adders to manipulate TGSW ciphertexts during an EP operation. An FFT core is similar to an IFFT core, except its data flow. As Figure 7(d) highlights, an FFT core comprises an address generation unit, a twiddle factor buffer, two input/output FIFOs, and 128 butterfly cores, each of which consists of two 64-bit integer adders and two 64-bit binary shifters. The address generation unit guides butterfly cores to access the twiddle factor buffer. Design Overhead. We implemented MATCHA in RTL, and synthesized it in 16𝑛𝑚 PTM process technology using state-of-theart tools. We used CACTI to model all SPM components and register file banks. Due to its simple structure, the entire design of MATCHA can run at 2𝐺𝐻𝑧. Among various on-chip network architectures, e.g., meshs, rings, and crossbars, we selected two 8×32, and one 8×8 bit-sliced crossbars, i.e., SPM → cores/clusters, cores/clusters → SPM, and cores/clusters → cores/clusters. The hardware overhead and power consumption of MATCHA are shown in Table 2. Totally, MATCHA occupies 36.96𝑚𝑚 2 and consumes 39.98 Watt. The HBM2 bandwidth is 640𝐺𝐵/𝑠.
Error and Noise. The error of the polynomial multiplication result caused by approximate multiplication-less integer FFT and IFFT kernels is shown in Figure 8. All polynomial coefficients are 32-bit integers, while we quantize the twiddle factors of FFT and IFFT with various bitwidths. With an increasing bitwidth of twiddle factors, the error caused by approximate FFT and IFFT decreases, and is similar to that generated by original double-precision floating point FFT and IFFT. With 64-bit dyadic-value-quantized twiddle factors (DVQTFs), the error caused by approximate FFT and IFFT is
Simulation and Compilation: To simulate the performance of MATCHA at cycle level, we used a CGRA modeling framework, OpenCGRA [21], which has been validated against multiple ASIC accelerators. OpenCGRA first compiles a TFHE logic operation into a data flow graph (DFG) of the operations supported by MATCHA, solves its dependencies, and removes structural hazards. The architecture of MATCHA is abstracted to an architecture description (AD) in OpenCGRA, which computes the latency and the energy consumption of each TFHE logic operation by scheduling and mapping the DFG onto the AD.
Our Baselines. We compared MATCHA against state-of-the-art CPU-, GPU-, FPGA-, and ASIC-based TFHE hardware platforms. Our CPU baseline is a 8-core 3.7𝐺𝐻𝑧 Xeon E-2288G processor executing the TFHE library [6], while our GPU baseline is a 5120core Tesla-V100 GPU equipped with a 16GB HBM2 DRAM running the cuFHE library [7]. TFHE Vector Engine (TVE) [10] was implemented on a low-end ZedBoard Zynq-7000 FPGA. We implemented 8 copies of TVE on a Stratix-10 GX2800 FPGA, and used it as our FPGA baseline, since the Stratix-10 board has more resources. Because there is no existing ASIC-based design, we synthesized our FPGA baseline with the 16𝑛𝑚 PTM process as our ASIC baseline. We enable BKU on CPU, GPU, and MATCHA but fix 𝑚 = 1 on FPGA and ASIC, since they do not support BKU.
TFHE Operations and Parameters. We studied all TFHE logic operations including NOT, AND, OR, NAND, XOR, and XNOR, but we only report the results on NAND in Section 6. This is because AND, OR, NAND, XOR, and XNOR have almost the same latency which is dominated by the bootstrapping step, while NOT has no bootstrapping at all. To maintain the standard 110-bit security, we adopt the TFHE parameters from [6], i.e., the polynomial degree in the ring 𝑁 = 1024, the TLWE dimension 𝑘 = 1, the basis and length for the TGSW ciphertext decomposition 𝐵𝑔 = 1024 and 𝓁 = 3.
Latency. The latency comparison of a TFHE NAND gate between our various baselines and MATCHA is shown in Figure 9. The NAND gate on CPU costs 13.1𝑚𝑠, while 𝑚 = 2 reduces its latency to 6.67𝑚𝑠. Aggressive BKU with an increasing 𝑚 cannot further reduce the NAND gate latency anymore on CPU, due to the limited number of cores, more cache conflicts, and the nonpipelined processing style. It takes only 0.37𝑚𝑠 for GPU to process a NAND gate. With an enlarging 𝑚, GPU gradually reduces the NAND gate latency. When 𝑚 = 4, the NAND gate latency on GPU is 0.18𝑚𝑠. MATCHA reduces the NAND gate latency by 13% over GPU only when 𝑚 = 3, since GPU can fully use its all resources to process one TFHE gate when 𝑚 = 1 or 2. MATCHA cannot support aggressive BKU with 𝑚 = 4 efficiently either, since it has only 8 TGSW clusters. FPGA and ASIC do not have any pipelined design or memory optimization to support BKU, and they need > 6.8𝑚𝑠 to complete a NAND gate when 𝑚 = 1.
Throughput. The NAND gate throughput comparison between various baselines and MATCHA is shown in Figure 10. FPGA and ASIC duplicate 8 copies of the TVE [10], so they support only 𝑚 = 1. By enabling aggressive BKU, even CPU (𝑚 = 2) can achieve higher gate processing throughput than ASIC and FPGA with 𝑚 = 1. GPU and MATCHA obtain much higher throughput than ASIC, FPGA and CPU. Compared to GPU, MATCH improves the NAND gate throughput by 2.3× (𝑚 = 3), due to its pipelined architecture for aggressive BKU.
Throughput per Watt. The comparison of the NAND gate throughput per Watt between various baselines and MATCHA is shown in Figure 11. FPGA and ASIC consume only ∼ 40𝑊 and ∼ 26𝑊 , and improve the NAND gate throughput per Watt by 2.4× and 8.3× over CPU respectively, when 𝑚 = 1. Due to the large power consumption (> 200𝑊 ) of GPU, the best throughput per Watt of GPU (𝑚 = 4) is only about 58% of that of ASIC. Compared to ASIC, MATCHA improves the NAND gate throughput per Watt by 6.3×, since it consumes only 39.98𝑊 .
TFHE enables arbitrary computations with an unlimited multiplicative depth to directly occur on ciphertexts. However, TFHE gates are time-consuming and power-hungry on state-of-the-art hardware platforms. In this paper, we build MATCHA to accelerate TFHE gates. MATCHA allows aggressive bootstrapping key unrolling to process TFHE gates without decryption errors by approximate multiplication-less integer FFTs and IFFTs, and a pipelined datapath. Compared to prior CPU-, GPU-, FPGA-and ASIC-based solutions, MATCHA improves the TFHE gate processing throughput by 2.3×, and the throughput per Watt by 6.3×.