2021.08.02

"신뢰할 수 없는 환경에서 신뢰를 확보한다" SMPC란 무엇인가

‘SMPC(Secure Multiparty Computation)’는 사람들이 네트워크를 통해 협력해 합의점을 찾거나 값을 계산하고 그 답이 옳다고 신뢰할 수 있는 일련의 알고리즘을 의미한다. 
 
ⓒ Getty Images Bank 

이 아이디어는 암호 기법 전문가들이 네트워크를 통해 게임을 플레이하는 방법을 찾으면서 등장했다. 처음에는 컴퓨터가 스스로 작동했다. 네트워크가 등장했을 때 프로그래머들이 컴퓨터와 함께 솔루션을 개발하는 방법을 찾아냈다. 지금은 가상 머신이 적절한 응답을 찾을 때까지 협력하는 것이 일반적이다. 문제는 아무도 속이지 않으면서 이를 안전하게 수행하는 방법을 찾는 것이다.

이론 수학자들은 MPC(Multi-Party Computation)를 수십 년 동안 연구했다. 이제 알고리즘이 개발되어 개발 중인 더욱 복잡한 웹 애플리케이션, API, 서비스 분야에서 역할을 찾고 있다.


새로운 역할, 신뢰가 부족한 곳에 있다

대부분의 기업용 스택(Stack)은 서로 협력해 같은 방향으로 이동하는 코드로 채워져 있다. 한 기기에 저장된 데이터와 템플릿이 제3의 기기에 의해 다른 기기에 저장된 데이터를 결합해 하나의 웹 서비스 쿼리(Query)에 답할 수 있다. 이 모든 것을 로드 밸런서(Load Balancer) 뒤에서 작동하는 쿠버네티스(Kubernetes) 클러스터 슈퍼바이저에 의해 조율된다. 한데 묶여 있는 데스크톱 기기들도 CPU 칩이 그래픽 카드 및 네트워크 카드와 협력해 같은 사용자에게 서비스를 제공한다고 신뢰한다.

이 모든 예가 작은 샹그리라(Shangri-La) 또는 신뢰의 방울(Bubble of trust) 안에서 이뤄진다. 다른 기기와 소프트웨어 스택 계층을 서로 신뢰하지 않는 사람들이 운영한다면 어떻게 될까? 그들은 정치적 노선이 서로 다를 수 있다. 서로 보호해야 할 대상과 의무가 다를 수 있다. 아니면 서로 좋아하지 않을 수 있다. 

SMPC 알고리즘을 통해 사람들과 그들의 컴퓨터는 서로를 신뢰하지 않는 상태에서도 서로 협력할 수 있다. 그들은 충분한 기본적인 감사 및 암호 기법을 동원해 서로 최종 답변이 올바른지 확인할 수 있으며, 네트워크 반대편에 있는 적이 배신하고 모든 것을 훔치려고 할 때에도 확인할 수 있다. 


SMPC의 작동방식

대부분의 암호화 알고리즘은 한 사람이 실행하며 모든 수학적 계산은 그 사람 또는 한 개체의 신뢰의 방울 안에서 이뤄진다. 파일을 개인적인 비밀번호로 보호되는 기기에서 안전하게 암호화한 후 이메일로 전송하거나 무법지대인 인터넷에 보관할 수 있다. 디지털 서명은 공개가 방지된 키를 사용해 개인용 기기에 의해 생성되어 다른 사람들이 키의 소유주만이 서명을 생성했다고 믿게 된다.

SMPC는 이런 많은 기본적인 알고리즘을 사용해 정치적으로 더욱 복잡한 문제에 대한 해결책을 찾을 수 있다. 같은 표준 암호화 또는 디지털 서명을 사용할 때도 많지만 이를 합의한 방식대로 적용해 신뢰의 방울을 확장한다. 

많은 암호화폐가 사용하는 블록체인(Blockchains)은 기본적인 디지털 서명을 합의된 방식으로 적용해 서로 모르는 사람 사이에서 더 큰 신뢰의 방울을 생성할 수 있는 방법에 대한 좋은 기본적인 예이다. 

이런 많은 알고리즘에서 특정 암호화폐의 소유권은 비밀 키를 아는 것과 연동되어 있으며, 암호화폐는 소유권을 다른 사람의 비밀 키로 이전하는 디지털 서명을 추가해 사용한다. 이런 트랜잭션을 큰 블록 안에서 다른 사람의 디지털 서명에 의한 다른 트랜잭션으로 인증하는 경우가 많다. 이를 통해 이 디지털 서명 웹은 돈의 소유권을 추적하고 언젠가 안정적인 경제의 기초를 형성할 수 있다.

SMPC는 또한 이론 컴퓨터 공학 세계에서 더욱 정확한 정의를 갖고 있다. 초기 알고리즘 가운데 일부는 임의의 계산을 분할해도 여전히 신뢰할 수 있는 답을 제공한다는 사실이 입증됐다. 초기 증명에서 불린(Boolean) 게이트의 시퀀스로 표현된 임의의 연산에 적용할 수 있었다. 수 년 동안, 수학자들은 문제를 해결할 수 있는 더욱 정교하고 집중적인 알고리즘을 개발했다.


SMPC의 유형

SMPC에서는 많은 알고리즘을 고려한다. 초기 알고리즘은 수학자들이 포커 같은 게임을 카드 처리 중 속이는지 볼 수 없는 먼 곳에 떨어져 있는 양쪽이 함께 플레이할 수 있는 방법을 찾으면서 1970년대에 처음 공개됐다. 그들은 곧 임의의 불 함수(Boolean functions)를 해결하는 알고리즘을 찾기 시작했다.

다음의 보편적인 알고리즘 유형을 스스로 작은 문제에 사용하거나 결합해 더욱 정교한 문제를 해결할 수 있다.

- 비밀 공유: 비밀 값은 N개의 부분으로 분할되며, K의 부분 집합으로 비밀을 재구성하기에 충분하다. 가장 단순한 예는 비밀을 라인의 Y 인터셉터로 인코딩하는 것이다. 라인의 N개 지점을 무작위로 선택한다. 2개만으로도 라인을 재구성하고 (이 예에서) Y 인터셉터인 K=2를 복구할 수 있다. 더욱 정교한 수학은 더 큰 K 값에 적용할 수 있다. 숨겨져 있는 비밀은 큰 파일에 대한 사설 키인 경우가 많다. 부분들이 분산되고 오리지널 키가 파괴되면 K명의 사람들이 협력해야 잠금을 해제할 수 있다.

- 잘라내기와 선택: 이 기본적인 단계는 여러 알고리즘의 기초이다. 왜냐하면 이를 통해 한 쪽이 비밀 정보를 공개하지 않고 다른 쪽을 감사할 수 있기 때문이다. 한 쪽이 데이터를 어떤 식으로 변환된 여러 개의 데이터 패킷으로 변환한다. 이것들이 제공되면 반대쪽은 패킷 중 일부를 선택하고 패킷을 다시 변환하는 키를 요청해 무작위로 감사한다. 모든 것이 일관되고 데이터가 올바르면 다시 변환된 패킷을 버리고 감사되지 않은 패킷이 올바른 것으로 가정한다. 양쪽이 감사되지 않은 부분을 비밀로 유지하면서 정보 공유를 약속할 수 있다. 

- 영지식(Zero-knowledge) 증명: 증명의 생성자가 스스로 가치를 드러내지 않고 지식을 입증할 수 있는 더욱 정교한 디지털 서명 버전이다. 한쪽이 비밀을 공개하지 않고 선택할 수 있기 때문에 더욱 복잡한 알고리즘에서 유용한 경우가 많다. 

단순한 버전을 ‘비트위임(Bit Commitment)’이라 부르며 여러 게임에서 프로토콜로 사용된다. 양쪽이 서로 무작위로 앞 또는 뒤를 선택해 안전하지 못한 라인 위에서 코인을 뒤집을 수 있다. 각각은 비밀을 위해 SHA(Secure Hash Algorithm) 등의 단방향 함수를 사용해 추가적인 무작위성으로 선택을 변환한다. 

우선, 양쪽은 서로 변환된 버전을 공유한다. 양쪽이 변환된 값을 알고 난 후, 양쪽은 앞 또는 뒤의 미가공 무작위 값을 공개한다. 값이 일치하면 한 쪽이 이기고 그렇지 않으면 다른 쪽이 이긴다. 양쪽은 단방향 함수를 다시 연산해 서로를 감사할 수 있다.

- 비상호적(Non-interactive) 영지식 증명: 초기의 영지식 증명은 양쪽이 상호작용하고 한 쪽이 다른 쪽에게 진술을 증명해야 했다. 나중에 비 양방향 버전이 등장했고 SNARK 또는 ZK-SNARK 같은 이름을 붙였다. 목표는 모든 증명의 정보가 포함된 작은 비트 묶음을 생성하는 것이었다. 누구든 이후에 묶음을 검토하고 유사한 계산을 수행해 같은 결론에 도달할 수 있었다.

이런 묶음은 일부 정보를 비밀로 유지하면서 복잡한 사실을 증명해 더욱 강력한 디지털 서명처럼 작용했다. 어떤 사람이 21세 이상이고 실제 나이나 생일을 밝히지 않고도 술을 구매할 수 있음을 증명하는 운전면허증이 그 예가 될 수 있다.


SMPC 사용례

이 알고리즘을 통해 사람들은 서로를 신뢰하면서 모든 활동을 검증할 수 있기 때문에 여러 분야의 비즈니스 거래에 유용하다. 사용례는 다음과 같다.
  
  • 암호화폐: 사회에서 경제를 디지털 화폐에 위탁해야 하는지에 대한 논쟁은 여전히 남아 있지만 시장 자본화가 SMPC의 힘을 증명한다는 사실은 의심의 여지가 없다. 대부분의 트랜잭션은 양쪽이 예상한 대로 지속적으로 원활하게 진행된다. 많은 중대한 문제는 알고리즘의 실패가 아니라 주변 컴퓨터 시스템의 유출로 인해 발생했다.
  •  
  • 게임 플레이: 사람들이 엔터테인먼트를 위해 온라인으로 전환하면서 속이기가 쉬워졌다. 서로에게 로컬 하드웨어에 대한 통제권을 제공하는 것은 사기꾼들이 게임 소프트웨어에 침투해 지도 등의 숨겨진 데이터를 찾을 수 있도록 초대하는 것과 같다. 일부는 데이터 구조를 변경해 추가적인 힘이나 돈을 얻을 수도 있다. SMPC 알고리즘은 특수 하드웨어 없이도 이런 속임수를 방지하는 데 도움이 될 수 있다.
  •  
  • 계약 협상: 많은 기업이 일부 중요한 협력업체들과 긴밀하게 협력하지만 서로를 전적으로 신뢰할 수 없는 경우가 많다. 예를 들어, 자동차 판매업자는 대출을 위해 은행과 협력하고 보험업체와 협력해 자산을 보증한다. 전통적으로, 각자가 스스로를 보호하기 위해 구매에 많은 서류 작업이 수반된다. SMPC는 더 많은 사람들이 정교한 서류작업 없이 계약을 체결할 수 있다.
  •  
  • 데이터 수집: 사람들은 개인정보를 공개하고 싶지 않기 때문에 연구에 참여하기를 꺼리는 경우가 많다. 많은 시장이 수요와 공급에 대해 정확하게 취합된 데이터에 의존한다. 하지만 이 정보를 수집하는 것이 까다로울 수 있다. 왜냐하면 참가자들이 미가공 수치를 공유하고 싶어하지 않기 때문이다. 안정한 알고리즘은 프라이버시를 보호하는 방식으로 이 정보를 수집하는 데 도움이 될 수 있다.
  •  
  • 자동화된 시장: 전통적인 시장은 결정권자로서 중립적인 역할을 하는 사람에게 의존하는 경우가 많다. 비트코인 블록체인은 알고리즘이 거래의 중개자를 대체할 수 있는 하나의 예에 불과하다. editor@itworld.co.kr


2021.08.02

"신뢰할 수 없는 환경에서 신뢰를 확보한다" SMPC란 무엇인가

‘SMPC(Secure Multiparty Computation)’는 사람들이 네트워크를 통해 협력해 합의점을 찾거나 값을 계산하고 그 답이 옳다고 신뢰할 수 있는 일련의 알고리즘을 의미한다. 
 
ⓒ Getty Images Bank 

이 아이디어는 암호 기법 전문가들이 네트워크를 통해 게임을 플레이하는 방법을 찾으면서 등장했다. 처음에는 컴퓨터가 스스로 작동했다. 네트워크가 등장했을 때 프로그래머들이 컴퓨터와 함께 솔루션을 개발하는 방법을 찾아냈다. 지금은 가상 머신이 적절한 응답을 찾을 때까지 협력하는 것이 일반적이다. 문제는 아무도 속이지 않으면서 이를 안전하게 수행하는 방법을 찾는 것이다.

이론 수학자들은 MPC(Multi-Party Computation)를 수십 년 동안 연구했다. 이제 알고리즘이 개발되어 개발 중인 더욱 복잡한 웹 애플리케이션, API, 서비스 분야에서 역할을 찾고 있다.


새로운 역할, 신뢰가 부족한 곳에 있다

대부분의 기업용 스택(Stack)은 서로 협력해 같은 방향으로 이동하는 코드로 채워져 있다. 한 기기에 저장된 데이터와 템플릿이 제3의 기기에 의해 다른 기기에 저장된 데이터를 결합해 하나의 웹 서비스 쿼리(Query)에 답할 수 있다. 이 모든 것을 로드 밸런서(Load Balancer) 뒤에서 작동하는 쿠버네티스(Kubernetes) 클러스터 슈퍼바이저에 의해 조율된다. 한데 묶여 있는 데스크톱 기기들도 CPU 칩이 그래픽 카드 및 네트워크 카드와 협력해 같은 사용자에게 서비스를 제공한다고 신뢰한다.

이 모든 예가 작은 샹그리라(Shangri-La) 또는 신뢰의 방울(Bubble of trust) 안에서 이뤄진다. 다른 기기와 소프트웨어 스택 계층을 서로 신뢰하지 않는 사람들이 운영한다면 어떻게 될까? 그들은 정치적 노선이 서로 다를 수 있다. 서로 보호해야 할 대상과 의무가 다를 수 있다. 아니면 서로 좋아하지 않을 수 있다. 

SMPC 알고리즘을 통해 사람들과 그들의 컴퓨터는 서로를 신뢰하지 않는 상태에서도 서로 협력할 수 있다. 그들은 충분한 기본적인 감사 및 암호 기법을 동원해 서로 최종 답변이 올바른지 확인할 수 있으며, 네트워크 반대편에 있는 적이 배신하고 모든 것을 훔치려고 할 때에도 확인할 수 있다. 


SMPC의 작동방식

대부분의 암호화 알고리즘은 한 사람이 실행하며 모든 수학적 계산은 그 사람 또는 한 개체의 신뢰의 방울 안에서 이뤄진다. 파일을 개인적인 비밀번호로 보호되는 기기에서 안전하게 암호화한 후 이메일로 전송하거나 무법지대인 인터넷에 보관할 수 있다. 디지털 서명은 공개가 방지된 키를 사용해 개인용 기기에 의해 생성되어 다른 사람들이 키의 소유주만이 서명을 생성했다고 믿게 된다.

SMPC는 이런 많은 기본적인 알고리즘을 사용해 정치적으로 더욱 복잡한 문제에 대한 해결책을 찾을 수 있다. 같은 표준 암호화 또는 디지털 서명을 사용할 때도 많지만 이를 합의한 방식대로 적용해 신뢰의 방울을 확장한다. 

많은 암호화폐가 사용하는 블록체인(Blockchains)은 기본적인 디지털 서명을 합의된 방식으로 적용해 서로 모르는 사람 사이에서 더 큰 신뢰의 방울을 생성할 수 있는 방법에 대한 좋은 기본적인 예이다. 

이런 많은 알고리즘에서 특정 암호화폐의 소유권은 비밀 키를 아는 것과 연동되어 있으며, 암호화폐는 소유권을 다른 사람의 비밀 키로 이전하는 디지털 서명을 추가해 사용한다. 이런 트랜잭션을 큰 블록 안에서 다른 사람의 디지털 서명에 의한 다른 트랜잭션으로 인증하는 경우가 많다. 이를 통해 이 디지털 서명 웹은 돈의 소유권을 추적하고 언젠가 안정적인 경제의 기초를 형성할 수 있다.

SMPC는 또한 이론 컴퓨터 공학 세계에서 더욱 정확한 정의를 갖고 있다. 초기 알고리즘 가운데 일부는 임의의 계산을 분할해도 여전히 신뢰할 수 있는 답을 제공한다는 사실이 입증됐다. 초기 증명에서 불린(Boolean) 게이트의 시퀀스로 표현된 임의의 연산에 적용할 수 있었다. 수 년 동안, 수학자들은 문제를 해결할 수 있는 더욱 정교하고 집중적인 알고리즘을 개발했다.


SMPC의 유형

SMPC에서는 많은 알고리즘을 고려한다. 초기 알고리즘은 수학자들이 포커 같은 게임을 카드 처리 중 속이는지 볼 수 없는 먼 곳에 떨어져 있는 양쪽이 함께 플레이할 수 있는 방법을 찾으면서 1970년대에 처음 공개됐다. 그들은 곧 임의의 불 함수(Boolean functions)를 해결하는 알고리즘을 찾기 시작했다.

다음의 보편적인 알고리즘 유형을 스스로 작은 문제에 사용하거나 결합해 더욱 정교한 문제를 해결할 수 있다.

- 비밀 공유: 비밀 값은 N개의 부분으로 분할되며, K의 부분 집합으로 비밀을 재구성하기에 충분하다. 가장 단순한 예는 비밀을 라인의 Y 인터셉터로 인코딩하는 것이다. 라인의 N개 지점을 무작위로 선택한다. 2개만으로도 라인을 재구성하고 (이 예에서) Y 인터셉터인 K=2를 복구할 수 있다. 더욱 정교한 수학은 더 큰 K 값에 적용할 수 있다. 숨겨져 있는 비밀은 큰 파일에 대한 사설 키인 경우가 많다. 부분들이 분산되고 오리지널 키가 파괴되면 K명의 사람들이 협력해야 잠금을 해제할 수 있다.

- 잘라내기와 선택: 이 기본적인 단계는 여러 알고리즘의 기초이다. 왜냐하면 이를 통해 한 쪽이 비밀 정보를 공개하지 않고 다른 쪽을 감사할 수 있기 때문이다. 한 쪽이 데이터를 어떤 식으로 변환된 여러 개의 데이터 패킷으로 변환한다. 이것들이 제공되면 반대쪽은 패킷 중 일부를 선택하고 패킷을 다시 변환하는 키를 요청해 무작위로 감사한다. 모든 것이 일관되고 데이터가 올바르면 다시 변환된 패킷을 버리고 감사되지 않은 패킷이 올바른 것으로 가정한다. 양쪽이 감사되지 않은 부분을 비밀로 유지하면서 정보 공유를 약속할 수 있다. 

- 영지식(Zero-knowledge) 증명: 증명의 생성자가 스스로 가치를 드러내지 않고 지식을 입증할 수 있는 더욱 정교한 디지털 서명 버전이다. 한쪽이 비밀을 공개하지 않고 선택할 수 있기 때문에 더욱 복잡한 알고리즘에서 유용한 경우가 많다. 

단순한 버전을 ‘비트위임(Bit Commitment)’이라 부르며 여러 게임에서 프로토콜로 사용된다. 양쪽이 서로 무작위로 앞 또는 뒤를 선택해 안전하지 못한 라인 위에서 코인을 뒤집을 수 있다. 각각은 비밀을 위해 SHA(Secure Hash Algorithm) 등의 단방향 함수를 사용해 추가적인 무작위성으로 선택을 변환한다. 

우선, 양쪽은 서로 변환된 버전을 공유한다. 양쪽이 변환된 값을 알고 난 후, 양쪽은 앞 또는 뒤의 미가공 무작위 값을 공개한다. 값이 일치하면 한 쪽이 이기고 그렇지 않으면 다른 쪽이 이긴다. 양쪽은 단방향 함수를 다시 연산해 서로를 감사할 수 있다.

- 비상호적(Non-interactive) 영지식 증명: 초기의 영지식 증명은 양쪽이 상호작용하고 한 쪽이 다른 쪽에게 진술을 증명해야 했다. 나중에 비 양방향 버전이 등장했고 SNARK 또는 ZK-SNARK 같은 이름을 붙였다. 목표는 모든 증명의 정보가 포함된 작은 비트 묶음을 생성하는 것이었다. 누구든 이후에 묶음을 검토하고 유사한 계산을 수행해 같은 결론에 도달할 수 있었다.

이런 묶음은 일부 정보를 비밀로 유지하면서 복잡한 사실을 증명해 더욱 강력한 디지털 서명처럼 작용했다. 어떤 사람이 21세 이상이고 실제 나이나 생일을 밝히지 않고도 술을 구매할 수 있음을 증명하는 운전면허증이 그 예가 될 수 있다.


SMPC 사용례

이 알고리즘을 통해 사람들은 서로를 신뢰하면서 모든 활동을 검증할 수 있기 때문에 여러 분야의 비즈니스 거래에 유용하다. 사용례는 다음과 같다.
  
  • 암호화폐: 사회에서 경제를 디지털 화폐에 위탁해야 하는지에 대한 논쟁은 여전히 남아 있지만 시장 자본화가 SMPC의 힘을 증명한다는 사실은 의심의 여지가 없다. 대부분의 트랜잭션은 양쪽이 예상한 대로 지속적으로 원활하게 진행된다. 많은 중대한 문제는 알고리즘의 실패가 아니라 주변 컴퓨터 시스템의 유출로 인해 발생했다.
  •  
  • 게임 플레이: 사람들이 엔터테인먼트를 위해 온라인으로 전환하면서 속이기가 쉬워졌다. 서로에게 로컬 하드웨어에 대한 통제권을 제공하는 것은 사기꾼들이 게임 소프트웨어에 침투해 지도 등의 숨겨진 데이터를 찾을 수 있도록 초대하는 것과 같다. 일부는 데이터 구조를 변경해 추가적인 힘이나 돈을 얻을 수도 있다. SMPC 알고리즘은 특수 하드웨어 없이도 이런 속임수를 방지하는 데 도움이 될 수 있다.
  •  
  • 계약 협상: 많은 기업이 일부 중요한 협력업체들과 긴밀하게 협력하지만 서로를 전적으로 신뢰할 수 없는 경우가 많다. 예를 들어, 자동차 판매업자는 대출을 위해 은행과 협력하고 보험업체와 협력해 자산을 보증한다. 전통적으로, 각자가 스스로를 보호하기 위해 구매에 많은 서류 작업이 수반된다. SMPC는 더 많은 사람들이 정교한 서류작업 없이 계약을 체결할 수 있다.
  •  
  • 데이터 수집: 사람들은 개인정보를 공개하고 싶지 않기 때문에 연구에 참여하기를 꺼리는 경우가 많다. 많은 시장이 수요와 공급에 대해 정확하게 취합된 데이터에 의존한다. 하지만 이 정보를 수집하는 것이 까다로울 수 있다. 왜냐하면 참가자들이 미가공 수치를 공유하고 싶어하지 않기 때문이다. 안정한 알고리즘은 프라이버시를 보호하는 방식으로 이 정보를 수집하는 데 도움이 될 수 있다.
  •  
  • 자동화된 시장: 전통적인 시장은 결정권자로서 중립적인 역할을 하는 사람에게 의존하는 경우가 많다. 비트코인 블록체인은 알고리즘이 거래의 중개자를 대체할 수 있는 하나의 예에 불과하다. editor@itworld.co.kr


X