💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

SafeStats는 빈도 계산, 정렬 및 비선형 수학 함수를 특화된 프로토콜을 통해 최적화함으로써 범용 라이브러리 대비 상당한 속도 향상과 통신 감소를 달성하며 통계 분석에 맞춤화된 효율적인 보안 양자 간 연산 툴킷입니다.

원저자: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

게시일 2026-07-29

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

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

당신과 친구가 함께 미스터리를 풀려고 한다고 상상해 보세요. 하지만 두 사람에게는 엄격한 규칙이 하나 있습니다. 서로의 개인적인 단서(clue)를 절대 보여주지 않는 것입니다. 예를 들어, 실제 숫자를 공개하지 않고도 누가 돈을 더 많이 가졌는지 확인하기 위해 각자의 은행 계좌를 비교하거나, 자신의 건강 기록을 노출하지 않고 특정 질병 패턴과 일치하는지 확인하는 것과 같습니다. 이것이 바로 **안전한 2자간 계산(Secure Two-Party Computation, 2PC)**의 세계입니다. 이것은 두 사람이 서로의 찬장 안을 들여다보지 않고도, 비밀 재료를 섞어 케이크(결과물)를 구울 수 있는 마법 같은 잠긴 방이라고 생각하면 됩니다. 오랫동안 과학자들은 이 잠긴 방 안에서 간단한 수학적 계산(더하기나 곱하기 등)을 돕기 위한 놀라운 도구들을 만들어 왔습니다. 하지만 정렬(sorting)이나 특정 범주에 속하는 사람의 수를 세는 것과 같이 더 복잡한 과제를 수행할 때, 기존의 도구들은 느리고 투박하며 실생활에서 사용하기에는 너무 비용이 많이 드는 경우가 많았습니다.

여기, 이러한 통계적 미스터리를 훨씬 더 쉽게 해결할 수 있도록 설계된 새로운 툴킷인 SAFESTATS가 등장했습니다. 연구원 탠렌 리우(Tanren Liu)와 그의 팀이 만든 이 툴킷은, 만약 기존 방식이 모든 카드를 하나하나 서로 비교하며 덱을 정렬하는 것이었다면, SAFESTATS는 마치 전체 덱을 한 번의 매끄러운 동작으로 정렬할 수 있는 아주 똑똑한 조수를 둔 것과 같습니다. 연구팀은 대부분의 통계적 작업이 세 가지 주요 업무, 즉 '무언가가 얼마나 자주 나타나는지 세기', '순서대로 정렬하기', 그리고 '까다로운 비선형 수학 연산하기'로 요약된다는 점에 주목했습니다. 이 세 가지 업무를 위한 영리한 지름길을 발명함으로써, 그들은 훨씬 더 빠르고 "대화"(통신)가 적게 필요한 시스템을 만들어냈습니다. 테스트 결과, 이들의 새로운 방식은 특정 작업에서 기존 시도들보다 최대 20배 더 빨랐으며, 이는 개인정보를 보호하면서도 복잡한 데이터 분석을 기다림 없이 수행할 수 있음을 증명했습니다.

SAFESTATS의 세 가지 마법 기술

연구진은 사람들이 실제로 데이터를 분석할 때 무엇을 하는지 알아보기 위해 표준 스프레드시트 프로그램(Microsoft Excel과 같은)을 살펴보았습니다. 그들은 거의 모든 것—최빈값(Mode)을 찾거나, 중앙값(Median)을 구하거나, 카이제곱 검정(Chi-Square test)을 실행하는 것 등—이 단 세 가지 핵심 구성 요소에 의존한다는 것을 발견했습니다. SAFESTATS는 이 세 가지 블록이 비밀스럽고 효율적으로 작동하도록 재발명했습니다.

1. 세기를 위한 "시프트(Shift)" 기술
당신에게 100개의 빈 상자가 있는 줄이 있고, 데이터 리스트에서 비밀 숫자, 예를 들어 "7"이 몇 번 나타나는지 세고 싶다고 가정해 봅시다. 기존 방식은 리스트의 모든 항목에 대해 "이 숫자가 7인가?"라고 묻는 것이었습니다. 만약 아이템이 백만 개라면, 백만 번의 질문을 던져야 하므로 시간이 엄청나게 오래 걸립니다.
SAFESTATS는 대신 "시프트" 기술을 사용합니다. 하나의 전등 스위치가 켜져 있고 나머지 스위치는 모두 꺼져 있다고 상상해 보세요. 만약 당신의 비밀 숫자가 7이라면, 당신은 그 "켜진" 불빛을 오른쪽으로 일곱 칸 밀기만 하면 됩니다. 이제 불빛은 7번째 상자에 위치하게 됩니다. 당신은 비밀 리스트의 모든 항목에 대해 이 작업을 수행하지만, 아무도 당신이 불빛을 어느 상자로 옮기는지 알 수 없는 방식으로 수행합니다. 마지막으로, 각 상자에 있는 불빛을 모두 더하기만 하면 됩니다. 만약 7번째 상자에 50개의 불

2. 정렬을 위한 "버킷(Bucket)" 기술
비밀 데이터를 정렬하는 것은 보통 숫자를 비교하여 어느 쪽이 더 큰지 확인해야 하기 때문에 악몽과 같습니다. 하지만 비교할 필요가 없다면 어떨까요? SAFESTATS는 숫자가 아주 크지 않을 때(예: 무작위의 거대한 숫자가 아니라 0~100 사이의 나이를 정렬할 때) 완벽한 "계수 정렬(Counting Sort)"이라는 방법을 사용합니다.
이것은 마치 100개의 우편함이 있는 우체국과 같습니다. "이 편지가 5번 슬롯용인가, 6번 슬롯용인가?"라고 묻는 대신, 그냥 번호에 맞는 슬롯에 편지를 넣기만 하면 됩니다. SAFESTATS는 이를 비밀리에 수행합니다. 그들은 "구간 지표(segment indicator)" 프로토un콜이라는 특별한 방법을 사용합니다. 당신에게 비밀 숫자 리스트가 있다고 상상해 보세요. 숫자를 하나씩 정렬하는 대신, 시스템은 "모든 5는 최종 리스트의 특정 범위에 들어간다"라고 말하는 "지도"를 만듭니다. 그런 다음 모든 5를 한꺼번에 그 범위에 떨어뜨립니다. 이는 느리고 비밀스러운 비교 과정을 건너뛰게 해줍니다. 값의 범위가 작은 데이터셋의 경우, 이 새로운 방법은 기존의 가장 좋은 방법들보다 3.4배에서 20.5배 더 빠른 것으로 나타났으며, 통신 비용을 최대 7.6배까지 절감했습니다.

3. 어려운 수학을 위한 "이분법(Bisection)" 기술
일부 통계 공식은 제곱근이나 로그와 같이 비밀리에 계산하기 까다로운 수학을 포함합니다. 일반적인 방법은 먼저 숫자를 관리 가능한 크기로 축소한 다음(마치 지도를 축소하는 것처럼) 다항식 공식을 사용하여 답을 추측하는 것입니다. 여기서 느린 부분은 얼마나 축소할지를 결정하는 것이었습니다.
기old 방식은 특정 단어를 찾기 위해 책 페이지를 한 페이지씩 넘겨보는 것과 같았습니다. SAFESTAT는 "숫자 맞추기 게임"과 같은 "이분법" 방법을 사용합니다. 책의 페이지를 하나하나 확인하는 대신, 책을 반으로 나누고, 단어가 앞쪽 절반에 있는지 뒤쪽 절반에 있는지 확인한 다음, 다시 그 절반을 또 반으로 나눕니다. 숫자가 정확히 어디에 위치해야 하는지 찾을 때까지 검색 범위를 계속 절반으로 줄여나갑니다. 이 "분할 정복(divide and conquer)" 접근 방식은 이러한 수학 함수를 처리하는 데 걸리는 시간을 1.2배에서 1.7배 단축했으며, 통신 시간 또한 절약했습니다.

종합: 카이제곱 검정

연구진은 이 툴킷이 제대로 작동하는지 증명하기 위해 14가지의 다양한 실제 통계 시나리오에 대해 SAFESTATS를 테스트했습니다. 눈에 띄는 사례 중 하나는 두 가지 요소가 서로 관련이 있는지(예: 빨간 셔츠를 입는 것이 운에 영향을 미치는지) 확인하는 데 흔히 사용되는 카이제곱 검정이었습니다.
기존의 범용 도구들을 사용하여 이 테스트를 실행했을 때는 느리고 통신량이 많았습니다. 하지만 SAFESTATS를 사용했을 때 결과는 인상적이었습니다. 테스트는 1.5배 더 빠르게 실행되었고, 두 당사자가 주고받아야 하는 데이터의 양은 4.2배 감소했습니다.

이 논문은 단순히 이러한 결과만을 주장하는 것이 아닙니다. 연구진은 실제로 이 시스템을 구축하고 수치를 실행했습니다. 그들은 통계 분석의 특수한 요구 사항에 집중함으로써(즉, "모두를 위한 하나의 도구"를 만들려 하기보다), 데이터를 비공개로 유지하면서도 우리에게 필요한 답을 얻을 수 있는 훨씬 더 효율적인 방법을 만들 수 있음을 보여주었습니다. 이는 때때로 문제를 해결하는 가장 좋은 방법은 더 큰 망치를 만드는 것이 아니라, 더 나은 드라이버를 발명하는 것임을 상기시켜 줍니다.

기술 요약: SAFESTATS

문제 정의

민감한 데이터셋(예: 의료 기록, 금융 거래)에 대한 통계 분석은 의사결정에 매우 중요하지만 심각한 개인정보 보호 문제를 야기합니다. 보안 2자 계산(Secure Two-Party Computation, 2PC)은 저수준 프리미티브(덧셈, 곱셈)와 머신러닝 응용 분야에서 크게 발전해 왔으나, 특정 통계 함수를 처리하는 데 있어서는 여전히 비효율적입니다. 기존의 접근 방식들은 일반적으로 범용 2PC 프리미티브를 직접 조합하여 통계 연산(예: 중앙값, 순위, 최빈값)을 재현하려고 시도합니다. 이러한 "나이브한(naive)" 조합은 과도한 오버헤드를 초래합니다. 예를 들어, $2^{12}$ 개의 요소에 대해 순위(Rank) 함수를 계산하는 작업은 최첨단 프로토콜을 사용하더라도 18분 이상 소요될 수 있습니다. 주요 병목 현상은 값비싼 보안 등가 테스트(equality tests), 보안 비교(comparisons)에 대한 의존성, 그리고 작은 열거 가능한 특징 도메인을 가진 대규모 데이터셋의 통계 작업을 수행할 때 잘 확장되지 않는 순차적 회로 깊이(sequential circuit depths)입니다.

방법론

저자들은 2PC 통계 분석에 특화된 보안 툴킷인 SAFESTATS를 제안합니다. 개발 과정에서는 Microsoft Excel의 통계 라이브러리를 분석하여 대부분의 통계 연산이 세 가지 핵심 빌딩 블록인 빈도 계산(frequency counting), 정렬(sorting), **비선형 수학 함수(non-linear mathematical functions)**에 의존한다는 점을 확인했습니다. SAFESTATS는 가능한 경우 범용 프리미티브를 피하면서, 각 블록에 특화된 효율적인 2PC 프로토콜을 도입합니다.

1. 보안 빈도 계산 (Shift 기반 전략)

전통적인 방식은 각 입력 요소에 대해 $m$ 번의 등가 테스트를 수행하며, 이는 $O(m\ell)$ 번의 Oblivious Transfer (OT) 호출을 발생시킵니다.

혁신: SAFESTATS는 입력 $x$ 가 임의의 값 $v \in [0, m-1]$ 와 일치하는지 확인하는 결과가 단위 벡터 $\vec{e}_x$ 를 형성한다는 점에 주목합니다. $\vec{e}_x$ 를 $m$ 번의 등가 테스트를 통해 구축하는 대신, 이 프로토콜은 $\vec{e}_x$ 를 베이스 단위 벡터 $\vec{e}_0$ 를 오프셋 $x$ 만큼 오른쪽으로 시프트(right-shifted)한 버전으로 취급합니다.
메커니즘: 프로토콜은 **Random Vector Oblivious Shift Evaluation ( $F_{RVOSE}$ )**을 사용하는 보안 시프트 기반 전략을 활용합니다. 이는 $m$ 번의 등가 테스트를 단일 벡터 시프트 연산으로 대체합니다.
최적화: 최빈값의 빈도가 $n/2$ 를 초과하는 경우, 저자들은 중국인의 나머지 정리(Chinese Remainder Theorem, CRT) 기반 최적화를 도입합니다. 이는 큰 특징 도메인을 더 작은 서로소(co-prime) 부분 도메인으로 분해하여, 더 짧은 빈도 벡터를 구축하고 최빈값을 로컬로 재구성할 수 있게 합니다.

2. 보안 정렬 (Segment Indicator를 이용한 Counting 기반 방식)

범용 보안 정렬(예: 보안 비교 기반)은 높은 회로 깊이와 통신 라운드 문제를 겪으며, 이는 주로 보안 비교 비용에 의해 지배됩니다.

혁신: SAFESTATS는 보안 비교를 제거하는 **보안 카운팅 기반 정렬(secure counting-based sort)**을 제안합니다.
메커니즘: 이 프로토콜은 빈도 벡터 구축(위의 방법 사용)과 요소 삽입으로 구성됩니다. 삽입을 위해, 저자들은 보안 세그먼트 인디케이터(secure segment-indicator) 프로토콜을 도입합니다. 이 프로토콜은 특정 구간 $[a, b]$ 에 대해서는 1이고 그 외에는 0인 비밀 공유 벡터를 생성합니다.
효율성: 세그먼트 인디케이터를 사용함으로써, 동일한 값을 가진 모든 요소는 단일 요소별 곱셈을 통해 출력 벡터에 삽입될 수 있으며, 이를 통해 삽입 단계에서 상수( $O(1)$ ) 회로 깊이를 달성합니다. 이는 OT 복잡도를 $O(n \log n \log(nm))$ 에서 $O(n(m + \log m))$ 으로 줄여줍니다.
특수 사례 (백분위수): 백분위수는 전체 정렬을 필요로 하지 않는다는 점을 인식하여, 저자들은 문제를 구간 테스트(interval-testing) 문제로 재정의합니다. 타겟 순위 $k$ 를 포함하는 누적 빈도 벡터의 구간을 확인함으로써 전체 정렬을 피하고 성능을 더욱 최적화합니다.

3. 보안 비선형 수학 함수 (Bisection 기반 범위 축소)

비선형 함수(예: 로그, 제곱근)의 보안 평가는 일반적으로 "축소 후 근사(reduce-then-approximate)" 패러다임을 따르며, 여기서 가장 큰 비용은 범위 축소(가장 중요한 비제로 비트, MSNZ 식별)입니다.

혁신: 기존 프로토콜은 디지털의 선형적이고 순차적인 스캔을 통해 MSNZ 비트를 식별하며, 이는 $O(d)$ 의 통신 라운드를 요구합니다.
메커제니즘: SAFESTATS는 이분법 기반 범위 축소(bisection-based range reduction) 프로토콜을 도입합니다. 순차적으로 스캔하는 대신, 프로토콜은 입력을 재귀적으로 분할하고 각 단계에서 비제로(non-zero)인 절반을 선택합니다.
효율성: 이는 MSNZ 식별을 위한 통신 라운드를 $O(d)$ 에서 $O(\log d)$ 로 줄여, 비선형 함수 평가의 레이턴시를 크게 낮춥니다.

주요 기여

보안 카운팅 함수: 등가 테스트 기반 방식의 OT 호출을 $O(m\ell)$ 에서 $O(\log m)$ 으로 줄이는 시프트 기반 빈도 계산 프로토콜 및 최빈값 계산을 위한 CRT 기반 변형.
보안 정렬 함수: 상수 통신 라운드를 달성하고 보안 비교를 피하기 위해 보안 세그먼트 인디케이터 메커니즘을 사용하는 카운팅 기반 정렬 프로토콜 및 백분위수를 위한 구간 테스트 접근법.
보안 비선형 함수: 통신 라운드를 $O(n)$ 에서 $O(\log n)$ 으로 줄이는 이분법 기반 MSNZ 식별 프로토콜 및 구간 압축을 위한 다항식 근사 범위 분석.
구현 및 평가: 14가지 일반적인 통계 케이스(Mode, Median, Rank, Chi-Square test 등 포함)를 벤치마킹하고 범용 2PC 라이브러리(예: EzPC)와 비교한 SAFESTATS의 전체 구현.

결과

저자들은 SAFESTATS를 구현하여 14가지 통계 분석 케이스에 대해 테스트를 수행했습니다. 결과는 범용 2PC 프리미티브를 직접 사용하는 베이스라인 모델에 비해 일관된 개선을 보여줍니다:

카이제곱 검정(Chi-Square Test): 1.5 $\times$ 의 런타임 가속 및 4.2 $\times$ 의 통신 감소를 달ット했습니다.
빈도 계산(Frequency Counting): 등가 기반 방식 대비 4.0–7.9 $\times$ 의 런타임 개선 및 3.1–8.6 $\times$ 의 통신 개선을 달성했습니다.
보안 정렬(Secure Sort): 이전의 비교 기반 정렬 방식( $m \le \log_2 n$ 인 시나리오 기준) 대비 3.4–20.5 $\times$ 의 런타임 가속 및 1.3–7.6 $\times$ 의 통신 감소를 달성했습니다.
비선형 함수(Non-Linear Functions): 현재 연구 모델 대비 1.2–1.7 $\times$ 의 런타임 감소 및 1.15–1.16 $\times$ 의 통신 감소를 달성했습니다.

의의

본 논문은 SAFESTATS가 실질적이고 효율적인 프라이버시 보존 통계 분석 툴킷을 제공하며, 기존 2PC 솔루션이 너무 느려 실제 통계 애플리케이션에 적용하기 어려웠던 간극을 해결한다고 주장합니다. 통계 연산을 세 가지 핵심 함수로 분해하고 각 함수에 특화된 프로토콜을 설계함으로써, SAFESTATS는 보안 통계 분석과 관련된 계산 및 통신 오버헤드를 크게 줄입니다. 본 연구는 Semi-honest 공격자에 대해 유니버설 컴포저빌리티(Universal Composability, UC) 프레임워크 내에서 보안성을 공식적으로 증명하였습니다. 저자들은 이들의 접근 방식이 소규모 특징 도메인을 가진 대규모 데이터셋(예: 소득 수준과 교육 수준 간의 관계 분석)을 다루는 애플리케이션에서 보안 통계 분석을 가능하게 만든다는 점을 강조합니다.