💻 computer science

Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

본 논문은 복제-집계 불변량(replicated-aggregate invariant)을 활용하여 회전 복잡도를 $O(m^2)$ 에서 $O(m)$ 으로 줄임으로써, 비트 역전 동형 암호 레이아웃에 대한 회전 최적 프리픽스 스캔 알고리즘을 소개하며, 이를 통해 계산 지연 시간, 메모리 사용량, 평가 키 저장 공간을 크게 낮추는 동시에 더 깊은 다운스트림 파이프라인을 가능하게 한다.

원저자: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

게시일 2026-07-07

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Anis Bkakria, Madicke-Diadji Mbodj, Mawloud Omar, Reda Yaich

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

당신은 모든 셀에 비밀 숫자가 들어 있는 거대한 암호화된 스프레드시트를 가지고 있다고 상상해 보세요. 당신은 이 모든 숫자들에 대해 한 번에 특정 수학적 기법을 수행하고 싶습니다. 각 셀에 대해, 그 앞에 나온 모든 숫자들의 "누적 합계(running total)"를 알아내야 합니다. 동형 암호(Homomorphic Encryption, 데이터를 복호화하지 않고 암호화된 상태로 계산하는 기술)의 세계에서, 이것은 "프리픽스 스캔(prefix scan)"이라고 불립니다.

문제는 데이터가 1, 2, 3, 4처럼 깔끔한 행 형태로 저장되어 있지 않다는 것입니다. 암호화 방식 때문에 데이터는 **"비트 역순(bit-reversed order)"**이라는 특정한 패턴으로 뒤섞여 있습니다. 이것은 마치 페이지가 뒤섞인 책과 같습니다: 1페이지 다음에는 8페이지가 오고, 그다음엔 4페이지, 그다음엔 12페이지가 오는 식입니다.

기존 방식: "정확한 이웃" 문제

누적 합계를 계산하려면 보통 당신의 이웃에게 숫자를 물어봐야 합니다. 일반적인 행에서는 이웃이 바로 한 단계 옆에 있습니다. 하지만 이 뒤섞인 "비트 역순" 책에서는, 논리적인 이웃이 방 반대편에 앉아 있을 수도 있습니다.

기존 방식은 메신저(회전, rotation)를 보내서 당신이 필요로 하는 정확히 그 이웃을 데려오려고 시도했습니다.

비유: 당신이 8개의 선반이 있는 도서관에 있다고 상상해 보세요. 당신은 왼쪽 바로 옆에 있는 사람과 대화해야 합니다. 하지만 선반들이 뒤섞여 있기 때문에, "왼쪽"이라는 의미는 사람마다 물리적 거리가 다르게 됩니다.
비용: 모든 사람이 올바른 이웃을 얻을 수 있도록 사서가 많은 다양한 경로로 메신저를 보내야 했습니다. 8페이지짜리 작은 책의 경우, 6명의 메신저가 필요했습니다. 더 큰 책의 경우, 이 숫자는 폭발적으로 늘어났습니다(1+2+3+4...와 같이 삼각형 모양으로 증가했습니다). 이는 느리고 비용이 많이 들었으며, 모든 서로 다른 지점으로 메신저를 보내기 위한 수많은 "키(허가증)"가 필요했습니다.

새로운 방식: "카피캣(Copycat)" 전략

이 논문의 저자들은 우리가 너무 까다롭게 굴고 있었다는 사실을 깨달았습니다. 우리는 정확한 이웃이 필요한 것이 아니라, 그저 이웃 그룹과 동일한 정보를 가진 누구라도 필요했던 것입니다.

비유: 왼쪽의 특정 인물에게 묻는 대신, 그룹(선반 블록) 내의 모든 사람이 그룹의 총점에 대한 동일한 복사본을 들고 있다고 상상해 보세요.
마법 같은 움직임: 저자들은 계산의 각 단계마다 도서관 전체를 단 한 번만 회전시키는 방법을 찾아냈습니다. 이 단 한 번의 회전은 모든 사람을 인접한 그룹의 누군가 옆에 서게 만듭니다. 모든 사람이 그 그룹의 총점 복사본을 들고 있기 때문에, 어떤 특정 사람으로부터 정보를 얻느냐는 중요하지 않으며, 수학적 결과는 완벽하게 성립합니다.
결과: 8페이지를 위해 6명의 메신저를 보내는 대신, 당신은 단계당 단 1명의 메신저만 필요하게 됩니다. 전체 책을 기준으로 보면, 메신저가 삼각형 수(예: 28)만큼 필요했던 것에서 단계 수(예: 7)만큼으로 줄어듭니다.

그들이 실제로 증명한 것

이 논문은 단순히 "이것이 더 빠르다"라고 말하는 데 그치지 않습니다. 그들은 세 가지 어려운 수학적 사실을 증명했습니다:

더 나은 방법은 없다: 그들은 아무리 영리하게 행동하더라도, 계산 단계만큼의 회전은 반드시 사용해야 한다는 것을 증명했습니다. 메신저를 아예 건너뛸 수는 없습니다.
"완벽한" 경로: 그들은 최소한의 메신저를 사용한다면, 그 메신저들이 매우 구체적이고 엄격한 패턴(2의 거듭제곱과 관련된)을 따라야 한다는 것을 보여주었습니다. 선택의 여지는 없으며, 수학이 이 특정한 경로를 강제합니다.
트레이드오프(Trade-off): 메신저를 아끼기 위해서는 로컬에서 조금 더 많은 수학적 작업(하나의 숫자 대신 두 세트의 숫자를 유지하는 것)을 해야 합니다. 하지만 그들의 테스트에서, 메신저를 아끼는 것이 훨씬 더 가치 있는 것으로 나타났습니다.

실제 테스트 ( "올림(Carry)" 문제)

그들은 이 기술을 매우 흔한 수학 문제인 **"올림(Carrying numbers)"**에 테스트했습니다 (예를 들어 9 + 3을 하면 12가 되어, 1을 다음 자릿수로 넘겨주는 것과 같습니다).

설정: 그들은 숫자들을 암호화하고, 순서를 뒤섞은 채로 올림 문제를 해결하려고 시었습니다.
결과:
- 속도: 중간 규모의 문제에 대해 새로운 방식이 기존의 "정확한 이웃" 방식보다 약 20% 더 빨랐습니다.
- 메모리: 많은 허가 키를 저장할 필요가 없었기 때문에 메모리를 64% 적게 사용했습니다.
- 큰 승리: 긴 계산 체인에서, 그들의 방식은 "부트스트래핑(bootstrapping)"이라 불리는 매우 느린 리셋 절차를 피할 수 있을 만큼 충분한 "암호화 능력"을 아껴주었습니다. 이로 인해 전체 과정이 4.3배 더 빨라졌습니다.

요약

릴레이 경주라고 생각해보세요.

기존 방식: 모든 주자가 자신의 특정 팀원을 찾기 위해 고유하고 길며 구불구불한 경로를 달려야 했습니다. 많은 에너지와 시간이 소요되었습니다.
새로운 방식: 팀은 그저 짧고 표준화된 루프를 돌기만 하면, 모두가 똑같은 바턴을 든 누군가 옆에 서게 된다는 것을 깨달았습니다. 주자들이 몇 개의 바턴을 더 들고 있어야 했음에도 불구하고, 더 적은 단계와 적은 에너지를 사용하여 일을 완수했습니다.

이 논문은 이와 같은 종류의 뒤섞인 암호화 데이터에 대해 이 방식이 가능한 가장 빠른 방법임을 증명합니다.

기술 요약: 비트 역순 호모모픽 레이아웃에서의 회전 최적화 비가환 접두사 스캔

문제 정의

패킹된 호모모픽 암호화(HE), 특히 CKKS 스킴에서, SIMD 연산은 암호화된 벡터에 대한 병렬 계산을 허용한다. 그러나 슬롯 간의 통신은 순환 회전(갈로아 오토모피즘)을 필요로 하며, 이는 키 스위칭을 수반하는 비용이 큰 연산이다. 회전 비용은 데이터의 물리적 레이아웃에 따라 달라진다.

본 논문은 $n = 2^m$ 개의 요소로 구성된 결합 법칙이 성립하는(비가환 모노이드일 수 있는) 순서 있는 접두사 계산(스캔)을 **비트 역순 순서(bit-reversed order)**로 저장된 경우에 수행하는 문제를 다룬다. 이 레이아웃은 빠른 변환 및 패킹 변환 시 흔히 사용된다.

핵심 과제는, 논리적 전구체(predecessor)까지의 거리를 재귀적으로 두 배씩 늘리는 표준 "전송된 전구체(transported-predecessor)" 스캔 방식이 비트 역순 레이아웃에서는 높은 라우팅 비용을 초래한다는 점이다. 비트 역순은 논리적 인덱스를 치환하므로, 단일 논리적 이동 $2^t$ 는 여러 개의 서로 다른 순환 변위 클래스로 분해된다. 결과적으로, 직접적인 구현은 $R_{direct} = \sum_{t=0}^{m-1} (m-t) = \frac{m(m+1)}{2}$ 번의 회전을 요구한다. 저자들은 이러한 삼각 형태의 비용이 비트 역순 레이아웃에서의 접두사 계산의 고유한 특성인지, 아니면 특정 라우팅 토폴로지의 산물인지를 조사한다.

방법론 및 구성

본 논문은 회전 횟수를 이차(quadratic)에서 선형(linear)으로 줄이기 위해 **복제된 집계 불변량(replicated-aggregate invariant)**을 도입한다.

의미적 복제(Semantic Replication): 모든 슬롯을 정확한 논리적 전구체로 라우팅하는 대신, 정렬된 논리 블록 내의 모든 슬롯이 해당 블록의 **완전한 집계값(complete aggregate)**을 저장하도록 상태를 유지한다.
형제 블록 교환(Sibling-Block Exchange): 스캔의 각 레벨 $d$ $d$ (크기 $2^d$ $2^{d}$ 인 블록들을 결합)에서, 알고리즘은 특정 오프셋 $s_d = 2^{m-d-1}$ $s_{d} = 2^{m - d - 1}$ 만큼 집계 상태를 회전시킨다.
- 비트 역순 하에서, 부모 블록의 두 자식은 정확히 $s_d$ 만큼 떨어진 물리적 코셋(coset)을 점유한다.
- $s_d$ 만큼의 회전은 슬롯을 형제 블록 내의 어떤 위치로 매핑한다. 형제 블록의 집계값은 모든 슬롯에 복제되어 있으므로, 형제 블록 내의 어떤 위치든 올바른 의미적 값을 제공한다.
- 이를 통해 단일 방향 순환 변위를 사용하여 두 자식 방향 모두에 유효한 집계값을 동시에 공급할 수 있으며, 공용 마스크(public masks)를 통해 피연산자의 순서를 선택함으로써 비가환 모노이드에 대한 정당성을 보존한다.
배타적 스캔 공식화(Exclusive Scan Formulation): 본 논문은 배타적 스캔(현재 요소 전의 접두사를 출력)을 구현한다. 이는 자릿수 교정(digit correction)을 위한 유입되는 캐리를 가져오기 위해 마지막 논리적 전구체 이동을 수행할 필요를 없애주며, 그렇지 않을 경우 레이아웃에 민가한 라우팅이 다시 도입될 수 있다.
하한선 증명(Lower Bound Proofs): 저자들은 $2^m$ 개의 입력을 모두 사용하는 회로를 계산하는 모델에서 $m$ 번의 회전이 전역적 하한임을 입증한다. 이 증명은 부분집합 합(subset-sum) 논리에 기반한다. 만약 $R$ 번의 회전이 사용된다면, 최대 $2^R$ 개의 고유한 입력 변위가 고정된 출력에 도달할 수 있다. 모든 $2^m$ 개의 입력을 커버하려면 $R \ge m$ 이 필수적이다. 또한, 본 논문은 이 하한을 달성하기 위해서는 회전 오프셋이 완전한 2-진 기저(2-adic basis)(값 $0, \dots, m-1$ 에 대한 하나의 오프셋)를 형성해야 함을 증명한다.

주요 기여

최적 스캔 구성: 비트 역순 레이아웃에 대해 $R = m$ 번의 회전과 $D = m$ 의 모노이드 깊이를 달성하는 포함적(inclusive) 및 배타적(exclusive) 스캔 알고리즘을 제공한다. 이는 회전 횟수를 직접적인 토폴로지의 $O(m^2)$ 에서 $O(m)$ 으로 감소시킨다.
최적성의 경직성(Rigidity of Optimality): 모든 최적 회로에 대한 특성화를 제공한다. 회로가 정확히 $m$ 번의 회전을 사용하는 경우, 오프셋은 완전한 2-진 기저를 형성해야 한다. 이는 회로의 토폴로지가 변하더라도 회전 프로파일은 경직되어 있음을 증명한다.
회전-키 프런티어(Rotation-Key Frontier): 직접 키가 지정된 오프셋의 수( $K$ $K$ )와 온라인 회전 호출 횟수( $R$ $R$ ) 사이의 트레이드오프를 분석한다.
- 본 논문은 곱 형태의 하한 $\prod (c_j + 1) \ge 2^m$ 을 도출한다 (여기서 $c_j$ 는 키 $j$ 가 사용된 횟수이다).
- $K$ 가 $m$ 을 나누는 경우, 정확한 프런티어는 $R^* = K \cdot (2^{m/K} - 1)$ 임이 증명되었다.
Radix-CKKS 인스턴스화: 배타적 스캔을 **진법 기반 CKKS의 정확한 캐리 및 빌림 전파(exact carry and borrow propagation)**에 적용한다. 이를 통해 자연스러운 순서를 복구하거나 최종 시프트를 수행하지 않고도 정수 비교 및 나머지 연산을 수행할 수 있다.
배칭 효율성(Batching Efficiency): 복제된 스캔의 이점이 회전 횟수를 배가시키지 않으면서 $g$ 개의 독립적인 정수가 단일 암호문에 패킹된 digit-major interleaving에서도 유지됨을 입증한다.

결과 및 평가

저자들은 알고리즘을 Lattigo(Go)로 구현하여 다음 두 가지 베이스라인과 비교하였다:

직접 비트 역순 전구체(Direct Bit-Reversed Predecessor): 나이브한 $O(m^2)$ 회전 방식.
정규화-스캔-복구(Normalize–Scan–Restore): 데이터를 자연 순서로 변환하고, 스캔한 뒤, 다시 변환하는 베이스라인.

$m=7$ (128 슬롯)에서의 주요 결과:

회전: 28회(직접 방식)에서 7회(복제 방식)로 감소.
평가 키(Evaluation Keys): 저장 공간이 70.0% 감소 (908.6 MB $\to$ 272.6 MB).
메모리: 피크 힙 사용량이 63.9% 감소 (2.30 GB $\to$ 830.5 MB).
지연 시간(Latency): 복제된 스캔은 직접 전구체 방식보다 격리된 스캔 지연 시간을 19.9% 개선했다.
엔드 투 엔드 파이프라인: 깊이-5의 다운스트림 파이프라인에서, 복제된 스캔은 normalize-restore 베이스라인에서 요구되는 전체 부트스트래핑 연산을 피할 수 있었다. 이는 평균 4.31배의 속도 향상을 가져왔다 (95% CI [3.69, 4.92]).

본 논문은 "normalize–scan–restore" 방식이 작은 $m$ 에 대해서는 모노이드 합성 횟수가 적어 격리된 지연 시간이 더 낮을 수 있지만, $m \ge 5$ 인 경우 복제된 스캔이 더 빨라지며 리소스 효율성(키, 메모리, 모듈러스 레벨) 측면에서 우월하다고 언급한다.

의의 및 주장

본 논문은 비트 역순 SIMD 표현을 유지하는 것이 순서 있는 접두사 계산에 있어 피할 수 없는 회전 오버헤드를 부과하지 않는다는 점을 주장한다. 이 연구의 의의는 다음과 같다:

이차 장벽 돌파: 비트 역순 레이아웃에서의 직접적인 라우팅이 갖는 $O(m^2)$ 비용이 고유한 특성이 아니라, 의미적 복제를 통해 이론적 하한인 $O(m)$ 으로 줄일 수 있음을 증명했다.
리소스 트레이드오프: 회전 비용(회전)과 키 저장소의 감소가 패킹된 모노이드 연산( $2m-1$ 합성 vs $m$ ) 및 두 번째 라이브 상태 벡터의 증가라는 비용을 수반함을 밝힌다. 저자들은 이 트레이드오프가 모듈러스 레벨과 부트스트래핑이 병목이 되는 깊은 파이프라인에서 유리하다고 주장한다.
정확성: 휴리스틱 최적화를 넘어, 특정 의존성 패턴에 대한 증명 가능한 한계와 회전-키 관리를 위한 정확한 하한 및 프런티어 특성화를 제공한다.

이 작업은 비트 역순 레이아웃 제약에 특화된 최적화로서 일반적인 접두사 네트워크 이론과는 구별되며, 엄격한 조합론적 증명과 표준 CKKS 구현에서의 경험적 평가를 통해 검증되었다.