Generating High-Performance Number Theoretic Transform Implementations for Vector Architectures

Naifeng Zhang, Austin Ebel, Negar Neda, Patrick Brinich, Benedict Reynwar, Andrew G. Schmidt, Mike Franusich, Jeremy Johnson, Brandon Reagen, Franz Franchetti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Fully homomorphic encryption (FHE) offers the ability to perform computations directly on encrypted data by encoding numerical vectors onto mathematical structures. However, the adoption of FHE is hindered by substantial overheads that make it impractical for many applications. Number theoretic transforms (NTTs) are a key optimization technique for FHE by accelerating vector convolutions. Towards practical usage of FHE, we propose to use SPIRAL, a code generator renowned for generating efficient linear transform implementations, to generate high-performance NTT on vector architectures. We identify suitable NTT algorithms and translate the dataflow graphs of those algorithms into SPIRAL's internal mathematical representations. We then implement the entire workflow required for generating efficient vectorized NTT code. In this work, we target the Ring Processing Unit (RPU), a multitile long vector accelerator designed for FHE computations. On average, the SPIRAL-generated NTT kernel achieves a 1.7x speedup over naive implementations on RPU, showcasing the effectiveness of our approach towards maximizing performance for NTT computations on vector architectures.

Original languageEnglish (US)
Title of host publication2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350308600
DOIs
StatePublished - 2023
Event2023 IEEE High Performance Extreme Computing Conference, HPEC 2023 - Virtual, Online, United States
Duration: Sep 25 2023Sep 29 2023

Publication series

Name2023 IEEE High Performance Extreme Computing Conference, HPEC 2023

Conference

Conference2023 IEEE High Performance Extreme Computing Conference, HPEC 2023
Country/TerritoryUnited States
CityVirtual, Online
Period9/25/239/29/23

Keywords

  • code generation
  • Fully homomorphic encryption
  • number theoretic transform
  • SPIRAL
  • vectorization

ASJC Scopus subject areas

  • Control and Optimization
  • Modeling and Simulation
  • Artificial Intelligence
  • Computer Science Applications
  • Software
  • Media Technology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Generating High-Performance Number Theoretic Transform Implementations for Vector Architectures'. Together they form a unique fingerprint.

Cite this