Hardware-Friendly Randomization: Enabling Random-Access and Minimal Wiring in FHE Accelerators with Low Total Cost

논문 요약: 하드웨어 친화적 무작위화 (Hardware-Friendly Randomization)

1. 문제 정의 (Problem)

완전 동형 암호화 (FHE) 가속기, 특히 링-학습 오류 (RLWE) 기반 FHE 를 구현할 때 다음과 같은 심각한 하드웨어적 병목 현상이 발생합니다.

• 통신 및 메모리 오버헤드: RLWE 암호문과 공개 키 (Key-Switching Keys) 는 대규모 다항식 쌍 $(b, a)$로 구성됩니다. 여기서 $a$는 균일하게 무작위 추출된 다항식으로, 보안에 필수적이지만 데이터 양이 매우 큽니다 (예: 단일 다항식 13MB, 키 스위칭 키 130MB 이상). 이를 클라이언트에서 서버로 전송하는 것은 통신 대역폭과 가속기 내 로딩 시간을 크게 저해합니다.
• 기존 방식의 한계 (Seed 기반 생성): 통신량을 줄이기 위해 클라이언트는 작은 시드 (Seed) 만 전송하고, 서버는 가속기 내에서 PRNG(의사 난수 생성기) 를 통해 $a$를 온더플라이 (on-the-fly) 로 생성하는 방식이 사용됩니다.
• 하드웨어 구현의 어려움:
  • 배선 (Wiring) 비용: 중앙 집중식 PRNG 에서 생성된 데이터를 수만 개의 병렬 연산 유닛 (Modular Multipliers 등) 으로 분배하려면 긴 배선이 필요하여 전력 소모가 크고, 금속 층 (Metal Layer) 사용량이 급증합니다.
  • 직렬 의존성 (Serial Dependency): 기존 해시 기반 XOF(Extendable Output Function) 는 직렬적으로 동작합니다. $k$번째 출력을 얻으려면 $0$부터$k-1$까지 모두 생성해야 하므로, 가속기 내 연산 스케줄링이 제한되고 메모리 버퍼가 많이 필요합니다.
  • 비결정적 지연: 거절 표본 추출 (Rejection Sampling) 과정은 성공 확률에 따라 실패할 수 있어, 지연 시간이 불규칙해지고 정적 스케줄링이 어렵습니다.

2. 방법론 (Methodology)

저자들은 위의 문제들을 해결하기 위해 분산형 PRNG 아키텍처와 랜덤 액세스가 가능한 시드 기반 생성 알고리즘을 제안합니다.

• 분산형 PRNG 아키텍처 (Distributed PRNG):

  • 중앙 집중식 생성기를 제거하고, 가속기 내의 각 연산 유닛 그룹 근처에 로컬 PRNG 엔진을 배치합니다.
  • 각 로컬 엔진은 독립적으로 시드, 모듈러스 ($q$), 세그먼트 ID ($id_{seg}$) 를 입력받아 해당 세그먼트의 데이터를 생성합니다.
  • 효과: 긴 배선 (Long-reach wiring) 을 제거하고 로컬 배선만 사용하여 전력 소모와 금속 층 사용을 극도로 줄입니다.

• 도메인 분리 (Domain Separation) 및 랜덤 액세스:

  • 해시 함수의 직렬적 특성을 극복하기 위해 입력값에 도메인 분리를 적용합니다.
  • 입력 시드: seed || q || id_seg
    • seed: 모든 엔진 공유.
    • q: 특정 RNS Limb(나머지) 에 해당하는 모듈러스.
    • id_seg: 다항식을 $N$개의 세그먼트로 나눈 각 세그먼트의 고유 ID.
  • 이를 통해 특정 RNS Limb 나 특정 세그먼트를 순차적 생성 없이 임의로 (Random Access) 직접 생성할 수 있게 됩니다.

• 결정적 스케줄링을 위한 알고리즘 (Algorithm 1 & 2):

  • Algorithm 1: 다중 나머지 다항식 (MRP) 을 생성합니다. 각 Limb 를 $n_{seg}$개의 세그먼트로 나누고, 각 세그먼트를 독립적으로 생성한 후 필요 시 순열 (Permutation) 을 적용하여 논리적 순서를 맞춥니다.
  • Algorithm 2: 해시 출력을 기반으로 특정 모듈러스 $q$ 범위 $[0, q)$ 내의 균일한 값을 생성합니다.
  • 거절 표본 추출 최적화: 클라이언트 측에서 생성 실패 확률을 낮게 (예: 3% 미만) 설정하여, 서버 가속기는 항상 성공적인 파라미터를 받도록 보장합니다. 이는 서버 측의 비결정적 대기 시간을 제거하고 결정적 (Deterministic) 실행 프로파일을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 배선 및 전력 최적화: 중앙 집중식 PRNG 를 분산형으로 전환하여 칩 내 긴 배선과 두꺼운 금속 층 사용을 제거했습니다. 이는 고처리량 구성에서 칩당 수십 와트 (Tens of Watts) 의 전력을 절감할 수 있음을 보여줍니다.
2. 랜덤 액세스 지원: RNS Limb 단위의 무작위 접근을 가능하게 하여, 특정 Limb 만 필요한 연산 (예: 키 스위칭 시 일부 모듈러스만 사용) 에서 불필요한 생성 및 메모리 저장을 방지합니다.
3. 결정적 실행 보장: 클라이언트 측에서 시드 유효성 검사를 수행하여 서버 가속기가 항상 성공적인 생성 파라미터를 받도록 함으로써, 복잡한 흐름 제어 (Flow Control) 나 버블 (Bubble) 없이 정적 스케줄링이 가능하게 했습니다.
4. 클라이언트 오버헤드 최소화: 생성 실패 확률을 3% 미만으로 제한하여, 클라이언트 측의 추가 계산 부하가 전체 키 생성 과정의 3% 미만으로 유지되도록 설계했습니다.

4. 결과 및 성능 (Results)

• 시뮬레이션 설정: $N=2^{16}$, 32-bit 워드 크기, 1GHz 동작 주파수, 16,384 개의 병렬 곱셈기를 가진 15mm 정사각형 칩을 가정했습니다.
• 전력 소모 감소: 중앙 집중식 방식의 경우 데이터 전송에 약 19.7W의 전력이 소모되는 것으로 추정되었으나, 분산형 방식은 데이터 이동 거리가 짧아져 이 전력 소모가 거의 제거되었습니다.
• 모듈러스 지원 범위: SHAKE128 및 KangarooTwelve 를 사용하며, HWNAF(Hamming Weight) 가 5 이하인 NTT 친화적 소수들을 지원합니다. $len$ (세그먼트 길이) 을 조절하여 3% 미만의 실패 확률을 유지하면서도 다양한 모듈러스 크기를 지원할 수 있음을 입증했습니다 (Table 1 참조).
• 시드 길이: 288 비트 시드를 사용하여 보안성을 유지하면서도 유효 시드 공간이 충분히 크다는 것을 확인했습니다.

5. 의의 및 결론 (Significance)

이 논문은 FHE 가속기 하드웨어 설계의 핵심 병목 현상인 내부 배선 비용과 전력 소모를 획기적으로 줄이는 실용적인 아키텍처를 제시합니다.

• 확장성: FHE 가속기의 병렬도가 높아질수록 배선 비용이 기하급수적으로 증가하는 문제를 해결하여, 대규모 FHE 애플리케이션의 에너지 효율적인 확장을 가능하게 합니다.
• 시스템 통합: 클라이언트 - 서버 간 통신 오버헤드를 줄이는 기존 기법 (Seed 기반) 을 하드웨어 구현 관점에서 최적화하여, 실제 ASIC 구현 시 발생할 수 있는 유연성 부족과 전력 문제를 해결합니다.
• 생태계 영향: 이 방식이 FHE 가속기 벤더와 라이브러리 (OpenFHE, Lattigo 등) 에 널리 채택된다면, 암호화된 대규모 애플리케이션의 실행 비용과 에너지를 크게 낮출 수 있는 기반을 마련합니다.

결론적으로, 이 연구는 FHE 가속기의 이론적 성능을 실제 하드웨어 제약 조건 (배선, 전력, 스케줄링) 에 맞춰 현실화하는 중요한 단계로 평가됩니다.