이 글은 privacyguides.org에서 CC-BY-SA-4.0 로 배포한 콘텐츠를 번역및 일부 재구성 하였으며 번역된 내용은 게시자의 의견이 아닙니다 이 게시글의 문자는 CC-BY-SA-4.0로 배포됩니다.
출처

우리는 E2EE 를 사용하여 데이터를 안전하게 보관하는법을 알고 있습니다. 그럼 서버에서 데이터를 하면서도 프라이버시를 보장받을 방법이 없을까요?

역사
Adi Shamir, Ronald L. Rivest 와 Leonard M. Adleman는 1979년 "멘탈 포커"라는 서로 멀리 떨어져도 메시지만으로 포커를 할수 있는 방법을 고안했습니다. 공정한 카드 분배를 설명하겠습니다.

Bob은 자신의 키로 10개의 모든 카드를 암호화해 Alice에게 보냅니다. 이때 Alice는 카드의 내용을 모르는 상태에서 자신의 카드분 5개를 자신의 키로 암호화 하여 Bob에게 전부 넘겨줍니다. Bob은 자신의 키로 카드들을 복호화 합니다. 여기서 Bob은 완전하게 복호화 됩니다. 암호화된 5개는 Alice의 카드입니다. 이제 암호화가 안 풀린 카드를 Alice에게 넘겨 Alice가 자신의 카드를 알게 합니다. 여기에는 Alice의 암호화가 적용되어도 Bob이 암호화를 해제할수 있다는 전제를 기반으로 합니다.

안전한 쌍방 계산(Secure Two-Party Computation)

Alice와 Bob은 둘 다 백만장자 부자입니다. 여기서 누가 더 부자인지 서로 가진 금액을 공개하지 않고 공개 하고 싶어합니다.  다행히 우리는 이는 Andrew Yao가 발명한 가블드 회로를 통해 다자간 계산(MPC)로 이용하여 이 백만장자 문제 를 해결할수 있습니다. 가블드 회로는 어떤 문제든 Boolean 회로 즉, AND, OR, XOR 등과 같은 논리 게이트 집합으로 표혀할수 있다면 모든 문제에 MPC를 사용할 수 있습니다.

가블드 회로

2명의 당사자를 생성자와 평가자로 나눕니다. 생성자는 사용할 암호화를 설정하며 평가자는 실제 계산을 수행합니다.

먼저 입력에 대한 진리표를 작성합니다. 진리표의 값을 가리기 위해 각 입력마다 다른 레이블을 할당합니다. 즉 1은 각각의 입력에서 동일한 레이블로 표시되지 않습니다. 또한 행의 순서도 무작위로 섞어서 순서를 통해 값을 유추할 수 없어야야 합니다.

우리는 논리 게이트의 유형을 아는것을 기반하여 출력값을 알수 있습니다 예를 들어 and 게이트는 하나의 다른 출력만을 가짐으로 출력은 1이고 나머지 출력은 0이라는 추론을 할수 있습니다. ㅇ이를 해결하기 위해 입력 레이블을 키로 사용하여 각 행을 암호화합니다. 이렇게 하면 올바른 출력만 복호화할 수 있습니다. 하지만 여전히 문제는 있습니다. 평가자는 자신의 입력을 어떻게 넣을 수 있을까요? 레이블을 둘다 요청하면 하나 이상의 출력을 복호화할 수 있고, 자신의 입력값을 그대로 알려주면 태초의 목적이 사라집니다. 이를 해결하는 방법은 망각 전송(Oblivious Transfer)입니다.

이 방법에서는 평가자가 두 개의 공개키를 생성하고, 그중 하나에 대해서만 개인키를 가집니다. 생성자는 제공받은 공개키로 평가자의 입력에 대한 두 레이블을 각각 암호화한 뒤 평가자에게 다시 보냅니다. 평가자는 두 레이블 중 하나에 대한 개인키만 가지고 있으므로 자신이 원하는 레이블 하나만 복호화할 수 있습니다. 생성자는 평가자가 원하는 값을 선택할수 있도록 순서대로 레이블을 배치합니다. 이는 평가자가 복호화 가능한 키를 여러 개 보내지 않는다는 신의에 의존합니다. 따라서 어느 정도의 신뢰가 필요하기 때문에 이 프로토콜은 준정직(semi-honest)모델로 간주됩니다.

관심이 있다면 Yao의 가블드 회로를 단계별로 설명한 이 자료 를 참고해주세요

다자간 컴퓨팅의 탄생

다자간 컴퓨팅은 Oded Goldreich, Silvio Micali, Avi Wigderson의 연구와 GMW 패러다임을 통해 확립되었습니다.

두 개 이상의 당사자

기블드 회로는 두개의 당사자로 제한되어있었습니다. 하지만 GMW 패러다임은 이를 확장하여 당사자의 제한이 없으며 대다수가 정직하다면 악의적인 행위도 처리할수있습니다.

비밀공유

GMW 패러다임은 비밀 공유를 사용합니다. 비밀 공유는 암호화 키와 같은 개인 정보를 여러 부분으로 나누는 방법입니다. 이렇게 나누어진 조각들은 따로 있을 때는 비밀을 드러내지 않지만, 조각들을 합치면 원래의 비밀을 복원할 수 있습니다. GMW  프로토콜은 간단한 덧셈을 사용합니다. 예를 들어 비밀숫자가 69라면 이를 2명에게 나눈다면

10 + 59 = 69

각각 10 과 59를 가지게 됩니다. 나중에 더하면 비밀숫자인 69가 나옵니다.

영지식 증명

GMW 패러다임은 영지식 증명(ZKP)을 통해 악의적인 공격자에게서 보호하는 기능을 도입했습니다. 영지식 증명은 어떤 당사자가 다른 당사자에게 특정 명제가 참이라는 사실을 증명하면서도, 그 명제가 참이라는 사실 외에는 어떠한것도 공개하지 않고도 그 명제를 참이라 확신할수있는 기술입니다. 영지식 증명의 개념은 1985년 Shafi Goldwasser, Silvio Micali, Charles Rackoff의 논문에서 처음 소개되었습니다. How to Explain Zero-Knowledge Protocols to Your Children(당신의 자녀에게 영지식 증명을 소개하는법) 이라는 제목을 가진 이 논문은 영지식 증명을 동화처럼 설명합니다.

핵심은 확률에 있습니다. 어떤 당사자가 올바른 결과를 얻는 방법을 알고 있다면, 그 당사자는 확실하게 정답을 얻을 수 있어야 합니다.

식당으로 비유하겠습니다. 김창섭과 쌀숭이는 식당에 왔습니다. 식당에는 두 개의 출입문이 있습니다 이 두 출입문은 김창섭 인증 출입문과 연결됩니다. 김창섭은 이 김창섭 인증 출입문을 이용할수있음을 증명하고 싶지만 쌀숭이에게 김창섭 인증과정은 공개하고 싶지 않습니다. 증명자라는 역할을 맡은 김창섭은 식당으로 들어갑니다 이때 쌀숭이는 어디문으로 들어갔는지 알수없습니다. 검증자를 맡은 쌀숭이는 식당 밖에서 "XX쪽으로 나와" 말합니다. 만일 창섭인증을 정상적으로 이용할수있다면 김창섭으로 어느쪽으로도 나올수 있습니다. 이 과정을 여러번 하면 김창섭은 창섭인증 출입문을 쓸수있음을 증명할수 있습니다.

BGW 프로토콜

GMW 프로토콜은 MPC를 크게 발전시킨 중요한 도약이었지만, 여전히 큰 한계가 있었습니다. 가블드 회로 프로토콜은 불리언 논리 게이트(Boolean logic gate)로 제한되어 다양한 연산을 구현하기 어렵웠습니다. 게이트 마다 통신이 필요하여 비효율적이기도 했고요. 연구자인 Michael Ben-Or, Shafi Goldwasser, Avi Wigderson은 논문 Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation 에서 MPC의 효율성과 견고성을 여러 방식으로 향상시켜 실적용에 한 걸음 다가섰습니다.

산술 회로

BGW 프로토콜은 불리언 회로 대신 산술 회로(Arithmetic Circuits)를 사용합니다. 이를 통해 개별 비트의 논리 게이트에 국한되지 않고 곱셈이나 덧셈과 같은 수학적 연산을 더 쉽게 수행할 수 있습니다. 이는 당사자 간의 통신량에 큰 차이를 가져오며, 결과적으로 프로토콜의 효율성을 높여줍니다.

샤미르 비밀 공유

BGW 프로토콜은 덧셈 대신 다항식을 사용하는 샤미르의 비밀 공유 방식 을 활용합니다 . 이를 통해 곱셈의 효율성을 높이고, 복원화를 위해 모든 조각이 필요한 것이 아니라 일정 개수 이상의 조각만 있으면 되는 임계값을 설정할 수있습니다.

적은 통신

BGW 프로토콜은 당사자들 사이에 그렇게 많은 통신을 요구하지 않습니다. 산술 연산에 효율적인 샤미르 비밀 공유를 쓰기때문입니다/. 또한 BGW 프로토콜은 망각 전송이나 영지식 증명을 필요로 하지 않습니다. 대신 Shamir의 비밀 공유와 오류 정정 코드를 사용하여, 더 효율적으로 같은 성질을 제공하기 때문입니다.

fair play

Fairplay 시스템의 도입으로 이 분야는 한층 더 발전했습니다.
이 논문이 발표되기 전까지 MPC는 부울 회로나 산술 회로로만 제한되어 있었는데, 이는 고수준 언어를 사용하는 데 익숙한 프로그래머에게는 그리 친숙하지 않은 환경이었습니다. Fairplay는 고수준 언어를 부울 회로로 컴파일한 후 해당 회로를 안전하게 연산할 수 있는 SFDL 컴파일러를 도입했습니다.
또한 Fairplay는 효율성 면에서도 몇 가지 발전을 이루었습니다. 고정된 8라운드의 상수 라운드를 활용하여 통신 오버헤드를 줄였습니다. 또한 무료 XOR 기법을 사용하여 XOR 게이트에서 암호화 연산을 수행할 필요가 없도록 함으로써 효율성을 높였습니다.

실사용 사례

보스턴 여성 인력 위원회

2016년 보스턴 여성 인력 위원회는 69개 기업과 협력하여 여성이 남성과 동일한 임금을 받는지 조사했습니다. MPC를 사용함으로써 기업들은 직원들의 실제 임금을 공개하지 않고도 데이터를 처리할 수 있었습니다. 수집된 임금 데이터는 112,600명으로, 보스턴 광역권 전체 노동력의 약 11%에 해당합니다. 자세한 조사 결과는 보고서에서 확인할 수 있지만, 연구 결과에 따르면 여성은 남성보다 임금이 적은 것으로 나타났습니다. 평균적으로 여성은 남성이 버는 1달러당 77센트를 받는 셈입니다. 2023년에 보도된 바에 따르면, 이 데이터 덕분에 보스턴 여성 인력 위원회는 임금 격차를 30% 줄일 수 있었습니다.

오늘날의 MPC

오늘날 MPC Alliance 는 MPC의 활용을 발전시키기 위해 여러 기업들이 함께 모인 단체입니다. MPC는 암호화폐 부터 HIPAA를 준수해야하는 위한 의료 분야 까지 다양한 곳에서 사용되고 있습니다. NIST와 같은 기관에서 MPC의 표준화 를 위한 노력을 지속하고 있지만, MPC 프로토콜과 활용 사례의 다양성이 워낙 방대하여 이는 쉽지 않은 과제입니다. 각국이 전자 투표로 전환함에 따라, 안전하고 검증 가능한 공정한 전자 투표를 위해 MPC를 활용하는 연구가 진행되고 있습니다. 기술의 발전를 완전히 외면해서는 안 되지만, 이러한 기술은 극도의 주의와 과학적 엄밀성을 바탕으로 도입되어야 합니다. MPC와 같은 개방적이고 증명 가능한 보안 기술이 없는 상태에서 블랙박스 방식의 전자 투표를 도입하는 것은 무책임한 일이며, 선거의 공정성을 위협한다고 생각합니다.

MPC는 도구 상자 속 필수적인 개인정보 보호 도구 역할을 합니다. 이는 동형 암호화와 같은 다른 개인정보 보호 기술(PETs)과도 연관되어 있는데, 동형 암호화는 데이터를 암호화한 상태에서도 암호 해독된 데이터를 노출하지 않고 연산을 수행할 수 있도록 하는 방식입니다.

MPC는 개인정보 보호 환경을 바꾸고 있는 여러 도구 중 하나입니다. 앞으로 MPC가 어떻게 활용될지, 그리고 어떤 새로운 발전을 가능하게 할지 기대됩니다.