Paper 2019/1066

HEAX: An Architecture for Computing on Encrypted Data

M. Sadegh Riazi, Kim Laine, Blake Pelton, and Wei Dai

Abstract

With the rapid increase in cloud computing, concerns surrounding data privacy, security, and confidentiality also have been increased significantly. Not only cloud providers are susceptible to internal and external hacks, but also in some scenarios, data owners cannot outsource the computation due to privacy laws such as GDPR, HIPAA, or CCPA. Fully Homomorphic Encryption (FHE) is a groundbreaking invention in cryptography that, unlike traditional cryptosystems, enables computation on encrypted data without ever decrypting it. However, the most critical obstacle in deploying FHE at large-scale is the enormous computation overhead. In this paper, we present HEAX, a novel hardware architecture for FHE that achieves unprecedented performance improvement. HEAX leverages multiple levels of parallelism, ranging from ciphertext-level to fine-grained modular arithmetic level. Our first contribution is a new highly-parallelizable architecture for number-theoretic transform (NTT) which can be of independent interest as NTT is frequently used in many lattice-based cryptography systems. Building on top of NTT engine, we design a novel architecture for computation on homomorphically encrypted data. We also introduce several techniques to enable an end-to-end, fully pipelined design as well as reducing on-chip memory consumption. Our implementation on reconfigurable hardware demonstrates 164-268× performance improvement for a wide range of FHE parameters.

Note: To appear in the proceedings of the twenty-fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) 2020.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Fully Homomorphic EncryptionPrivacy-Preserving Machine LearningComputing on Encrypted DataSecurityCloudHigh-Performance Architecture
Contact author(s)
sadeghriazi @ gmail com
History
2020-01-22: last of 2 revisions
2019-09-23: received
See all versions
Short URL
https://ia.cr/2019/1066
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1066,
      author = {M.  Sadegh Riazi and Kim Laine and Blake Pelton and Wei Dai},
      title = {HEAX: An Architecture for Computing on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1066},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1066}},
      url = {https://eprint.iacr.org/2019/1066}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.