We design, implement, and deploy post-quantum secure systems.

  • The team investigates post-quantum secure computing systems and cryptosystems, examines their security vulnerabilities, advances algorithmic modifications for efficient hardware implementations, and performs cryptanalysis of these systems.

  • Post-Quantum Cryptography

  • Post-Quantum Hardware Library

  • Lattice-Based Cryptography

  • Code-Based Cryptography

  • Cryptographic Agility

  • Homomorphic Encryption Hardware

  • Zero Knowledge Proof

  • Post-Quantum Transition

  • Post-Quantum Cryptosystems Training

.

Homomorphic-Encryption Accelaration Architectures

Many computing devices are small and limited by power, storage, or compute capabilities, and hence, they will achieve many of their full functionality via coupling with cloud services. However, this gives rise to data privacy issues as sensitive data is stored and computed over the cloud, which at most times, is a shared resource. Homomorphic encryption can be used along with cloud services to perform computations on encrypted data, guaranteeing data privacy. While about a decade's work on improving homomorphic encryption has ensured its practicality, it is still several magnitudes slower than expected, making it expensive and infeasible to use in many medical device applications.

Today’s state-of-the-art processors are not designed to address the computation needs of Fully homomorphic encryption (FHE); new hardware design and implementations are needed to address this challenge - especially in the privacy critical application domain. We are investigating among other research activities, a lattice cryptography processor with configurable parameters using a library-based approach consisting of RLWE-Based homomorphic encryption primitives.
The overhead incurred by using existing architectures like x86-64, GPUs and FPGAs make homomorphic encryption too slow, too inefficient, too expensive or a combination of these to make it practical and widely available - especially in the targeted domain of applications. Our aim is to advance a solution that offers an order of magnitude improvement over current approaches.

Background

Homomorphic encryption is a ground-breaking technique to enable secure private cloud storage and computation services. Homomorphic encryption allows evaluating functions on encrypted data to generate an encrypted result. This result, when decrypted, matches the result of the same operations performed on the unencrypted data. Thus, a data owner can encrypt the data and then send it to cloud for processing. The cloud running the homomorphic encryption based services will perform computations on the encrypted data and send the results back to the data owner. The data owner, having access to the private key, performs the decryption and obtains the result. The cloud does not have access to the private key or the plain data, and, hence, the security concerns related to private data processing on the cloud can be mitigated.

illustration

The idea of homomorphic encryption was first proposed in 1978 by Rivest et al. In 2009, Gentry’s seminal work provided a framework to make fully homomorphic encryption feasible, and almost a decade’s work has now made it practical. While homomorphic encryption has become realistic, it still remains several magnitudes too slow, making it expensive and resource intensive. There are no existing homomorphic encryption schemes with performance levels that would allow large-scale practical usage. Substantial efforts have been put forward to develop full-fledged software libraries for homomorphic encryption. Such libraries include SEAL, Palisade, cuHE, HElib, NFLLib, Lattigo, and HEAAN. All of these libraries are based on the RLWE-based encryption scheme, and they generally implement Brakerski-Gentry-Vaikuntanathan (BGV), FanVercauteren (FV), and Cheon-Kim-Kim-Song (CKKS) homomorphic encryption schemes with very similar parameters.

Design Methodology

Given the fluid state of improvements and new schemes in the field of HE, our design methodology is to provide a hardware suite to support the operations and functionalities common across the different HE algorithms, instead of optimizing the hardware for one particular algorithm. This approach provides flexibility to experiment with new designs and ideas using the core operations for lattices, polynomials, arithmetic, logic, statistical samplings, and finite fields.

Large Arithmetic Word Size (LAWS)

We know that word size directly relates to the signal-to-noise ratio (SNR) of how a ciphertext is stored and manipulated in computation. There currently is no hardware architecture that natively supports the register sizes and/or the execution units performing the fundamental mathematical and logical operations for lattice FHE schemes; to make matters worse, x86 is native to 64-bit registers/operands and GPU architectures are built for 16-bit or 32-bit operands/operators. These intrinsic hardware constructions, which were designed to solve other problems, place a heavy burden in overhead for FHE computations that would natively be performed with registers and operators 1000s of bit wide. We are designing an architecture with LAWS to address this limitation on state of the art hardware today that hinders FHE computation.

ISA Informed by FHE Mathematical Operations

This design methodology seeks to create an ISA based on the core mathematical foundation required by FHE algorithms and informed by the research on FHE schemes on how to optimize them. The large number of finite field operations involved in virtually every known FHE scheme is a major computational bottleneck. The heavy use of sampling from various statistical distributions are also a computational concern that the methodology addresses.

ISA Based Reconfigurable Architecture

It is not yet certain that any known FHE schemes today are optimal nor that the algorithms that will be standardized will be those known today. We therefore want to provide a platform that is able to provide significant performance gains in lattice based FHE as well as the flexibility to experiment with new designs and ideas using the core operations for lattices, polynomials, arithmetic, logic and finite fields that will be available in our platform in the form of instructions.

Fast Arithmetic Hardware Library For RLWE-Based Algorithms

Using our methodology, we introduce an open-source, first-of-its-kind, arithmetic hardware library with a focus on accelerating the arithmetic operations involved in Ring Learning with Error (RLWE)-based homomorphic encryption (HE). We design and implement a hardware accelerator consisting of submodules like Residue Number System (RNS), Chinese Remainder Theorem (CRT), NTT-based polynomial multiplication, modulo inverse, modulo reduction, and all the other polynomial and scalar operations involved in HE.

For all of these operations, wherever possible, we include a hardware-cost efficient serial and a fast parallel implementation in the library. A modular and parameterized design approach helps in easy customization and also provides flexibility to extend these operations for use in most homomorphic encryption applications that fit well into emerging FPGA-equipped cloud architectures.

Using the submodules from the library, we prototype a hardware accelerator on FPGA. The evaluation of this hardware accelerator shows a speed up of approximately 4200× and 2950× to evaluate a homomorphic multiplication and addition respectively when compared to an existing software implementation.

Residue Number System

rns

Barrett Reduction

barrett

NTT Polynomial Multiplication & Theoretic Transform (NTT) modules

ntt

Chinese Remainder Theorem

crt

Modulo Inverse Modules

inverse

Relinearisation Modules

Relinearisatior

Additional Submodules

submodules

Candidate Architecture Design

HERISCV (Homomorphic-Encryption Enabled RISC-V) is a RISC-V accelerator architecture informed by the key arithmetic operations involved in Ring Learning with Error (RLWE) based homomorphic encryption. It provides native ISA support for submodules like Residue Number System (RNS), Chinese Remainder Theorem (CRT), NTT-based polynomial multiplication, modulo inverse, modulo reduction, and the other polynomial and scalar operations. To validate the HERISCV candidate, we are working to use it to accelerate signal processing in the encrypted domain (SPED), especially their core linear algebra kernels.

x

Hardware Downloads

A zip file of the source code for this project is available for download by clicking on the download sign on the right. First, we would like to thank our sponsors who have generously supported these efforts for multiple years now. Second, many thanks to the STAM Center researchers and students, both present and former, who have contributed to the code base. These are open-source projects provided under the MIT License. 
One can also access the project code through the github directory by clicking on the github icon.

Authors

Image

PQC Secure is developed and maintained as a collaborative effort between the members of the Secure Micro Technologies crypto team and members of the Secure, Trusted, and Assured Microelectronics (STAM) Center in the Ira A. Fulton Schools of Engineering at Arizona State University.

Navigations

Copyright ©. All Rights Reserved — Secure Micro Technologies