💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

본 논문은 재구성된 연산, 추가 평가 키, 그리고 다단계 리스케일링 방식을 통해 두 개 이상의 입력을 지원하도록 확장된 동형 암호를 위한 최적화된 다입력 암호문 곱셈 방법을 제안하며, 이로 인해 기존 설계에 비해 논리 영역과 지연 시간을 크게 줄이는 하드웨어 아키텍처를 도출한다.

원저자: Sajjad Akherati, Xinmiao Zhang

게시일 2026-05-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Sajjad Akherati, Xinmiao Zhang

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

당신이 두꺼운 무거운 오븐 장갑을 끼고 있어 재료를 만져보거나 볼을 볼 수 없는데도 모든 섞기와 굽기를 해야 하는 마스터 셰프라고 상상해 보세요. 이것이 바로 **동형 암호화 (HE)**입니다. 이는 컴퓨터가 "암호화된" 데이터(장갑 안의 케이크 반죽) 를 해독(장갑을 벗는 것) 하지 않고도 수학 연산을 수행할 수 있게 합니다. 이는 의료 기록이든 은행 잔고가든 비밀을 안전하게 보호합니다.

그러나 이러한 "장갑"을 끼고 수학을 수행하는 것은 매우 느리고 지저분합니다. 가장 큰 병목 현상은 곱셈입니다. 표준 암호화에서는 한 번에 두 가지 재료만 곱할 수 있습니다. 하지만 질병을 인식하는 AI 를 훈련시키거나 복잡한 금융 추세를 분석하는 것과 같은 많은 현대적 작업은 한 번에 많은 재료(암호문) 를 곱해야 합니다.

이 논문은 인기 있는 암호화 방법인 CKKS를 위해 이러한 암호화된 재료를 곱하는 새로운 초효율적인 방법을 소개합니다. 여기 간단한 비유를 사용한 그들의 획기적인 성과에 대한 설명이 있습니다:

1. 문제: "지저분한 주방"

암호화된 숫자를 곱할 때 "노이즈"(오븐 장갑이 만들어낸 지저분함) 가 점점 더 커집니다. 너무 많은 숫자를 한 번에 곱하고 정리하지 않으면 노이즈가 실제 데이터를 덮어버려 결과가 쓰레기가 됩니다.

이를 해결하기 위해 암호화 시스템은 곱셈 후 **리스케일링 (Rescaling)**이라는 "정리" 단계를 수행해야 합니다. 이를 카운터를 닦고 재료를 다시 정리하기 위해 멈추는 것으로 생각하세요.

옛 방식: 10 가지 재료를 곱해야 한다면, 옛 방식은 두 개를 곱하고 멈춰서 정리한 뒤, 두 개를 더 곱하고 멈춰서 정리하는 식의 컨베이어 벨트와 같았습니다. 이는 느렸고 많은 정리 용품(하드웨어 자원) 이 필요했습니다.
이전의 "세 가지 재료" 시도: 저자들의 이전 연구는 세 가지 재료를 한 번에 곱할 수 있음을 보여줬으며, 이는 더 빨랐습니다. 하지만 여전히 불필요한 정리 단계가 많았습니다.

2. 해결책: "스마트 조립 라인"

저자들은 이 과정을 더 빠르고 작게 만들기 위해 두 가지 주요 업그레이드를 제안합니다:

A. "한 번의 정리" (개선된 3 입력 곱셈)

세 가지 재료를 곱하는 새로운 설계에서 그들은 정리 (리스케일링) 와 재배치 (선형화) 를 어색하고 우회적인 방식으로 수행하고 있음을 깨달았습니다.

비유: 반죽이 든 그릇 세 개가 있다고 가정해 보세요. 옛 방식은 그들을 섞고, 섞은 것을 새 그릇에 부은 뒤, 옛 그릇을 닦고, 다시 섞은 것을 부은 뒤, 또다시 닦는 것이었습니다.
해결책: 그들은 섞고 정리를 한 번의 매끄러운 동작으로 할 수 있도록 과정을 재설계했습니다. 카운터를 닦는 횟수를 줄이기 위해 정리 단계를 결합하는 방법을 찾아냈습니다.
결과: 그들의 새로운 "세 그릇 믹서"는 이전 최고의 설계에 비해 속도 (지연 시간) 가 50% 빨라졌고, 칩에서 차지하는 공간 (면적) 이 15% 줄었습니다.

B. "그룹 정리" (다중 입력 곱셈)

만약 네 개, 다섯 개, 심지어 열두 개의 재료를 한 번에 곱해야 한다면 어떨까요?

옛 방식: 당신은 "두 그릇 믹서"의 긴 줄을 만들 것입니다. 두 개를 섞고 정리한 뒤, 두 개를 더 섞고 정리한 뒤, 그 결과를 섞고 다시 정리합니다. 이는 매우 긴 줄 (높은 "곱셈 깊이") 을 만들어 노이즈가 너무 빨리 쌓이게 합니다.
새 전략: 저자들은 재료를 다르게 그룹화하면 **"그룹 정리"**를 할 수 있음을 깨달았습니다.
- 매 단계마다 정리하는 대신, 그들은 **멀티 리스케일링 (Multi-Rescaling)**이라고 불리는 수학적 트릭을 개발하여 여러 층의 지저분함을 한 번에 정리할 때까지 기다릴 수 있게 했습니다.
- 비유: 접시를 씻고, 말리고, 치운 뒤, 컵을 씻고, 말리고, 치우는 대신, 접시 더미를 한 번에 씻고, 더미를 한 번에 말린 뒤, 모두 치우는 것을 상상해 보세요. 당신은 "말리는" (비싸고 느린) 작업을 전체 그룹에 대해 한 번만 수행합니다.
결과: 재료를 그룹화하는 방식 (분할) 을 재배열함으로써 이러한 정리 단계를 결합할 수 있습니다. 4 개에서 12 개 사이의 재료를 곱할 때, 그들의 새로운 방법은 기존의 "두 개씩" 방식에 비해 공간을 32% 절약하고 시간을 절반으로 줄여 45% 더 빠릅니다.

3. 이것이 중요한 이유 (논문에 따르면)

이 논문은 엄격하게 하드웨어 아키텍처, 즉 이 수학을 수행하는 컴퓨터 칩의 물리적 설계에 초점을 맞춥니다.

그들은 수학을 조직하는 방식 (알고리즘) 과 칩을 구축하는 방식 (아키텍처) 을 변경함으로써 복잡한 암호화된 수학을 훨씬 더 빠르게 수행할 수 있음을 증명했습니다.
그들은 특히 머신 러닝, 의료 진단, 금융 분석과 같은 응용 분야에 도움이 된다고 구체적으로 언급했는데, 이러한 분야는 종종 많은 암호화된 데이터 포인트를 함께 곱해야 하기 때문입니다.

요약

이 논문은 오븐 장갑을 벗을 수 없는 셰프를 위한 새로운 초효율적인 주방을 발명하는 것과 같습니다.

그들은 지저분함을 만들지 않고 세 가지 재료를 한 번에 섞는 방법을 알아냈습니다.
그들은 하나씩이 아니라 여러 층의 지저분함을 동시에 정리하는 방법을 고안했습니다.
그 결과, 복잡한 수학을 수행하면서도 비밀을 안전하게 지키는 데 더 작고, 더 빠르고, 더 적은 에너지가 필요한 주방이 되었습니다.

저자들은 이 논문에서 실제 환자나 실제 은행 계좌를 테스트하지 않았습니다. 그들은 이 작업을 수행하도록 설계된 기계가 우리가 이전에 가지고 있던 기계보다 훨씬 더 우수함을 증명했을 뿐입니다.

기술 요약: 동형 암호화를 위한 다중 입력 암호문 곱셈

문제 제기
동형 암호화 (HE), 특히 RNS-CKKS 방식은 암호화된 데이터에 대한 산술 연산을 가능하게 하여 머신러닝 및 의료 진단과 같은 프라이버시 보호 응용 분야에서 중요합니다. 그러나 표준 HE 방식은 암호문 곱셈을 두 개의 입력에 대해서만 정의합니다. 신경망 활성화 함수 (예: ReLU) 의 고차 다항식 근사, 의사결정나무, 게놈 시퀀싱 등 많은 실용적 응용 분야는 여러 개의 암호문 ( $n > 2$ ) 을 곱하는 것을 요구합니다.

다중 입력 곱셈을 처리하는 기존 접근 방식은 일반적으로 이진 트리 구조로 여러 개의 2 입력 곱셈기를 체인 (chain) 합니다. 이 방법은 두 가지 주요 비효율성을 겪습니다:

높은 지연 시간과 면적: 2 입력 유닛을 사용하여 $n$ 개의 암호문을 순차적으로 곱하면 상당한 하드웨어 오버헤드와 지연 시간이 발생합니다.
노이즈 증가 및 리스케일링 오버헤드: 각 곱셈은 노이즈 수준을 증가시키므로 메시지 스케일을 복원하기 위해 리스케일링 연산이 필요합니다. 표준 이진 트리에서는 지수적 노이즈 증가를 방지하기 위해 각 곱셈 단계 후에 리스케일링이 수행되어야 합니다. 이로 인해 각각 비싼 정수론적 변환 (NTT) 및 역 정수론적 변환 (INTT) 연산이 필요한 많은 수의 리스케일링 유닛이 필요하게 되어, 계산 복잡도와 하드웨어 자원 사용량이 크게 증가합니다.

방법론
본 논문은 곱셈 깊이를 최소화하고 하드웨어 복잡도를 줄이는 직접적인 $n$ 입력 암호문 곱셈을 위한 프레임워크를 제안합니다. 방법론은 두 가지 주요 기여로 나뉩니다:

개선된 3 입력 곱셈기:
저자들은 먼저 3 입력 곱셈 과정을 재구성합니다. 선행 연구 [26] 에서는 리네어라이제이션과 리스케일링이 별도로 수행되어 여러 번의 ModUp/ModDown 연산과 수많은 (I)NTT 블록이 필요했습니다. 새로운 설계는 다음과 같습니다:
- 리네어라이제이션 재구성: $P^{-1}$ 스케일링 인자를 기저 변환 (BConv) 및 평가 키 곱셈 내부로 이동시켜 별도의 스케일링 단계를 제거합니다.
- 최적화된 리스케일링: 저자들은 데이터 경로를 재구성하여 최종 NTT 이전의 원래 도메인에서 리스케일링을 수행하도록 하여, NTT 도메인에서의 리스케일링을 피합니다. 이를 통해 중복된 (I)NTT 연산을 제거할 수 있습니다.
- 결과: 이러한 변경 사항으로 데이터 경로 내 (I)NTT 블록의 수가 8 개에서 4 개로 줄어들어 데이터 경로 길이가 효과적으로 절반으로 단축됩니다.
결합된 리스케일링을 통한 다중 입력 확장:
곱셈 깊이를 증가시키지 않고 곱셈을 $n > 3$ 개의 입력으로 확장하기 위해, 논문은 다음을 도입합니다:
- 일반화된 평가 키: $n$ 개의 암호문을 곱하여 생성된 고차 다항식 항 ( $d_t s^t$ ) 을 리네어라이제이션하여 결과를 다시 2 다항식 형식으로 줄이는 새로운 평가 키 ( $ek_t$ ) 가 도입됩니다.
- 멀티-리스케일링 (Multi-RS) 알고리즘: 이론적 분석을 통해 여러 리스케일링 연산을 지연하고 결합할 수 있는 조건을 규명합니다. 저자들은 단일 리스케일링과 동일한 수의 (I)NTT 연산을 사용하여 $\mu$ 개의 연결된 리스케일링 연산을 수행하는 알고리즘을 제안합니다. 이는 입력을 INTT 도메인으로 변환한 후, 계수 도메인에서 반복적인 리스케일링을 수행하고 다시 변환하여, 사전 계산된 상수를 활용하여 연산을 병합함으로써 달성됩니다.
- 입력 분할 가이드라인: 논문은 최적의 곱셈 깊이인 $\lceil \log_2 n \rceil$ 을 유지하면서 결합된 리스케일링 연산의 수를 최대화하기 위해 $n$ 개의 입력을 그룹 (예: $(n_1, n_2, \dots, n_m)$ ) 으로 분할하는 가이드라인을 제공합니다. 이는 리스케일링 단계 전에 더 많은 입력을 그룹화할 수 있도록 가능한 경우 불균형 트리 구조를 생성하는 것을 포함합니다.

주요 기여

알고리즘적 재구성: 중간 계산을 결합하여 (I)NTT 연산의 수를 줄이고 데이터 경로를 단축하는 3 입력 곱셈을 위한 새로운 공식화.
다중 입력 프레임워크: 일반화된 평가 키와 트리 구조 곱셈기를 사용하여 임의의 $n$ 개 입력으로 암호문 곱셈을 확장.
결합된 리스케일링: 결합 단계 수 ( $\mu$ ) 에 관계없이 여러 리스케일링 수행의 복잡도를 단일 리스케일링 수준으로 줄이는 새로운 멀티-리스케일링 알고리즘.
하드웨어 아키텍처: 제안된 곱셈기를 위한 풀 파이프라인 하드웨어 아키텍처 설계로, 최적화된 ModUp, ModDown 및 리스케일링 유닛을 포함합니다.

결과
제안된 설계는 $N=2^{16}$ , $L=K=24$ , $w=64$ 의 파라미터로 GlobalFoundries 22FDX 공정을 사용하여 합성되었습니다.

3 입력 곱셈기: 선행 연구 [26] 와 비교하여 개선된 3 입력 곱셈기는 논리 면적이 15% 감소하고 지연 시간이 50% 감소했습니다. 또한 (I)NTT 유닛이 줄어들어 메모리 요구 사항이 약 20% 감소했습니다.
다중 입력 곱셈기 ( $n=4$ 에서 $12$): 2 입력 곱셈기의 이진 트리를 사용한 기준 구현과 비교하여 제안된 방법은 평균 총 면적이 32% 감소하고 지연 시간이 45% 감소했습니다.
리스케일링 효율성: 2 의 거듭제곱이 아닌 입력 (예: $n=17$ ) 의 경우, 최적화된 분할과 멀티-리스케일링을 결합하면 표준 이진 트리 접근 방식에 비해 리스케일링 유닛 (및 관련 (I)NTT 연산) 의 총 수가 약 47% 감소합니다.

의의
본 논문은 이러한 개선 사항이 복잡한 프라이버시 보호 응용 프로그램에 필수적인 HE 의 다중 입력 곱셈 병목 현상을 해결한다고 주장합니다. 암호문 곱셈의 하드웨어 복잡도와 지연 시간을 줄임으로써 제안된 아키텍처는 리소스 제약 환경이나 고처리량 환경에서 HE 의 배포를 더 실현 가능하게 만듭니다. 이 연구는 알고리즘적 재구성과 신중한 입력 분할을 통해 암호화 방식의 보안이나 정확성을 훼손하지 않고 노이즈 관리 (리스케일링) 의 오버헤드를 크게 최소화할 수 있음을 보여줍니다. 저자들은 향후 연구가 더 많은 수의 입력을 위한 곱셈기를 더욱 단순화하는 데 초점을 맞출 것이라고 언급합니다.

1. 문제: "지저분한 주방"

2. 해결책: "스마트 조립 라인"

A. "한 번의 정리" (개선된 3 입력 곱셈)

B. "그룹 정리" (다중 입력 곱셈)

3. 이것이 중요한 이유 (논문에 따르면)

요약

유사한 논문