Tech Briefs

Improving the efficiency and scalability of Fully Homomorphic Encryption (FHE).

Prior to the Proceed program, the main challenges preventing practical demonstrations and use of Fully Homomorphic Encryption (FHE) were efficiency and scalability. At the start of the Program, the state-of-the-art FHE implementations were both inefficient and not scalable. Work in Scalable Implementation of Primitives for Homomorphic EncRyption (SIPHER) has brought FHE into the realm of practice, bringing several orders of magnitude runtime improvement, and resulting in FHE implementations that can be executed on single and multicore computers (including iPhones). Furthermore, implementation of an FHE hardware accelerator on a Virtex 7 Field Programmable Gate Array (FPGA) can speed up core FHE functions by over three orders of magnitude.

Layered SIPHER approach

Previous FHE schemes were inefficient because the underlying algorithms and their implementations took too long to run at an appropriate level of assured security. Similarly, these FHE schemes were not scalable because memory requirements for encrypting practical-length messages with a reasonable level of security exceed the abilities of highly parallel computation devices like FPGAs. These issues are driven by several factors:

  • The very large keys required for an assured level of security and large expansion of unencrypted plaintext messages to encrypted ciphertext.
  • The large computation depth needed for Bootstrapping/Recryption circuits (an efficiency bottleneck of FHE schemes).
  • The lack of scalable and highly optimized implementations of basic modulus ring operations, which are building blocks used across many lattice FHE schemes.

These activities culminated in many orders of magnitude improvement for these bottlenecks. This revolutionary improvement was achieved by significantly advancing the state of the art in a number of independent focus areas:

  • Multiple foundational improvements in the underlying FHE scheme for more efficient and scalable implementations of FHE operations. These improvements include a new approach to FHE Recryption, and the use of modulus and ring reduction to limit ciphertext expansion.
  • Parallelizable, efficient algorithm design for scalable implementations of basic computational primitives at the core of lattice FHE schemes improving runtime of all FHE operations.
  • Advanced code development approach for efficient and flexible embedded and FPGA implementations.

The accompanying Figure shows the layered SIPHER approach. Software interfaces are provided for optimized basic FHE operations. This lets users construct general applications computing on encrypted data. Core lattice-based primitives form the heart of the FHE implementations. This modular approach allows users to:

  1. construct and experimentally modify multiple implementations of FHE operations and
  2. easily deploy code on FPGA hardware to run the primitives on cost-effective, massively parallel hardware, providing 3 orders of magnitude improvement in basic FHE operation runtimes.

This work was done by David Cousins, Kurt Rohloff, Christopher Peikert, and Daniel Sumorok of Raytheon BBN Technologies for the Air Force Research Laboratory. AFRL-0244

This Brief includes a Technical Support Package (TSP).

SIPHER: SCALABLE IMPLEMENTATION OF PRIMITIVES FOR HOMOMORPHIC ENCRYPTION (reference AFRL-0244) is currently available for download from the TSP library.

Please Login at the top of the page to download.