CiFlow: Dataflow Analysis and Optimization of Key Switching for Homomorphic Encryption

Negar Neda, Austin Ebel, Benedict Reynwar, Brandon Reagen

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

Abstract

Homomorphic encryption (HE) is a privacy-preserving computation technique that enables computation on encrypted data. Today, the potential of HE remains largely unrealized as it is impractically slow, preventing it from being used in real applications. A major computational bottleneck in HE is the key-switching operation, accounting for approximately 70 % of the overall HE execution time and involving a large amount of data for inputs, intermediates, and keys. Prior research has focused on hardware accelerators to improve HE performance, typically featuring large on-chip SRAMs and high off-chip bandwidth to deal with large scale data. In this paper, we present a novel approach to improve key-switching performance by rigorously analyzing its dataflow. Our primary goal is to optimize data reuse with limited on-chip memory to minimize off-chip data movement. We introduce three distinct dataflows: Max-Parallel (MP), Digit-Centric (DC), and Output-Centric (OC), each with unique scheduling approaches for key-switching computations. Through our analysis, we show how our proposed Output-Centric technique can effectively reuse data by significantly lowering the intermediate key-switching working set and alleviating the need for massive off-chip band-width. We thoroughly evaluate the three dataflows using the RPU, a recently published vector processor tailored for ring processing algorithms, which includes HE. This evaluation considers sweeps of bandwidth and computational throughput, and whether keys are buffered on-chip or streamed. With OC, we demonstrate up to 4.16 x speedup over the MP dataflow and show how OC can save 12.25 x on-chip SRAM by streaming keys for minimal performance penalty.

Original languageEnglish (US)
Title of host publicationProceedings - 2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages61-72
Number of pages12
ISBN (Electronic)9798350376388
DOIs
StatePublished - 2024
Event2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024 - Indianapolis, United States
Duration: May 5 2024May 7 2024

Publication series

NameProceedings - 2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024

Conference

Conference2024 IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2024
Country/TerritoryUnited States
CityIndianapolis
Period5/5/245/7/24

Keywords

  • Accelerator
  • Fully Homomorphic Encryption
  • Key-switching

ASJC Scopus subject areas

  • Information Systems
  • Software
  • Safety, Risk, Reliability and Quality
  • Artificial Intelligence
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'CiFlow: Dataflow Analysis and Optimization of Key Switching for Homomorphic Encryption'. Together they form a unique fingerprint.

Cite this