Intel Homomorphic Encryption (HE) Acceleration Library

Intel:registered: HE Acceleration Library is an open-source library which provides efficient implementations of integer arithmetic on Galois fields. Such arithmetic is prevalent in cryptography, particularly in homomorphic encryption (HE) schemes. Intel HE Acceleration Library targets integer arithmetic with word-sized primes, typically 30-60 bits. Intel HE Acceleration Library provides an API for 64-bit unsigned integers and targets Intel CPUs. For more details on Intel HE Acceleration Library, see our whitepaper. For tips on best performance, see Performance.

Contents

• Intel Homomorphic Encryption (HE) Acceleration Library
  • Contents
  • Introduction
  • Building Intel HE Acceleration Library
    • Dependencies
    • Compile-time options
    • Compiling Intel HE Acceleration Library
      • Linux and Mac
      • Windows
  • Performance
  • Testing Intel HE Acceleration Library
  • Benchmarking Intel HE Acceleration Library
  • Using Intel HE Acceleration Library
  • Debugging
  • Threading
• Community Adoption
• Documentation
• Contributing
  • Repository layout
• Citing Intel HE Acceleration Library
  • Version 1.2
  • Version 1.1
  • Version 1.0
• Contributors

Introduction

Many cryptographic applications, particularly homomorphic encryption (HE), rely on integer polynomial arithmetic in a finite field. HE, which enables computation on encrypted data, typically uses polynomials with degree N a power of two roughly in the range N=[2^{10}, 2^{17}]. The coefficients of these polynomials are in a finite field with a word-sized prime, q, up to q~62 bits. More precisely, the polynomials live in the ring Z_q[X]/(X^N + 1). That is, when adding or multiplying two polynomials, each coefficient of the result is reduced by the prime modulus q. When multiplying two polynomials, the resulting polynomials of degree 2N is additionally reduced by taking the remainder when dividing by X^N+1.

The primary bottleneck in many HE applications is polynomial-polynomial multiplication in Z_q[X]/(X^N + 1). For efficient implementation, Intel HE Acceleration Library implements the negacyclic number-theoretic transform (NTT). To multiply two polynomials, q_1(x), q_2(x) using the NTT, we perform the FwdNTT on the two input polynomials, then perform an element-wise modular multiplication, and perform the InvNTT on the result.

Intel HE Acceleration Library implements the following functions:

• The forward and inverse negacyclic number-theoretic transform (NTT)
• Element-wise vector-vector modular multiplication
• Element-wise vector-scalar modular multiplication with optional addition
• Element-wise modular multiplication

For each function, the library implements one or several Intel(R) AVX-512 implementations, as well as a less performant, more readable native C++ implementation. Intel HE Acceleration Library will automatically choose the best implementation for the given CPU Intel(R) AVX-512 feature set. In particular, when the modulus q is less than 2^{50}, the AVX512IFMA instruction set available on Intel IceLake server and IceLake client will provide a more efficient implementation.

For additional functionality, see the public headers, located in include/hexl

Building Intel HE Acceleration Library

Intel HE Acceleration Library can be built in several ways. Intel HE Acceleration Library has been uploaded to the Microsoft vcpkg C++ package manager, which supports Linux, macOS, and Windows builds. See the vcpkg repository for instructions to build Intel HE Acceleration Library with vcpkg, e.g. run vcpkg install hexl. There may be some delay in uploading latest release ports to vcpkg. Intel HE Acceleration Library provides port files to build the latest version with vcpkg. For a static build, run vcpkg install hexl --overlay-ports=/path/to/hexl/port/hexl --head. For dynamic build, use the custom triplet file and run vcpkg install hexl:hexl-dynamic-build --overlay-ports=/path/to/hexl/port/hexl --head --overlay-triplets=/path/to/hexl/port/hexl. For detailed explanation, see instruction for building vcpkg port using overlays and use of custom triplet provided by vcpkg.

Intel HE Acceleration Library also supports a build using the CMake build system. See below for the instructions to build Intel HE Acceleration Library from source using CMake.

Dependencies

We have tested Intel HE Acceleration Library on the following operating systems:

• Ubuntu 20.04
• macOS 10.15 Catalina
• Microsoft Windows 10

Intel HE Acceleration Library requires the following dependencies:

| Dependency | Version | |-------------|----------------------------------------------| | CMake | >= 3.13 * | | Compiler | gcc >= 7.0, clang++ >= 5.0, MSVC >= 2019 |

* For Windows 10, you must check whether the version on CMake you have can generate the necessary Visual Studio project files. For example, only from CMake 3.14 onwards can MSVC 2019 project files be generated.

Compile-time options

In addition to the standard CMake build options, Intel HE Acceleration Library supports several compile-time flags to configure the build. For convenience, they are listed below:

| CMake option | Values | Default | | | ------------------------------| ---------| --------| ----------------------------------------------------------- | | HEXL_BENCHMARK | ON / OFF | ON | Set to ON to enable benchmark suite via Google benchmark | | HEXL_COVERAGE | ON / OFF | OFF | Set to ON to enable coverage report of unit-tests | | HEXL_SHARED_LIB | ON / OFF | OFF | Set to ON to enable building shared library | | HEXL_DOCS | ON / OFF | OFF | Set to ON to enable building of documentation | | HEXL_TESTING | ON / OFF | ON | Set to ON to enable building of unit-tests | | HEXL_TREAT_WARNING_AS_ERROR | ON / OFF | OFF | Set to ON to treat all warnings as error |

Compiling Intel HE Acceleration Library

To compile Intel HE Acceleration Library from source code, first clone the repository and change directories to where the source has been cloned.

Linux and Mac

The instructions to build Intel HE Acceleration Library are common to Linux and MacOS.

Then, to configure the build, call

cmake -S . -B build

adding the desired compile-time options with a -D flag. For instance, to use a non-standard installation directory, configure the build with

cmake -S . -B build -DCMAKE_INSTALL_PREFIX=/path/to/install

Or, to build Intel HE Acceleration Library as a shared library, call

cmake -S . -B build -DHEXL_SHARED_LIB=ON

Then, to build Intel HE Acceleration Library, call

cmake --build build

This will build the Intel HE Acceleration Library library in the build/hexl/lib/ directory.

To install Intel HE Acceleration Library to the installation directory, run

cmake --install build

Windows

To compile Intel HE Acceleration Library on Windows using Visual Studio in Release mode, configure the build via

cmake -S . -B build -G "Visual Studio 16 2019" -DCMAKE_BUILD_TYPE=Release

adding the desired compile-time options with a -D flag (see Compile-time options). For instance, to use a non-standard installation directory, configure the build with

cmake -S . -B build -G "Visual Studio 16 2019" -DCMAKE_BUILD_TYPE=Release -DCMAKE_INSTALL_PREFIX=/path/to/install

To specify the desired build configuration, pass either --config Debug or --config Release to the build step and install steps. For instance, to build Intel HE Acceleration Library in Release mode, call

cmake --build build --config Release

This will build the Intel HE Acceleration Library library in the build/hexl/lib/ or build/hexl/Release/lib directory.

To install Intel HE Acceleration Library to the installation directory, run

cmake --build build --target install --config Release

Performance

For best performance, we recommend using Intel HE Acceleration Library on a Linux system with the clang++-12 compiler. We also recommend using a processor with Intel AVX512DQ support, with best performance on processors supporting Intel AVX512-IFMA52. To determine if your processor supports AVX512-IFMA52, simply look for -- Setting HEXL_HAS_AVX512IFMA printed during the configure step.

See the below table for setting the modulus q for best performance. | Instruction Set | Bound on modulus q | |------------------|----