기술 요약: Jaguar

문제 정의

하이브리드 동형 암호(HE) 및 보안 2자 간 연산(2PC) 프레임워크는 현재 정확한 프라이빗 합성곱 신경망(CNN) 추론을 위한 실질적인 설계 지점이며, 이를 통해 완전 동형 암호의 다항식 근사로 인한 정확도 저하를 피할 수 있습니다. 그러나 이러한 시스템은 두 가지 결정적인 병목 현상에 직면해 있습니다:

1. HE 합성곱 지연 시간: 선형 레이어 연산은 수론적 변환(NTT) 기반의 다항식 산술과 모듈러 소수 축소(modular prime reductions)에 의해 지배됩니다. Cheetah와 같은 최첨단 시스템의 프로파일링 결과, 합성곱 자체가 선형 레이어 지연 시간의 96% 이상을 소비하며, 이 중 NTT 연산과 모듈러 축소가 대부분의 시간을 차지하는 것으로 나타났습니다.
2. 비효효율적인 정밀도 흐름: 고정 소수점 추론에서 선형 레이어는 두 배의 소수점 정밀도($2f$ 비트)를 가진 출력을 생성합니다. 기존의 하이브리드 시스템은 이 넓은 비트폭의 값을 ReLU 프로토콜로 직접 전달한 다음, 목표 정밀도를 복구하기 위해 별도의 대화형 2PC 절삭(truncation) 프로토콜을 수행합니다. 이 방식은 ReLU 과정에서 더 넓은 비트폭에 대한 불필요한 계산 비용을 발생시키고, 절삭 단계에서 상당한 통신 오버헤드를 추가합니다.

두 문제의 근본 원인은 표준 FHE 라이브러리 설계에서 상속된 소수 모듈러스(특히 NTT 친화적인 소수)에 대한 의존성입니다. 이는 일반적인 다항식 곱셈에는 최적이지만, 단일 선형 레이어 수행 후 즉시 $\mathbb{Z}_{2^\ell}$ 상의 가산 공유(additive shares)로 변환되는 하이브리드 HE/2PC 시스템에는 차선책입니다.

방법론

Jaguar는 단 하나의 핵심적인 설계 선택을 통해 이러한 병목 현상을 해결합니다: 기존의 소수 모듈러스 대신 2의 거듭제곱 형태의 암호문 링(power-of-two ciphertext ring, $q = 2^Q, p = 2^P$)을 산술 기저로 채택하는 것입니다. 이 선택은 세 가지 상호 연결된 기술적 혁신을 가능하게 합니다:

1. SPA-CONV: 계수 영역 합성곱(Coefficient-Domain Convolution)

2의 거듭제곱 링을 활용함으로써, Jaguar는 선형 경로에서 NTT 기반 다항식 곱셈의 필요성을 제거합니다. 대신 스칼라-다항식 누적(SPA-CONV) 방식을 사용합니다.

• 메커니즘: 합성곱은 이동된 스칼라-다항식 곱의 합으로 평가됩니다. 각 필터 가중치(스칼라)에 대해, 시스템은 입력 암호문의 계수별 시프트(coefficient-wise shift)를 수행하고 그 결과를 누적합니다.
• 장점: 이 접근 방식은 값비싼 다항식 간의 곱셈과 모듈러 소수 축소를 스칼라-다항식 곱셈, 계수 시프트, 그리고 비트 마스킹(모듈로 $2^Q$ 축소를 위한)으로 대체합니다. 이는 텍스트-암호문 다항식 곱셈이나 서버 측 NTT를 필요로 하지 않습니다.

2. 정확한 Pre-ReLU 암호측 절삭(Exact Pre-ReLU Ciphertext-Side Truncation)

2의 거듭제곱 모듈러스는 BFV 스케일 팩터 $\Delta = q/p = 2^{Q-P}$ 또한 2의 거듭제곱이 되도록 보장합니다.

• 메커니즘: 이 가분성(divisibility) 덕분에 ReLU 연산 전, 암호문 구성 요소에 대해 산술적 오른쪽 시프트(부호 없는 잔여값에 대한 논리적 시프트로 구현됨)를 통한 정확한 절삭이 가능합니다.
• 이점: 이를 통해 별도의 대화형 2PC 절삭 프로토콜을 제거할 수 있습니다. 또한, ReLU 프로토콜의 입력 비트폭을 $\ell$에서 $\ell-f$로 줄여 비선형 단계의 통신 및 계산 비용을 감소시킵니다.

3. NTT 지원 복호화(NTT-Assisted Decryption)

서버 측 선형 경로는 NTT를 피하지만, 클라이언트는 여전히 복호화 중에 다항식 곱셈($\hat{c}'_1 \cdot \hat{s}$)을 수행해야 합니다.

• 메커니즘: Jaguar는 이 특정 로컬 연산을 위해 보조 NTT 친화적 소수($q_{ntt}$)를 사용하여 복호화 효율성을 회복합니다. 클라이언트는 계수를 이 보조 소수로 매핑하여 NTT를 통해 곱셈을 수행하고, 결과를 다시 2의 거듭제곱 링으로 매핑합니다.
• 이점: 이는 2의 거듭제곱 프로토콜 기저를 해치거나 서버 측에 NTT 비용을 도입하지 않으면서도, 클라이언트 측의 $O(N \log N)$ 복잡도를 유지합니다.

주요 기여

• 2의 거듭제곱 산술 기저: Jaguar는 ImageNet 규모의 CNN 추론을 위해 기존의 NTT-소수 백엔드에서 벗어나 2의 거듭제곱 암호문 링을 중앙 산술 체계로 사용하는 최초의 HE/2PC 시스템입니다.
• SPA-CONV 커널: 점별(pointwise), 밀집(dense), 심층(depthwise) 합성곱을 스칼라-다항식 곱과 계수 시프트의 합으로 평가하여, 선형 경로에서 NTT와 모듈러 소수 축소를 제거하는 새로운 합성곱 커널입니다.
• 제로-통신 절삭(Zero-Communication Truncation): 기존 하이브리드 시스템에는 없는, post-ReLU 절삭 프로토콜을 완전히 제거하는 정확한 암호측 절삭에 대한 정당성 증명입니다.
• NTT 지원 복호화: 2의 거듭제곱 설계를 유지하면서 복호화 효율성을 유지하기 위해 보조 소수를 활용하는 클라이언트 로컬 기술입니다.

실험 결과

저자들은 Dual Intel Xeon Gold 6250 환경(AVX 비활성화)에서 ImageNet 규모의 ResNet-18, ResNet-50, MobileNetV2를 대상으로 Jaguar를 평가했습니다.

• 지연 시간: Jaguar는 LAN 및 WAN 설정 모두에서 Cheetah보다 2.07~3.72배, Rhombus보다 2.16~3.36배 낮은 엔드 투 엔드 지연 시간을 달면합니다.
  • ResNet-50의 경우, 합성곱 커널 지연 시간이 79% 감소했습니다.
  • ReLU+절삭 단계에서 2.32배(LAN) 및 **1.80배(WAN)**의 지연 시간 감소를 보였습니다.
• 통신: Jaguar는 Cheetah 대비 통신량을 1.16~1.76배 감소시켰습니다.
  • 절삭 단계의 통신량은 **제로(zero)**로 줄었습니다.
  • ReLU 통신은 더 작은 입력 비트폭 덕분에 감소했습니다.
  • 참고: ResNet-50에서 Jaguar의 통신량은 Rhombus보다 약간 높습니다(1.28배). 이는 Rhombus가 ResNet-50의 통신을 지배하는 점별 및 행렬-벡터 성분에 특화되어 있기 때문이며, Jaguar는 전체 합성곱 경로의 계산량을 크게 낮추는 대신 일부 통신량을 희생합니다. 그러나 ResNet-18 및 MobileNetV2에서는 Jaguar가 지연 시간과 통신량 모두에서 Rhombus를 능가합니다.
• 마이크로 벤치마크: 계산 전용 합성곱 벤치마크(AVX 비활성화)에서, 패킹 레이아웃에 대해 Jaguar는 Cheetah 대비 기하 평균 속도 향상인 2.47배(밀집), 11.82배(점별), 11.65배(심층)를 기록했습니다.

의의

본 논문은 암호화의 기본 산술 체계를 소수 모듈러스에서 2의 거듭제곱으로 변경하는 것이, 기존 백엔드 위에 단순히 패킹이나 통신을 최적화하는 것만으로는 달성할 수 없는 실질적인 프라이빗 CNN 추론의 상당한 이득을 끌어낼 수 있음을 입증합니다. 암호문 모듈러스를 공유 도메인($\mathbb{Z}_{2^\ell}$)과 일치시키고 축소 없는 산술을 가능하게 함으로써, Jaguar는 HE 합성곱과 정밀도 흐름의 주요 병목 현상을 동시에 해결합니다. 이 시스템은 합성곱(스칼라-다항식 누적)과 복호화(로컬 NTT 회복)의 특정 요구 사항을 충족한다면, 2의 거듭제곱 링이 하이브리드 HE/2PC 추론에 있어 유효할 뿐만 아니라 우월하다는 것을 증명합니다.