MPC (Multi Party Computation): 다자간 계산

 

https://www.youtube.com/watch?v=vRVudJADQLk&t=143s 

위 영상을 보고 정리한 것

 

 

 

 

---

 

말하는 사람 : Ivan Damgård

Partisia의 수석 암호학자이자 덴마크 ahus 대학의 컴퓨터공학 교수.

 

다자간 계산

 

예를들어, 같은 사업 분야에 많은 사람들이 있고, 그들이 우리 급여의 평균의 얼마인지 알아내는 데 관심이 있다고 가정해보겠습니다.

하지만 이것은 본인이 사업 분야에서 사람들이 버는 평균보다 훨씬 적을 수도 있고??, 분명히 개인 정보 보호 문제도 있습니다.

즉, 모든 사람이 자신이 얼마나 버는지 다른 사람에게 공개하고 싶어한다는 것은 분명하지 않지만, 다행히도 그럴 필요는 없습니다.

다자간 계산이 그 문제를 해결해 줄 것입니다.

 

4명의 사람이 있다. P1~P4 까지, 그리고 각 사람마다 급여가 있다고 가정해 보겠습니다.

 

사람	급여
P1	a
P2	b
P3	c
P4	d

P1

: 4개의 난수를 선택하는 것. 그 4개의 난수는 a1, a2, a3, a4 라고 부르겠습니다.

: P1의 급여와 함께 합산되어야 하는 조건.

: a4 -> P4

: a3 -> P3

: a2 -> P2 에게 줍니다.

나머지 p2~ 도 모두 동일하게 남은 것을 다른 애들한테 나눠줍니다.

 

P2

: b1, b2, b3, b4  

 

P3

: c1, c2, c3, c4 

 

P4

: d1, d2, d3, d4 

 

사람	급여\	P1	P2	P3	P4	합계
P1	a	a1	a2	a3	a4	S1
P2	b	b1	b2	b3	b4	S2
P3	c	c1	c2	c3	c4	S3
P4	d	d1	d2	d3	d4	S4

 

마지막 합계인 S1, S2, S3, S4는 모두에게 공개할 것인데,

네 사람의 모든 급여의 합 = a + b + c + d = S1 + S2 + S3 + S4 라고 한다.

이유는???

a1 ~ d4 까지의 4x4의 16개의 숫자들 때문이다.

우리가 하고 있는 것은 실제로 모든 숫자를 합산하는 것.

 

a + a1 +b1 + c1 + d1 = a + S1

b + b2 + a2 + c2 + d2 = b + S2

c + a3 + b3 + c3 + d3 = c + S3

d + a4 + b4 + c4 + d4 = d + S4

 

이 과정에서 누구의 급여도 알지 못하지만, 급여의 합계는 알 수 있게 되었다.

이것이 다자간 커뮤니케이션이 작동하는 방식을 매우 잘 보여준다.