Homomorphic encryption (HE) enables computations on encrypted data by concealing information under noise for security. However, the process of bootstrapping, which resets the noise level in the ciphertext, is computationally expensive and requires a large bootstrapping key. The TFHE scheme offers a faster and programmable bootstrapping algorithm called PBS, crucial for security-focused applications like machine learning. Nevertheless, the current TFHE scheme lacks support for ciphertext packing, resulting in low throughput. This work thoroughly analyzes TFHE bootstrapping, identifies the bottleneck in GPUs caused by the blind rotation fragmentation problem, and proposes a hardware TFHE accelerator called Strix. Strix introduces a two-level batching approach to enhance the batch size in PBS, utilizes a specialized microarchitecture for efficient streaming data processing, and incorporates a fully-pipelined FFT microarchitecture to improve performance. It achieves significantly higher throughput than state-of-the-art implementations on both CPUs and GPUs, outperforming existing TFHE accelerators by a factor of 7.4.
호모모르피즘 암호화(HE)는 보안을 위해 노이즈 아래에 정보를 숨김으로써 암호화된 데이터에서의 계산을 가능하게 합니다. 그러나 노이즈 수준을 초기화하는 부트스트래핑 과정은 연산 비용이 많이 들며 큰 부트스트래핑 키가 필요합니다. TFHE 방식은 머신 러닝과 같은 보안 중심의 응용 프로그램에서 필수적인 더 빠르고 프로그래밍 가능한 부트스트래핑 알고리즘인 PBS를 제공합니다. 그러나 현재의 TFHE 방식은 암호문 패킹을 지원하지 않아 처리량이 낮습니다. 본 연구는 TFHE 부트스트래핑을 철저히 분석하고, GPU에서의 맹목적 회전 파편화 문제로 인한 병목 현상을 식별하며, Strix라는 하드웨어 TFHE 가속기를 제안합니다. Strix는 PBS에서 배치 크기를 향상시키기 위해 두 수준의 배치 방식을 도입하며, 효율적인 스트리밍 데이터 처리를 위한 전용 마이크로아키텍처를 활용하고, 성능을 향상시키기 위해 완전 파이프라인화된 FFT 마이크로아키텍처를 통합합니다. 이는 CPU와 GPU에서 최첨단 구현체보다 훨씬 높은 처리량을 달성하며, 기존의 TFHE 가속기보다 7.4배 우수한 성능을 발휘합니다.