“여러 대학병원이 보유한 암 환자의 유전체(Genome) 데이터를 결합해 신약 통계 분석(GWAS)을 수행하고 싶지만, 개인정보 보호법상 어느 병원도 환자 데이터를 단 1비트조차 외부로 반출할 수 없다.” “경쟁 관계에 있는 시중 은행들이 자사의 고객 명단이나 내부 거래 그래프를 전혀 공개하지 않은 채, 은행 간 자금세탁 경로만 공동으로 추적하고 싶다.”
상식적으로 생각하면 이는 모순된 요구처럼 보인다. 함수 $f(x_1, x_2, \dots, x_n)$을 계산하려면 누군가(신뢰할 수 있는 제3자, TTP)가 모든 입력 데이터 $x_i$를 한곳에 모아 평문으로 복호화한 뒤 연산을 수행해야만 할 것 같기 때문이다. 그러나 1980년대 후반 현대 암호학은 놀라운 수학적 정리에 도달했다. “신뢰할 수 있는 제3자가 전혀 존재하지 않아도, 참여자들이 각자의 비밀 입력 $x_i$를 단 1비트도 노출하지 않고 임의의 계산 가능한 함수 $f(x_1, \dots, x_n)$의 출력 결과만 정확히 얻을 수 있다."
이 기술을 다자간 보안 컴퓨팅(Secure Multi-Party Computation, MPC)이라 부른다. 본 글에서는 직관적인 두 가지 사고실험에서 출발하여, MPC를 지탱하는 양대 수학적 엔진인 샤미르(Shamir)의 임계값 비밀 분산과 라그랑주 보간법·비버의 곱셈 트리플(산술 회로 엔진), 그리고 불감 전송(Oblivious Transfer, OT)과 야오의 가블드 서킷(Garbled Circuits)(불리언 회로 엔진)의 원리를 수식과 파이썬 코드로 완벽히 해부한다.
1. 직관을 뒤집는 두 가지 사고실험: ‘상사 없는 평균 연봉 계산’과 ‘야오의 백만장자 문제’
1.1 사고실험 ①: 누구에게도 내 연봉을 알리지 않고 3명의 ‘평균 연봉’만 계산하는 법
카페에 모인 세 명의 엔지니어 $A, B, C$가 자신들의 평균 연봉 $\bar{x} = \frac{x_A + x_B + x_C}{3}$를 알고 싶지만, 자신의 개별 연봉 $x_A, x_B, x_C$는 다른 두 사람에게 절대 알리고 싶지 않다. 이들은 가법 비밀 분산(Additive Secret Sharing)과 일회용 패드(One-Time Pad) 원리만으로 이를 해결할 수 있다.
- 난수 마스크 생성과 첫 번째 귓속말 ($A \to B$): 세 사람은 연봉 합계보다 훨씬 큰 법(Modulus) $M$(예: $M = 10^9$)을 정한다. 엔지니어 $A$는 유한환 $\mathbb{Z}_M$에서 자신만 아는 균일 난수 $r \xleftarrow{\$} \mathbb{Z}_M$을 뽑아 자신의 연봉에 더한 값 $s_1 = (x_A + r) \bmod M$만 $B$에게 귓속말로 전달한다. $r$이 완전한 균일 난수이므로 $s_1$ 역시 $\mathbb{Z}_M$ 위에서 균일 분포를 따르며, 섀넌의 완전 비밀성(Perfect Secrecy)에 의해 $B$는 $s_1$으로부터 $x_A$에 대한 정보를 단 1비트도 얻을 수 없다($I(X_A; S_1) = 0$).
- 누적 덧셈과 전달 ($B \to C \to A$): $B$는 $s_1$에 자신의 연봉 $x_B$를 더해 $s_2 = (x_A + x_B + r) \bmod M$을 $C$에게 전달하고, $C$는 자신의 연봉 $x_C$를 더해 $s_3 = (x_A + x_B + x_C + r) \bmod M$을 처음의 $A$에게 돌려준다.
- 마스크 제거 및 평균 공개: $A$는 $s_3$에서 자신이 처음에 더했던 난수 $r$을 빼서 정확한 합계 $S = (s_3 - r) \bmod M = x_A + x_B + x_C$를 구한 뒤, 3으로 나눈 평균 연봉을 공개한다!
[!NOTE] 왜 2명이 아니라 최소 3명($n \ge 3$)이어야 할까? 만약 참여자가 앨리스와 밥 2명뿐이라면, 설령 신이 나타나 평균 $\bar{x} = \frac{x_A + x_B}{2}$만 알려주더라도 앨리스는 $x_B = 2\bar{x} - x_A$라는 뺄셈을 통해 밥의 연봉을 즉시 역산할 수 있다. 이는 프로토콜의 결함이 아니라 함수 출력 자체가 상대의 비밀을 결정해 버리는 수학적 성질이다. MPC가 보장하는 것은 “자신의 입력과 최종 출력으로부터 논리적으로 도출되는 정보 외에는 계산 과정에서 단 1비트의 추가 정보도 새어나가지 않는다"는 점이다.
1.2 사고실험 ②: 앤드류 야오(Andrew Yao)의 1982년 ‘백만장자 문제’
덧셈은 선형 연산이므로 난수 마스킹만으로 쉽게 해결되었다. 그렇다면 비선형 연산인 대소 비교(부등호)는 어떨까? 1982년 튜링상 수상자 앤드류 야오(Andrew Chi-Chih Yao)는 역사적인 논문 *“Protocols for Secure Computations”*에서 백만장자 문제(Millionaires’ Problem)를 제기했다. 두 백만장자 앨리스(자산 $x$백만 달러)와 밥(자산 $y$백만 달러)이 제3자의 도움 없이 오직 비교 술어 $f(x, y) = [x > y] \in \{0, 1\}$(누가 더 부자인가)라는 1비트 진릿값만 계산하되, 각자의 실제 자산 액수나 두 사람의 자산 차이($x - y$)조차 전혀 노출하지 않는 문제다.
2. MPC 보안성의 수학적 정식화: 이상 세계와 현실 세계의 시뮬레이션 패러다임
Goldreich, Micali, Wigderson(GMW 1987)은 프로토콜의 안전성을 증명하기 위해 이상/현실 세계 시뮬레이션 패러다임(Ideal/Real Simulation Paradigm)을 확립했다.
flowchart TD
subgraph IdealWorld["이상 세계 (Ideal World): 절대적 보안의 기준"]
direction TB
PA1["참여자 P1 (비밀 입력 x1)"] -->|"안전한 전용 채널"| TTP["절대 매수되지 않는 이상적 기능 F (신/금고)"]
PA2["참여자 P2 (비밀 입력 x2)"] -->|"안전한 전용 채널"| TTP
PAn["참여자 Pn (비밀 입력 xn)"] -->|"안전한 전용 채널"| TTP
TTP -->|"오직 출력 y = f(x1,...,xn) 만 반환"| Out1["전원이 출력 y 만 획득 (중간 과정 유출 정의상 0)"]
Out1 --> Sim["시뮬레이터 S (공격자의 입력과 출력 y 만으로 가짜 통신 로그 생성)"]
end
subgraph RealWorld["현실 세계 (Real World): 실제 암호 프로토콜 Π"]
direction TB
RB1["참여자 P1 (비밀 입력 x1)"] <-->|"암호문 및 난수 셰어 교환"| RB2["참여자 P2 (비밀 입력 x2)"]
RB2 <-->|"암호문 및 난수 셰어 교환"| RBn["참여자 Pn (비밀 입력 xn)"]
RB1 <-->|"암호문 및 난수 셰어 교환"| RBn
RB2 --> View["공격자 A 가 관측한 전체 통신 뷰 View_A(x1,...,xn)"]
end
Sim <-->|"확률 분포상 구별 불가능 (View_A ≈ Sim)"| View
$$\left\{ \mathcal{S}\left(I, \{x_i\}_{i \in I}, \{y_i\}_{i \in I}\right) \right\} \stackrel{c}{\approx} \left\{ \text{View}_I^\Pi(x_1, \dots, x_n) \right\}$$실제 통신 메시지를 수신하는 것은 자기 방에서 혼자 주사위를 굴리는 것과 정보량 측면에서 완전히 동치이므로, 출력 이상의 정보 유출이 0비트임이 수학적으로 증명된다. 공격자 모델은 규칙을 지키며 로그만 분석하는 반정직(Semi-Honest / Passive) 공격자와 거짓 값을 보내 프로토콜을 조작하는 악의적(Malicious / Active) 공격자로 구분된다.
3. 제1의 수학적 엔진: 샤미르의 $(t, n)$ 임계값 비밀 분산, 라그랑주 보간법 및 BGW / SPDZ 프로토콜
3.1 유한체 $\mathbb{F}_p$ 위의 다항식 분산과 라그랑주 복원
$$P(x) = s + a_1 x + a_2 x^2 + \dots + a_{t-1} x^{t-1} \pmod p$$$$s = P(0) = \sum_{i \in T} y_i \prod_{j \in T,\, j \ne i} \frac{-x_j}{x_i - x_j} \pmod p$$반면 $t-1$개의 점만으로는 모든 후보 비밀 $s' \in \mathbb{F}_p$에 대해 그 점들을 지나는 $t-1$차 다항식이 정확히 하나씩 동일 확률 $1/p^{t-1}$로 존재하므로, 조건부 엔트로피 $H(S \mid \text{Shares}_{t-1}) = H(S)$가 성립하여 정보이론적 완전 보안을 달성한다.
3.2 BGW 프로토콜과 비버의 곱셈 트리플(Beaver’s Multiplication Triples)
BGW 프로토콜(1988)에서 두 비밀의 덧셈($[a] + [b] = [a + b]$)은 통신 비용이 완전히 0이다(각자 로컬에서 $P(x_i) + Q(x_i) \bmod p$만 계산하면 된다). 반면 곱셈($[a] \cdot [b] = [a \cdot b]$)은 다항식 차수를 $2(t-1)$로 두 배 증가시키므로 $2t - 1 \le n$(즉 과반수가 정직한 Honest Majority) 조건과 1라운드의 차수 축소(Degree Reduction) 재분산 통신이 필요하다.
$$[x \cdot y] = [w] + d \cdot [v] + e \cdot [u] + d \cdot e \pmod p$$4. 제2의 수학적 엔진: 불감 전송($\text{OT}_1^2$)과 야오의 가블드 서킷(Garbled Circuits)
대소 비교($x > y$)나 비트 연산에는 불리언 논리 회로 엔진이 압도적으로 유리하다.
flowchart TD
subgraph Step1["1. 앨리스 (회로 생성자 Garbler)"]
W["모든 와이어 w_i 에 0용과 1용 랜덤 128비트 키 쌍 (k_i^0, k_i^1) 생성"] --> G["각 게이트 진리표 4행을 입력 키로 이중 암호화: Enc(k_a^α, k_b^β, k_c^g(α,β))"]
G --> P["4개 암호문의 행 순서를 무작위로 셔플 (Garbled Table 생성)"]
end
subgraph Step2["2. 키 전달 및 1-out-of-2 불감 전송 (OT_1^2)"]
P -->|"가블드 테이블과 앨리스 입력 키 k_a^x 전송"| Eval["밥 (회로 평가자 Evaluator)"]
BobIn["밥의 비밀 입력 비트 y ∈ {0,1}"] --> OT["1-out-of-2 불감 전송 (OT_1^2)"]
W -->|"후보 키 쌍 (k_b^0, k_b^1)"| OT
OT -->|"밥은 오직 k_b^y 만 획득 (앨리스는 y 를 모름)"| Eval
end
subgraph Step3["3. 밥 (평가자): 단방향 블라인드 회로 평가"]
Eval --> Dec["보유한 키 쌍 (k_a^x, k_b^y) 으로 4행 중 정확히 1행만 복호화하여 출력 키 k_c^z 획득"]
Dec --> Out["최종 출력 와이어 키로부터 계산 결과 z = f(x,y) 만 확인"]
end
- 마이클 라빈(Michael Rabin)의 1-out-of-2 불감 전송($\text{OT}_1^2$): 송신자 앨리스는 두 메시지 $(m_0, m_1)$를, 수신자 밥은 선택 비트 $b \in \{0, 1\}$를 가진다. 밥은 이산대수 문제에 기반해 자신이 비밀키 $k$를 아는 공개키 $PK_b = g^k$와 비밀키를 모르는 공개키 $PK_{1-b} = C / g^k$를 만들어 보냄으로써, 앨리스가 $b$를 전혀 알 수 없게 하면서도 자신은 오직 선택한 $m_b$만 복호화한다.
- 야오의 가블드 서킷과 3대 현대 최적화: 앨리스는 각 와이어에
0과1을 나타내는 랜덤 AES 키 $(k_i^0, k_i^1)$를 부여하고 진리표 4행을 이중 암호화·셔플하여 밥에게 보낸다. 밥은 $\text{OT}_1^2$로 자신의 입력 키 $k_b^y$를 받아 회로 깊이에 무관하게 상수 라운드($O(1)$) 만에 회로를 평가한다. 여기에 Point-and-Permute(컬러 비트로 복호화 행 즉시 지정), Free-XOR($k_i^1 = k_i^0 \oplus \Delta$로 설정해 모든XOR게이트의 암호문과 연산량을 완전히 0으로 제거), Half-Gates(AND게이트당 암호문을 4개에서 이론적 하한인 2개로 축소) 최적화가 더해져 초기 대비 1,000배 이상의 속도 향상을 이루었다.
5. 파이썬(Python) 완전 구현: 유한체 $\mathbb{F}_p$ 위의 샤미르 비밀 분산과 비버 곱셈 트리플
| |
6. 프라이버시 강화 기술(PETs) 4대 접근법 비교 및 실제 산업 응용
| 비교 항목 | 다자간 보안 컴퓨팅 (MPC) | 완전 동형암호 (FHE) | 영지식 증명 (ZKP) | 신뢰 실행 환경 (TEE) |
|---|---|---|---|---|
| 핵심 해결 문제 | 다수 주체의 개별 비밀 입력 $x_1, \dots, x_n$ 결합 연산 | 단일 서버의 암호문 상태 연산 $\text{Enc}(x) \mapsto \text{Enc}(f(x))$ | 단일 증명자가 이미 아는 비밀 $w$의 정당성 증명 | CPU 하드웨어 격리 영역(Enclave) 내부에서 평문 연산 |
| 연산 및 통신 병목 | CPU 연산은 매우 가벼우나 네트워크 통신 라운드가 병목 | 통신은 1회뿐이나 CPU 연산이 평문 대비 $10^3 \sim 10^5$배 무거움 | 검증은 초고속이나 증명 생성에 대규모 연산 필요 | 네이티브 수준 속도이나 Enclave 메모리 제한 존재 |
| 신뢰 모델과 한계 | 비결탁 가정(임계값 $t$ 미만의 서버가 담합하지 않는 한 안전) | 격자 암호학적 난제(RLWE)에만 의존 | 수학적 건전성(다수의 비밀 입력을 결합하는 기술은 아님) | 하드웨어 제조사(Intel/AMD) 신뢰 및 부채널 공격 취약점 |
오늘날 MPC는 2008년 덴마크 사탕무 생산 쿼터 경매(세계 최초 상용 MPC), 보스턴시(BWWC) 기업 간 성별·인종별 임금 격차 조사, Google Chrome / Apple iCloud의 비밀번호 유출 확인(PSI), 다기관 유전체 연관 분석(Secure GWAS), 그리고 수천억 달러의 디지털 자산을 지키는 MPC 임계값 서명 지갑(Fireblocks / Coinbase)에 이르기까지, 제도적 신뢰를 수학적 확실성으로 대체하고 있다.