Semi-custom accelerator device for bootstrappable fully homomorphic encryption
An FPGA-based accelerator for bootstrappable fully homomorphic encryption (FHE) employs (1) acceleration of scalar arithmetic operations using a multi-word approach for efficient utilization of standard-width components (multipliers/adders) on custom-width operands; (2) a performant, shift-based modular reduction technique that avoids the need for expensive multipliers; (3) an improved datapath for an expensive Key Switch operation; and (4) an efficient organization of on-chip memory for storing custom-width operands and supplying them at high bandwidth to computation units.
1. A computing device comprising an FPGA semi-custom accelerator device for hardware acceleration of modular arithmetic operations in a cryptography system employing a cyphertext modulus Q with associated operand bit-width log q ( v q), the semi-custom accelerator device including an array of N sets of functional units configured for parallel operation on corresponding ones of N streams of c-bit-width coefficients and producing corresponding ones of N streams of results, comprising:
an interface to a host CPU configured to execute a fully homomorphic encryption (FHE) application using the FPGA semi-custom accelerator device for bootstrappable FHE (FAB) operations with selection of parameters that are optimized for hardware constraints;
on-chip memory for storing v q-width operands and v q-width results, wherein the memory has one or more banks each organized as a two-dimensional arrangement of fixed-size memory units of bit-width m≠c, the two-dimensional arrangement having a width W and depth D of memory units, W being selected to enable storage of an integer number Wm/c of the c-bit-width coefficients across the width of the arrangement, D being selected as a quotient N/(Wm/c) to enable simultaneous retrieval of N coefficients in a single memory access cycle; and
an arithmetic unit coupled to the memory to receive the v q-width operands and produce the v q-width results, the arithmetic unit including (1) a plurality p of standard arithmetic blocks having v q/p bit-width, the arithmetic blocks operating on corresponding distinct v q/p-width portions of the v q-width operands and producing corresponding distinct v q/p-width portions of the v q-width results, and (2) custom logic interconnecting the arithmetic blocks in a manner providing for an overall v q-width arithmetic operation to produce the v q-width results from the v q-width operands,
wherein the array of N sets of functional units efficiently utilizes the memory units of the FPGA on-chip memory and maps data width of the coefficients to that of the memory banks to enable storage of up to a predetermined amount of data on-chip to reduce resource overhead.
2. The computing device of claim 1 , wherein p=2.
3. The computing device of claim 1 , wherein the custom logic includes (1) pipeline registers for receiving respective v q/p-width portions of modulus values and time-aligning them with respective outputs of the p arithmetic blocks, (2) additional standard arithmetic blocks for operating on respective time-aligned v q/p-width portions of modulus values and outputs of the p arithmetic blocks to produce respective portions of modulus-reduced arithmetic results, and (3) selection logic for selecting between the outputs of the p arithmetic blocks and the modulus-reduced arithmetic results to produce the v q-width results.
4. The computing device of claim 3 , wherein the selection logic is configured to realize a multi-condition selection based on values of respective carry outputs from the standard p arithmetic blocks, the multi-condition selection being based partly on a most-significant carry output being asserted and there being corresponding selection-specific mathematical relationships between the time-aligned v q/p-width portions of modulus values and the respective outputs of the p arithmetic blocks.
5. The computing device of claim 1 , wherein the FPGA semi-custom accelerator device further includes:
a modular reduction unit coupled to the arithmetic unit to receive (2* v q−1)-width non-reduced values and produce corresponding v q-width reduced values, the modular reduction unit including (1) a shifter operative to produce a first intermediate value v1 by a predetermined number of shifts of a second intermediate value v2, (2) an adder to produce v2 by adding v1 to a pre-computed modulus adder value, and (3) second custom logic to (a) first initialize v2 to a most-significant part of a non-reduced value from the arithmetic unit, (b) then iteratively operate the shifter and adder over successive cycles to produce a final second intermediate value v2f, and (c) then combine v2f with a least-significant part of the non-reduced value from the arithmetic unit to produce the corresponding v q-width reduced value.
6. The computing device of claim 5 , wherein the modular reduction unit is further configured and operative to perform modular reduction with respect to a set of prime elements stored as respective arrays in the memory.
7. The computing device of claim 1 further providing for hardware acceleration of a key switch operation of the FHE application, the key switch operation converting a first ciphertext M1 decryptable under a first key to a same-message second ciphertext M2 decryptable under a distinct second key, wherein:
the memory is further configured for storing operands and results of the key switch operation; and
the FPGA semi-custom accelerator device further includes a set of computing elements including a decomposition unit, an up-modulus unit, an inner product unit, and a down-modulus unit, the decomposition unit configured to generate blocks of first limbs of M1, the inner product unit having first and second sub-units, the first sub-unit configured to perform a first part of an inner product operation on the first limbs from the decomposition unit and producing an intermediate result, the second sub-unit configured to perform a remaining part of the inner product operation using the intermediate result and extended limbs generated by the up-modulus unit from the first limbs, the down-modulus unit configured to perform a modulus-reducing operation on extended-modulus results from the inner product unit to produce M2.
8. The computing device of claim 7 , wherein the first part of the inner product operation includes providing the first limbs in evaluation representation to the up-modulus unit to generate the extended limbs for use in the remaining part of the inner product operation, while avoiding use of off-chip memory for temporarily storing the limbs in coefficient representation after an up-modulus operation.
9. The computing device of claim 1 , wherein the FPGA semi-custom accelerator device further includes an Automorph unit which performs permutation for a Rotate operation of the FHE application.
10. The computing device of claim 9 , wherein the permutation by the Automorph unit includes reading a polynomial from the on-chip memory and store storing the polynomial in a
register file in a permuted order per a given rotation index k.