Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption

기술 요약: Recifhe – 완전 동형 암호(FHE)를 위한 암호문 및 다항식 수준 최적화

문제 정의
RNS-CKKS와 같은 완전 동형 암호(FHE) 스킴은 암호화된 데이터에 대한 프라이버시 보존 컴퓨팅을 가능하게 하지만, 프로그래밍 및 성능 측면에서 상당한 부담을 지웁니다. 프로그래머는 레벨(level)과 스케일(scale) 같은 암호문 속성을 처리하기 위해 Rescale, Bootstrap과 같은 암호문 관리 연산을 수동으로 삽입해야 합니다. 최근의 FHE 컴파일러들은 이 과정을 자동화하지만, 주로 **암호문 수준(ciphertext level)**에서 동작하며, 여기서 각 암호문 연산은 일련의 다항식 연산으로 구성된 하나의 원자적 단위로 취급됩니다. 이러한 거친 입도(granularity)로 인해 컴파일러는 서로 다른 암호문 연산 사이에 발생하는 중복 다항식 계산을 제거하는 것과 같은 미세한 최적화 기회를 놓치게 됩니다. 반대로, 기존 방식들은 연산을 다항식 시퀀스로 분해하더라도 복잡성 문제로 인해 단일 암호문 연산 내로 최적화를 제한하거나, 고정된 알고리즘을 사용하는 수동 라이브러리 최적화에 의존합니다. 이러한 수동 최적화는 가변적인 데이터 흐름에 적응하지 못하며, 수익성을 평가하지 않고 무조건적으로 연산을 더 무거운 RNS 기저(PQ 기저)로 격상시켜 불필요한 성능 오버헤드나 과도한 메모리 증가를 초래할 수 있습니다.

방법론
본 논문은 암호문 수준의 거친 최적화와 다항식 수준의 미세한 최적화 사이의 간극을 메우기 위해 설계된 다층(multi-level) 컴파일러인 Recifhe를 소개합니다. Recifhe는 두 단계의 중간 표현(IR) 전략을 채택합니다:

1. 암호문 수준 최적화(Ciphertext-Level Optimization): Recif하여 비-FHE 입력 프로그램(Python DSL로 작성됨)을 FHE 프로그램으로 변환합니다. 이 단계에서는 암호문 관리 연산(Rescale, Bootstrap)을 배치하고 Rescale hoisting을 적용하는 것과 같은 전역 최적화를 수행합니다. 이러한 거친 입도의 접근 방식은 전체 다항식 시퀀스 상에서 직접 동작하는 것보다 전역 최적화의 복잡도를 낮춰줍니다.
2. 다항식 수준 최적화(Polynomial-Level Optimization): 암호문 연산이 그에 대응하는 다항식 시퀀스로 하향 조정(lowering)된 후, Recifhe는 암호문 경계를 가로질러 미세한 최적화를 수행합니다. 주요 기술은 다음과 같습니다:
   • 공통 부분식 제거(Common Subexpression Elimination, CSE): 서로 다른 하향된 시퀀스들 사이에서 동일한 입력을 가진 중복 다형식 계산을 제거합니다.
   • 성능 인지형 ModDown Hoisting: 이것이 핵심 혁신 사항입니다. Recifhe는 여러 개의 ModDown 연산(RNS 기저를 $PQ$에서$Q$로 줄이는 연산)을 통합할 수 있는 영역을 식별합니다. 고정된 알고리즘을 사용하는 기존 방식과 달리, Recifhe는 오프라인 프로파일링을 사용하여 $Q$ 및 $PQ$ 기저 모두에서의 연산 지연 시간(latency)을 추정합니다. Recifhe는 ModDown 연산을 제거함으로써 얻는 이득과, 무거운 $PQ$ 기저에서 실행되는 둔감한 연산(예: 덧셈)으로 인한 오버헤드 사이의 트레이드오프를 계산합니다. 호이스팅(Hoisting)은 추정된 지연 시간 이득이 오버헤드를 초과할 때만 적용됩니다.
   • 연산 퓨전(Operation Fusion): Recifhe는 인접한 연산(예: ModDown과 Rescale)을 퓨전하여 내부의 이산 푸리에 변환(NTT) 및 역 이산 푸리에 변환(iNTT) 쌍을 상쇄함으로써, 다항식이 평가 도메인에 머물도록 유지합니다. 필요한 경우 연산 간의 퓨전을 가능하게 하기 위해 피연산자를 $PQ$ 기저로 끌어올리는 invModDown을 활용합니다.
   • Liveness-Driven 스케줄링: 다항식 수준 최적화로 인해 발생하는 메모리 증가(중간값의 생존 기간 연장으로 인한 현상)를 억제하기 위해, Recifhe는 연산을 가장 최근에 정의된 피연산자 바로 다음에 실행되도록 스케줄링합니다. 이를 통해 활성 범위(live range)를 축소하고 데드 값(dead value)을 위한 버퍼를 재사용하여 메모리 압박을 완화합니다.

주요 기여

• 다층 아키텍처: 단일 입도 접근 방식의 한계를 해결하기 위해 전역 암호문 수준 최적화와 미세한 다항식 수준 최적화를 통합한 새로운 컴파일러 설계를 제공합니다.
• 데이터 흐름 적응형 호이스팅: 특정 데이터 흐름과 연산 지연 시간에 따라 변환의 수익성을 동적으로 평가하는 성능 인지형 ModDown 호이스팅 알고리즘을 제공하여, 고정된 휴리스틱의 함정을 피합니다.
• 메모리 관리: 다항식 수준 최적화가 유발하는 메모리 오버헤드를 구체적으로 겨냥한 liveness 기반 스케줄링 메커니즘을 통해, 성능 이득이 과도한 메모리 사용으로 이어지지 않도록 보장합니다.
• 포괄적인 최적화 스위트: 암호문 연산 경계를 넘어 중복 계산을 제거하기 위해 CSE, 연산 퓨전 및 기저 민감형 스케줄링을 통합했습니다.

결과
Recifhe는 12개의 벤치마크(LeNet, ResNet, VGG16과 같은 머신러닝 모델 포함)를 대상으로 암호문 수준 전용 최적화 도구 및 수동으로 최적화된 Cheddar 라이브러리와 비교 평가되었습니다.

• 성능: Recifhe는 12개 벤치마크 모두에서 암호문 수준 전용 베이스라인 대비 1.25배의 속도 향상을 달랐습니다. Cheddar 베이스라인과 비교했을 때, 성공적으로 완료된 9개의 벤치마크에서 1.36배의 속도 향상을 달랐습니다. 주목할 점은, Chedda 베이스라인은 부적절한 무조건적 최적화로 인해 3개의 벤치마크에서 속도가 저하되었습니다(암호문 전용 베이스라인 대비 평균 0.92배).
• 메모리 사용량: Recifhe는 Cheddar보다 적은 메모리를 사용했습니다. Chedda 베이스라인의 0.93배 및 암호문 전용 베이스라인의 1.14배의 메모리 점유율을 달eric했습니다. 반면, Cheddar는 관리되지 않은 live range로 인해 3개의 벤치마크에서 메모리 부족(OOM) 오류로 인해 실행에 실패했습니다.
• 컴파일 시간: 다항식 수준 패스는 컴파일 시간을 증가시켰으며, 전체 컴파일 시간의 평균 39.0%를 차지했습니다(암호문 전용 베이스라인의 기하 평균의 2.92배). 성능 인지형 호이스팅과 퓨전은 각각 전체 시간의 1.31%와 14.3%를 차지했습니다.

의의
본 논문은 Recifhe가 FHE 컴파일러에서 다층 최적화의 필요성을 입증한다고 주장합니다. 암호문 수준을 넘어섬으로써, 이전의 컴파일러와 수동 라이브러리 최적화가 놓쳤던 중복 다항식 계산을 성공적으로 제거했습니다. 결정적으로, Recifhe는 고정된 휴리스틱이 아닌 데이터 흐름 분석과 지연 시간 프로파일링에 의해 유도되는 변환을 적용한다면, 다항식 수준 최적화가 과도한 메모리 비용이나 성능 페널티 없이 효과적으로 적용될 수 있음을 증명했습니다. 이 연구는 복잡한 다항식 연산에 내재된 메모리 제약을 관리하면서 실행 속도를 극대화하는 균형 잡힌 접근 방식을 제공함으로써, FHE 컴파일의 새로운 표준을 제시합니다.