The safety and security of critical information – whether it is sensitive intellectual property (IP), financial information, personally identifiable information (PII), intelligence insight, or beyond – is of vital importance. Conventional data encryption methods or cryptographic solutions, such as Advanced Encryption Standards (AES), translate data into a secret “code” that can only be decoded by people with access to a decryption key. These methods protect data as it is transmitted across a network or at rest while in storage. Processing or computing on this data however requires that it is first decrypted, exposing it to numerous vulnerabilities and threats.
Fully homomorphic encryption (FHE) offers a solution to this challenge. FHE enables computation on encrypted data, or ciphertext, rather than plaintext, or unencrypted data – essentially keeping data protected at all times. The benefits of FHE are significant, from enabling the use of untrusted networks to enhancing data privacy. Despite its potential, FHE requires enormous computation time to perform even simple operations, making it exceedingly impractical to implement with traditional processing hardware.
FHE relies on a particular type of cryptography called lattice cryptography, which presents complex mathematical challenges to would-be attackers that require technologies beyond the current state of the art to solve. While effective at keeping data protected, the challenge with modern lattice-based FHE is the unavoidable accumulation of noise with each calculation performed.
With each homomorphic computation, a certain amount of noise – or error – is generated that corrupts the encrypted data representation. Once this noise accumulation reaches a certain point, it becomes impossible to recover the original underlying plaintext. Essentially, the data in need of protection is now lost. Computational structures called “bootstrapping” help address this untenable noise accumulation, reducing it to a level that is comparable to the original plaintext, but produces massive compute overhead to perform.
“While a number of solutions have been developed, running FHE in software on standard processing hardware remains a nearly impossible challenge,” said DARPA program manager, Dr. Tom Rondeau.
“Under previous programs like the Programming Computation on Encrypted Data (PROCEED) program, DARPA helped uncover FHE algorithms and proved what could be possible with FHE running on standard CPUs. It also shed light on the compute penalty and critical limitations of the technology. Today, DARPA is continuing to invest in the exploration of FHE, focusing on a re-architecting of the hardware, software, and algorithms needed to make it a practical, widely usable solution.”
DARPA developed the Data Protection in Virtual Environments (DPRIVE) program 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. DPRIVE specifically seeks to reduce the computational run time overhead by many orders of magnitude compared to current software-based FHE computations on conventional CPUs, and accelerate FHE calculations to within one order of magnitude of current performance on unencrypted data.
Key to DPRIVE is the exploration of Large Arithmetic Word Size (LAWS) data representations. LAWS can help address the challenges of noise accumulation with FHE computations and the compute overhead currently encountered using conventional CPU architectures and software, creating enormous improvements in processing speed and computation runtime. Current standard CPUs are based on 64-bit words, which are the units of data that determine a particular processor’s design. Word size directly relates to the signal-to-noise ratio of how encrypted data is stored and processed, as well as the error generated each time an FHE calculation is processed.
Recent studies demonstrate that using words that are thousands of bits long – or LAWS – increases the signal-to-noise ratio in FHE computations, which equates to less noise accumulating with each compute step. This means that more calculations can be performed before the irreparable noise threshold is reached where data can no longer be recovered. It also means the overhead compute burden from costly operations like bootstrapping is dramatically reduced.
Unfortunately, current processing hardware – the traditional 64-bit CPUs – are not built to handle these extremely long word lengths. While virtualization of larger bit word sizes is possible, processing them on traditional CPUs requires reducing them down to word sizes of 64-bits or less while continuing to encounter the associated overhead challenges. DPRIVE seeks to develop a hardware accelerator that can process LAWS without this word size reduction and overhead, instead natively processing on LAWS of 1024 bits or more.
To develop the target accelerator, DPRIVE will explore new integrated approaches to the full FHE hardware and software stacks. Specifically, the program seeks to develop novel approaches to memory management, flexible data structures and programming models, and formal verification methods that ensure the design of the FHE implementation is effective and accurate. As the co-design of FHE algorithms, hardware, and software will be critical to the program, it will require teams with varied technical expertise to take on the research objectives.
“DPRIVE is looking to solve a really hard technical challenge that will involve a deep understanding of mathematics, algorithms, software, hardware, and circuit design. I expect that there are very few organizations that have the needed expertise in all of these areas, which are each critical to the program’s success. As a result, I anticipate very interesting teams will form to cover the breadth of the research,” said Rondeau.
