다자간 계산
IT위키
더 많은 작업
다자간 계산(多者間計算, Secure Multi-Party Computation, MPC, SMPC)은 여러 참여자가 각자 가진 입력을 서로에게 드러내지 않은 채 그 입력들에 대한 함수의 결과만 함께 계산해 얻는 암호 기술이다.
1982년 앤드루 야오(Andrew Yao)가 백만장자 문제로 처음 정식화했다. 두 백만장자가 자기 재산액을 상대에게 알리지 않고 누가 더 부자인지만 알아내는 문제다. 이후 1987년 골드라이히·미칼리·위그더슨(GMW)이 어떤 함수든 여러 참여자가 안전하게 계산할 수 있음을 보였다.
다자간 계산이 지키려는 성질은 둘이다.
- 입력 기밀성(privacy) : 각 참여자는 계산 결과와 자기 입력에서 알 수 있는 것 이상을 알지 못한다
- 정확성(correctness) : 일부 참여자가 속여도 결과가 틀리지 않거나, 틀리면 들킨다
이상적으로는 모든 입력을 믿을 수 있는 제3자에게 맡겨 결과만 돌려받는 것과 같은 효과를 내는데, 그 제3자를 암호 프로토콜로 대신한다는 것이 핵심이다. 데이터를 한곳에 모으지 않고도 공동 분석이 가능해 개인정보 보호 강화기술(PET)의 한 축으로 꼽힌다.
| 기법 | 원리 | 특징 |
|---|---|---|
| 비밀 분산(Secret Sharing) | 값을 무작위 조각(share)으로 쪼개 참여자마다 하나씩 나눠 준다. 정해진 수(임계값 t) 미만의 조각으로는 원래 값에 대해 아무것도 알 수 없고, t 개 이상이 모이면 복원된다(샤미르 비밀 분산은 다항식 보간, 덧셈 분산은 조각의 합) | 덧셈은 각자 자기 조각끼리 더하면 되고, 곱셈은 참여자끼리 한 번 통신(비버 삼중항 등)이 필요하다. 참여자가 많은 계산에 쓴다 |
| 가블드 회로(Garbled Circuit) | 계산할 함수를 논리 회로로 바꾸고, 한쪽이 각 선의 0·1 값을 무작위 키로 바꾼 암호화된 진리표(뒤섞인 회로)를 만든다. 다른 쪽은 자기 입력에 해당하는 키만 받아 회로를 풀어 결과를 얻는다 | 야오의 방식. 통신 라운드가 일정해 지연이 큰 망에서 유리하지만 회로 크기만큼 자료가 오간다 |
| 불확정 전송(Oblivious Transfer, OT) | 보내는 쪽은 메시지 여러 개를 내놓고, 받는 쪽은 그중 하나만 받는다. 보내는 쪽은 무엇을 골랐는지 모르고, 받는 쪽은 나머지를 모른다 | 가블드 회로에서 입력 키를 넘길 때 쓰는 기본 부품 |
| 동형 암호 기반 | 입력을 암호화한 채로 연산하고, 결과를 키 소유자들이 함께 복호화한다(임계 복호화) | 통신은 적지만 계산량이 크다 |
- 준정직(semi-honest, honest-but-curious) 모델 : 참여자가 프로토콜은 지키되 주고받은 값으로 남의 입력을 알아내려 한다고 가정한다. 빠르다
- 악의적(malicious) 모델 : 참여자가 아무렇게나 속일 수 있다고 가정한다. 영지식 증명·정보 이론적 MAC 등으로 부정을 잡아내야 해 비용이 크다
- 공모 한계 : 전체 n 명 중 t 명까지 공모해도 안전한지를 정한다. 정직한 참여자가 과반이면(t < n/2) 더 효율적인 프로토콜을 쓸 수 있고, 과반이 아니어도 안전한 프로토콜(dishonest majority, 예: SPDZ 계열)은 더 무겁다
| 구분 | 내용 |
|---|---|
| 장점 | 원본 데이터를 밖으로 내보내거나 한곳에 모으지 않는다. 믿을 만한 중앙 기관 없이도 공동 계산이 된다. 키를 한 곳에 두지 않아 단일 장애점·내부자 위험을 줄인다 |
| 한계 | 참여자 사이 통신 라운드와 대역폭이 크고, 일반 계산보다 수십~수천 배 느릴 수 있다. 결과 자체가 입력을 드러낼 수 있어(예: 두 명의 평균) 출력 설계나 차분 프라이버시를 함께 써야 한다. 참여자가 연결을 끊으면 계산이 멈출 수 있다 |
| 다른 PET 와 차이 | 동형 암호는 계산을 맡은 서버를 믿지 않을 때, 기밀 컴퓨팅은 하드웨어(TEE)를 믿고 처리할 때, 연합 학습은 모델만 모을 때 쓴다. 다자간 계산은 서로 경쟁하거나 믿지 않는 여러 기관이 공동으로 계산할 때 맞다 |
| 종류 | 내용 | 활용 |
|---|---|---|
| 2자 계산(2PC) | 두 참여자가 가블드 회로·OT 로 계산한다 | 두 기관 간 비교, 비공개 검색 |
| 다자 비밀 분산 계산 | 3명 이상이 비밀 분산 조각 위에서 연산한다(BGW, SPDZ 등) | 기관 간 공동 통계, 급여·의료 자료 집계 |
| 비공개 교집합(Private Set Intersection, PSI) | 두 집합의 공통 원소만 알아내고 나머지는 드러내지 않는다 | 고객 명단 매칭, 연락처 탐색, 감염자 동선 대조 |
| 보안 집계(Secure Aggregation) | 여러 단말의 값을 합계만 알 수 있게 더한다 | 연합 학습의 모델 갱신 합산 |
| 임계 암호(Threshold Cryptography) | 개인키를 조각으로 나눠 t 개 이상이 협력해야 서명·복호화가 되게 한다. 키 전체가 어느 한 곳에도 모이지 않는다 | 키 관리, 전자서명, 가상자산 지갑 |
| 프라이버시 보존 기계 학습 | 학습·추론을 MPC 위에서 한다 | 여러 병원 자료로 공동 모델 학습 |
인증에서 가장 위험한 것은 비밀(개인키·비밀번호·생체 정보)이 한 곳에 온전히 저장되는 것이다. 다자간 계산은 이 비밀을 조각으로 나눠 여러 곳에 두고, 인증할 때도 비밀을 다시 합치지 않은 채 계산한다.
| 서비스 | 방식 | 효과 |
|---|---|---|
| 임계 서명 기반 인증·키 관리 | 서명용 개인키를 사용자 단말·서비스 서버·백업 서버 등에 조각으로 나눠 둔다(예: 2-of-3). 인증·서명할 때 각자 자기 조각으로 부분 서명을 만들고 합쳐 하나의 정상 전자서명을 만든다 | 키가 어디에도 통째로 없어 서버 해킹·단말 분실에 강하다. 검증하는 쪽은 일반 서명과 똑같이 검증한다. 공동인증서·MPC 지갑·클라우드 키 관리에 쓴다 |
| 분산 비밀번호 검증 | 비밀번호 검증 값을 여러 서버에 비밀 분산하고, 로그인할 때 서버들이 MPC(임계 OPRF 등)로 일치 여부만 계산한다 | 한 서버가 털려도 비밀번호 해시 사전 대입 공격이 안 된다 |
| 생체 인증 템플릿 보호 | 등록한 생체 템플릿을 조각으로 나눠 저장하고, 인증할 때 새로 읽은 특징과의 거리(유사도)를 MPC 로 계산해 임계값을 넘는지만 낸다 | 생체 정보는 바꿀 수 없어 유출 피해가 크다. 원본 템플릿이 복원되지 않는다 → 바이오정보 |
| 분산 신원·자격 증명 | 발급 기관의 서명키를 여러 기관이 나눠 갖고 공동으로 자격 증명을 발급한다 | 한 기관이 단독으로 위조·발급하지 못한다 |
| 비공개 대조 인증 | PSI 로 가입자 정보·유출 비밀번호 목록을 서로 드러내지 않고 대조한다 | 유출 계정 확인, 기관 간 본인 확인 |
- 구성 : 사용자 단말(조각 1) + 인증 서버(조각 2) + 복구·백업 서버 또는 HSM(조각 3), 조각 갱신(proactive refresh)으로 시간이 지나도 탈취한 조각이 쓸모없게 만든다
- 성능 : 서명·검증 한 번에 여러 차례 통신이 오가므로 지연을 고려해 2-of-2·2-of-3 처럼 참여자 수를 작게 잡는다
- 복구 : 단말을 잃었을 때 남은 조각으로 키를 재발급(re-sharing)하는 절차를 둔다
- 표준·검증 : 임계 서명 프로토콜은 구현 오류가 곧 키 유출로 이어진다. 검증된 프로토콜과 라이브러리를 쓰고 FIDO 같은 기존 인증 체계와 함께 설계한다
- Andrew C. Yao, 「Protocols for Secure Computations」, 23rd IEEE Symposium on Foundations of Computer Science, 1982.
- Oded Goldreich, Silvio Micali, Avi Wigderson, 「How to Play Any Mental Game」, STOC 1987.