SMPC-03. 덧셈 기반 비밀 공유를 이용한 평균 연봉 계산 방법

보안 다자간 계산(SMPC)은 여러 참여자가 각자 가진 비밀 정보를 노출하지 않으면서, 그 정보들을 종합하여 특정 함수(예: 합산, 평균)의 결과만을 얻고자 할 때 사용하는 암호 기술입니다. '덧셈 기반 비밀 공유'는 이를 구현하는 간단하면서도 강력한 방법 중 하나입니다.

핵심 원리: 비밀을 조각내어 분배하기

핵심 아이디어는 각자의 비밀 값을 의미 없는 여러 개의 '조각(share)'으로 나눈 뒤, 이 조각들을 서로에게 교환하는 것입니다. 어떤 참여자도 비밀 값의 조각 하나만으로는 원래 정보를 추측할 수 없지만, 모든 조각이 모이면 원래 정보를 복원할 수 있습니다.

 

덧셈 기반 비밀 공유에서는 비밀 값 $S$를 $S = s1 + s2 + s3 + ...$ 와 같이 여러 조각의 합으로 표현합니다.

계산 절차

여기서는 3명의 참여자(A, B, C)가 각자의 연봉을 공개하지 않고 평균 연봉을 계산하는 과정을 단계별로 상세히 설명합니다.

• 참여자 및 비밀값 (연봉)
  • A (Alice): 5,000만 원
  • B (Bob): 6,000만 원
  • C (Carol): 7,000만 원

1단계: 비밀 값 분배

모든 참여자는 자신의 연봉을 3개의 임의의 조각으로 나눕니다. 그리고 그중 하나는 자신이 갖고, 나머지 두 개는 다른 참여자에게 각각 전달합니다.

• A (연봉 5000)의 분배
  • A는 자신의 연봉 5000을 세 조각 a1, a2, a3로 나눕니다. (5000 = a1 + a2 + a3)
  • 예시: a1 = 1234, a2 = 2345와 같이 참여자 수(3명)보다 하나 적은 2개의 조각을 완전히 임의의 숫자로 정합니다.
  • a3는 5000 - 1234 - 2345 = 1421로 계산됩니다.
  • 분배 결과: A는 a1을 갖고, a2를 B에게, a3를 C에게 보냅니다.
• B (연봉 6000)의 분배
  • B는 자신의 연봉 6000을 세 조각 b1, b2, b3로 나눕니다. (6000 = b1 + b2 + b3)
  • 예시: b1 = 3456, b3 = 1111 (임의의 숫자)
  • b2는 6000 - 3456 - 1111 = 1433으로 계산됩니다.
  • 분배 결과: B는 b2를 갖고, b1을 A에게, b3를 C에게 보냅니다.
• C (연봉 7000)의 분배
  • C는 자신의 연봉 7000을 세 조각 c1, c2, c3로 나눕니다. (7000 = c1 + c2 + c3)
  • 예시: c2 = 4567, c3 = 2222 (임의의 숫자)
  • c1은 7000 - 4567 - 2222 = 211로 계산됩니다.
  • 분배 결과: C는 c3를 갖고, c1을 A에게, c2를 B에게 보냅니다.

이 단계의 핵심: 각 참여자는 다른 사람의 연봉 조각 일부만 받게 됩니다. 예를 들어 A는 b1, c1 조각을 받지만, 이것만으로는 B나 C의 실제 연봉을 절대 알 수 없습니다.

2단계: 부분 합 계산

이제 각 참여자는 자신 소유의 조각 1개와 다른 두 명으로부터 받은 조각 2개를 더해, '부분 합'을 계산합니다. 이 부분 합 자체만으로는 여전히 아무 정보도 얻을 수 없습니다.

• A 계산 부분 합: $Sum_A = a1 + b1 + c1 = 1234 + 3456 + 211 = 4901$
• B 계산 부분 합: $Sum_B = a2 + b2 + c2 = 2345 + 1433 + 4567 = 8345$
• C 계산 부분 합: $Sum_C = a3 + b3 + c3 = 1421 + 1111 + 2222 = 4754$

3단계: 최종 합산

참여자들이 각자 계산한 부분 합을 공개하여 모두 더합니다. 이 값이 바로 전체 연봉의 총합이 됩니다.

$$\text{전체 총합} = Sum_A + Sum_B + Sum_C = 4901 + 8345 + 4754 = 18000$$

왜 이것이 총합이 될까요?

 

수식을 풀어보면 명확해집니다.

$$\begin{flalign} &Sum_A + Sum_B + Sum_C \\ &= (a1 + b1 + c1) + (a2 + b2 + c2) + (a3 + b3 + c3) \\ &= (a1 + a2 + a3) + (b1 + b2 + b3) + (c1 + c2 + c3) \\ &= (A\text{의 연봉}) + (B\text{의 연봉}) + (C\text{의 연봉}) \\ &= 5000 + 6000 + 7000 \\ &= 18000\end{flalign}$$

4단계: 평균 계산

이제 총합을 알았으니, 평균을 계산하는 것은 간단합니다.

$$\text{평균 연봉} = \text{전체 총합 / 참여자 수} = 18000 / 3 = 6000$$

결론

이 과정을 통해 참여자 A, B, C는 각자의 연봉(5000, 6000, 7000)을 그 누구에게도 직접 노출하지 않으면서, 평균 연봉이 6000이라는 사실을 안전하게 계산해낼 수 있었습니다.

 

보안 강화: 실제 시스템에서는 숫자가 음수가 되거나, 조각들을 통해 정보를 유추하는 것을 막기 위해 '모듈러 연산(Modular Arithmetic)'을 사용합니다. 매우 큰 소수(prime number)를 정해 모든 덧셈과 뺄셈을 그 소수로 나눈 나머지 값으로 처리함으로써, 조각 값들이 완전히 무작위처럼 보이게 하여 보안성을 크게 높입니다.