SMPC-02. 보안 다자간 계산(SMPC)의 핵심: 비밀 공유 기법

1. 비밀 공유(Secret Sharing)란 무엇인가?

비밀 공유는 하나의 비밀 정보를 여러 개의 조각으로 나누어 서로 다른 참여자들에게 분배하는 암호 기술입니다. 이 기술의 핵심은, 정해진 수(임계값) 이상의 조각이 모여야만 원래의 비밀 정보를 복원할 수 있고, 그보다 적은 수의 조각으로는 비밀에 대한 어떠한 정보도 얻을 수 없다는 점입니다.

이러한 특성 때문에 비밀 공유는 참여자들이 자신의 입력값을 직접 노출하지 않고도 공동의 함수를 계산할 수 있게 하는 보안 다자간 계산(SMPC)의 근간이 됩니다. 예를 들어, 여러 사람이 각자의 연봉을 공개하지 않으면서 평균 연봉을 계산하고 싶을 때, 각자의 연봉을 비밀 공유 기법으로 분배한 뒤 연산을 수행하면 안전하게 결과를 얻을 수 있습니다.

2. 주요 비밀 공유 기법

가. 샤미르의 비밀 공유 (Shamir's Secret Sharing, SSS)

아디 샤미르(Adi Shamir)가 제안한 이 기법은 다항식의 성질을 이용한 가장 대표적인 비밀 공유 방식입니다. $(t, n)$ 임계 구조를 가지며, 이는 $n$명의 참여자에게 비밀 조각을 나누어주고, 그중 $t$명 이상이 모여야만 비밀을 복원할 수 있음을 의미합니다.

동작 원리

1) 비밀 분배 단계

• 비밀 설정: 복원하려는 비밀을 $S$라고 합니다.
• 다항식 생성: 비밀 $S$를 상수항으로 갖는 $t-1$차 다항식 $f(x)$를 무작위로 생성합니다.
  
  • $f(x) = a_{t-1}x^{t-1} + ... + a_1x + S$
  • 여기서 계수 $a_1, ..., a_{t-1}$는 모두 무작위로 선택된 값입니다.
• 조각 생성: $n$명의 각 참여자에게 $f(1), f(2), ..., f(n)$과 같이 다항식 위의 서로 다른 점의 좌표 $(x, f(x))$를 하나의 조각으로 나누어 줍니다.

2) 비밀 복원 단계

• 조각 수집: 비밀을 복원하기 위해 최소 $t$개의 조각(서로 다른 점의 좌표)을 수집합니다.
• 다항식 복원: $t$개의 점이 주어지면, 이 점들을 모두 지나는 $t-1$차 다항식은 유일하게 하나로 결정됩니다. 참여자들은 라그랑주 보간법(Lagrange Interpolation)과 같은 방법을 사용하여 원래의 다항식 $f(x)$를 복원할 수 있습니다.
• 비밀 확인: 복원된 다항식 $f(x)$의 상수항, 즉 $f(0)$의 값이 바로 우리가 찾던 원래의 비밀 $S$가 됩니다.

핵심 아이디어

$t-1$차 다항식을 완전히 정의하기 위해서는 최소 $t$개의 점이 필요하다는 수학적 원리를 활용합니다. $t-1$개의 조각만으로는 무수히 많은 다항식이 만들어질 수 있어 비밀 $S$를 추측할 수 없습니다.

예시

$(2, 3)$ 임계 구조를 가정해 봅시다.

1. 비밀 $S=123$을 3명에게 공유하고 2명만 모이면 복원 가능하게 하려면, $t=2$이므로 1차 다항식 $f(x) = ax + S$를 만듭니다.
2. 무작위로 $a=7$을 선택하면 $f(x) = 7x + 123$이 됩니다.
3. 참여자 1, 2, 3에게 각각 조각 $(1, f(1))=(1, 130)$, $(2, f(2))=(2, 137)$, $(3, f(3))=(3, 144)$를 분배합니다.
4. 이 중 2개의 점(예: $(1, 130)$과 $(2, 137)$)만 있으면 연립방정식을 통해 $f(x)$를 복원하고, $f(0)=123$을 쉽게 찾을 수 있습니다.

나. 블레이클리의 비밀 공유 (Blakley's Secret Sharing)

샤미르의 기법과 거의 동시에 독립적으로 제안된 방식으로, 기하학적 원리에 기반합니다. 다항식 대신 t차원 공간에서의 초평면(hyperplane)의 교점을 이용합니다.

동작 원리

1) 비밀 분배 단계

• 비밀 설정: 비밀 S를 t차원 공간의 한 점 P의 좌표 중 하나로 설정합니다. 예를 들어, $P = (S, r_2, ..., r_t)$ 와 같이 첫 번째 좌표를 비밀로 하고 나머지는 무작위 값으로 채웁니다.
• 초평면 생성: 이 점 P를 지나는 서로 다른 n개의 초평면을 생성합니다.
• 조각 분배: n명의 각 참여자에게 이 초평면의 방정식($a_1x_1 + ... + a_tx_t = b$)을 하나의 조각으로 나누어 줍니다.

2) 비밀 복원 단계

• 조각 수집: 비밀을 복원하기 위해 최소 t개의 조각(초평면의 방정식)을 수집합니다.
• 교점 계산: t개의 초평면 방정식을 연립하여 풀면 유일한 교점 P를 찾을 수 있습니다.
• 비밀 확인: 계산된 교점 P의 첫 번째 좌표값이 바로 원래의 비밀 S입니다.

핵심 아이디어

t차원 공간에서 하나의 점을 유일하게 결정하기 위해서는 최소 t개의 독립적인 초평면이 필요하다는 기하학적 원리를 이용합니다. t-1개의 초평면의 교점은 점이 아닌 선 또는 평면이 되므로 비밀을 특정할 수 없습니다. 예를 들어, 3차원 공간을 생각해보십시오. 2개의 평면(t-1=2)이 만나면 하나의 '선'을 이룹니다. 이 선 위에는 무수히 많은 점이 존재하므로 비밀을 특정할 수 없습니다. 하지만 3개의 평면(t=3)이 만나면 유일한 하나의 '점'이 결정되는 것과 같은 원리입니다.

다. 덧셈 기반 비밀 공유 (Additive Secret Sharing)

덧셈 기반 비밀 공유는 개념적으로 매우 간단하고 계산 효율성이 높아 SMPC에서 널리 사용되는 기법입니다.

동작 원리

1) 비밀 분배 단계

• 비밀 설정: 비밀을 $S$라고 합니다.
• 조각 생성: $n$명의 참여자가 있을 때, $n-1$개의 조각($s_1, s_2, ..., s_{n-1}$)을 완전히 무작위로 선택합니다.
• 마지막 조각 계산: 마지막 참여자의 조각 $s_n$은 다음 수식을 통해 계산됩니다.
  
  • $s_n = S - (s_1 + s_2 + ... + s_{n-1})$
• 분배: 각 참여자는 $s_1, s_2, ..., s_n$ 조각을 하나씩 나눠 갖습니다.

2) 비밀 복원 단계

• 단순 합산: 비밀을 복원하려면 모든 참여자의 조각을 단순히 더하기만 하면 됩니다.
  
  • $s_1 + s_2 + ... + s_n = S$

특징과 한계

• 장점: 구현이 매우 간단하고 덧셈 및 뺄셈 연산에 대해 매우 효율적입니다.
• 단점: $(n, n)$ 임계 구조를 가집니다. 즉, 모든 참여자가 자신의 조각을 제공해야만 비밀 복원이 가능합니다. 단 한 명의 조각이라도 없으면 비밀을 복원할 수 없으며, 반대로 $n-1$개의 조각이 노출되면 나머지 한 조각과 비밀이 쉽게 계산되어 보안에 취약합니다.

라. 불리언 비밀 공유 (Boolean Secret Sharing)

불리언 값(참/거짓 또는 0/1), 즉 비트(bit) 단위의 비밀을 공유하는 데 특화된 기법입니다. XOR(배타적 논리합) 연산을 기반으로 하며, 동작 방식은 덧셈 기반 비밀 공유와 매우 유사합니다.

동작 원리

1) 비밀 분배 단계

• 비밀 설정: 비밀을 비트 S (0 또는 1)라고 합니다.
• 조각 생성: n-1개의 조각($s_1, ..., s_{n-1}$)을 무작위 비트(0 또는 1)로 생성합니다.
• 마지막 조각 계산: 마지막 조각 $s_n$은 모든 조각과 비밀을 XOR하여 계산합니다.
  
  • $s_n = S ⊕ s_1 ⊕ s_2 ⊕ ... ⊕ s_{n-1}$ (여기서 ⊕는 XOR 연산)
• 분배: 각 참여자는 $s_1, ..., s_n$ 조각을 하나씩 나눠 갖습니다.

2) 비밀 복원 단계

• 단순 XOR: 비밀을 복원하려면 모든 참여자의 조각을 단순히 XOR 연산하면 됩니다.
  
  • $s_1 ⊕ s_2 ⊕ ... ⊕ s_n = S$
  • XOR 연산은 a ⊕ a = 0이고 a ⊕ 0 = a인 성질이 있으므로, 모든 $s_i$가 상쇄되고 S만 남습니다.

특징과 활용

(n, n) 임계 구조를 가지며, SMPC에서 AND, OR 같은 논리 게이트로 구성된 불리언 회로를 계산할 때 매우 효율적이라 핵심적인 역할을 수행합니다.

3. 기법 비교

특징	샤미르의 비밀 공유	블레이클리의 비밀 공유	덧셈 기반 비밀 공유	불리언 비밀 공유
기반 원리	다항식 보간법	기하학 (초평면 교점)	덧셈의 역원	XOR 연산
임계 구조	(t, n) 구조 (유연함)	(t, n) 구조 (유연함)	(n, n) 구조 (엄격함)	(n, n) 구조 (엄격함)
보안성	t-1개 조각까지 정보 노출 없음	t-1개 조각까지 정보 노출 없음	n-1개 조각 노출 시 비밀 유출	n-1개 조각 노출 시 비밀 유출
계산 복잡도	상대적으로 높음	상대적으로 높음	매우 낮고 효율적	매우 낮고 효율적
주요 활용	높은 보안과 유연성 필요 시	높은 보안과 유연성 필요 시	효율적 덧셈 연산 필요 시	불리언 회로 계산 시
활용 분야 예시	암호화폐 키 복구, 분산 키 관리 시스템	보안 시스템 접근 제어, 기밀 정보 저장	프라이버시 보존 통계 (평균 연봉 계산 등)	보안 경매, 전자 투표, Private Set Intersection

4. 결론

비밀 공유는 데이터를 암호화된 상태 그대로 연산할 수 있게 하여 프라이버시를 보존하는 강력한 도구입니다. 샤미르의 비밀 공유와 블레이클리의 비밀 공유는 일부 참여자의 부재나 악의적인 행동을 용인할 수 있는 유연한 보안 모델을 제공하는 반면, 덧셈 기반 비밀 공유와 불리언 비밀 공유는 모든 참여자의 신뢰가 보장되는 환경에서 최고의 연산 효율성을 제공합니다. 따라서 실제 SMPC 시스템은 해결하려는 문제의 특성과 보안 요구사항에 따라 적절한 비밀 공유 기법을 선택하거나 조합하여 사용합니다.