본문으로 이동

다자간 보안 컴퓨팅

위키백과, 우리 모두의 백과사전.

다자간 보안 컴퓨팅(보안 컴퓨팅(secure computation), 다자간 컴퓨팅(multi-party computation, MPC) 또는 개인 정보 보호 컴퓨팅(privacy-preserving computation) 이라고도 함)은 당사자가 입력을 비밀로 유지하면서 입력에 대한 함수를 공동으로 계산할 수 있는 방법을 만드는 것을 목표로 하는 암호학 의 하위 분야이다. 암호화가 통신 또는 저장의 보안과 무결성을 보장하고 적이 참가자 시스템 외부에 있는(발신자와 수신자의 도청자) 전통적인 암호화 작업과 달리, 이 모델의 암호화는 참가자의 개인정보를 서로로부터 보호한다.

안전한 다자간 계산의 기반은 1970년대 후반 신뢰할 수 있는 제3자를 필요로 하지 않고 원거리에서 게임 플레이/계산 작업을 시뮬레이션하는 암호학 문제인 멘탈 포커 문제로 시작되었다. 전통적으로 암호화는 콘텐츠를 숨기는 것이었지만, 이 새로운 유형의 계산 및 프로토콜은 여러 소스의 데이터를 사용하여 계산하고 출력을 올바르게 생성하는 동안 데이터에 대한 부분 정보를 숨기는 것이다. 1980년대 후반까지 Michael Ben-Or, Shafi Goldwasser 및 Avi Wigderson 과 독립적으로 David Chaum, Claude Crépeau 및 Ivan Damgård 는 "보안 채널 설정에서 모든 기능을 안전하게 계산하는 방법"을 보여주는 논문을 발표했다.[1]

역사[편집]

특정 작업을 위한 특수 목적 프로토콜은 1970년대 후반에 시작되었다.[2] 나중에 보안 계산은 1982년(부울 술어(Boolean predicate) 문제인 소위 백만장자 문제 에 대해) 보안 쌍방 계산 (Secure two-party computation, 2PC)으로 공식적으로 도입되었으며 일반적인 수준으로는 1986년에 앤드류 야오[3][4]에 의해 다음과 같이 실행 가능한 모든 계산에 대해 도입되었다. 이 영역은 보안 기능 평가(Secure Function Evaluation, SFE)라고도 한다.2자(Two-party)는 Oded Goldreich, Silvio Micali 및 Avi Wigderson에 의해 다자간(multi-party)으로 일반화되었다. 계산은 잠재적으로 악의적인 경우에 대한 모든 입력 및 영지식 증명의 비밀 공유를 기반으로 한다. 여기서 악의적인 상대의 경우 나쁜 행동이 감지되고 부정직한 참여자가 제거되거나 입력이 공개된 상태로 계산이 계속된다. 이 연구는 보안 컴퓨팅을 위한 미래의 모든 다자간 프로토콜이 따라야 할 매우 기본적인 일반 체계를 제안했다.[5] 이 연구에서는 반 정직한 공격자(semi-honest adversary)로부터 안전한 다자간 계산 프로토콜을 악의적인 공격자로부터 안전한 프로토콜로 컴파일하기 위한 GMW 패러다임이라는 접근 방식을 도입했다. 이 연구는 자주 사용되는 '주식 공유 아이디어'[6]와 당사자 중 한 명이 입력을 숨길 수 있는 프로토콜을 발명한 작업을 통해 누구의 출력도 공개하지 않고 잘못된 동작을 허용하는 최초의 강력한 보안 프로토콜이 뒤따랐다. 무조건 입력한다.[7] GMW 패러다임은 기본 프로토콜에 가져오는 막대한 오버헤드 때문에 수년 동안 비효율적인 것으로 간주되었다. 그러나 효율적인 프로토콜을 달성하는 것이 가능하다는 것이 입증되었으며[8] 이는 실용적인 관점에서 이러한 연구 계열을 더욱 흥미롭게 만든다. 위의 결과는 공격자가 다항 시간 계산으로 제한하고 모든 통신을 관찰하는 모델에 있으므로 이 모델을 '계산 모델'이라고 한다. 또한, 망각 전송 프로토콜은 이러한 작업에 대해 완전한 것으로 나타났다.[9] 위의 결과는 대다수의 사용자가 정직할 때 위의 변형에서 안전한 계산을 달성하는 것이 가능하다는 것을 입증했다.

해결해야 할 다음 문제는 공격자들이 사용할 수 없는 단말간 보안 통신 채널이다. 이 경우에는 참여자 중 최대 1/3이 잘못된 행동을 하고 악의적인 경우에도 암호화 도구를 적용하지 않고서(보안 통신이 가능하므로) 통신채널을 운영할 수 있어야 한다.[10][11] 브로드캐스트 채널을 추가하면 시스템이 잘못된 행동을 하는 소수의 1/2까지 허용할 수 는다.[12] 통신 그래프의 연결 제약은 Perfectly Secure Message Transmission이라는 책에서 조사되었다.[13]

수년에 걸쳐 범용 다자간 프로토콜이라는 개념은 사전 예방적 비밀 공유 와 같은 보편적인 구성 가능성 이나 모바일 공격자와 같은 기본적이면서 일반적인 프로토콜 문제를 조사할 수 있는 비옥한 영역이 되었다.[14]

2000년대 후반부터, 그리고 확실히 2010년 이후부터 범용 프로토콜의 영역은 실제 적용을 염두에 두고 프로토콜의 효율성 향상을 다루는 방향으로 이동했다. MPC에 대해 점점 더 효율적인 프로토콜이 제안되었으며 이제 MPC는 다양한 실제 문제(특히 비밀의 선형 공유만 필요하고 주로 당사자 간의 상호 작용이 많지 않은 공유에 대한 로컬 작업만 필요한 문제)에 대한 실용적인 솔루션으로 간주될 수 있다. ) 분산 투표, 비공개 입찰 및 경매, 서명 공유 또는 복호화 기능, 개인 정보 검색 등이 있다.[15] 다자간 계산을 대규모로 실제로 적용한 최초의 사례는 2008년 1월에 열린 덴마크 사탕무 경매 에서 전자 이중 경매를 실행한 것이다.[16] 분명히 이론적 개념과 조사, 적용 구성이 모두 필요하다(예: MPC를 일상 업무의 일부로 이동하기 위한 조건이[17] 에서 옹호되고 제시되었다).

2020년에는 보안 다자간 컴퓨팅을 담당하는 여러 회사가 "MPC 기술의 인식, 수용 및 채택 가속화"를 목표로 MPC 협회를 설립했다.

정의 및 개요[편집]

MPC에서는 주어진 참가자 수 p 1, p 2, ... , p N 은 각각 개인 데이터를 가지고 있으며 각각 d 1, d 2, ... , d N . 참가자는 자신의 입력을 비밀로 유지하면서 해당 개인 데이터인 F(d 1, d 2, ..., d N )에 대한 공개 함수의 값을 계산하기를 원한다.

예를 들어, 세 당사자인 Alice, Bob, Charlie가 있고 각각의 입력 x, y 및 z가 급여를 나타낸다고 가정한다. 그들은 각자의 연봉이 얼마인지 서로에게 밝히지 않고 세 사람의 급여 중 가장 높은 금액을 알고 싶어한다. 수학적으로 이는 다음을 계산하는 것으로 해석된다.

F(x, y, z) = max(x, y, z)

신뢰할 수 있는 외부 당사자가 있는 경우(예를 들어 비밀을 지킬 수 있는 공통 친구 Tony가 있는 경우) 그들은 각각 Tony에게 급여를 말할 수 있고 Tony는 최대 금액을 계산하여 그 숫자를 그들 모두에게 알릴 수 있다. MPC의 목표는 서로 메시지를 교환함으로써 Alice, Bob, Charlie가 누가 무엇을 만드는지 밝히지 않고 Tony에 의존하지 않고도 F(x, y, z) 학습할 수 있는 프로토콜을 설계하는 것이다. 그들은 부패하지 않고 완벽하게 신뢰할 수 있는 Tony와 상호 작용하여 배우는 것보다 더 많은 것을 프로토콜에 참여함으로써 배워서는 안 된다.

특히 당사자가 배울 수 있는 것은 출력과 자신의 입력에서 배울 수 있는 것뿐이다. 따라서 위의 예에서 출력이 z 이면 Charlie는 자신의 z 최대값이라는 것을 알게 되는 반면, Alice와 Bob은 ( x, y 및 z 서로 다른 경우) 입력이 최대값과 같지 않다는 것을 알게 된다. 보유된 최대값은 z 와 같다. 기본 시나리오는 당사자가 여러 입력 및 출력을 갖고 함수가 당사자마다 다른 값을 출력하는 경우로 쉽게 일반화될 수 있다.

비공식적으로 말하면, 다자간 계산 프로토콜이 보장하려는 가장 기본적인 속성은 다음과 같다.

  • 입력 개인 정보 보호: 당사자가 보유한 개인 데이터에 대한 정보는 프로토콜 실행 중에 전송된 메시지에서 추론할 수 없다. 개인 데이터에 대해 추론할 수 있는 유일한 정보는 함수의 출력만 보고 추론할 수 있는 정보이다.
  • 정확성: 프로토콜 실행 중에 정보를 공유하거나 지침에서 벗어나려는 적대적인 공모 당사자의 적절한 하위 집합은 정직한 당사자가 잘못된 결과를 출력하도록 강요할 수 있어서는 안 된다. 이 정확성 목표는 두 가지 형태로 제공된다. 즉, 정직한 당사자가 올바른 출력을 계산하도록 보장하거나("강력한" 프로토콜) 오류를 발견하면 중단한다("중단 포함" MPC 프로토콜).

동전 던지기 같은 간단한 작업부터 전자 경매(예: 시장 정산 가격 계산), 전자 투표 또는 개인 정보 보호 데이터 마이닝과 같은 보다 복잡한 작업에 이르기까지 다양한 실제 응용 프로그램이 있다. 고전적인 예는 백만장자의 문제이다. 두 명의 백만장자가 누가 더 부유한지 알고 싶어하므로 둘 중 누구도 상대방의 순자산을 배우지 않는다. 이 상황에 대한 해결책은 본질적으로 비교 기능을 안전하게 평가하는 것이다.

보안 정의[편집]

다자간 계산 프로토콜이 효과적이려면 안전해야 한다. 현대 암호화에서 프로토콜의 보안은 보안 증명과 관련이 있다. 보안 증명은 프로토콜의 보안이 기본 기본 요소의 보안으로 축소되는 수학적 증명이다. 그럼에도 불구하고 당사자의 지식과 프로토콜 정확성을 기반으로 암호화 프로토콜 보안 검증을 공식화하는 것이 항상 가능한 것은 아니다. MPC 프로토콜의 경우 프로토콜이 작동하는 환경은 현실 세계/이상 세계 패러다임과 연관된다.[18] 당사자는 작업의 출력을 배워야 하고 출력은 입력에 따라 달라지므로 아무것도 배우지 않는다고 말할 수 없다. 또한 출력의 정확성은 당사자의 입력에 따라 달라지며 입력이 올바른 것으로 가정해야 하기 때문에 출력의 정확성이 보장되지 않는다.

현실 세계/이상 세계 패러다임은 두 가지 세계를 명시한다. (i) 이상 세계 모델에는 각 프로토콜 참가자가 입력을 보내는 부패할 수 없는 신뢰할 수 있는 당사자가 존재한다. 이 신뢰할 수 있는 당사자는 자체적으로 함수를 계산하고 적절한 출력을 각 당사자에게 다시 보낸다. (ii) 반면, 실제 모델에서는 신뢰할 수 있는 당사자가 없으며 당사자가 할 수 있는 일은 서로 메시지를 교환하는 것뿐이다. 이상적인 세계에서 배울 수 있는 것보다 현실 세계에서 각 당사자의 개인적인 입력에 대해 더 이상 배울 수 없는 경우 프로토콜이 안전하다고 한다. 이상적인 세계에서는 당사자 간에 메시지가 교환되지 않으므로 현실 세계에서 교환된 메시지는 어떠한 비밀 정보도 드러낼 수 없다.

현실 세계/이상 세계 패러다임은 MPC 프로토콜의 핵심이 실제로 이상적인 실행이라는 가정하에 애플리케이션을 구축할 수 있도록 MPC의 복잡성에 대한 간단한 추상화를 제공한다. 이상적인 경우에 애플리케이션이 안전하다면 실제 프로토콜이 대신 실행될 때도 안전한다.

MPC 프로토콜의 보안 요구 사항은 엄격한다. 그럼에도 불구하고 1987년에는 악의적인 적에 대한 보안을 통해 모든 기능을 안전하게 계산할 수 있다는 것이 입증되었으며[5] 앞서 언급한 기타 초기 작업이 수행되었다. 이러한 연구 결과에도 불구하고 MPC는 당시 실제로 사용할 수 있을 만큼 효율적으로 설계되지 않았다. 무조건적으로 또는 정보 이론적으로 안전한 MPC는 비밀 공유 문제, 특히 많은 보안 MPC 프로토콜이 활동 중인 공격자에 대해 사용하는 검증 가능한 비밀 공유 (VSS) 문제를 기반으로 하며 밀접하게 관련되어 있다.

암호화나 서명과 같은 전통적인 암호화 애플리케이션과 달리 MPC 프로토콜의 공격자는 시스템에 참여하는(또는 내부 당사자를 제어하는) 플레이어 중 하나라고 가정해야 한다. 해당 부패한 당사자는 프로토콜의 보안을 위반하기 위해 공모할 수 있다. 프로토콜의 당사자 수를 , 적대적일 수 있는 당사자의 수를 로 정의하겠다. 프로토콜 및 솔루션은 (즉, 정직한 다수가 가정되는 경우)와 그러한 가정이 이루어지지 않는 경우에 다르게 정리된다. 후자의 경우에는 2PC(Two-party computation)에서 중요한 문제인 참가자 중 한 사람이 타락할 수 있는 경우를 포함한다. 그리고, 무제한의 참가자가 타락하고 공모하여 정직한 참가자를 공격하는 일반적인 경우가 포함된다.

다양한 프로토콜에 직면한 공격자는 프로토콜에서 얼마나 벗어나려는 의지에 따라 분류될 수 있다. 본질적으로 두 가지 유형의 공격자가 있으며, 각각은 서로 다른 형태의 보안을 제공한다(그리고 각각은 서로 다른 실제 시나리오에 적합하다).

  • 반정직(수동) 보안: 이 경우 손상된 당사자는 단지 프로토콜에서 정보를 수집하기 위해 협력할 뿐 프로토콜 사양에서 벗어나지 않는다고 가정한다. 이는 실제 상황에서 보안이 취약한 순진한 공격 모델이다. 그러나 이 수준의 보안을 달성하는 프로토콜은 (협력하는 경우라면) 당사자 간의 우발적인 정보 유출을 방지하므로 이것이 유일한 관심사인 경우 유용한다. 또한 반정직 모델의 프로토콜은 매우 효율적이며 더 높은 수준의 보안을 달성하기 위한 중요한 첫 번째 단계인 경우가 많다.
  • 악성(능동) 보안: 이 경우 공격자는 부정 행위를 시도하기 위해 프로토콜 실행에서 임의로 벗어날 수 있다. 이 모델에서 보안을 달성하는 프로토콜은 매우 높은 보안 보장을 제공한다. 잘못된 행동을 하는 다수의 당사자의 경우: 부정직한 다수의 경우 공격자가 할 수 있는 유일한 일은 부정 행위를 감지한 정직한 당사자가 "중단"하도록 만드는 것이다. 정직한 당사자가 결과를 얻으면 그것이 정확하다는 것이 보장된다. 그들의 개인정보는 항상 보호된다.

활동적인 공격자에 대한 보안은 일반적으로 효율성 감소로 이어진다. 비밀 보안(covert secrity)는[19] 보안 정의를 약화시키는 대신 더 큰 효율성을 허용하는 것을 목표로 하는 대안이다. 이는 적들이 잡히지 않은 경우에만 적극적으로 속이려고 하는 상황에 적용할 수 있다. 예를 들어, 그들의 평판이 손상되어 향후 다른 정직한 당사자와의 협력이 방해받을 수 있다. 따라서 은밀하게 보안되는 프로토콜은 일부 당사자가 지침을 따르지 않을 경우 75% 또는 90%라는 높은 확률로 발견될 수 있도록 보장하는 메커니즘을 제공한다. 어떤 면에서, 은밀한 공격자는 외부의 비암호화(예: 비즈니스) 문제로 인해 수동적으로 행동할 수밖에 없는 적극적인 공격자이다. 이 메커니즘은 실제로 충분히 효율적이고 안전한 프로토콜을 찾기 위해 두 모델 사이에 가교를 설정한다.

많은 암호화 프로토콜 과 마찬가지로 MPC 프로토콜의 보안은 다양한 가정에 의존할 수 있다.

  • 이는 계산적일 수도 있고(즉, 인수분해와 같은 일부 수학적 문제 기반) 무조건적일 수도 있다. 즉, 채널에서 메시지를 물리적으로 사용할 수 없는 것에 의존한다(일반적으로 임의적으로 작게 만들 수 있는 일부 오류 확률이 있음).
  • 모델은 참가자가 "틱"에 전송된 메시지가 항상 다음 "틱"에 도착하는 동기화된 네트워크를 사용하거나 안전하고 신뢰할 수 있는 브로드캐스트 채널이 존재하거나 모든 쌍 사이에 보안 통신 채널이 존재한다고 가정할 수 있다. 적이 채널 등에서 메시지를 읽거나, 수정하거나 생성할 수 없는 참가자.

계산 작업을 실행할 수 있는 정직한 당사자 집합은 액세스 구조 개념과 관련이 있다. 공격 구조는 적이 다자간 계산을 시작하기 전에 희생자를 선택하는 정적 구조일 수도 있고, 다자간 계산을 실행하는 동안 희생자를 선택하여 방어를 더욱 어렵게 만드는 동적 구조일 수도 있다. 적대적 구조는 임계 구조 또는 더 복잡한 구조로 정의될 수 있다. 임계값 구조에서 공격자는 특정 임계값까지 여러 참가자의 메모리를 손상시키거나 읽을 수 있다. 한편, 복잡한 구조에서는 미리 정의된 참가자의 특정 하위 집합에 영향을 미쳐 다양한 공모 가능성을 모델링할 수 있다.

프로토콜[편집]

2자 컴퓨팅(2PC)과 다자간 컴퓨팅(MPC)을 위해 제안된 프로토콜 간에는 큰 차이가 있다. 또한 중요한 특수 목적 프로토콜의 경우 일반적인 프로토콜(투표, 경매, 지불 등)에서 벗어나는 특수 프로토콜을 설계해야 하는 경우가 많다.

2자 컴퓨팅(Two-party computation)[편집]

특히 2자 설정은 적용 측면에서도 흥미롭지만, 다자간 경우에는 적용되지 않는 특수한 기법을 2자 설정에 적용할 수 있다는 점에서 흥미롭다. 실제로 보안 다자간 계산(실제로는 단일 함수만 평가되는 보안 함수 평가로 제한된 경우)이 2자 설정에서 처음으로 제시되었다. 원본 작업은 Yao의 두 논문 중 하나에서 나온 것으로 자주 인용된다.[20] 논문에는 현재 Yao의 왜곡된 회로 프로토콜로 알려진 내용이 실제로 포함되어 있지 않는다.

Yao의 기본 프로토콜은 반정직한 공격자(semi-honest adversaries)에 대해 안전하며 라운드 수 측면에서 매우 효율적이며 일정하며 평가되는 대상 기능과 무관한다. 이 함수는 고정 길이의 이진수 입력을 갖는 부울 회로로 간주된다. 부울 회로는 세 가지 다른 유형의 와이어(회로 입력 와이어, 회로 출력 와이어 및 중간 와이어)로 연결된 게이트 모음이다. 각 게이트는 두 개의 입력 와이어를 수신하고 팬아웃(즉, 다음 레벨의 여러 게이트로 전달)될 수 있는 단일 출력 와이어를 갖는다. 회로의 일반 평가는 각 게이트를 차례로 평가하여 수행된다. 게이트가 위상적으로 정렬되었다고 가정한다. 게이트는 가능한 각 비트 쌍(입력 와이어의 게이트에서 나오는 비트)에 대해 고유한 출력 비트를 할당하는 진리표로 표시된다. 이는 게이트의 출력 와이어 값이다. 평가 결과는 회로 출력 와이어에서 얻은 비트이다.

Yao는 송신자와 수신자 두 당사자가 회로의 출력만 학습할 수 있도록 회로를 왜곡(구조 숨기기)하는 방법을 설명했다. 높은 수준에서 발신자는 왜곡된 회로를 준비하여 수신자에게 보낸다. 수신자는 회로를 인식하지 못한 채 평가하여 자신과 발신자의 출력에 해당하는 인코딩을 학습한다. 그런 다음 보낸 사람의 인코딩을 다시 보내면 보낸 사람이 출력의 일부를 계산할 수 있다. 송신자는 수신자의 출력 인코딩에서 비트로의 매핑을 수신자에게 전송하여 수신자가 출력을 얻을 수 있도록 한다.

보다 구체적으로, 왜곡된 회로는 다음과 같이 계산된다. 주요 구성 요소는 이중 키 대칭 암호화 체계이다. 회로의 게이트가 주어지면 입력 와이어의 가능한 각 값(0 또는 1)은 난수(레이블)로 인코딩된다. 4개의 가능한 입력 비트 쌍 각각에서 게이트를 평가한 결과 값도 무작위 레이블로 대체된다. 게이트의 왜곡된 진리표는 입력 레이블을 키로 사용하는 각 출력 레이블의 암호화로 구성된다. 진리표에서 이 네 가지 암호화의 위치는 무작위로 지정되므로 게이트 정보가 유출되지 않는다.

각 왜곡된 게이트를 올바르게 평가하기 위해 암호화 체계에는 다음 두 가지 속성이 있다. 첫째, 두 개의 서로 다른 키에 따른 암호화 기능의 범위는 서로 분리되어 있다(압도적인 확률). 두 번째 속성은 주어진 암호문이 주어진 키로 암호화되었는지 여부를 효율적으로 확인할 수 있다는 것이다. 이 두 가지 속성을 사용하여 수신기는 모든 회로 입력 와이어에 대한 레이블을 얻은 후 먼저 4개의 암호문 중 어느 것이 레이블 키로 암호화되었는지 알아낸 다음 해독하여 출력 와이어의 레이블을 얻음으로써 각 게이트를 평가할 수 있다. . 평가 중에 모든 수신기가 비트 인코딩을 학습하므로 이는 무의식적으로 수행된다.

송신자(즉, 회로 작성자)의 입력 비트는 평가자에게 인코딩으로 전송될 수 있다. 입력 비트에 해당하는 수신기(즉, 회로 평가자)의 인코딩은 2개 중 1개 OT(망각 전송) 프로토콜을 통해 획득된다. 1-out-of-2 OT 프로토콜은 C1과 C2 두 값을 소유한 송신자가 수신자가 요청한 값({1,2}의 ba 값)을 송신자가 알 수 없도록 하는 방식이다. 전송되었으며 수신자는 쿼리된 값만 학습한다.

악의적인 공격자를 고려하고 있다면 양 당사자의 올바른 행동을 보장하기 위한 추가 메커니즘을 제공해야 한다. OT 프로토콜이 악의적인 공격자로부터 이미 안전하다면 송신자에게 보안을 보여주는 것은 쉽다. 수신자가 할 수 있는 일은 명령에서 벗어날 경우 회로 출력 전선에 도달하지 못하는 왜곡된 회로를 평가하는 것뿐이다. 보내는 사람 측의 상황은 매우 다르다. 예를 들어, 수신자의 입력을 드러내는 함수를 계산하는 잘못된 왜곡된 회로를 보낼 수 있다. 이는 프라이버시가 더 이상 유지되지 않음을 의미하지만 회로가 왜곡되었기 때문에 수신기는 이를 감지할 수 없다. 그러나 영지식 증명을 효율적으로 적용하여 반정직한 프로토콜(Semi-honesst protocol)에 비해 작은 오버헤드로 악의적인 공격자로부터 이 프로토콜을 보호할 수 있다.[8]

다자간 프로토콜[편집]

2PC 프로토콜과 달리 대부분의 MPC 프로토콜은 특히 비공개 채널의 무조건적인 설정에서 비밀 공유를 사용한다. 비밀 공유 기반 방법에서는 당사자가 특별한 역할(야오의 경우처럼 작성자 및 평가자)을 수행하지 않는다. 대신, 각 전선과 관련된 데이터가 당사자들 사이에서 공유되고, 프로토콜이 각 게이트를 평가하는 데 사용된다. 이 함수는 이제 Yao에 사용되는 이진 회로와 달리 유한 필드에 대한 "회로"로 정의된다. 이러한 회로는 문헌에서 산술 회로라고 불리며, 연산된 값이 유한 필드에 대해 정의되는 덧셈과 곱셈 "게이트"로 구성된다.

비밀 공유를 사용하면 각 당사자에게 공유를 배포하여 여러 당사자에게 비밀을 배포할 수 있다. 두 가지 유형의 비밀 공유 방식이 일반적으로 사용된다. Shamir 비밀 공유 및 추가 비밀 공유. 두 경우 모두 공유는 필드의 비밀을 합산하는 유한 필드의 무작위 요소이다. 직관적으로 보안은 부적합한 공유 집합이 무작위로 분산되어 있는 것처럼 보이기 때문에 달성된다.

비밀 공유 계획은 전체 n 개 당사자 중 최대 t 개 당사자를 제어하는 공격자가 허용될 수 있다. 여기서 t는 계획에 따라 다르며, 적은 수동적이거나 능동적일 수 있으며, 적의 힘에 대해 서로 다른 가정이 이루어진다. Shamir 비밀 공유 계획은 다음과 같은 경우에 수동적인 적으로부터 안전한다. 활동적인 공격자가 있을 때 정보 이론적 보안을 달성하는 동안, 즉 적이 무한한 계산 능력을 갖고 있더라도 공유의 기초가 되는 비밀에 대한 어떤 정보도 알아낼 수 없다. 비밀 공유에 대한 덧셈과 곱셈을 계산하는 방법을 정의하는 BGW 프로토콜[21] 은 Shamir 비밀 공유를 사용하여 함수를 계산하는 데 자주 사용된다. 추가적 비밀 공유 계획은 한 당사자를 제외한 모든 당사자를 통제하는 적이 허용될 수 있다. , 무한한 계산 능력을 갖춘 수동적 및 능동적 적에 대한 보안을 유지한다. 일부 프로토콜에는 계산적으로 제한된 공격자에 대해서만 안전할 수 있는 설정 단계가 필요하다.

많은 시스템에서 비밀 공유 방식을 사용하여 다양한 형태의 MPC를 구현했다. 가장 인기 있는[22] 추가 비밀 공유로 MPC를 구현하고 활성 공격자로부터 보호되는 SPDZ이다.

기타 프로토콜[편집]

2014년에 "출력 수신을 중단한 상대방이 상호 미리 정의된 금전적 벌금을 지불하도록 강요받는 보안 계산의 공정성 모델"이 비트코인 네트워크 또는 공정한 복권에 대해 설명되었으며 이더리움 에서 성공적으로 구현되었다.[23][24]

실용적인 MPC 시스템[편집]

최근 몇 년 동안 2PC 및 MPC 시스템에 많은 발전이 이루어졌다.

Yao 기반 프로토콜[편집]

Yao 기반 프로토콜로 작업할 때 주요 문제 중 하나는 안전하게 평가할 기능(임의의 프로그램일 수 있음)이 일반적으로 XOR 및 AND 게이트로 구성된 회로로 표현되어야 한다는 것이다. 대부분의 실제 프로그램에는 루프와 복잡한 데이터 구조가 포함되어 있으므로 이는 매우 중요한 작업이다. Fairplay 시스템[25] 이 문제를 해결하기 위해 설계된 최초의 도구였다. Fairplay는 두 가지 주요 구성 요소로 구성된다. 첫 번째는 사용자가 간단한 고급 언어로 프로그램을 작성하고 이러한 프로그램을 부울 회로 표현으로 출력할 수 있도록 하는 컴파일러이다. 그런 다음 두 번째 구성 요소는 회로를 왜곡하고 프로토콜을 실행하여 왜곡된 회로를 안전하게 평가할 수 있다. Yao의 프로토콜을 기반으로 한 2자간 계산뿐만 아니라 Fairplay는 다자간 프로토콜도 수행할 수 있다. 이는 Yao의 수동적 보안 프로토콜을 활성 사례로 확장하는 BMR 프로토콜[25] 을 사용하여 수행된다.

Fairplay가 도입된 후 몇 년 동안 Yao의 기본 프로토콜은 효율성 향상과 능동 보안 기술의 형태로 많은 개선이 이루어졌다. 여기에는 XOR 게이트를 훨씬 간단하게 평가할 수 있는 자유 XOR 방법과 잘못된 행 감소(2개의 입력이 있는 잘못된 테이블의 크기를 25% 줄임)와 같은 기술이 포함된다.[26]

지금까지 능동적인 보안을 확보하는 데 가장 효과적이라고 생각되는 접근 방식은 왜곡 기법과 "잘라내기 및 선택" 패러다임의 조합에서 비롯된다. 이 조합은 보다 효율적인 구성을 제공하는 것으로 보인다. 부정직한 행동과 관련하여 앞서 언급한 문제를 피하기 위해 동일한 회로의 많은 왜곡이 생성자에서 평가자에게 전송된다. 그런 다음 일관성을 확인하기 위해 그 중 약 절반(특정 프로토콜에 따라 다름)이 열리고, 그렇다면 열리지 않은 대부분의 항목이 높은 확률로 정확한다. 결과는 모든 평가의 과반수 투표이다. 여기에는 다수의 출력이 필요하다. 출력에 불일치가 있는 경우 수신자는 발신자가 부정 행위를 하고 있다는 것을 알지만, 그렇지 않으면 입력에 대한 정보가 유출될 수 있으므로 불평할 수 없다.

능동 보안을 위한 이러한 접근 방식은 Lindell과 Pinkas에 의해 시작되었다.[27] 이 기술은 Pinkas et al.에 의해 구현되었다. 2009년에[26] 이는 매우 복잡하고(약 30,000개의 AND 및 XOR 게이트로 구성됨) 사소하지 않은 기능으로 간주되는 AES(Advanced Encryption Standard) 회로에 대한 최초의 적극적 보안 2자 평가를 제공했다. 잠재적인 응용 프로그램), 부정 행위 확률을 확보하기 위해 계산하는 데 약 20분이 걸리고 160개의 회로가 필요하다.

많은 회로가 평가되므로 당사자(수신자 포함)는 모든 반복에서 동일한 값이 사용되도록 입력을 커밋해야 한다. Pinkas 등의 실험. 보고된[26] 프로토콜의 병목 현상이 일관성 검사에 있음을 보여준다. 그들은 AES 회로를 평가하기 위해 다양한 값에 대한 약 6,553,600개의 약속을 인터넷을 통해 보내야 했다. 최근 결과[28] 에서는 적극적으로 보안되는 Yao 기반 구현의 효율성이 훨씬 더 향상되어 40개의 회로만 필요하고 훨씬 적은 수의 약속만 필요하다. 부정 행위 확률. 개선 사항은 전송된 회로에서 잘라내기 및 선택을 수행하는 새로운 방법론에서 비롯된다.

최근에는 코어가 많은 CPU 에서 실행되도록 설계된 왜곡된 회로를 기반으로 한 고도의 병렬 구현에 중점을 두고 있다. Kreuter, et al.[29] 강력한 클러스터 컴퓨터의 512개 코어에서 실행되는 구현을 설명한다. 이러한 리소스를 사용하여 회로가 거의 60억 개의 게이트로 구성된 4095비트 편집 거리 기능을 평가할 수 있다. 이를 달성하기 위해 그들은 Fairplay보다 더 잘 최적화된 맞춤형 회로 컴파일러와 파이프라이닝과 같은 몇 가지 새로운 최적화를 개발했다. 이를 통해 회로의 나머지 부분이 계속 생성되는 동안 네트워크를 통해 왜곡된 회로의 전송이 시작된다. AES를 계산하는 시간은 512노드 클러스터 시스템을 사용하는 경우 활성 사례에서 블록당 1.4초, 노드 1개를 사용하는 경우 115초로 단축되었다. Shelat과 Shen[30] 상용 하드웨어를 사용하여 이를 블록당 0.52초로 개선했다. 동일한 문서에서는 초당 21블록의 처리량을 보고하지만 지연 시간은 블록당 48초이다.

한편, 또 다른 연구자 그룹은 비슷한 수준의 병렬 처리를 달성하기 위해 소비자급 GPU를 사용하는 방법을 조사했다.[31] 그들은 GPU 특정 프로토콜을 설계하기 위해 인식되지 않는 전송 확장 및 기타 새로운 기술을 활용한다. 이 접근 방식은 비슷한 수의 코어를 사용하여 클러스터 컴퓨팅 구현과 비슷한 효율성을 달성하는 것으로 보인다. 그러나 저자는 약 50,000개의 게이트가 있는 AES 회로의 구현에 대해서만 보고했다. 반면에 여기에 필요한 하드웨어는 훨씬 더 접근하기 쉽다. 유사한 장치가 이미 많은 사람들의 데스크톱 컴퓨터나 게임 콘솔에서 발견될 수 있기 때문이다. 저자는 표준 GPU를 사용하여 표준 데스크톱에서 AES 블록당 2.7초의 타이밍을 얻었다. 보안을 비밀 보안과 유사한 수준으로 낮추는 경우 AES 블록당 0.30초의 런타임을 얻는다. 수동적 보안의 경우 2억 5천만 개의 게이트와 초당 7,500만 개의 게이트 속도로 회로를 처리한다는 보고가 있다.[32]

안전한 다자간 계산 데이터 분석 구현[편집]

안전한 다자간 계산의 주요 응용 프로그램 중 하나는 데이터 관리자가 수행 중인 데이터 분석의 종류를 이해하지 못하도록 여러 당사자가 보유한 데이터를 분석하거나 제3자가 데이터를 맹목적으로 분석할 수 있도록 하는 것이다.

시연 및 생산 시스템[편집]

분석 데이터 관리자 기술 제공자 도입 연도 노트 아직 사용 중이신가요?
보스턴 여성 인력 협의회 보고서[33] 보스턴 지역 고용주 보스턴대학교 2016년
Allegheny 카운티 데이터세트[34][35][36][37] 다양한 카운티 사무소의 여러 데이터 세트 갈루아와 초당적 정책 센터 2018

소프트웨어 라이브러리[편집]

이름 개발자 도입 연도 노트 아직도 유지되고 있나요?
SEPIA - 개인정보 수집을 통한 보안
SCAPI - 보안 컴퓨팅 API[38]
PALISADE - 동형암호 라이브러리[39]
MP-SPDZ - 다자간 계산을 위한 다목적 프레임워크[40] CSIRO 의 Data61 2018 40가지 프로토콜 변형, 기계 학습 기능에 중점 2023년 기준

하드웨어 구현체[편집]

이름 개발자 도입 연도 노트 아직도 유지되고 있나요?
트라이던트 MPC i4p 정보학 회사 2019 암호화 키 관리를 위해 SMPC(Secure Multi-party Computation)를 적용하도록 설계된 시장 최초의 Common Criteria EAL4+ 인증 물리적 하드웨어 보안 모듈이다 . 2024년 기준

같이 보기[편집]

각주[편집]

  1. ↑ Ran Canetti, et al., "Adaptively Secure Multi-party", TOC/CIS groups, LCS, MIT (1996), p. 1.
  2. ↑ A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.
  3. ↑ Andrew C. Yao, Protocols for secure computations (extended abstract)
  4. ↑ Andrew Chi-Chih Yao:How to Generate and Exchange Secrets (Extended Abstract). FOCS 1986: 162-167
  5. ↑ 가 나 Oded Goldreich, Silvio Micali, Avi Wigderson:How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. STOC 1987: 218-229
  6. ↑ Zvi Galil, Stuart Haber, Moti Yung: Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. CRYPTO 1987: 135-155
  7. ↑ David Chaum, Ivan Damgård, Jeroen van de Graaf: Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result. 87-119
  8. ↑ 가 나 Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (2020년 10월 30일). 〈Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC〉. 《Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security》. CCS '20. Virtual Event, USA: Association for Computing Machinery. 1591–1605쪽. doi:10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. 
  9. ↑ Joe Kilian: Founding Cryptography on Oblivious Transfer. STOC 1988: 20-31
  10. ↑ D. Chaum, C. Crepeau; I. Damgard. “Multiparty unconditionally secure protocols”. 《Stoc 1988》. 
  11. ↑ Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). STOC 1988: 1-10
  12. ↑ Tal Rabin, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85
  13. ↑ Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Perfectly Secure Message Transmission. J. ACM 40(1): 17-47 (1993)
  14. ↑ Rafail Ostrovsky, Moti Yung: How to Withstand Mobile Virus Attacks. PODC 1991. pp. 51-59
  15. ↑ Claudio Orlandi: Is multiparty computation any good in practice?[깨진 링크(과거 내용 찾기)], ICASSP 2011
  16. ↑ Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft (2008). “Multiparty Computation Goes Live”. 《Cryptology ePrint Archive》 (Report 2008/068). 
  17. ↑ Moti Yung: From Mental Poker to Core Business: Why and How to Deploy Secure Computation Protocols? ACM Conference on Computer and Communications Security 2015: 1-2 https://dl.acm.org/citation.cfm?doid=2810103.2812701
  18. ↑ Michael Backes, Birgit Pfitzmann, and Michael Waidner. "A general composition theorem for secure reactive systems." In Theory of Cryptography Conference, pp. 336-354. Springer, Berlin, Heidelberg, 2004.
  19. ↑ Y. Aumann; Y. Lindell. “Security against covert adversaries”. 《TCC 2007》. 
  20. ↑ Andrew C. Yao, "How to generate and exchange secrets," SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 162-167, 1986.
  21. ↑ Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi (1988년 1월 1일). 〈Completeness theorems for non-cryptographic fault-tolerant distributed computation〉. 《Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88》. ACM. 1–10쪽. doi:10.1145/62212.62213. ISBN 978-0897912648. 
  22. ↑ I. Damgård, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.
  23. ↑ Iddo Bentov, Ranjit Kumaresan (2014). “How to Use Bitcoin to Design Fair Protocols” (PDF). 《Cryptology e Print》 (129): 1–38. 2014년 10월 9일에 확인함. 
  24. ↑ Mikhail Kalinin, Danny Ryan, Vitalik Buterin (2021). “EIP-3675: Upgrade consensus to Proof-of-Stake”. 《Ethereum Improvement Proposals》. 2023년 10월 16일에 확인함. 
  25. ↑ 가 나 A. Ben-David, N. Nisan and B. Pinkas, "FairplayMP: a system for secure multi-party computation," ACM CCS 2008, pp. 257–266, 2008.
  26. ↑ 가 나 다 B. Pinkas, T. Schneider, N. Smart and S. Williams, "Secure two-party computation is practical," Asiacrypt 2009, vol. Springer LNCS 5912, pp. 250–267, 2009.
  27. ↑ Y. Lindell and B. Pinkas, "An efficient protocol for secure two-party computation in the presence of malicious adversaries," Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.
  28. ↑ Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries," Crypto 2013, vol. Springer LNCS 8043, pp. 1-17, 2013.
  29. ↑ B. Kreuter, a. shalet and C.-H. Shen, "Billion gate secure computation with malicious adversaries," USENIX Security Symposium 2012, pp. 285–300, 2012.
  30. ↑ A. Shelat and C.-H. Shen, "Fast two-party secure computation with minimal assumptions," ACM CCS 2013, pp. 523–534, 2013.
  31. ↑ T. Frederiksen and J. Nielsen, "Fast and maliciously secure two-party computation using the GPU, "ACNS 2013, vol. Springer LNCS 7954, pp. 339–356, 2013.
  32. ↑ Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose.," CRYPTO, vol. Springer LNCS 8043, pp. 18-35, 2013.
  33. ↑ “Boston Women's Workforce Council Report” (PDF). Boston Women's Workforce Council. January 2017. 2024년 2월 14일에 확인함. 
  34. ↑ “BPC Partners with Allegheny County on New Privacy-Preserving Data Project | Bipartisan Policy Center”. 
  35. ↑ Hart, N.R.; Archer, D.W.; Dalton, E. (March 2019). “Privacy-Preserved Data Sharing for Evidence-Based Policy Decisions” (PDF). Bipartisan Policy Center. 2024년 2월 14일에 확인함. 
  36. ↑ Galois 2018 Technical Report
  37. ↑ “Route Fifty”. 2023년 8월 25일. 
  38. ↑ “SCAPI: The Secure Computation API Library | BIU Cyber Center”. 
  39. ↑ https://palisade-crypto.org/
  40. ↑ https://mp-spdz.readthedocs.io

추가 읽기[편집]

외부 링크[편집]

  • JavascriptMPC — JavascriptMPC Javascript 파일을 잘못된 회로로 컴파일할 수 있는 golang MPC 프레임워크
  • 보안 분산 CSP(DisCSP) 솔버 — 애플릿 인터프리터가 포함된 웹 애플리케이션으로 SMC 선언 언어 기반의 완전한 보안 다자간 계산을 설계하고 실행할 수 있음. 안전한 산술 회로 평가 및 믹스넷을 사용
  • Fairplay 프로젝트 — 함수가 고급 기능 설명 언어를 사용하여 정의되고 부울 회로의 보안 평가를 위해 Yao의 프로토콜을 사용하여 평가되는 안전한 양방향 계산을 위한 소프트웨어 패키지가 포함되어 있음
  • 보안 다자간 컴퓨팅 언어(Secure Multiparty Computation Language) - '보안 다자간 컴퓨팅을 위한 도메인별 프로그래밍 언어' 및 관련 암호화 런타임 개발을 위한 프로젝트
  • Myst 프로젝트 - 안전한 다자간 키 생성, 서명 및 암호 해독을 구현하는 JavaCard 애플릿
원본 주소 "https://ko.wikipedia.org/w/index.php?title=다자간_보안_컴퓨팅&oldid=37270450"