Bootstrapping-Oriented Software and Hardware Solutions for Accelerating Fully Homomorphic Encryption = 완전동형암호 가속을 위한 부트스트래핑 지향 소프트웨어 및 하드웨어 솔루션 설계

다국어 초록 (Multilingual Abstract)

With increasing awareness of data security and privacy in cloud-based services, homomorphic encryption (HE) has emerged as a promising solution for securely outsourcing computation. HE enables direct computation on encrypted data (ciphertext) without requiring decryption, thereby preventing potential privacy breaches during cloud processing.

However, since HE relies on noisy encryption schemes in which noise accumulates with each operation, early-stage HE schemes could support only a limited number of computations before the noise corrupted the data. To overcome this limitation, fully homomorphic encryption (FHE) introduces a bootstrapping operation that refreshes the accumulated noise without decrypting the data, thereby enabling an unlimited number of computations on encrypted data. Bootstrapping is an essential operation for applying HE to real-world workloads. Unfortunately, bootstrapping incurs substantial computational and memory bandwidth overhead, making HE less practical in many scenarios.

In this dissertation, we present hardware solutions to make HE more practical by focusing on accelerating the bootstrapping process. As a starting point, we accelerate the Number Theoretic Transform (NTT)—a core primitive responsible for the majority of computational overhead in HE operations—on a popular computing platform: the GPU.
With
Through in-depth analysis, we identify that NTT computations on GPUs suffer significantly from memory bandwidth bottlenecks, particularly under large parameter settings required to support bootstrapping.
To address this, we propose a data reuse strategy that leverages the hierarchical memory system of modern GPUs to substantially reduce off-chip memory access.
Furthermore, we introduce efficient on-the-fly generation methods for the constants used in NTT, yielding additional reductions in memory access and improving overall performance.
However, in broad scope, computing bootstrapping on GPU still suffers from
high memory bandwidth bottleneck due to memory expansion caused by HE encryption.

To overcome this challenge, we propose BTS—a Bootstrappable, Technology-driven, Secure accelerator architecture for FHE. We identify key challenges in supporting bootstrapping within hardware accelerators and analyze the associated off-chip memory bandwidth and computational requirements. In particular, considering the limitations of modern memory technologies, we determine parameter sets for homomorphic encryption that are well-suited for efficient FHE acceleration.

Based on the insights from our analysis, we design BTS to exploit the inherent parallelism of HE operations by deploying a large grid of processing elements. We detail the architectural and microarchitectural design of BTS, including a network-on-chip (NoC) optimized for the deterministic communication patterns characteristic of FHE workloads. BTS achieves 5,556× and 1,306× speedups over CPU implementations on ResNet-20 and logistic regression, respectively, while occupying 373.6mm² of chip area and consuming up to 163.2W of power.

국문 초록 (Abstract)

클라우드 기반 서비스에서 데이터 보안과 프라이버시에 대한 인식이 높아짐에 따라, 연산을 안전하게 외부에 위탁할 수 있는 방안으로 동형암호(Homomorphic Encryption, HE)가 주목받고 있다. HE는 암호문 상태에서 직접 연산을 수행할 수 있어, 클라우드 처리 중 발생할 수 있는 개인정보 유출을 방지할 수 있다.

하지만 HE는 연산이 반복될수록 잡음(noise)이 누적되는 암호 방식에 기반하고 있어, 초기의 HE 스킴은 제한된 횟수의 연산만을 허용하는 한계가 있었다. 이러한 제약을 극복하기 위해 완전동형암호(Fully Homomorphic Encryption, FHE)에서는 누적된 잡음을 제거하는 부트스트래핑(bootstrapping) 기법이 도입되었으며, 이를 통해 암호문을 복호화하지 않고도 무제한 연산을 가능하게 한다. 부트스트래핑은 HE를 실제 응용에 적용하기 위해 필수적인 연산이지만, 과도한 연산량과 메모리 대역폭 요구로 인해 실용화에 큰 장애물이 되고 있다.

본 논문에서는 이러한 문제를 해결하기 위해, 부트스트래핑 연산을 중심으로 HE의 실용성을 높일 수 있는 하드웨어 가속 방안을 제시한다. 먼저, HE 연산의 대부분을 차지하는 핵심 연산인 수론적 변환(Number Theoretic Transform, NTT)을 범용 연산 플랫폼인 GPU에서 가속화한다. 분석 결과, 부트스트래핑을 위한 대규모 파라미터 환경에서는 GPU가 메모리 대역폭 병목 현상에 크게 영향을 받는다는 사실을 확인하였다. 이에 따라, 현대 GPU의 계층적 메모리 구조를 활용하여 오프칩 메모리 접근을 줄이는 데이터 재사용 기법을 제안하고, NTT에서 사용하는 상수를 실시간으로 생성하는 방식(on-the-fly generation, OT)도 함께 도입하여 메모리 접근량과 연산 시간을 향상시켰다.

그러나 HE 암호화로 인한 데이터 크기 증가 문제로 인해, GPU 기반의 부트스트래핑은 여전히 메모리 대역폭의 병목 문제를 완전히 해결하지 못하는 한계가 존재한다. 이를 극복하기 위해, 본 논문에서는 FHE를 위한 전용 하드웨어 가속기인 BTS(Bootstrappable, Technology-driven, Secure accelerator)를 제안한다.
BTS는 부트스트래핑 연산을 하드웨어에서 효율적으로 처리하기 위한 구조적 과제를 분석하고, 이에 따른 연산량과 오프칩 메모리 요구사항을 정량적으로 평가한다. 특히, 최신 메모리 기술의 한계를 고려하여 FHE에 적합한 파라미터 셋을 도출하고, 이러한 분석을 바탕으로 HE 연산의 병렬성을 극대화할 수 있는 구조를 설계한다. 구체적으로는, 대규모 처리 유닛 그리드와 FHE 연산의 결정적 통신 패턴에 최적화된 온칩 네트워크(Network-on-Chip, NoC)를 포함한 BTS 아키텍처 및 마이크로아키텍처 설계를 수행한다.
최종적으로, BTS는 ResNet-20과 로지스틱 회귀 작업에서 각각 5,556배 및 1,306배의 성능 향상을 범용 CPU 대비 달성하였다.

목차 (Table of Contents)

• Abstract i
• Contents iv
• List of Tables vii
• List of Figures viii
• 1 Introduction 1
• 1.1 Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs 3
• 1.2 BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption 4
• 1.3 Research Contribution 5
• 1.4 Outline 6
• 2 Background and Motivation 8
• 2.1 Homomorphic Encryption (HE) 8
• 2.2 CKKS: An Emerging HE Scheme 9
• 2.2.1 Primitive Operations (ops) of CKKS 11
• 2.2.2 Multiplicative Level and HE Bootstrapping 13
• 2.2.3 Modern Algorithmic Optimizations in CKKS and Amortized Multiplication Time per Slot 14
• 2.2.4 Interplay between Key CKKS Parameters 16
• 2.2.5 Computational Breakdown of HE Ops 17
• 3 Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs 21
• 3.1 An Overview of GPUs 22
• 3.2 Comparing NTT with DFT 24
• 3.3 Analysis of Common Optimizations 29
• 3.3.1 Batching NTT with Various Batch Sizes 29
• 3.3.2 Register-based High Radix Implementation 30
• 3.3.3 Shared Memory (SMEM) Implementation 32
• 3.4 Accelerating NTT using On-the-fly Twiddling (OT) 38
• 3.5 Evaluation 40
• 3.6 Discussion: Impacts of Hardware Advance on the Computational Characteristics of NTT 43
• 4 BTS: An Accelerator for Bootstrappable Fully Homomorphic Encryption 49
• 4.1 Technology-driven Parameter Selection of Bootstrappable Accelerators 49
• 4.1.1 Technology Trends Regarding Memory Hierarchy 49
• 4.1.2 Realistic Oracle of HE Accelerator Execution Time 50
• 4.2 Desirable Target CKKS Parameters for HE Accelerators 51
• 4.3 Architecting BTS 52
• 4.3.1 Limitations in Prior Works and the Balanced Design of BTS 53
• 4.3.2 BTS Organization Exploiting Data Parallelism 55
• 4.4 BTS Microarchitecture 57
• 4.4.1 Datapath for (i)NTT 58
• 4.4.2 Base Conversion Unit (BConvU) 60
• 4.4.3 Scratchpad 61
• 4.4.4 Network-on-Chip (NoC) Design 62
• 4.5 Evaluation 63
• 4.5.1 Hardware Modeling of BTS 63
• 4.5.2 Experimental Setup 64
• 4.5.3 Performance and Efficiency of BTS 66
• 4.6 Discussion 73
• 5 Related Work 75
• 6 Conclusion 77
• 6.1 Conclusion 77
• REFERENCES 79
• 국문초록 99