Triple-Hoisted Baby-Step Giant-Step Linear Transformation over CKKS Homomorphic Encryption and Hardware Accelerator

기술 요약: CKKS 동형 암호화 및 하드웨어 가속기를 위한 3 단계 호스팅된 베이비-스텝 자이언트-스텝 선형 변환

문제 제기
동형 암호화 (HE), 특히 CKKS 방식은 암호화된 데이터에 대한 프라이버시 보호 연산을 가능하게 하여 의료 진단, 금융 분석, 게놈 시퀀싱과 같은 응용 분야에서 중요합니다. HE 기반 신경망 및 트랜스포머의 기본 연산은 선형 변환 (HE-LT) 입니다. 대각선 방법은 행렬의 대각선을 다항식에 패킹하여 HE-LT 를 가능하게 하지만, 고차원 행렬의 경우 금지할 정도로 많은 암호문 회전이 필요합니다. 이러한 회전은 복잡한 자동사상 (automorphism) 과 키 스위칭 연산을 수반하여 상당한 계산 오버헤드와 막대한 오프칩 메모리 접근을 초래합니다. 기존 하드웨어 가속기들은 베이비-스텝 자이언트-스텝 (BSGS) 분해와 더블 호스팅 기법을 활용하더라도 상당한 지연 시간과 메모리 대역폭 병목 현상에 시달리며, 일반적인 파라미터 세트의 경우 수백 기가바이트의 오프칩 데이터 전송이 종종 필요합니다.

방법론
본 논문은 알고리즘적 복잡성과 하드웨어 데이터 흐름 모두를 해결하는 포괄적인 솔루션을 제안합니다:

1. 3 단계 호스팅된 BSGS (TH-BSGS) 알고리즘:
   저자들은 기존 더블 호스팅 BSGS 알고리즘을 확장하여 "베이비 스텝"을 두 계층으로 추가 분해함으로써 3 계층 구조 ($n = n'_1 n'_2 n'_3$) 를 생성합니다.

   • 3 단계 호스팅: 이 기법은 모든 3 계층의 회전에 적용됩니다. 연산을 재배열하고 스위칭 키에 역자동사상을 적용함으로써, 알고리즘은 계층 내 모든 내부 회전에 대해 비용이 많이 드는 Decompose 연산 (비싼 키 스위칭 단계) 을 단 한 번만 수행하도록 보장합니다.
   • 지연된 ModDown: 이전 호스팅 방법과 유사하게 ModDown 연산은 지연되고 결합됩니다. 제안된 설계에서는 ModDown이 중간 곱이 아닌 누적 합에만 적용되어 필요한 모듈러 연산의 수를 크게 줄입니다.
   • 트레이드오프 유연성: 분해 인자 $n'_1, n'_2, n'_3$를 조정함으로써, 알고리즘은 필요한 스위칭 키 (메모리) 와 계산 복잡성 간의 유연한 트레이드오프를 허용합니다.

2. 메모리 최적화 데이터 경로:
   오프칩 메모리 접근으로 인한 지연 시간을 해결하기 위해 TH-BSGS 알고리즘은 6 개의 명확한 단계로 분할됩니다.

   • 단계 분할: 알고리즘은 재구조화되어 오프칩 메모리에서 데이터를 읽은 후, 중간 결과를 온칩에 저장하고 재사용하며, 각 단계가 끝날 때만 다시 기록하도록 설계되었습니다.
   • 데이터 재사용: 스위칭 키와 다항식 리임 (limbs) 의 로딩을 신중하게 스케줄링함으로써 온칩 메모리 재사용을 극대화합니다. 예를 들어, 중간 계층에서는 스위칭 키를 온칩 메모리에 로드하여 여러 반복에 걸쳐 재사용함으로써 트래픽을 최소화합니다.
   • 병렬성 튜닝: 스위칭 키, 다항식 리임, 암호문의 처리를 균형 있게 맞추기 위해 6 개의 병렬성 파라미터 ($m_1$부터 $m_6$까지) 가 도입되었으며, 이는 FPGA 온칩 메모리 (예: Xilinx U280 의 43MB) 의 제약 조건 내에서 설계를 가능하게 합니다.

3. 하드웨어 가속기 아키텍처:
   제안된 알고리즘을 구현하기 위한 효율적인 FPGA 기반 가속기가 설계되었습니다.

   • 최적화된 치환 회로: 자동사상 $\phi_r$을 구현하기 위해 새로운 치환 회로가 도입되었습니다. NTT 도메인에서 자동사상의 특정 속성과 계수의 비트 반전 저장 순서를 활용함으로써, 기존 기술 대비 멀티플렉서 수를 절반으로 줄이고 스크래치패드 메모리 버퍼의 필요성을 제거했습니다. 이로 인해 치환 연산의 지연 시간이 절반으로 감소했습니다.
   • 모듈형 구성 요소: 아키텍처에는 NTT, INTT 및 계수별 연산을 지원하는 처리 요소 (PE) 어레이; 합계를 위한 트리 어더 (TA) 어레이; 그리고 치환 회로 (PC) 어레이가 포함됩니다.

주요 기여

• 알고리즘적 혁신: 더블 호스팅 접근법 대비 암호문 회전 및 Decompose 연산의 수를 줄이기 위해 베이비 스텝을 더 분해한 3 단계 호스팅된 BSGS 알고리즘 제안.
• 데이터 경로 최적화: TH-BSGS 알고리즘의 재배열된 연산에 맞춰 온칩 데이터 재사용을 극대화함으로써 오프칩 메모리 트래픽을 획기적으로 줄이는 단계 기반 메모리 최적화 전략.
• 하드웨어 효율성: 자동사상 지연 시간을 50% 줄이고 추가 메모리 버퍼링을 제거한 단순화된 치환 회로를 갖춘 하드웨어 가속기 개발.

실험 결과
본 설계는 Xilinx Virtex UltraScale+ (U280) 장치에서 합성되었으며, 128 비트 보안을 지원하는 3 가지 다른 HE 파라미터 세트 (Set-A, Set-B, Set-C) 하에서 최첨단 하드웨어 가속기 (FAME, CHAM 및 [25] 의 설계 포함) 와 비교 평가되었습니다.

• 오프칩 메모리 접근: 동일한 파라미터 설정 하에서 제안된 설계는 최상의 기존 설계 (FAME) 대비 오프칩 메모리 접근을 2.9 배에서 4.2 배까지 줄였습니다. 대각선 방법과 비교할 때 메모리 접근 감소 효과는 최대 10.6 배에 달합니다.
• 계산 지연 시간: 제안된 가속기는 기존 하드웨어 가속기 대비 계산 지연 시간을 2.9 배에서 10.6 배까지 줄였습니다.
• 자원 활용도: 설계는 상당한 성능 향상에도 불구하고 하드웨어 자원 요구 사항 (LUT, FF, DSP, BRAM) 을 기존 솔루션과 비슷하거나 약간 더 나은 수준으로 유지합니다.
• 알고리즘적 비교: TH-BSGS 알고리즘은 더블 호스팅 BSGS (DH-BSGS) 알고리즘 대비 스위칭 키에 대한 메모리 요구량을 약 3.65 배 줄이지만, 다항식 곱셈이 전체 복잡도를 지배하기 때문에 전체 계산 복잡도는 DH-BSGS 및 BSGS 와 유사하게 유지됩니다.

의의
본 논문은 제안된 TH-BSGS 알고리즘과 이에 수반되는 하드웨어 가속기가 HE-LT 효율성에서 중요한 진전을 이루었다고 주장합니다. 키 스위칭의 알고리즘적 오버헤드와 오프칩 메모리 접근의 하드웨어 병목 현상을 동시에 해결함으로써, 이 설계는 더 빠르고 확장 가능한 프라이버시 보호 선형 변환을 가능하게 합니다. 오프칩 메모리 트래픽 감소는 특히 중요하며, 데이터 전송은 HE-LT 연산에서 지연 시간의 대부분을 차지하기 때문입니다. 이 연구는 베이비 스텝의 추가 분해와 엄격한 데이터 경로 최적화 및 특수 하드웨어의 결합이 하드웨어 자원 비용을 증가시키지 않으면서 상당한 성능 개선을 가져올 수 있음을 보여줍니다. 향후 작업은 특정 응용 분야를 위한 선형 변환의 추가 최적화에 초점을 맞출 것으로 명시되어 있습니다.