Bespoke Asynchronous Silicon-Accelerated LWE Intrinsics through Software/Hardware Codesign (BASALISC)
This Galois-led project, part of DARPA’s Data Protection in Virtual Environments (DPRIVE) program, aims to accelerate the “last mile” of data encryption with purpose-built ASICs that accelerate fully homomorphic encryption (FHE) computations. A key aim of the project is that our hardware should be cloud-ready—suitable for deployment in typical cloud server installations—to maximize commercial and government transition potential. This project seeks to bring homomorphic encryption performance within a factor of 10 of computing “in the clear,” something not possible using current software-only or hardware-accelerated approaches.
Sensitive financial, health, and identity data is protected by encryption methods like the Advanced Encryption Standard (AES), which translates data into a code that can only be decrypted by a special key. However, data must be decrypted for computation to occur. Once “in the clear,” that data is vulnerable to compromise.
Fully homomorphic encryption (FHE) helps ensure that this “last mile” of data confidentiality is secure, by keeping data encrypted even when computation is occurring. Data is encrypted by data providers before being transmitted (for example, to a cloud server) for computation. Computation can then take place, and encrypted results can be returned for decryption. However, current software-based FHE techniques are not efficient enough to make this level of security practical. DARPA’s DPRIVE program was developed to “design and implement a hardware accelerator for FHE computations that aims to significantly reduce the current computational burden to drastically speed up FHE calculations.”
Galois proposes the Bespoke Asynchronous Silicon-Accelerated LWE Intrinsics through Software/Hardware Codesign (BASALISC) project to answer this challenge. BASALISC will realize both hardware and software innovations, bringing together Galois’s core strengths in homomorphic encryption, formal verification, advanced ASIC design, and compiler research to create an accelerator that maximizes efficient FHE performance while remaining flexible enough to support diverse FHE parameter settings. The project derives its inspiration from the mythical basilisk that could repel threats with a glance, essentially protecting its own “last mile.”
Software/Hardware Codesign
Galois believes BASALISC will succeed by taking a software/hardware co-design approach, and by formally verifying the basic computation engines included in the BASALISC design.
Formal Verification
Galois’s Cryptol domain-specific language will be central to providing correct-by-construction circuit synthesis and proofs of correct operation for the accelerator.
Asynchronous Circuit Performance
In order to achieve our target performance at reasonable power and area cost, Galois plans to use asynchronous circuit design techniques for the core functionality of BASALISC. Asynchronous designs take variable amounts of time to compute, allowing each computation to run “as fast as it can,” rather than being limited by the worst case.
On-Chip Data Movement
Traditional CPU architectures are designed to efficiently move and compute on small data elements—64 bits or so. However, the mechanisms used to enable computation on encrypted data via FHE result in individual data elements that are much larger, even megabytes in size. To address this challenge in BASALISC, Galois plans to create its own dataflow microarchitecture designed to route data “just in time” to independently operating processing elements. As part of this dataflow engine Galois will develop optimized access sequences to support commonly used optimizations, such as the “butterfly” sequences needed to implement the Discrete Fourier Transforms used in homomorphic multiplication.
Planned Results
Galois believes an overall performance gain of ~10,000X is feasible relative to current software-based FHE solutions. Roughly, we expect the following key gains:
- 300X from ASIC-based hardware acceleration;
- 2X or more from use of asynchronous instead of clocked logic;
- 10X from large arithmetic word size operations in hardware, foregoing the need for unwieldy residue number system representations;
- 3.5X from an optimized dataflow approach that maximizes utilization of arithmetic functional units; and
- 2X from optimized memory access patterns and vectorization.
BASALISC is designed to substantially enhance the performance of FHE for key application classes, resulting in a potential sea change for FHE adoption.
Read the announcement of the BASALISC project at our blog.
This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR0011-21-C-0034.
Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA).
