💻 computer science

Compiler-Guided Polynomial-Level Parallelism for FHE-Encrypted Machine Learning Inference

이 논문은 ANT-ACE 컴파일러 프레임워크 내에서 런타임 SIMD 벡터화를 컴파일 타임 OpenMP 병렬화로 교체함으로써 FHE로 암호화된 머신러닝 추론을 위한 안전한 다항식 수준의 병렬성을 가능하게 하여 상당한 속도 향상과 지연 시간 감소를 가져오는 컴파일러 가이드 방식인 CRISP를 소개한다.

원저자: Zijian Duan, Zuoyan Zhang, Tao Dai, Zhihong Liang, Jie Zhao

게시일 2026-09-14

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Zijian Duan, Zuoyan Zhang, Tao Dai, Zhihong Liang, Jie Zhao

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 디지털 세상에서 민감한 정보는 종종 낯선 이들이 제어하는 네트워크를 통해 이동합니다. 은행은 자신이 소유하지 않은 서버에서 대출 신청을 처리할 수 있고, 병원은 제삼자가 운영하는 클라우드 서비스를 사용하여 환자의 기록을 분석할 수 있습니다. 이러한 시나리오에서 데이터는 취약합니다. 만약 서버가 해킹당한다면, 개인 정보가 노출될 수 있기 때문입니다. 수십 년 동안, 이러한 상황에서 데이터를 보호하는 유일한 방법은 데이터를 오프라인 상태로 유지하거나 서버 운영자를 완전히 신뢰하는 것뿐이었습니다. 완전 동형 암호(Fully Homomorphic Encryption)는 다른 길을 제시합니다. 이것은 컴퓨터가 암호화된 상태로 잠겨 있는 데이터에 대해 계산을 수행할 수 있게 하는 수학적 방법입니다. 컴퓨터는 실제 숫자를 보지 못하며, 오직 뒤섞인 코드만을 조작합니다. 계산이 끝나면, 마치 원래의 암호화되지 않은 데이터에 작업을 수행한 것처럼, 결과는 복호화되어 올바른 답을 드러냅니다. 이 기술는 계산이 신뢰할 수 없는 인프라에서 발생하더라도 프라이버시가 보존되는 미래를 약속합니다.

하지만 이러한 프라이버시는 값비싼 대가를 치러야 합니다. 컴퓨터가 명확한 숫자 대신 뒤섞인 코드로 작업해야 하기 때문에, 계산 속도가 믿기 힘들 정도로 느리기 때문입니다. 일반적인 데이터로는 순식간에 끝날 작업이 암호화된 상태에서는 몇 시간, 심지어 며칠이 걸릴 수도 있습니다. 이러한 느린 속도는 의료 영상을 분석하거나 금융 거래를 실시간으로 처리하는 것과 같은 실시간 애플리케이션에 이 기술이 사용되는 것을 가로막아 왔습니다. 병목 현상은 컴퓨터가 암호화를 유지하기 위해 요구되는 방대한 양의 수학적 작업을 처리하는 방식에 있습니다. 이 기술을 실용적으로 만들기 위해서, 연구자들은 데이터의 안전을 지키는 보안 규칙을 깨뜨리지 않으면서도 이러한 계산 속도를 높일 방법을 찾아야 합니다.

후난 대학교와 광둥성 전력 시스템 네트워크 보안 핵심 실험실의 연구팀은 이 속도 문제를 해결하기 위한 새로운 방법을 개발했습니다. 그들은 암호화된 계산을 실행하는 컴퓨터 코드를 위한 특화된 번역기 역할을 하는 CRISP라는 시스템을 만들었습니다. 그들의 연구는 머신러닝 작업에 널리 사용되는 CKKS라고 알려진 특정 암호화 방식에 초점을 맞추고 있습니다. 이 방식에서 암호화된 데이터는 다항식(polynomials)이라 불리는 거대한 수학적 객체들의 집합으로 표현됩니다. 계산을 수행하기 위해 컴퓨터는 이 다항식들을 더 작은 조각들로 나누고 다시 조립하는 일련의 단계들을 거쳐 처리해야 합니다. 연구진은 이러한 계산을 실행하는 데 사용되는 기존 소프트웨어가 현대적인 컴퓨터 프로세서의 성능을 충분히 활용하지 못하고 있다는 사실을 발견했습니다.

현대적인 컴퓨터 프로세서는 여러 개의 코어를 포함하고 있는데, 이는 마치 각자가 일을 동시에 수행할 수 있는 팀원들과 같습니다. 암호화된 계산을 위한 표준 소프트웨어는 SIMD라는 기술을 사용하도록 설계되었습니다. 이는 마치 한 명의 작업자가 특수 도구를 사용하여 많은 작은 항목들에 대해 한꺼번에 작업을 수행하는 것과 같습니다. 이 방식은 효과적이긴 하지만, 동시에 활성화될 수 있는 작업자의 수를 제한합니다. 연구진은 암호화된 계산의 구조가 다른 전략을 허용한다는 점을 깨달았습니다. 즉, 모든 작은 항목에 대해 특수 도구에 의존하는 대신, 서로 다른 큰 작업 덩어리들을 서로 다른 작업자들에게 할당할 수 있다는 것입니다. 그들은 코드가 실행되기 전에 코드를 재구성하여 컴퓨터가 다중 코어를 더 효과적으로 사용할 수 있도록 하는 컴파일러 가이드 방식을 개발했습니다. '단일 작업자, 다수 항목' 방식에서 '다수 작업자, 다수 덩어리' 방식으로의 이러한 전환이 그들 혁신의 핵심입니다.

연구진은 기존의 엔드 투 엔드(end-to-end) 컴파일러인 ANT-ACE 위에 자신들의 시스템인 CRISP를 구축했습니다. 이 컴파일러는 이미지를 인식하는 데 사용되는 것과 같은 머신러닝 모델을 가져와 이를 암호화된 데이터에서 실행될 수 있는 프로그램으로 자동 변환합니다. 연구팀은 프로그램이 암호화 라이브러리가 이해할 수 있는 다항식 연산으로 번역되는 최종 단계에 이 새로운 병렬화 전략을 삽입했습니다. 이 과정을 컴파일러 수준에서 수행함으로써, 그들은 계산의 전체 구조를 파악하고 새로운 작업 분할 방식이 암호화의 엄격한 규칙을 위반하지 않도록 보장할 수 있었습니다. 암호화된 데이터는 반드시 보존되어야 하는 특정 수학적 속성을 가지고 있기 때문에 매우 주의해야 했습니다. 만약 작업을 잘못 나누면 최종 결과가 틀리게 됩니다. 그들의 방법은 서로 다른 계산 부분들 사이의 의존성을 면밀히 분석하여 병렬 작업자들이 서로 간섭하지 않도록 보장합니다.

실험 결과는 매우 유의미했습니다. 그들은 여섯 가지의 서로 다른 암호화 머신러닝 모델을 사용하여 멀티 코어 컴퓨터 프로세서에서 시스템을 테스트했습니다. 새로운 방법으로 암호화된 계산을 실행했을 때, 핵심적인 수학적 연산들은 표준 방식보다 평균 2.65배 빨라졌습니다. 이러한 속도 향상은 암호화된 숫자의 덧셈과 곱셈을 포함한 다양한 유형의 계산에서 일관되게 나타났습니다. 전체 머신러닝 추론 과정(단일 데이터에 대해 모델을 실행하는 데 걸리는 시간)에 대해, 새로운 방법은 기존의 가장 우수한 버전과 비교했을 때 총 시간을 평균 137초 단축했습니다. 어떤 경우에는 특정 곱셈 작업에 대해 시스템이 거의 7배 더 빠르게 실행되는 등 그 감소 폭이 훨씬 더 극적이었습니다. 이러한 개선은 기본 암호화 방식을 변경하거나 새로운 하드웨어를 요구하지 않고도 달성되었으며, 그 성과는 기존의 작업을 더 똑똑하게 조직하는 방식에서 비롯되었습니다.

연구진은 또한 자신들의 방법이 다른 최적화 기법들과 결로 잘 작동하는지 검증했습니다. 머신러닝 모델은 시간을 절약하기 위해 서로 다른 연산들이 하나로 합쳐지는 복잡한 단계들을 포함하는 경우가 많습니다. 연구팀은 자신들의 병렬화 전략이 이러한 병합 기술들과 공존할 수 있으며, 두 가지의 이점을 모두 보존할 수 있음을 보여주었습니다. 그들은 최대 16개의 프로세서 코어를 사용하여 시스템을 테스트했으며, 시스템이 메모리 대역폭의 한계에 도달함에 따라 이득이 완만해지기 시작했지만 성능이 계속 향상된다는 것을 발견했습니다. 이는 해당 방법이 더 강력한 하드웨어와 함께 잘 확장됨을 나타냅니다. 결정적으로, 그들은 새로운 시스템에 의해 생성된 결과가 표준 시스템에 의해 생성된 결과와 수학적으로 동일함을 확인하여, 속도가 정확도를 희생하면서 얻어진 것이 아님을 증명했습니다.

이 연구는 암호화된 머신러닝을 실제 환경에서 실행 가능하게 만드는 데 있어 실질적인 진전을 의미합니다. 계산의 병렬화 제어권을 런타임 라이브러리에서 컴파일러로 옮김으로써, 연구진은 이전에는 접근할 수 없었던 새로운 수준의 성능을 끌어냈습니다. 그들의 접근 방식은 마법이나 새로운 이론적 돌파구에 의존하는 것이 아니라, 기존 도구들을 사용하는 방식을 신중하게 재구성하는 것에 기반합니다. 이 연구 결과는 암호화된 데이터 처리가 실시간 사기 탐지나 개인화된 의료 진단과 같이 즉각적인 결과가 필요한 애플리케b한 애플리케이션을 위해 충분히 빠르게 만들어질 수 있음을 시사합니다. 연구팀은 다른 사람들이 연구하고 발전시킬 수 있도록 구현 내용을 공개하여, 추가적인 개선을 위한 문을 열어두었습니다. 프라이버시를 보존하는 계산에 대한 수요가 증가함에 따라, CRISP와 같은 방법은 보안 데이터 처리를 이론적인 가능성이 아닌 디지털 환경의 표준적인 부분으로 만드는 명확한 경로를 제공합니다.

기술 요약: FHE 암호화 머신러닝 추론을 위한 컴파일러 유도 다항식 수준 병렬화

문제 정의

완전 동형 암호(Fully Homomorphic Encryption, FHE)는 신뢰할 수 없는 환경에서도 데이터의 프라이버시를 보호하며 머신러닝(ML) 추론을 가능하게 한다. 기존의 FHE 컴파일러(예: ANT-ACE, CHET, EVA)는 ML 계산 그래프를 암호문 다항식 프로그램으로 변환하는 **단계적 로어링 전략(staged lowering strategy)**으로 수렴해 왔으나, **다항식 수준의 병렬성(polynomial-level parallelism)**은 여전히 미개척 영역으로 남아 핵심적인 병목 구간이다.

현재의 접근 방식은 계수 수준의 병렬성을 활용하기 위해 런타임 라이브러리 내에 하드코딩된 SIMD 벡터화에 크게 의존하고 있다. 그러나 이러한 라이브러리들은 RNS 수준의 병렬성(Residue Number System 채널 간의 병렬성)을 안전하게 활용하거나, 컴파일러 수준의 변환인 다항식 퓨전(polynomial fusion)과 병렬성을 조율할 수 있는 시맨틱 컨텍스트가 부족하다. 결과적으로, 런타임 라이브러리는 컴파일 단계 전반에 걸친 데이터 의존성이나 암호학적 불변성을 안전하게 추론할 수 없으므로, 멀티 코어 CPU 자원을 활용하는 데 한계가 있다.

방법론: CRISP

저자들은 ANT-ACE 엔드 투 엔드 FHE 컴 컴파일러 내에 구현된 컴파일러 패스인 CRISP(Compiler-Reasoned Inter-stage Safe Parallelization)를 제안한다. CRISP는 병렬화 전략을 런타임 관리형 SIMD 벡터화에서 평탄화된 다항식 실행 공간에 대한 컴파일 타임 OpenMP 병렬화로 전환한다.

핵심 기술 변환

트레이드오프 전략: CRISP는 미세한 계수 수준의 SIMD 벡터화를 거친 병렬성(coarse-grained)인 OpenMP 스레드 수준 병렬화와 교환한다. 이는 RNS 채널이 명시적으로 루프로 표현되는 POLY IR(Polynomial Intermediate Representation) 단계를 타겟으로 한다.
의존성 제거 및 프라이베타이제이션(Privatization):
- 기존의 POLY IR은 병렬화를 방해하는 루프 내 의존성(예: 공유 모듈러스 포인터)을 포함하는 경우가 많다. CRISP는 변수를 프라이베타이제이션(예: 루프 인덱스로부터 프라이빗 모듈러스 포인터를 유도)함으로써 이를 제거한다.
- 또한, 라이브러리의 SIMD 최적화된 프리미티브(hw_*)로부터 스칼라 산술 루틴(예: Add_int64_with_mod)을 복구하여, 병렬화에 적합한 순수하고 부수 효과가 없는(side-effect-free) 계산 공간을 생성한다.
루프 평탄화(Loop Flattening): CRISP는 중첩된 RNS 및 계수 루프를 하나의 1차원 반복 공간( $N \times r$ , 여기서 $N$ 은 다항식 차수, $r$ 은 RNS 채널 수)으로 평탄화한다. 이를 통해 정적 OpenMP 스케줄링을 위한 더 크고 균일한 워크로드를 노출한다.
퓨즈된 연산을 위한 하이브리드 실행: CMul(Ciphertext-Ciphertext Multiplication)과 같이 리스케일링(rescaling) 및 릴리니어라이제이션(relinearization)을 포함하는 복잡한 퓨즈 연산의 경우, CRISP는 선택적 병렬화 전략을 적용한다:
- 단계 I (곱셈): 평탄화된 OpenMP 루프를 통해 완전히 병렬화된다.
- 단계 II & III (리스케일링/릴리니어라이제이션): 이 단계들은 도메인 전환(계수에서 NTT로) 및 구조적 제약을 포함한다. CRISP는 도메인 불변성이 중요한 내부 루프에서는 SIMD 벡터화를 유지하며, 외부의 도메인이 안정적인 루프에만 OpenMP를 적용한다. 이는 OpenMP-SIMD 하이브리드 실행 모델을 생성한다.
퓨전 보존: CRISP는 기존 최적화 파이프라인과의 호환성을 보장한다:
- 다항식 퓨전: 스칼라 루틴의 컴파일 타임 함수 인라이닝을 통해 달성되며, 이는 커스텀 런타임 프리미티브(예: hw_modmuladd)의 필요성을 대체한다.
- 루프 퓨전: 평탄화된 루프에서 동일한 반복 경계(iteration bounds)를 유지함으로써 보존된다. 이를 통해 표준 루프 퓨전 로직이 유효하게 유지될 수 있다.

안전성 및 정확성

CRISP는 일반적인 컴파일러가 검증할 수 없는 도메인 특화 암호학적 불변성(예: 모듈러스 정렬, 계수 순서)을 강제한다. RNS-CKKS 스킴의 정확성을 위반하거나 컴파일 단계 간의 최적화를 저해하지 않도록, CRISP는 암호학적 파라미터가 인스턴스화되는 POLY IR 레벨에서 동작한다.

주요 기여

컴파일 구조의 정형화: 본 논문은 현대 FHE 컴파일러가 공유하는 3단계 컴파일 구조(그래프 변환, 호모모픽 근사, 다항식 실행)를 식별하고 정형화하여, 현재 병렬성이 제한되는 지점을 명확히 한다.
컴파일러 유도 병렬화: SIMD를 OpenMP로 안전하게 교환하여, 하드코딩된 라이브러리 구현에 의존하지 않고도 RNS 및 계수 병렬성을 모두 활용할 수 있게 하는 도메인 인지형 컴파일러 패스를 도입한다.
단계 간 안전성: 공격적인 병렬화가 암호학적 불변성을 깨뜨리거나 부트스트래핑 배치 또는 그래프 수준 퓨전과 같은 상위 단계의 최적화를 무효화하지 않음을 입증한다.
성능 이득: ANT-ACE 내에서의 구현을 통해 다항식 수준 병렬성의 구체적인 기여도를 격리하여 평가함으로써, 엔드 투 엔드 레이턴시에 미치는 영향을 통제된 환경에서 보여준다.

실험 결과

실험은 Intel Xeon Platinum 8538C 멀티 코어 CPU에서 6개의 암호화된 ML 추론 워크로드(CryptoNet, LeNet, AlexNet, ResNet-20, MobileNet, SqueezeNet)를 대상으로 수행되었다.

다항식 수준 속도 향상: CRISP는 순차적인 ANT-ACE 베이스라인과 비교하여 핵심 다항식 연산(PAdd, PMul, CAdd, CMul)에서 평균 2.65배의 속도 향상을 달み한다. 특히 계산 집약도가 높은 PMul에서 가장 높은 성능 향상(7.17배)을 보였다.
ML 연산 영향: 암호화된 ResNet-20에서, CRISP는 병렬화된 부트스트래핑과 결합되었을 때 ML 연산 실행 시간을 평균 5.63%(약 2.68초) 단축했다.
엔드 투 엔드 레이턴시: 시스템은 베이스라인 대비 엔드 투 엔드 추론 레이턴시를 평균 137초 단축(6.41% 개선)했다.
확장성: 이 접근 방식은 16개 스레드까지 효과적으로 확장되나, 메모리 대역폭이 병목 현상이 됨에 따라 수확 체감 현상이 관찰된다.
컴파일 오버헤드: CRISP 통합은 평균적으로 컴파일 시간을 단 **6.81%**만 증가시켜, 무시할 수 있는 수준의 오버헤드를 보여주었다.
호환성: CRISP는 그래프 수준 퓨전(FHEFusion) 및 다양한 CKKS 파라미터 설정과 호환성을 유지하며 일관된 개선을 제공한다.

의의 및 주장

본 논문은 CRISP가 기존의 SIMD 기반 최적화를 효과적으로 보완하며, 런타임 라이브러리가 안전하게 활용할 수 없는 스레드 수준의 병렬성을 해제한다고 주장한다.

패러다임의 전환: 본 연구의 의의는 성능 최적화의 주체를 수동으로 설계된 런타임 라이브러리에서 컴파일러로 옮긴 데 있다. 이를 통해 데이터 흐름 및 암호학적 제약에 대한 전역적 추론이 가능해지며, 고립된 라이브러리 프리미티브로는 안전하게 구현할 수 없는 최적화(예: RNS 수준 병렬성)를 가능하게 한다.
안전 우선: 저자들은 자신들의 기여가 단순히 OpenMP나 SIMD를 발명한 것이 아니라, FHE의 특정 제약 조건(RNS 분해, 노이즈 관리, 도메인 불변성) 내에서 이러한 기술들을 안전하고 결합 가능한 방식으로 적용한 것임을 강조한다.
실질적 영향: 복잡한 모델에서 엔드 투 엔드 레이턴시를 100초 이상 단축함으로써, 본 연구는 컴파일러 유도 병렬화가 레이턴시에 민감한 애플리케이션을 위한 FHE를 더욱 실용적으로 만드는 데 실질적인 이점을 제공함을 입증한다.

결론적으로, 본 논문은 GPU 지원 및 이기종 실행이 유망한 미래 방향이지만, 현재의 연구가 FHE 컴로 파이프라인 전반에서 정확성과 결합성을 보존하는 컴파일러 유도 다항식 수준 병렬화를 위한 견고한 토대를 구축했음을 보여준다.