Closing the gap between privacy and computation time
In a world of ever-increasing data sharing, security and privacy are of utmost importance.
SRI International’s Computer Science Laboratory (CSL) plays a significant role in enhancing data safety and privacy through several public and commercial initiatives. SRI’s CSL combines the forces of computer scientists, electrical engineers, cybersecurity and cryptography researchers in an interdisciplinary team with public support to develop more effective data privacy and security systems.
A recent focus area for the lab is fully homomorphic encryption (FHE). FHE allows users to perform complex calculations on encrypted sensitive and private data stored in the cloud without the decryption key. This greatly reduces the risk of compromised data security and privacy.
SRI leads a stellar interdisciplinary team
SRI assembled a team of world-class computer science and electrical engineering experts to work on an accelerator design for encrypted computing to evaluate neural networks and other computations involved in machine learning. Leading the project is Karim Eldefrawy, a Principal Computer Scientist within CSL who has an understanding of both computer science and digital hardware based on 15 years of experience in cybersecurity and cryptography and a background in electrical engineering.
In addition to cryptography researchers and colleagues at CSL, the team includes members from MIT (Prof. Daniel Sanchez, Prof. Srini Devadas and graduate students Nikola Samardzic and Axel Feldman) and the University of Michigan (Prof. Chris Peikert and Prof. Ronald Dreslinski). In addition to the academics, the team also includes major microprocessor and chip manufacturers and open-source software organizations such as Arm Ltd (led by Dr. Hugo Vincent), Linaro (led by Joakim Bech) and Granite Mountain Technologies (led by Prof. Ken Stevens).
The challenge of prohibitive overheads in current architectures
There are significant benefits to being able to perform complex computations on encrypted data while preserving the privacy and security of information used in several application domains such as machine learning, genomic analysis, information retrieval and analysis of data sets.
Ensuring data authenticity, integrity and privacy typically come at a high cost, however. While the cloud provides the most practical and cost-effective storage of large quantities of information, developing architectures that prevent data breaches and protect individual identities in a big, amorphous data cloud can be complex and expensive.
Homomorphic encryption — a form of encryption that allows for computations on encrypted data without needing to decrypt it first — has long been researched as a technology that could solve the problem of ensuring both privacy of the data and accuracy of computation. However, practical use of fully homomorphic encryption was limited due to the processing time required to operate on encrypted data significantly exceeding the time needed for unencrypted data. In other words, there was a (theoretical) solution to the problem, but the technology to carry it out was prohibitively resource-intensive and expensive.
Partial homomorphism (such as the type provided by the classical RSA public-key encryption scheme) was the first step. Partial homomorphism enables the performance of limited types of operations (i.e., only multiplications in the case of RSA) on data while maintaining its privacy and security. However, moving toward FHE required advancements in multiple areas, including theoretical computer science, cryptography, algorithms, computer architecture and microprocessor design.
A system-based approach
To help bridge the gap between partial and full homomorphism, SRI’s team in the DARPA DPRIVE program developed CraterLake, a new accelerator architecture that makes the computational burden possible by increasing the number of processing bits. While standard processors are limited to 32- or 64-bit processing, CraterLake dramatically increases the effective number of bits (effectively in the thousands), significantly increasing the processing capability and allowing for major speedups in executing FHE programs.
The team broke down the thousands of bits required to represent the encrypted ciphertext into smaller 28-bit chunks that the hardware could operate on in parallel, simulating a processor that could handle many more bits. This innovation initially improved performance over standard processors/CPUs by 5400x to 17000x (as shown in the first research paper [F1] in 2021, which was selected for the IEEE Micro’s Top Picks from the Computer Architecture Conferences). The latest CraterLake design achieves another 10x improvement over [F1], as shown in the second CraterLake research paper presented at the 2022 International Symposium on Computer Architecture. CraterLake enables programs with unbounded multiplicative depth, thus unlocking the full power of FHE.
Applied benefits of FHE accelerators
This innovation increases known processing capabilities to execute arbitrary FHE programs while strengthening data privacy and security. As an example of what is possible, FHE enables machine learning systems to operate on encrypted data sets to preserve user privacy. Storing encrypted data on a cloud server and performing computations directly on it also avoids back-and-forth communication between servers and users. Such communication can be prohibitive in certain settings and is often required in other privacy-preserving technologies, such as secure multi-party computation (MPC). MPC has been deployed in recent years and enables parties to jointly distribute and perform computations on data while maintaining a high level of security and privacy, but it requires multiple parties to be online for the distributed computation.
SRI’s work at the intersection of computer science and hardware verification
SRI was crucial in unlocking collaboration to facilitate the formal hardware verification of FHE provided by CraterLake and its predecessor, F1. Because of SRI’s interdisciplinary approach and expert network of collaborators, it is able to address a complex problem such as FHE, which requires expertise in math, cryptography, microprocessor engineering, system architecture and software development. SRI also has a long history with top-tier commercial partners, ensuring the best opportunity for the wide use and deployment of its innovations.
What lies beyond FHE? The CraterLake design supports multiple FHE schemes, most notably CKK and BGV. Future extensions of CraterLake could accelerate other cryptographic primitives such as Lattice-based post-quantum encryption and signature schemes (currently in the final stages of standardization by NIST) and post-quantum zero-knowledge proof systems.
With the development of CraterLake to accelerate FHE, any data can be encrypted, uploaded to a public cloud server and given computational instructions while preserving data privacy and ensuring that even cloud operators cannot see the input data nor the calculated outputs. And this can be performed without requiring the severs to have access to the cryptographic keys and does not require an infrastructure with overly prohibitive overhead costs in computation time, memory and bandwidth.
This work was partially funded by DARPA. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government; performance claims have not been validated by DARPA.
- A Fast and Programmable Accelerator for Fully Homomorphic Encryption (Extended Version) (arxiv.org)
- CraterLake: A Hardware Accelerator for Efficient Unbounded Computation on Encrypted Data (acm.org)