SMPC-04. 샤미르 비밀 공유(Shamir's Secret Sharing)를 이용한 평균 연봉 계산 방법

보안 다자간 계산(SMPC)은 여러 참여자가 각자 가진 비밀 정보를 노출하지 않으면서, 그 정보들을 종합하여 특정 함수(예: 합산, 평균)의 결과만을 얻고자 할 때 사용하는 암호 기술입니다.

핵심 원리: 다항식의 덧셈 속성 활용

각자의 비밀(연봉)을 $y$절편으로 하는 다항식을 만듭니다. 이 다항식들을 모두 더하면, 새로운 합계 다항식이 만들어지는데, 이 다항식의 $y$절편은 모든 비밀(연봉)의 합과 같습니다.

계산 과정

3명의 직원(철수, 영희, 민수)이 평균 연봉을 계산하는 상황을 예시로 들어보겠습니다.

• 참여자($N$): 3명
• 비밀 복원에 필요한 최소 인원($t$): 3명 (모두의 정보가 합산되어야 하므로)
• 비밀 정보:
  • 철수 연봉: 5,000만 원
  • 영희 연봉: 6,000만 원
  • 민수 연봉: 7,000만 원

1단계: 비밀 다항식 생성 및 '비밀 조각' 분배

모든 참여자는 자신의 연봉을 $y$절편(상수항)으로 하고, 나머지 계수는 무작위로 선택한 $t-1$차 다항식을 각자 비밀리에 만듭니다. ($t=3$이므로 2차 다항식)

• 철수: $P_\text{철수}(x) = 5000 + 12x + 7x^2$
• 영희: $P_\text{영희}(x) = 6000 + 3x + 20x^2$
• 민수: $P_\text{민수}(x) = 7000 + 10x + 5x^2$

이제 각자 자신의 다항식에 $x=1,\ x=2,\ x=3$을 대입하여 3개의 비밀 조각(share)을 계산하고, 다른 사람들에게 나눠줍니다.

• 철수가 계산 및 분배:
  • $P_\text{철수}(1) = 5019$ -> (본인 보관)
  • $P_\text{철수}(2) = 5052$ -> 영희에게 전달
  • $P_\text{철수}(3) = 5117$ -> 민수에게 전달
• 영희가 계산 및 분배:
  • $P_\text{영희}(1) = 6023$ -> 철수에게 전달
  • $P_\text{영희}(2) = 6086$ -> (본인 보관)
  • $P_\text{영희}(3) = 6279$ -> 민수에게 전달
• 민수가 계산 및 분배:
  • $P_\text{민수}(1) = 7015$ -> 철수에게 전달
  • $P_\text{민수}(2) = 7040$ -> 영희에게 전달
  • $P_\text{민수}(3) = 7125$ -> (본인 보관)

이 과정이 끝나면, 각 참여자는 자신의 연봉을 포함한 어떤 개인 정보도 유추할 수 없는 숫자 조각들만 갖게 됩니다.

2단계: 각자 받은 조각 더하기

이제 모든 참여자는 자신이 받은 3개의 비밀 조각을 더합니다.

• 철수: $P_\text{철수}(1) + P_\text{영희}(1) + P_\text{민수}(1) = 5019 + 6023 + 7015 = 18057$
• 영희: $P_\text{철수}(2) + P_\text{영희}(2) + P_\text{민수}(2) = 5052 + 6086 + 7040 = 18178$
• 민수: $P_\text{철수}(3) + P_\text{영희}(3) + P_\text{민수}(3) = 5117 + 6279 + 7125 = 18521$

여기서 계산된 값은 전체 연봉 합계 다항식 $P_\text{합계}(x) = P_\text{철수}(x) + P_\text{영희}(x) + P_\text{민수}(x)$의 한 점이 됩니다.

• $P_\text{합계}(1) = 18057$
• $P_\text{합계}(2) = 18178$
• $P_\text{합계}(3) = 18521$

3단계: 전체 연봉 합계 복원하기

참여자들은 2단계에서 계산한 합계 값을 모두에게 공개합니다.

• 공개된 정보: $(1, 18057), (2, 18178), (3, 18521)$

이 3개의 점이 있으면, '두 점을 지나는 직선이 하나뿐'인 것처럼 '세 점을 지나는 2차 곡선(포물선)도 단 하나'라는 수학 원리를 이용해 $P_\text{합계}(x)$ 다항식을 완벽하게 복원할 수 있습니다. (전문적으로는 '라그랑주 보간법' 같은 기법이 사용됩니다.)

$$\begin{flalign}P_\text{합계}(x) &= (5000+6000+7000) + (12+3+10)x + (7+20+5)x^2 \\ &= 18000 + 25x + 32x^2\end{flalign}$$

우리가 원하는 전체 연봉의 합은 이 다항식의 $y$절편, 즉 $P_\text{합계}(0)$ 입니다.

$$\text{총 연봉 합계} = P_\text{합계}(0) = 18,000\text{만 원}$$

이 과정에서 그 누구의 연봉도 직접적으로 드러나지 않았습니다. 오직 전체 합계만 알아냈습니다.

4단계: 평균 연봉 계산

이제 공개된 총 연봉 합계를 참여자 수($N=3$)로 나누면 됩니다.

$$\text{평균 연봉} = 18,000 / 3 = 6,000\text{만 원}$$

왜 안전한가요?

• 개별 정보 비공개: 내가 받은 '비밀 조각'은 그저 의미를 알 수 없는 암호 같은 숫자에 불과합니다. 이 조각 하나만으로는 조각을 전달한 사람의 연봉이 높은지 낮은지조차 추측할 수 없으며, 여러 사람의 다항식이 더해졌기 때문에 어떤 정보도 얻을 수 없습니다.
• 최소 인원($t$)의 중요성: $t$개 미만의 조각으로는 원래의 다항식을 복원할 수 없으므로, 소수의 인원이 담합해도 비밀이 새어 나가지 않습니다. 이 예시에서는 3명 모두가 자신의 합산 결과를 공유해야만 최종 합계를 알 수 있습니다.
• 무작위성: 다항식의 다른 계수들이 무작위 값이기 때문에, 비밀 조각만으로는 어떤 정보도 추측할 수 없습니다.