Patent ID: 12200101

DETAILED DESCRIPTION

Incorporation by Reference of Prior US Provisional Application

The complete contents of U.S. Provisional Application No. 63/472,954 filed Jun. 14, 2023 are hereby incorporated by reference in their entirety. The description below includes specific references to U.S. Provisional Application No. 63/472,954 in the form of “Provisional Application, Section X”, where X stands for a specific section number.

Overview

Fully Homomorphic Encryption (FHE) offers protection to private data on third-party cloud servers by allowing computations on the data in encrypted form. To support general-purpose encrypted computations, existing FHE schemes require an expensive operation known as “bootstrapping”. Unfortunately, the computation cost and the memory bandwidth required for bootstrapping add significant overhead to FHE-based computations, limiting the practical use of FHE.

Described herein is an FPGA-based accelerator for bootstrappable FHE, which may be referred to as “FAB”. Prior FHE accelerators have proposed hardware acceleration of basic FHE primitives for impractical parameter sets without support for bootstrapping. FAB, in contrast, accelerates bootstrapping (along with basic FHE primitives) on an FPGA for a secure and practical parameter set. Prior hardware implementations of FHE that included bootstrapping are heavily memory bound, leading to large execution times and wasted compute resources. One contribution of the disclosed approach is a balanced FAB design which is not memory bound. To this end, algorithms for bootstrapping are leveraged while being cognizant of the compute and memory constraints of FPGA hardware. To architect a balanced FAB design, a minimal number of functional units are used for computing, operate at a low frequency, leverage high data rates to and from main memory, utilize the limited on-chip memory effectively, and perform operation scheduling carefully. In one example FAB is realized using a single Xilinx Alveo U280 FPGA and by scaling it to a multi-FPGA system consisting of eight such FPGAs. FAB may outperform existing state-of-the-art CPU and GPU implementations for both bootstrapping and an example application of logistic regression (LR) model training. FAB may also provide competitive performance when compared to the state-of-the-art ASIC design, at a fraction of the cost.

Embodiments

FIG.1shows an example system arrangement having a host CPU10coupled via a system bus12(e.g., PCIe) to a (N/W) network interface14and a set of FPGA-based hardware accelerator modules (ACCEL)16. The network interface14couples the system to an external network18. In one embodiment the system may be realized in a so-called cloud computing platform.

In operation, the host CPU10executes higher-level portions of an FHE-based application, i.e., an application that utilizes and operates upon encrypted data using FHE techniques as generally known. In the system ofFIG.1, the host CPU10is also responsible for initialization of field-programmable element(s) of the accelerator modules16, i.e., downloading customization logic in hardware description language (e.g., RTL) form, as described more below.

In particular, described herein is use of the system arrangement in an FHE scheme referred to as “Cheon-Kim-Kim-Song” or CKKS, which is outlined briefly below. Of particular relevance are operations of bootstrapping and key switching, including a number theoretic transform (NTT) and its inverse (INTT), all of which are outlined in the Provisional Application, Section 2.

FIG.2shows the system with particular emphasis on details of an accelerator16, shown as FPGA20. It includes a network interface shown as CMAC Subsystem22, global memory24, and a collection of processing logic shown as FAB26. The host CPU10interacts with the FPGA20via PCIe12. The CMAC subsystem22enables interaction among multiple FPGAs via an Ethernet Switch28. The global memory24is shown as having two separate sets or stacks of high-bandwidth memory (HBM2).

The RTL design of the FAB26is packaged as a kernel code which is downloaded from the host10to the FPGA20. To enable data transfer, the host10allocates a buffer of the dataset size in the global memory24. The host code communicates the base address of the buffer to the kernel code using atomic register reads and writes through an AXI4-Lite interface30The host code also communicates all kernel arguments consisting of the system parameters like prime moduli, the degree of a polynomial modulus N, and certain pre-computed scalar values (to be stored in the register file) through this interface.

The kernel is started by the host code using an API call such as a Xilinx runtime (XRT) API call or OpenCL API call. Once the kernel execution starts, no data transfer occurs between the host and the global memory so as to interface all 32 AXI ports from the global memory24to the kernel code. The results are transferred back to the host code once the kernel execution completes.

The kernel code instantiates 256 sets of functional units each having a set of modular arithmetic units and an automorph unit (Automorph). The modular arithmetic units are a modular multiplier Mod Mult, modular addition Mod Add, and modulator subtraction Mod Sub. A small register file RF, which may be 2 MB in size for example, stores all required system parameters and precomputed scalar values that are received from the host20. The RF also facilitates temporary storage of up to four polynomials that may be generated as intermediate results. Various details regarding all of these functional components are described further below.

The kernel has 32 memory-mapped 256-bit interfaces that are implemented using AXI4 master interfaces to enable bi-directional data transfers to/from the global memory. The kernel acts as a master accessing data stored in the global memory24. Read (Rd) FIFO and write (Wr) FIFO stream the data between the global memory24and on-chip memory of the FAB26, which includes URAM and BRAM resources organized into various banks as shown. The URAM memory banks are single-port banks, while the BRAM memory banks are dual-port banks. Also included respective address generation blocks for NTT, URAM and BRAM. A transmit (Tx) FIFO and a receive (Rx) FIFO stream data to and from the CMAC subsystem22.

In one embodiment, the total capacity of all the RFs is 2 MB. The RFs are spread across the design and are used by functional, address generation, and control units. Each RF has multiple read/write ports with single-cycle access latency. About one-fourth of the RF is used to store pre-computed values and system parameters, which are written by the host CPU10through atomic writes before launching the kernel code execution. The remaining RFs are used to store up to four intermediate polynomials that are generated as part of Rotate or Multiply operations.

In one embodiment, there are 32 synchronous Wr and Rd FIFOs (supporting 32 AXI ports on the HBM side) to stream the data between the global memory24and the on-chip memory URAM, BRAM. These FIFOs are composed of distributed RAM available on the FPGA20. The data width of each FIFO is equal to the data width supported by each AXI port i.e., 256˜bits. The depth of the Wr FIFO is 128 to support an HBM burst length of 128. The depth of the Rd FIFO is 512 to support up to four outstanding reads. The Transmit (Tx) and Receive (Rx) FIFOs, used to stream data between the CMAC subsystem22and the on-chip memory URAM, BRAM, are also synchronous FIFOs having a 512-bit data interface.

FIG.3illustrates content and arrangement of on-chip memory. In one embodiment, there are 962 blocks of URAM where each block is 288 Kb in size and can be used as single-port memory. Further, there are 4032 blocks of BRAM where each block is 18 Kb in size and can be used as both single and dual-port memory. Using such a combination of single and dual-port memory banks constructed using URAM and BRAM blocks, a total capacity of 43 MB and an internal memory bandwidth of 30 TB/s may be realized.

As shown inFIG.3, each URAM block has a data width of 72 bits and a depth of 4096. Three such URAM blocks are combined to achieve a data width of 216 bits, which allows for storing four 54-bit coefficients (216/4=54) at any given address. 64 of these 216-bit-wide subsets are arranged into a single URAM memory bank to enable storage of 256 coefficients. Thus, with every read and write, 256 54-bit coefficients are accessed in the same cycle, aligning with the number of functional units (seeFIG.2).

Using the above layout, a single memory bank consists of 64×3=192 URAMs and can store 16 polynomials (˜7.08 MB). The overall available URAM blocks are organized into five such banks as follows:1. The first two banks (c0 banks 1 and 2) store 31 limbs (23 original and 8 extension) of the c0 ring element of the ciphertext.2. The next two banks (cl banks 1 and 2) store 31 limbs (23 original and 8 extension) of the cl ring element of the ciphertext.3. The fifth bank can store 16 polynomials. The fifth bank is termed the “miscellaneous” bank as it is used to store multiple data items such as twiddle factors, Key Switch keys, and plaintext vectors that are read in from the global memory24.

As shown inFIG.3, the BRAM blocks are organized as 54-bit wide memory banks by combining three 18-bit wide BRAMs. As each address can store only a single 54-bit coefficient, 256 BRAM blocks are used to store 256 coefficients. In addition, the BRAM blocks are stacked two-high to get a depth of 2048, thus enabling storage of 8 polynomials in a single BRAM bank.

Similar to the URAM bank organization, the BRAM blocks are organized into multiple banks. There are three BRAM banks in total, where two banks consist of 1536 BRAMs each and can store 8 polynomials and thus, are ideal to store the extension limbs. The third bank consists of 768 BRAMs and can store 4 polynomials. The third bank is termed the “miscellaneous” bank and is used to store temporary data from the global memory24during various operations.

To summarize, FAB efficiently utilizes the available URAM/BRAM blocks on the FPGA20as on-chip memory. Mapping the data width of the polynomials to that of URAM/BRAM blocks enables storage of up to 43 MB of data on-chip, in one embodiment. FAB overcomes limited main memory bandwidth by utilizing a combination of single and dual-port memory banks that complement the operational needs of the underlying FHE operations, resulting in a balanced FPGA design.

Generally, the operations in FHE break down to integer modular arithmetic i.e., modular addition/subtraction and modular multiplication operations. Therefore, as shown inFIG.2, each of the 256 functional units in FAB consists of modular multiplication, modular addition, and modular subtraction components, as well as an automorph unit. A multi-word arithmetic approach is used to reduce 54-bit operations to 27-bit operations for addition/subtraction and 18-bit operations for multiplication. This facilitates efficient utilization of standard DSP arithmetic blocks on the FPGA (i.e., library components of predetermined fixed widths different than the FHE operand width).

FIGS.4and5illustrate multi-word modular addition and subtraction (Mod Add and Mod Sub inFIG.2). Overall, 54-bit addition/subtraction operations are performed using two sets of 27-bit operations (for indices 0 and 1 respectively) and a complex of specialized carry and selection logic.FIG.5shows the FPGA hardware instantiated to realize the addition/subtraction algorithm shown in the pseudocode ofFIG.4. Note that the upper and lower modulus values mod[1] and mod[0] ofFIG.4are shown as q[1] and q[0] inFIG.5. Also, the upper and lower result values C[1] and C[0] ofFIG.4are shown as c_upper and c_lower. With multi-word arithmetic and use of pipeline registers around the standard arithmetic blocks as shown, modular addition and subtraction can be performed in 7 clock cycles.

FIGS.6-9illustrate modular multiplication (Mod Mult inFIG.2). Generally, modular multiplication is accomplished by first multiplying the operands as integers, and then reducing the result. This implies a structure as shown inFIG.6in which modular multiplication is split across two operations i.e., an integer multiplication (Int Mult40) producing a non-reduced result C(N-R), followed by modular reduction (Mod Reduc42) producing a reduced result C(R), in a pipelined fashion.FIGS.7and8illustrate the integer multiplication40according to one embodiment, which is a technique referred to as the operand scanning algorithm. Input 54-bit operands are split into three 18-bit operands. For performance, loop unrolling is used and various multiplication operations are preferably computed in parallel, reducing the multiplication latency to 12 clock cycles while still adding all the required pipeline registers for DSP multipliers.

FIG.9illustrates an example modular reduction (Mod Reduc42), which is a particular form that requires only shift and addition operations. For performance, a technique is used that performs multiple bit shifts, requiring only 12 clock cycles for log q=54 for the modular reduction operation. In this example the number of shifts is set to 6, but it is worth noting that this algorithm is generic and can work with any number of bit shifts depending on the latency requirement and space constraints. This algorithm requires precomputing an array {madd} having 63 elements, where each element is (log q)/2 bits wide. In this particular use, modular reduction is performed with respect to 31 different primes, implying that it is necessary to precompute 31 such {madd} arrays requiring ˜7 KB of storage space in total. This precompute is done offline, so there is no compute overhead associated with it. All other steps in the proposed algorithm can be performed using inexpensive shift and addition operations.

Referring again toFIG.2, the final operation that forms each of the 256 sets of functional units is Automorph, which performs permutation for the Rotate operation of FHE. The function of the Automorph unit is to read a polynomial from the on-chip memory and store it in a register file RF in a permuted order per a given rotation index k. Any original slot indexed by i in ciphertext maps to the rotated slot through an automorphism equation, described in Provisional Application, Section 4.1.

Due to the limited number of rotation indices (e.g., about 60 different values) used in bootstrapping, various powers of 5 are precomputed and stored which correspond to each of the rotation index k. Division by two is a simple bit-shift, and reduction modulo N is significantly simplified because N is always a power of two. Thus, reduction modulo N can be achieved by simply performing an {AND} operation with N−1.

To summarize, the functional units in FAB are optimized for the available hardware to reduce resource overhead. They make effective use of high-performance multipliers and adders in DSP blocks to perform low-latency modular arithmetic. FAB efficiently utilizes these functional units through fine-grained pipelining and by issuing multiple scalar operations in a single cycle.

NTT/iNTT and Key Switch Datapaths

In this section, datapath optimizations are described for certain compute-intensive NTT operations and memory-intensive Key Switch operations of the CKKS scheme, efficiently utilizing FAB microarchitecture.

In one embodiment, the NTT datapath uses a unified Cooley-Tukey algorithm for both NTT and inverse-NTT (INTT). Using a unified NTT algorithm provides the convenience of leveraging the same data mapping logic for both NTT and iNTT. Modulo-256 modular addition, subtraction and multiplication units operate in parallel as radix-2 butterfly units, processing 512 coefficients of a polynomial at once, reducing processing time accordingly. NTT address generation unit (shown inFIG.2) takes care of uniquely mapping the data within each stage of the NTT/iNTT using a sub-unit, i.e. a data mapping unit. Furthermore, a twiddle factor mapping sub-unit within the NTT address generation unit takes care of reading the required twiddle factors for an NTT stage from the URAM miscellaneous bank. Both of these sub-units leverage the data and stage counters to generate the addresses on-the-fly using inexpensive shift, and AND operations. Thus, pipelining and parallelism are leveraged while computing NTT/iNTT by distributing the computations over the functional units, a data mapping unit, and a twiddle factor mapping unit. It is worth noting that the latency of the bit-reversal operation here is not included here, as bit-reversal is carried out along with automorph/multiplication operation that is performed just before NTT/INTT.

FIG.10illustrates datapath aspects for a Key Switch operation used in CKKS. At upper right is shown a nominal flow of operations of the Key Switch operation-decomposition (Decomp), increase modulus (ModUp), inner product (KSKIP), and decrease modulus (ModDown) in sequential order. The remainder ofFIG.10illustrates a particular datapath used for efficient on-chip memory utilization for these sub-operations, which avoids reads/writes of the ciphertext limbs to the global memory24and thus lowers the latency of FHE computing. With limited on-chip memory, the sub-operations require smart operation scheduling to efficiently utilize the on-chip memory. This is because Key Switch not only needs to operate on the extension limbs (the factors of P) but it also needs to perform an inner product with the Key Switch keys that are almost 3× the size of the ciphertext. The scheme ofFIG.10involves scheduling and organizing the sub-operations to manage ˜112 MB of data (84 MB keys and 28 MB ciphertext) within the available 43 MB on-chip memory without writing any resultant limbs back to the global memory24.

More particularly, the Key Switch operation is optimized by scheduling and reorganizing the sub-operations so as to split the key switch inner product (KSKInProd) step into two steps (step2and step4inFIG.10). Instead of performing the KSKInProd step all at once, the process makes progress on the inner product by performing the multiplications and additions as soon as the operands are in memory, which reduces transfers to/from the global memory24. More specifically, about 112 MB of data (84 MB of keys and 28 MB of ciphertext) are managed within the available 43 MB on-chip memory without writing any resultant ciphertext limbs back to the global memory24. The modified datapath also reduces the number of NTT computations, which is the most expensive subroutine in Key Switch operation. Through smart operation scheduling, high data reuse is enabled, inherent limb-wise parallelism is exploited, and uniform address generation logic is maintained by avoiding switching between limb-wise and slotwise accesses, along with the reduction of global memory traffic by not writing/reading resultant ciphertext limbs thereto.

Overall operation begins with L limbs in one of the ciphertext ring elements am(ciphertext has two ring elements amand bm) that are in evaluation representation. The Decomp step divides these L limbs into β≤dnum blocks of α limbs each. These a limbs then take two paths. First, they are used to begin the KSKInProd (KSKIP step2inFIG.10), with the intermediate sum being written out to URAM. This KSKIP operation is performed as the a limbs are still in evaluation representation. Second, these a limbs are input to a second path beginning with the iNTT step3.1, so that the extension limbs can be generated. Once these extension limbs are generated, they are used to complete the KSKIP operation at KSKIP step4.

Therefore, with this datapath modification, operation avoids writing the limbs to off-chip memory in coefficient representation after the ModUp step, reading the limbs back again into on-chip memory, and converting the limbs into evaluation representation to perform the KSKInProd. The modified datapath not only reduces the number of NTT computations (the most expensive subroutine in Key Switch operation) but also helps alleviate the memory bandwidth bottleneck by reducing memory traffic.

FIG.10shows the modified datapath only for the first three operations, DeComp, ModUp, and KSKIP. The ModDown operation is analogous to the ModUp operation and can use scheduling similar to that shown for ModUp.

Note that splitting KSKInProd into two steps does not change the Key Switch algorithm, only the order in which its steps are performed. The resulting noise from the Key Switch algorithm is identical with or without this reordering.

It is also noted that the improved Key Switch datapath is generally applicable to any FHE scheme, including for example BGV and BFV, that has a similar key switch operation.

FIG.11is a simplified flow chart for an example application of linear regression (LR) training for binary classification over a set of data. The important aspect here is the iterative nature of the training process and its relation to FHE bootstrapping. In one example, an LR model is trained for 30 iterations, each including one extended period of learning50which concludes with a corresponding update of the LR model. As indicated, FHE-based computations are used in this period50, and then a bootstrapping operation is performed at52before a next iteration is begun.

CKKS FHE and Associated Parameters

In the approach herein, FPGAs in particular are contemplated as they enable the design of custom hardware solutions that provide practical performance that can outperform CPU/GPU solutions, which at the same time being comparatively inexpensive relative to ASIC solutions. Use of FPGAs also provides a quick turnaround time for design updates, providing resilience to future FHE algorithm changes. The disclosed example supports the Cheon-Kim-Kim-Song (CKKS) FHE scheme in particular. FAB makes use of state-of-the-art analysis of the bootstrapping algorithm to design the FHE operations and select parameters that are optimized for the hardware constraints. This allows FAB to support practical FHE parameter sets (i.e. parameters large enough to support bootstrapping) without being bottlenecked by main-memory bandwidth, and without sacrificing computing efficiency.

In one example, FAB is architected for the Xilinx Alveo U280 FPGA accelerator card containing High Bandwidth Memory (HBM2). FAB is highly resource efficient, requiring only 256 functional units, where each functional unit supports various modular arithmetic operations. FAB exploits maximal pipelining and parallelism by utilizing these functional units per the computational demands of the FHE operations. FAB also makes efficient use of limited memory resources (e.g., 43 MB on-chip memory and 2 MB register files) to manage the >100 MB working dataset. FAB leverages a smart operation scheduling to enable high data reuse and prefetching of the required datasets from global memory without stalling the functional units. The smart scheduling evenly distributes the accesses to global memory to efficiently utilize the limited main memory bandwidth through homogeneous memory traffic.

In one example, a CKKS implementation as set forth in detail in the Provisional Application Section 2 is supported. This example utilizes the following parameter types and specific values:

ExampleParameterDescriptionvalueNNumber of coefficients in ciphertext216polynomialnNumber of plaintext elements inciphertex t(n ≤ N/2)QFull modulus of ciphertext coefficientqPrime modulus and a limb of Qlogq = 54(i.e., 54-bitlimbs)LMaximum number of limbs in ciphertext23lCurrent number of limbs in ciphertextdnumNumber of digits in switching key3aNumber of limbs that comprise a singledigit in the key-switching decomposition(fixed throughout computation)PProduct of the extension limbs added forthe raised modulus. There are a + 1extension limbs.fftIterMultiplicative depth of linear transform4in bootstrapping.
System/Device Realizations

There are several types of potential realizations of the disclosed technique. One realization is a physical computing unit encompassing one or more FPGAs that can run the FHE compute solution. Such a unit may be plugged into existing data centers using either PCIe slot or through high-speed network connection. In another realization, there could be an efficient mapping of FHE compute applications written in a high-level programming language (e.g., C/C++) to an FPGA. An existing FHE compiler/transpiler can be used to translate the program written in any programming language to an intermediate representation (IR) and then map the IR to an FPGA. A third potential realization would be a soft IP version having an entire software stack and RTL code base with mapping directly to FPGA-based accelerators such as already deployed on cloud servers.

The disclosure herein demonstrates the performance improvement for CKKS FHE scheme that supports operations on real numbers. The technique can be extended to other FHE schemes like BGV and BFV as these schemes have similar overall mathematical structure. Thus, support can be enabled for operations on integers as well and a wide variety of applications. Moreover, the technique can be implemented on different types of FPGAs beyond the specific example of a Xilinx Alveo U280 FPGA board. The design is generally parameterized, meaning that based on the underlying FPGA various parameters like datapath bitwidth can be fine-tuned to leverage specific resources on the FPGA. Furthermore, to boost performance of an application, the technique can be scaled to multiple FPGAs by running a similar set of operations on multiple ciphertexts in parallel.

While various embodiments of the invention have been particularly shown and described, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention as defined by the appended claims.