💻 computer science

HE-DAP: Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization for Statistical Computation

HE-DAP는 다양한 하드웨어 환경에서 프라이버시 보호 통계 분석을 위한 엔드 투 엔드 성능을 향상시키고 역 제곱근 계산을 크게 가속화하기 위해, 동형 암호에서의 다항식 평가와 부트스트래핑 사이의 트레이드오프를 자동으로 조정하는 크로스 플랫폼 최적화 프레임워크이다.

원저자: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

게시일 2026-06-11

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yun-Soo Park, Hyunmin Choi, Hyoungshick Kim, Mun-Kyu Lee

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

당신은 친구에게 비밀 메시지를 보내려고 하지만, 매우 엄격하고 편집증적인 우체국을 통해서만 보낼 수 있다고 상상해 보세요. 이 우체국(동형 암호 시스템)은 상자를 한 번도 열지 않고도 그 안의 내용물로 수학 연산을 수행할 수 있게 해줍니다. 이는 프라이버시 보호에는 매우 좋지만, 문제가 하나 있습니다. 바로 이 우체국이 굉장히 느리다는 점입니다. 계산을 할 때마다 상자는 점점 더 무거워지고 깨지기 쉬운 상태가 됩니다. 만약 계산을 너무 많이 하면 상자가 부서져 버리고, 당신의 비밀은 사라지게 됩니다.

역제곱근(inverse square root, '분수의 제곱근'이라고 생각하면 됩니다)을 구하는 것은 통계학에서 해결해야 하는 매우 흔한 수학 문제 중 하나입니다. 이는 특정 데이터 포인트가 얼마나 이례적인지를 파터내는 것과 같은 많은 데이터 분석 작업에서 핵심적인 단계입니다.

문제점: "일률적인 방식"의 실수

이전에 연구자들은 이 잠긴 상자 안에서 역제곱근 문제를 해결하기 위한 레시피를 가지고 있었습니다. 그들은 이를 PP-STAT라고 불렀습니다.

PP-STAT를 케이크를 굽는 고정된 레시피라고 생각해 보세요. 이 레시피는 다음과 같이 말합니다: "밀가루를 정확히 29컵 사용하고, 정확히 6시간 동안 굽습니다."

문제점: 이 레시피는 오직 하나의 특정 주방(Lattigo라는 라이브러리를 사용하는 특정 CPU 컴퓨터 칩)에서만 테스트되었습니다. 그 주방에서는 이 레시피가 괜찮게 작동했습니다.
현실: 하지만 만약 다른 주방으로 옮겨간다면 어떻게 될까요? 예를 들어, 당신에게 초고속 오븐(GPU)이나 다른 종류의 가스레인지(HEaaN이라는 다른 소프트웨어 라이브러리)가 있다면 어떨까요? 이런 새로운 주방에서는 "29컵의 밀가루"를 섞는 데 시간이 너무 오래 걸릴 수도 있고, 반대로 "6시간의 굽는 시간"이 느린 부분이 될 수도 있습니다.
결과: 새로운 주방에서 똑같은 고정된 레시피를 사용하는 것은 비효율적입니다. 당신은 1시간이면 구울 수 있는 것을 6시간 동안 재료를 섞느라 시간을 허비하거나, 혹은 그 반대의 상황을 겪을 수 있습니다. 논문은 어떤 환경에서는 기존 레시피가 잘못된 타이밍에 잘못된 작업을 수행함으로써 필요했던 것보다 거의 6배나 느려질 수 있음을 발견했습니다.

해결책: HE-DAP (똑똑한 주방 보조원)

저자들은 HE-DAP라는 새로운 도구를 만들었습니다. HE-DAP를 단순히 레시피를 따르는 것이 아니라, 주방의 맛을 먼저 보는 똑똑한 주방 보조원이라고 생각해 보세요.

실제 작업을 시작하기 전에, HE-DAP는 당신이 사용 중인 특정 컴퓨터와 소프트웨어에 대해 일련의 빠른 테스트를 실행합니다. 그리고 다음과 같이 묻습니다:

"여기서 밀가루를 섞는 것(수학 연산)이 느린가요, 아니면 굽는 시간(상자를 초기화하는 과정)이 느린가요?"
"밀가루를 적게 쓰는 대신 더 오래 굽는 것이 더 빠를까요?"
"밀가루를 더 많이 쓰는 대신 더 짧게 굽는 것이 더 빠를까요?"

이 테스트를 바탕으로, HE-DAP는 당신의 특정 기기에 딱 맞는 새로운 맞춤형 레시피를 동적으로 작성합니다. 결과물(완벽한 케이크)을 가장 빠른 시간 안에 얻기 위해 정확히 얼마만큼의 "밀가루"(수학적 복잡도)와 몇 번의 "굽기"(반복 횟수)가 필요한지 결정합니다.

작동 원리 (쉬운 설명)

트레이드오프(절충안): 비밀 상자가 부서지는 것을 막기 위해, 당신에게는 두 가지 선택지가 있습니다.
- 옵션 A: 아주 좋은 첫 추측값을 얻기 위해 처음에 매우 복잡한 계산(고차 다항식 사용 등)을 수행합니다. 이 방식은 계산이 쉬울 때는 빠르지만, 어려울 때는 느립니다.
- 옵션 B: 더 단순한 계산을 수행하되, 상자가 부서지지 않도록 "초기화(부트스트래핑)"를 합니다. 이 초기화 과정은 어떤 주방에서는 매우 비싸지만, 어떤 주방에서는 저렴합니다.
적응: HE-DAP는 당신의 특정 컴퓨터에서 어떤 옵션이 더 저렴한지 파악합니다.
- GPU(초고속 그래픽 카드)의 경우, "초기화" 버튼이 믿을 수 없을 정도로 빠릅니다. 그래서 HE-DAP는 이렇게 말합니다. "단순한 계산을 하고 초기화 버튼을 자주 누릅시다!"
- CPU(표준 프로세서)의 경우, "초기화" 버튼이 느립니다. 그래서 HE-DAP는 이렇게 말합니다. "초기화 버튼을 최대한 적게 누를 수 있도록 처음에 복잡한 계산을 합시다!"

결과: 더 빠르고 더 똑똑하게

이 논문은 이 새로운 "스마트 보조원"을 세 가지 유형의 컴퓨터 설정에서 테스트했습니다.

Lattigo (표준 CPU): 프로세스를 1.96배 더 빠르게 만들었습니다.
HEaaN-CPU: 프로세스를 2.18배 더 빠르게 만들었습니다.
HEaaN-GPU: 프로세스를 2.35배 더 빠르게 만들었습니다.

결정적으로, 이것은 단순히 속도만 높인 것이 아니라 결과의 정확도 또한 그대로 유지했습니다. 사실, 어떤 경우에는 잘못된 레시피를 새 기기에 강제로 적용하면서 발생하는 오류를 피했기 때문에 기존의 고정된 레시피보다 오히려 더 정확했습니다.

이것이 왜 중요한가

이 논문은 프라이버시를 보호하는 데이터 분석이 현실 세계에서 작동하려면, 단 하나의 정적인 규칙만을 사용해서는 안 된다는 것을 보여줍니다. 우리는 하드웨어에 적응할 수 있는 시스템이 필요합니다. HE-DAP는 이러한 설정을 자동으로 조정함으로써, 프라이버시를 보호하는 통계 분석을 실용적이고 효율적으로 만들 수 있음을 증명합니다. 즉, 느리고 투박한 과정을 보안과 정확성을 희생하지 않으면서도 거의 두 배 가까이 빠르게 만드는 것입니다.

요약하자면: HE-DAP는 여름에 두꺼운 겨울 코트를 입거나 겨울에 가벼운 티셔츠를 입는 실수를 방지하는 도구입니다. 이는 날씨(컴퓨터 환경)를 확인하고, 당신이 일을 가장 빠르고 편안하게 마칠 수 있도록 완벽한 옷(수학적 파라미터)을 입혀줍니다.

기술 요약: HE-DAP

문제 정의

동형 암호(Homomorphic Encryption, HE)는 암호화된 데이터에 대해 프라이버시를 보호하면서 분석을 가능하게 하지만, 높은 계산 오버헤드라는 문제를 안고 있다. 통계 및 머신러닝 워크로드에서 핵심적인 병목 구간은 역 제곱근(inverse square root, $1/\sqrt{a}$ ) 계산이다. 이는 Z-점수 정규화, 왜도(skewness), 첨도(kurtosis), 피어슨 상관 계수와 같은 함수를 수행하는 데 필수적인 연산이다.

PP-STAT [13] 및 HEaaN-STAT [24]와 같은 기존의 최첨단 방식들은 역 제곱근 계산을 위해 **고정된 파라미터 설정(fixed parameter configurations)**에 의존한다. 이러한 설정은 일반적으로 뉴턴 방법(Newton's method)의 초기화에 사용되는 체비쇼프 다항식(Chebyshev polynomial) 근사의 차수와 고정된 뉴턴-랩슨(Newton-Raphson) 반복 횟수를 포함한다. 저자들은 이러한 정적 접근 방식의 근본적인 결함을 지적한다. 즉, 두 가지 주요 HE 연산인 체비쇼프 다항식 평가와 부트스트래핑(노이즈 관리)의 상대적 계산 비용은 HE 라이브러리(예: Lattigo vs. HEaaN) 및 하드웨어 환경(CPU vs. GPU)에 따라 극적으로(최대 6배까지) 달라진다는 점이다.

결과적으로, 특정 환경(예: 부트스트래핑이 느리고 고차 다항식이 선호되는 Lattigo 기반 CPU 환경)에 최적화된 설정은 다른 환경(예: 부트스트래핑이 빠르고 다항식 평가가 병목인 HEaaN-GPU 환경)에서는 최적이 아니거나 비효율적이 된다. 이러한 환경 의존성은 기존 프레임워크를 일반화하기 어렵게 만들며, 이기종 시스템에 배포될 때 비효효율성을 초래한다.

방법론: HE-DAP

이를 해결하기 위해 저자들은 특정 실행 환경에 따라 역 제곱근 계산을 위한 최적의 파라미터를 자동으로 결정하는 크로스 플랫폼 프레임워크인 HE-DAP(Homomorphic Encryption-based Dynamic Adaptive Parameter Optimization)를 제안한다.

핵심 메커니즘

HE-DAP는 실제 데이터 처리 전의 프로비저닝 단계(provisioning stage) 동안 대상 서버의 성능 특성을 프로파일링하여 작동한다. 이는 CryptoInvSqrt 알고리즘을 위한 세 가지 핵심 파라미터를 동적으로 선택한다:

$d$ : 체비쇼프 다항식 근사의 차수.
$c$ : 사전 부트스트래핑(Pre-Bootstrapping) 여부를 나타내는 이진 지표 (역 제곱근 계산 전에 입력 암호문에 부트스트래핑을 적용함).
$i$ : 뉴턴-랩슨 반복 횟수.

알고-리듬 워크플로우

프로파일링(Profiling): HE-DAP는 $l_{BTS} + 1$ 부터 $l_{max}$ 까지의 모든 가능한 입력 암호문 레벨( $l$ )을 평가한다.
탐색 공간 탐색(Search Space Exploration): 각 레벨에 대해, 다항식 차수( $d$ $d$ ), 사전 부트스트래핑 지표( $c$ $c$ ), 반복 횟수( $i$ $i$ )의 조합을 테스트한다.
- 입력 레벨이 다항식 깊이를 충족하지 못하는 경우, 사전 부트스트래핑( $c=1$ )을 고려한다.
- 레벨이 충분한 경우, 사전 부트스트래핑 없이 진행한다( $c=0$ ).
최적화 기준(Optimization Criteria): 각 조합에 대해 시스템은 **평균 상대 오차(Mean Relative Error, MRE)**와 **실행 시간(runtime)**을 측정한다. 그 후 목표 MRE 임계값을 만족하는 최적의 반복 횟수( $i$ )를 식별한다.
파라미터 선택(Parameter Selection): 프레임워크는 각 레벨에 대해 두 가지 최적의 튜플을 기록한다:
- 정확도 지향(Accuracy-Oriented): 엄격한 MRE 제약 조건 내에서 실행 시간을 최소화한다.
- 속도 지향(Speed-Oriented): MRE와 관계없이 실행 시간을 최소화한다 (높은 오차를 허용하는 애플리케이션에 유용).
런타임 적용(Runtime Application): 실제 통계 분석 중에 서버는 현재 암호문 레벨에 해당하는 사전 계산된 최적 파라미터를 사용하여, 수동 튜닝이나 고정된 최적이 아닌 기본값의 필요성을 제거한다.

주요 기여

HE-DAP 프레임워크: 정적이고 환경 특정적인 파라미터 방식에서 벗어나, 다양한 HE 라이브러리와 하드웨어에 대해 역 제곱근 연산을 자동으로 구성하는 새로운 적응형 옵티마이저를 도입하였다.
성능 향상: HE-DAP가 핵심 역 제곱근 계산을 크게 가속화함을 입증하였다. HEaaN-GPU 환경에서, 고정된 PP-STAT 설정 대비 높은 수치 정확도(MRE $\le 3.1 \times 10^{-8}$ )를 유지하면서 최대 2.35 $\times$ 의 속도 향상을 달면 달성하였다.
포괄적 평가: 세 가지 서로 다른 설정(Lattigo, HEaaN-CPU, HEaaN-GPU)과 네 가지 핵심 통계 척도(Z-score, 왜도, 첨도, 피어슨 상관 계수)에 대해 엄격한 평가를 수행하였다. 결과는 HE-DAP가 CPU 및 GPU 환경 모두에서 일관되게 최적의 구성을 찾아냄을 확인시켜 준다.
오픈 소스: 재현성을 보장하기 위해 HE-DAP의 전체 구현을 공개하였다.

실험 결과

저자들은 CKKS 스킴을 사용하여 PP-STAT(Lattigo 기반) 및 HEaaN-STAT(GPU 기반)을 대상으로 HE-DAP를 평가하였다.

역 제곱근 성능:
- HEaaN-GPU: HE-DAP는 레벨 12에서 PP-STAT의 고정 설정 대비 2.35 $\times$ , 레벨 7(정확도 지향)에서 1.79 $\times$ 가속을 달성하였다. HEaaN-STAT와 비교했을 때, 더 낮은 MRE를 유지하면서 최대 2.15 $\times$ 빠른 실행 시간을 기록하였다.
- HEaaN-CPU: 레벨 12에서 PP-STAT 대비 2.18 $\times$ 의 속도 향상을 달성하였다.
- Lattigo: 레벨 11에서 PP-STAT 대비 1.96 $\times$ 의 속도 향상을 달성하는 동시에, 베이스라인인 PP-STAT보다 MRE를 79배 감소시켰다.
엔드 투 엔드 통계 분석:
- 실제 데이터셋(UCI Adult 및 Medical Cost Insurance)에 대해 Z-정규화(ZNorm), 왜도(Skew), 첨도(Kurt), 피어슨 상관 계수(PCC)를 적용했을 때 일관된 가속이 나타났다.
- Adult 데이터셋에서 HE-DAP는 유사한 MRE를 유지하면서 PP-STAT 대비 실행 시간을 42%~44% 단축시켰다.
- Insurance 데이터셋에서는 실행 시간 단축률이 **44.6%**에 달했다.
트레이드오프 분석: "속도 지향" 모드는 MRE의 증가를 대가로 더 큰 가속(GPU 상에서 HEaaN-STAT 대비 최대 6.34 $\times$ )을 가능하게 하여, 다양한 애플리케이션 요구 사항에 대한 프레임워크의 유연성을 입증하였다.

의의 및 주장

본 논문은 원칙적인 파라미터 최적화가 프라이버시를 보호하는 통계 분석을 실질적인 규모로 구현할 수 있게 함을 보여준다고 주장한다. 이기종 실행 환경에 대한 자동 적응을 통해, HE-DAP는 기존 프레임워크에서 발생하는 비효율성을 해결한다.

저자들은 최적의 다항식 평가와 부트스트래핑 사이의 균형이 보편적인 것이 아니라 특정 HE 라이브러리와 하드웨어에 따라 달라진다는 점을 인정하며, 자신들의 접근 방식이 **환경 인식적(environment-aware)**임을 강조한다. 이러한 트레이드오프를 동적으로 탐색함으로써, HE-DAP는 통계 분석의 근간이 되는 역 제곱근 연산이 최대 효율로 실행되도록 보장하며, 이를 통해 동형 암호의 프라이버시 보장 기능을 훼손하지 않으면서 복잡한 엔드 투 엔드 통계 워크플로의 성능을 높인다.

논문은 프로비저닝 단계(파라미터 탐색)에서 시간 비용(특히 Lattigo와 같은 CPU 라이브러리에서)이 발생하지만, 이는 실제 데이터 처리 단계에서 지속적인 성능 이득을 가져오는 일회성 설정 비용이라고 결론짓는다. 향후 연구로는 철저한 평가 대신 측정 가능한 대리 지표(proxies)를 활용하여 탐색 시간을 줄이는 방향을 제시하였다.