Beaver Triples의 이해: Secret Sharing에서의 안전한 곱셈 구현

안전한 다자간 계산(MPC) 영역에서, secret sharing은 참여자들이 자신의 입력을 비공개로 유지하면서 공동으로 함수를 계산할 수 있게 해줍니다. secret sharing에서의 덧셈은 선형적 특성 덕분에 간단하지만, 곱셈은 상당한 기술적 난관을 제시합니다. 단순히 두 개의 secret-shared 다항식을 곱하면 결과 다항식의 차수가 증가하며, 이는 결과적으로 비밀을 복구하는 데 필요한 참여자의 수를 증가시킵니다.

이를 해결하기 위해 암호학자들은 Beaver Triples라는 기술을 사용합니다. 이 방법은 다항식의 차수를 높이지 않고, 기저에 깔린 비밀을 드러내지 않으면서 참여자들이 secret-shared 값들에 대해 곱셈을 수행할 수 있게 합니다. 이 포스트에서는 개인정보를 보호하는 그룹 의사결정 과정의 실질적인 예시를 통해 Beaver Triples의 메커니즘을 탐구합니다.

문제점: 곱셈의 병목 현상

네 명의 친구들이 식당을 결정하려고 한다고 가정해 봅시다. 개인정보를 유지하기 위해, 각 친구는 각 식당에 대해 두 가지 점수를 제공합니다: 경제성 점수($a$)와 선호도 점수($f$). 목표는 "친구 수준 점수"($s = a imes f$)를 계산한 다음, 이를 모두 합산하여 "그룹 수준 점수"($S = ext{sum } s$)를 구하는 것입니다.

secret sharing scheme(예: Shamir's)을 사용하면, 각 입력은 share로 변환됩니다. 예를 들어, Alice의 경제성 점수는 $[a]$가 되고 그녀의 선호도 점수는 $[f]$가 됩니다. 이러한 share들을 더하는 것은 쉽지만, 곱하는 것은 쉽지 않습니다.

만약 share를 다항식 $p(x) = a + px$와 $q(x) = f + qx$로 나타낸다면, 이들을 곱하면 이차 다항식이 됩니다: $pqx^2 + (fp + aq)x + af$. 이는 복구 임계값을 증가시킵니다. 만약 원래의 비밀이 2명이 필요했다면, 곱셈 결과는 이제 3명이 필요하게 됩니다. 대규모 시스템에서는 이러한 "차수 팽창(degree bloat)"이 빠르게 감당할 수 없는 수준이 됩니다.

Beaver Triples의 기하학적 직관

다항식의 차수를 높이지 않고 두 개의 secret 값 $x$와 $y$를 곱하기 위해, 우리는 기하학적 항등식을 사용할 수 있습니다. 변의 길이가 $x$와 $y$인 직사각형을 생각해 봅시다. 직사각형 내부의 임의의 점 $(a, b)$를 선택하면, $x$와 $y$를 다음과 같이 표현할 수 있습니다:

$x = a + d$
$y = b + e$

여기서 $d = x - a$이고 $e = y - b$입니다.

큰 직사각형의 넓이($xy$)는 다음과 같이 네 개의 작은 영역으로 나눌 수 있습니다:

$xy = (a + d)(b + e) = ab + ae + bd + de$

$c = ab$라고 치환하면, Beaver Triples에서 사용되는 핵심 항등식을 얻을 수 있습니다:

$xy = c + ae + bd + de$

프로토콜 구현

개인정보를 보호하는 방식으로 이를 작동시키기 위해, $a, b,$ 그리고 $c$ (여기서 $c = ab$) 값들은 실제 입력 $x$와 $y$가 알려지기 전에 무작위로 생성되어 참여자들 사이에서 secret-shared 되어야 합니다. 이것이 바로 Beaver Triples $[a], [b], [c]$입니다.

단계별 프로세스

Precomputation: 신뢰할 수 있는 딜러(trusted dealer) 또는 안전한 프로토콜이 $c = ab$가 되도록 하는 triples $[a], [b], [c]$를 생성합니다. 각 참여자는 이 값들의 share를 받습니다.
Masking: secret shares $[x]$ and $[y]$를 곱하기 위해, 참여자들은 차이의 share를 계산합니다:
- $[d] = [x] - [a]$
- $[e] = [y] - [b]$
Opening: 참여자들은 $d$와 $e$의 값을 공개(open)합니다. $a$와 $b$는 무작위 mask이므로, $d$와 $e$는 원래의 비밀 $x$와 $y$에 대해 아무것도 드러내지 않습니다.
Final Computation: 이제 $d$와 $e$는 공개된 상수이므로, 참여자들은 secret sharing의 선형적 특성을 사용하여 곱셈 결과의 share $[xy]$를 계산할 수 있습니다: $[xy] = [c] + e[a] + d[b] + de$

이 연산은 덧셈과 공개된 상수와의 곱셈만을 포함하므로, 다항식의 차수가 증가하지 않습니다.

구체적인 예시

Ben의 식당 점수를 예시에 적용해 봅시다. Ben은 경제성 8, 선호도 8을 가지고 있습니다 ($x=8, y=8$). 그룹은 share $[8]$과 $[8]$을 가지고 있습니다.

사전 계산된 Beaver Triple은 $a=5, b=6, c=30$이라고 가정합니다.

Compute differences: $[d] = [8] - [5] = [3]$ and $[e] = [8] - [6] = [2]$.
Open differences: 그룹은 $d=3$과 $e=2$를 공개합니다.
Compute product: $[64] = [[30] + 2[5] + 3[6] + (3 imes 2) = [30] + [10] + [18] + 6 = [64]$.

핵심 보안 제약 조건

이 시스템이 안전하게 유지되려면 두 가지 규칙이 절대적입니다:

Randomness: $a$와 $b$는 반드시 진정으로 무작위여야 합니다. 만약 $a$가 알려진 상수라면, $d = x - a$를 공개하는 것은 즉시 $x$를 드러내는 것과 같습니다.
One-Time Use: 각 triple은 정확히 한 번만 사용되어야 합니다. 만약 동일한 triple $[a, b, c]$가 두 개의 서로 다른 곱셈 $(x, y)$ and $(x', y')$에 사용된다면, 관찰자는 $d' - d = x' - x$를 계산하여 두 비밀 입력 사이의 관계를를 드러낼 수 있습니다.

요약

Beaver Triples는 비선형 곱셈의 복잡한 문제를 일련의 선형 연산과 공개된 값의 공개로 변환합니다. 무거운 연산을 사전 계산 단계로 옮김으로써, MPC 프로토콜은 개별 데이터가 엄기하게 비공개로 유지되는 것을 보면서도—식당 결정과 같은—그룹의 합의를 효율적으로 계산할 수 있습니다.