시큐어 멀티 파티

Secure multi-party computation

시큐어 멀티 파티 계산(시큐어 계산, 멀티 파티 계산(MPC) 또는 프라이버시 보존 계산이라고도 함)은 암호학의 서브 필드이며, 입력 내용을 비공개로 유지하면서 당사자가 공동으로 함수를 계산하는 방법을 만드는 것을 목적으로 합니다.암호화가 통신 또는 스토리지의 보안과 무결성을 보장하고 상대방이 참가자 시스템(송신자와 수신자의 도청자) 밖에 있는 기존 암호 작업과 달리, 이 모델의 암호 기술은 참가자의 개인 정보를 서로 보호합니다.

시큐어 멀티 파티 컴퓨팅의 기반은 1970년대 후반, 신뢰할 수 있는 서드 파티 없이 먼 거리에서 게임 플레이/컴퓨팅 작업을 시뮬레이트하는 암호화 작업인 멘탈 포커에 관한 작업으로 시작되었습니다.전통적으로 암호학은 콘텐츠를 숨기는 것이었지만, 이 새로운 유형의 계산 및 프로토콜은 데이터에 대한 부분 정보를 숨기고 여러 소스의 데이터를 사용하여 계산하여 올바르게 출력을 생성하는 것입니다.1980년대 후반, Michael Ben-Or, Shafi Goldwasser 및 Avi Wigderson, 그리고 독립적으로 David Chaum, Claude Crépeau 및 Ivan Damgörd는 "보안 채널 [1]설정에서 함수를 안전하게 계산하는 방법"을 보여주는 논문을 발표했다.

역사

특정 작업에 대한 특수 목적 프로토콜은 1970년대 [2]말에 시작되었습니다.나중에 보안 계산은 1982년에 보안 양자 계산(2PC)으로 공식적으로 도입되었고(이른바 백만장자 문제의 경우, 부울 술어), 1986년에 Andrew [3][4]Yao에 의해 일반성(2PC)으로 도입되었다.이 영역은 Secure Function Evaluation(SFE)이라고도 합니다.두 당의 사례는 Goldreich, Micali, Wigderson에 의해 복수 정당에 대한 일반화로 이어졌다.계산은 모든 입력의 비밀 공유와 잠재적인 악의적 사례에 대한 제로 지식 증거에 기초한다.이 경우 악의적 적대 사례에 대한 정직한 대다수의 참가자는 나쁜 행동이 감지되고 부정직한 사람이 제거되거나 그의 입력이 드러난 상태에서 계산이 계속된다.이 작업은 보안 [5]컴퓨팅을 위해 기본적으로 모든 미래 멀티파티 프로토콜이 따라야 하는 매우 기본적인 일반적인 계획을 제시했습니다.이 연구는 반정직한 상대로부터 안전한 다중 파티 계산 프로토콜을 악의적 상대로부터 안전한 프로토콜로 컴파일하기 위한 GMW 패러다임으로 알려진 접근방식을 도입했다.이 작업은 이러한 목적을 위해 자주 사용되는 '공유 아이디어'[6]를 발명한 작업을 통해 누구의 출력도 드러내지 않고 결함 행동을 친절하게 용인하는 최초의 강력한 보안 프로토콜과 당사자 중 한 명이 그 [7]입력을 무조건 숨길 수 있도록 하는 프로토콜이 뒤따랐다.GMW 패러다임은 기본 프로토콜에 막대한 오버헤드로 인해 수년간 비효율적인 것으로 간주되었습니다.그러나 효율적인 프로토콜 [8]달성이 가능하며, 실용적인 관점에서 이 연구 라인을 더욱 흥미롭게 한다.위의 결과는 상대방이 다항식 시간 계산으로 제한되고, 모든 통신을 관찰하는 모델에 있으며, 따라서 이 모델을 '컴퓨팅 모델'이라고 한다.또한, 망각 전달 프로토콜은 이러한 [9]작업에 대해 완전한 것으로 나타났다.위의 결과에 따르면 대다수의 사용자가 정직할 때 위의 변형으로 안전한 계산을 할 수 있습니다.

다음으로 해결해야 할 문제는 포인트 투 포인트 통신을 적에게 제공할 수 없는 안전한 통신 채널의 경우였습니다.이 경우 최대 1/3의 당사자가 잘못된 행동을 하고 악의적으로 행동하면 해결책이 달성될 수 있으며 보안 통신을 이용할 수 있기 때문에 솔루션은 암호화 도구를 적용하지 않는 것으로 나타났습니다.브로드캐스트 채널을 추가하면 시스템이 1/2까지 잘못된 동작을 허용할 수 있는 [12]반면, 통신 그래프의 연결 제약은 "완벽하게 안전한 메시지 전송"[10][11][13]이라는 책에서 조사되었습니다.

수년간 범용 다중 파티 프로토콜의 개념은 사전 비밀 [14]공유와 같이 범용 구성 가능성이나 모바일 적과 같은 기본 및 일반 프로토콜 문제 속성을 조사하기 위한 비옥한 영역이 되었습니다.

2000년대 후반부터, 특히 2010년 이후, 범용 프로토콜의 영역은 실용적인 적용을 염두에 두고 프로토콜의 효율성 향상을 다루도록 이동해 왔습니다.MPC를 위한 보다 효율적인 프로토콜이 제안되었으며, MPC는 분산 투표, 비공개 입찰 및 au와 같은 다양한 실제 문제(특히 비밀의 선형 공유만 필요하고 주로 당사자 간의 상호 작용이 많지 않은 공유에 대한 로컬 운영)에 대한 실질적인 해결책으로 간주될 수 있습니다.ctions, 서명 또는 복호화 기능 공유 및 개인 정보 검색.[15]2008년 [16]1월 덴마크에서 최초로 대규모로 실용적으로 다당제 계산(실제 경매 문제에 대한 시연)이 실시되었다.이론적인 개념과 조사, 그리고 응용된 건설이 모두 필요한 것은 분명하다(예를 들어, MPC를 일상 업무의 일부로 이동시키는 조건이 주장되고 제시되었다[17]).

정의와 개요

MPC에서 소정의 수의 참가자 p1, p2, …, p는N 각각 d1, d2, …, d를N 가지고 있다.참가자는 자신의 입력을 비밀로 유지하면서 그 프라이빗 데이터 F(d1, d2, …, dN)에 대한 퍼블릭 함수의 값을 계산하고 싶어한다.

예를 들어, Alice, Bob, Charlie의 3개 파티가 있으며, 각각의 입력 x, y, z는 급여를 나타냅니다.그들은 세 개의 월급 중 가장 높은 연봉을 서로 밝히지 않고 알아보려고 합니다.수학적으로 계산하면 다음과 같습니다.

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

만약 믿을 수 있는 외부 파티가 있다면(예를 들어, 그들은 비밀을 지킬 수 있는 공통의 친구 토니를 알고 있다), 그들은 각자 자신들의 월급을 토니에게 말할 수 있고, 그는 최고치를 계산해서 그들 모두에게 그 숫자를 말할 수 있다.MPC의 목표는 Alice, Bob, Charlie가 Tony에게 의지할 필요 없이 F(x, y, z)를 배울 수 있는 프로토콜을 설계하는 것입니다.그들은 그들의 프로토콜에 참여함으로써 배우지 말아야 합니다. 그들이 청렴하고 완벽하게 신뢰할 수 있는 토니와의 상호작용을 통해 배우는 것처럼 말이죠.

특히, 당사자들이 배울 수 있는 것은 그들이 출력과 그들 자신의 입력으로부터 배울 수 있는 모든 것이다.위의 예에서 출력이 z이면 Charlie는 자신의 z가 최대값임을 학습하는 반면 Alice와 Bob은 입력이 최대값과 같지 않고 유지된 최대값이 z와 같다는 것을 학습합니다.기본 시나리오는 당사자가 여러 입력과 출력을 가지고 있고 함수가 서로 다른 값을 출력하는 경우에 쉽게 일반화할 수 있다.

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

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

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

보안 정의

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

Real World/Ideal World Paradamy에는 두 가지 세계가 있습니다. (i) 이상적인 세계 모델에는 각 프로토콜 참가자가 의견을 보내는 부패하지 않은 신뢰할 수 있는 당사자가 존재합니다.이 신뢰할 수 있는 당사자는 스스로 함수를 계산하여 적절한 출력을 각 당사자에게 반환합니다.(ii) 반면 실제 모델에서는 신뢰할 수 있는 당사자는 없으며 당사자가 할 수 있는 것은 서로 메시지를 교환하는 것뿐입니다.이상적인 세계에서 배울 수 있는 것처럼 현실 세계에서 각 당사자의 사적인 입력에 대해 더 이상 알 수 없다면 프로토콜은 안전하다고 한다.이상적인 세계에서는 당사자 간에 메시지가 교환되지 않기 때문에 실제 교환된 메시지는 어떠한 비밀 정보도 드러낼 수 없습니다.

현실세계/이상세계 패러다임은 MPC의 복잡성을 단순하게 추상화함으로써 MPC 프로토콜의 핵심이 실제로 이상적인 실행이라는 가정 하에 애플리케이션을 구축할 수 있도록 합니다.이상적인 경우 응용 프로그램이 안전하다면 실제 프로토콜을 대신 실행할 때도 안전합니다.

MPC 프로토콜의 보안 요건은 엄격합니다.그럼에도 불구하고 1987년에는 악성 공격자에[5] 대한 보안과 이전에 언급한 다른 초기 작업을 통해 모든 함수를 안전하게 계산할 수 있다는 것이 입증되었다.이러한 출판물에도 불구하고, MPC는 그 당시에 실제로 사용될 만큼 충분히 효율적이도록 설계되지 않았다.무조건 또는 정보 이론적으로 안전한 MPC는 비밀 공유, 특히 많은 보안 MPC 프로토콜이 활성 공격자에 대해 사용하는 검증 가능한 비밀 공유(VSS) 문제와 밀접하게 관련되어 있습니다.

암호화 또는 서명과 같은 기존 암호화 애플리케이션과 달리 MPC 프로토콜의 상대는 시스템에 관여하는(또는 내부 당사자를 제어하는) 플레이어 중 하나라고 가정해야 합니다.손상된 당사자는 프로토콜의 보안을 침해하기 위해 결탁할 수 있습니다.n n을 프로토콜의 당사자 수로 하고 t t를 적대적인 당사자 수로 .< / （ t / ）의 경우(즉, 정직한 과반수를 가정하는 경우)의 프로토콜과 솔루션은 그러한 가정이 이루어지지 않는 경우와는 다르다.이 후자의 케이스에는 참가자 중 한 명이 파손될 수 있는 양 당사자 계산의 중요한 케이스와 무제한의 참가자가 파손되어 정직한 참가자를 공격하기 위해 결탁하는 일반적인 케이스가 포함됩니다.

서로 다른 프로토콜에 직면하는 적대자들은 프로토콜에서 이탈하려는 의도에 따라 분류될 수 있습니다.기본적으로 두 가지 유형의 적이 있으며, 각각 다른 형태의 보안(각각 다른 실제 시나리오에 적합)을 발생시킵니다.

  • 준정직(패시브) 보안:이 경우, 손상된 당사자들은 단지 프로토콜로부터 정보를 수집하기 위해 협력할 뿐 프로토콜 규격에서 벗어나지 않는다고 가정한다.이는 실제 상황에서 취약한 보안을 제공하는 순진한 적대적 모델입니다.그러나 이 보안 수준을 달성하는 프로토콜은 (그렇지 않으면 협력하는) 당사자 간의 의도하지 않은 정보 유출을 방지하므로 이것이 유일한 관심사일 경우 유용합니다.또한, 준정직 모델의 프로토콜은 매우 효율적이며, 종종 더 높은 수준의 보안을 달성하기 위한 중요한 첫 번째 단계입니다.
  • 악의적인(액티브) 보안:이 경우, 상대방은 부정행위를 시도하면서 임의로 프로토콜 실행에서 벗어날 수 있습니다.이 모델에서 보안을 달성하는 프로토콜은 매우 높은 보안 보장을 제공합니다.부정한 행위를 하는 당사자의 과반수인 경우:부정직한 다수결의 경우에 적수가 할 수 있는 유일한 일은 정직한 당사자들이 부정행위를 적발한 것을 "포기"하게 만드는 것이다.정직한 당사자가 출력을 얻으면 그것이 올바른 것임을 보증합니다.그들의 사생활은 항상 보호된다.

액티브한 공격자에 대한 보안은 일반적으로 효율 저하로 이어지며, 이는 액티브한 보안의 완화된 형태인 은밀한 [19]보안으로 이어집니다.은밀한 보안은 보다 현실적인 상황을 포착합니다.적극적인 공격자는 체포되지 않은 경우에만 부정행위를 할 용의가 있습니다.예를 들어, 그들의 평판이 손상되어 다른 정직한 당사자들과의 향후 협력이 방해될 수 있습니다.따라서, 비밀리에 보안 보호된 프로토콜은 일부 당사자가 지침을 따르지 않을 경우, 75% 또는 90%의 높은 확률로 이를 인지할 수 있는 메커니즘을 제공한다.어떤 면에서 은밀한 적들은 외부의 비암호화(예: 비즈니스) 문제로 인해 수동적으로 행동해야 하는 능동적인 적입니다.이 메커니즘은 실제로 충분히 효율적이고 안전한 프로토콜을 찾기 위해 두 모델 간에 브리지를 설정합니다.

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

  • 이는 계산적(즉, 인수분해와 같은 일부 수학적 문제에 기초함)일 수도 있고 무조건적일 수도 있다. 즉, 채널에서 메시지를 물리적으로 이용할 수 없는 것에 의존할 수도 있다(일반적으로 채널에서 메시지를 물리적으로 이용할 수 없다.
  • 이 모델에서는 참가자가 동기화된 네트워크를 사용하고 있다고 가정할 수 있습니다.이 네트워크에서는 "tick"으로 송신된 메시지가 항상 다음 "tick"에 도착하거나 안전하고 신뢰할 수 있는 브로드캐스트채널이 존재하거나 상대방이 채널 내의 메시지를 읽거나 변경하거나 생성할 수 없는 안전한 통신채널이 모든 참가자 쌍 사이에 존재한다고 가정할 수 있습니다.기타.

계산 태스크를 실행할 수 있는 정직한 당사자의 집합은 액세스 구조의 개념과 관련되어 있습니다.적대적 구조는 정적일 수 있으며, 적들은 다중 파티 계산의 시작 전에 희생자를 선택하거나, 다방면의 계산 실행 과정에서 희생자를 선택하는 동적 구조일 수 있다.대립 구조는 역치 구조 또는 보다 복잡한 구조로 정의할 수 있습니다.문턱값 구조에서는 적은 문턱값까지 다수의 참가자의 메모리를 손상시키거나 읽을 수 있습니다.한편, 복잡한 구조에서는 참가자의 특정 사전 정의된 하위 집합에 영향을 미칠 수 있으며, 다양한 가능한 결합을 모델링할 수 있다.

프로토콜

양 당사자 계산 (2PC)과 다중 당사자 계산 (MPC)을 위해 제안된 프로토콜 사이에는 큰 차이가 있습니다.또한 중요한 특수 목적 프로토콜의 경우 일반 프로토콜에서 벗어나는 특수 프로토콜(투표, 경매, 결제 등)을 설계해야 하는 경우 등).

양 당사자의 계산

주요 기사:안전한 양 당사자 계산
참고 항목: 회로 왜곡

양 당사자 설정은 어플리케이션의 관점뿐만 아니라 멀티 파티의 경우 적용되지 않는 특수한 기술을 양 당사자 환경에서도 적용할 수 있기 때문에 특히 흥미롭다.실제로, 보안 다중 파티 계산(실제로 단일 기능만 평가되는 보안 기능 평가의 제한된 경우)이 양 당사자 환경에서 처음 제시되었습니다.원본은 종종 [20]Yao의 두 논문 중 하나에서 인용된다; 비록 그 논문들은 현재 Yao의 왜곡된 회로 프로토콜로 알려진 것을 실제로 포함하고 있지는 않다.

Yao의 기본 프로토콜은 반정직한 적들에 대해 안전하며, 평가 대상 함수와 독립적이고 일정하며 라운드 수 측면에서 매우 효율적입니다.함수는 고정 길이의 바이너리 입력이 있는 부울 회로로 표시됩니다.부울 회로는 회로 입력 와이어, 회로 출력 와이어 및 중간 와이어의 세 가지 다른 유형의 와이어로 연결된 게이트 집합입니다.각 게이트는 2개의 입력 와이어를 수신하고 팬아웃(즉, 다음 레벨에서 여러 게이트로 전달)할 수 있는 단일 출력 와이어를 가집니다.회로의 평이한 평가는 게이트가 위상적으로 정렬되어 있다고 가정하고 각 게이트를 차례로 평가함으로써 이루어집니다.게이트는 가능한 각 비트 쌍(입력 와이어의 게이트에서 나오는 비트)에 대해 테이블이 게이트의 출력 와이어 값인 고유한 출력 비트를 할당하도록 참값 테이블로 표시됩니다.평가 결과는 회로 출력 와이어에서 얻은 비트입니다.

Yao는, 송신자와 수신자의 쌍방이 회로의 출력을 학습할 수 있도록, 회로를 가글(구조를 숨김)하는 방법을 설명했습니다.높은 레벨에서는, 송신자는 왜곡 회로를 준비해, 수신자에게 송신하고, 수신자는, 자기와 송신자의 출력에 대응하는 부호화를 학습해, 회로를 망각적으로 평가한다.그런 다음 송신자의 인코딩만 전송하여 송신자가 출력의 일부를 계산할 수 있도록 합니다.송신측은, 리시버 출력 부호화로부터 비트로의 매핑을 리시버에 송신해, 리시버가 출력을 취득할 수 있도록 합니다.

보다 상세하게는 다음과 같이 왜곡회로를 계산한다.주요 요소는 이중 키 대칭 암호화 방식입니다.회로의 게이트를 지정하면 입력 와이어의 각 값(0 또는 1)은 난수(라벨)로 인코딩됩니다.가능한 4개의 입력 비트 쌍 각각에서 게이트를 평가한 결과 값도 랜덤 라벨로 대체됩니다.게이트의 왜곡된 진실 테이블은 입력 라벨을 키로 사용하는 각 출력 라벨의 암호화로 구성됩니다.진실 테이블에서 이들 4개의 암호화 위치가 랜덤화되므로 게이트의 정보는 유출되지 않습니다.

각 왜곡된 게이트를 올바르게 평가하기 위해 암호화 방식에는 다음 두 가지 속성이 있습니다.첫째, 두 개의 다른 키에서 암호화 기능의 범위는 (매우 높은 확률로) 분리되어 있습니다.두 번째 속성은 특정 암호문이 특정 키로 암호화되었는지 여부를 효율적으로 확인할 수 있음을 나타냅니다.이 두 가지 속성을 통해 수신기는 모든 회로 입력 와이어의 라벨을 취득한 후 먼저 라벨 키로 암호화되어 있는4개의 암호문 중 어느 것을 검출하고 나서 복호화하여 출력 와이어의 라벨을 취득함으로써 각 게이트를 평가할 수 있습니다.이는 평가 중에 수신자가 학습하는 모든 것이 비트의 인코딩이기 때문에 망각적으로 이루어집니다.

송신기(즉, 회로 생성기)의 입력 비트는 평가기에 대한 인코딩으로 전송될 수 있는 반면, 수신기의 입력 비트에 해당하는 (즉, 회로 평가기) 인코딩은 2개 중 1개의 망각 전송(OT) 프로토콜을 통해 얻을 수 있다.2개 중 1개의 OT 프로토콜은 2개의 값 C1과 C2를 소유하고 있는 송신자가 어떤 값이 전송되었는지 알 수 없고 수신자는 쿼리된 값만 학습하도록 수신자가 요구한 값({1,2}의 b 값)을 송신할 수 있도록 합니다.

악의적인 상대를 배려하고 있다면 양 당사자의 올바른 행동을 보장하기 위한 추가 메커니즘을 마련해야 한다.구조상 OT 프로토콜이 이미 악의적인 공격으로부터 안전하다면 송신자에 대한 보안을 쉽게 보여줄 수 있습니다. 수신자가 할 수 있는 일은 명령에서 벗어날 경우 회로 출력 와이어에 도달하지 못할 왜곡된 회로를 평가하는 것입니다.송신자측의 상황은 크게 다릅니다.예를 들어, 수신기의 입력을 나타내는 함수를 계산하는 잘못된 왜곡 회로를 전송할 수 있습니다.이것은 프라이버시가 유지되지 않게 되는 것을 의미합니다만, 회선이 불안정하기 때문에, 수신측은 이것을 검출할 수 없습니다.그러나 제로 지식 증명을 효율적으로 적용하여 반정직 [8]프로토콜에 비해 적은 오버헤드로 악의적인 공격자로부터 이 프로토콜을 보호할 수 있습니다.

멀티파티 프로토콜

대부분의 MPC 프로토콜은 2PC 프로토콜과 달리 특히 개인 채널의 무조건적인 설정 하에서 비밀 공유를 사용합니다.비밀 공유 방식에서는 당사자가 특별한 역할을 하지 않는다(작성자 및 평가자 야오).대신, 각 와이어와 관련된 데이터는 당사자들 간에 공유되며, 각 게이트를 평가하기 위해 프로토콜이 사용됩니다.이 함수는 이제 Yao에 사용되는 바이너리 회로가 아닌 유한 필드 상의 "회로"로 정의됩니다.이러한 회로를 문헌에서는 산술회로라고 하며, 이 회로는 덧셈과 곱셈 "게이트"로 구성되어 있으며, 여기서 동작하는 값은 유한 필드에 걸쳐 정의됩니다.

비밀 공유는 각 당사자에게 지분을 분배함으로써 여러 당사자에게 비밀을 분배할 수 있게 해준다.일반적으로 Shamir 비밀 공유와 추가 비밀 공유의 두 가지 유형의 비밀 공유 방식이 사용됩니다.두 경우 모두 주식은 유한한 분야의 무작위 요소이며, 그 분야의 비밀을 더한다.

비밀공유제도는 총 n개의 파티 중 최대 t개의 파티까지 상대방이 통제하는 것을 허용할 수 있다.여기서 t는 제도에 따라 다르며, 상대방은 수동적이거나 능동적일 수 있으며, 상대방이 가진 힘에 대해 다른 가정이 이루어진다.그 샤미르 비밀 공유 계획이 소극적인 상대 때 t<>n2{\displaystyle t<,{\frac{n}{2}}에}과 적극적인 상대 때 t<>n3{\displaystyle t<,{\frac{n}{3}}}는 동안, 비록 상대방의 무한한 계산력이 있는 사람이 cann 의미information-theoretic 보안 목적의 달성 안전합니다.은 배우y 공유의 기반이 되는 비밀에 대한 정보.비밀 공유에서 덧셈과 곱셈을 계산하는 방법을 정의하는 BGW [21]프로토콜은 Shamir 비밀 공유로 함수를 계산하는 데 종종 사용됩니다.추가 비밀 공유 방식은 한 당사자(t < \ t n )를 제외한 모든 당사자(t < n \ displaystyle t < n 를 상대방이 제어하는 것을 허용할 수 있으며 무한한 계산 능력을 가진 수동적이고 능동적인 상대방에 대한 보안을 유지할 수 있습니다.일부 프로토콜은 설정 단계를 필요로 하며, 이는 계산적으로 제한된 상대에게만 안전할 수 있습니다.

많은 시스템이 비밀 공유 스킴으로 다양한 형태의 MPC를 구현하고 있습니다.가장 인기 있는 것은 SPDZ입니다.[22]SPDZ는 추가 비밀 공유로 MPC를 구현하고 액티브한 공격자로부터 안전합니다.

기타 프로토콜

2014년에는 Bitcoin 네트워크 또는 공정한 [23]복권을 위해 "출력 수신을 중단하는 적대적 당사자가 상호 사전 정의된 금전적 위약금을 지불하도록 강요하는 안전한 계산의 공정성 모델"이 기술되었다.

실용적인 MPC 시스템

최근 몇 년간 2PC 및 MPC 시스템에서 많은 발전이 이루어졌습니다.

야오 기반 프로토콜

Yao 기반 프로토콜로 작업할 때 가장 큰 문제 중 하나는 안전하게 평가되어야 하는 함수(임의 프로그램일 수 있음)가 일반적으로 XOR과 AND 게이트로 구성된 회로로 표현되어야 한다는 것입니다.대부분의 실제 프로그램에는 루프와 복잡한 데이터 구조가 포함되어 있기 때문에 이는 매우 간단한 작업이 아닙니다.페어플레이[24] 시스템은 이 문제를 해결하기 위해 고안된 최초의 도구였다.페어플레이는 두 가지 주요 요소로 구성됩니다.첫 번째 컴파일러는 사용자가 간단한 고급 언어로 프로그램을 작성하고 이러한 프로그램을 부울 회로 표현으로 출력할 수 있도록 하는 컴파일러입니다.그런 다음 두 번째 구성요소는 회로를 가글링하고 프로토콜을 실행하여 가글링된 회로를 안전하게 평가할 수 있습니다.페어플레이는 Yao의 프로토콜을 기반으로 한 양 당사자 계산뿐만 아니라 다중 당사자 프로토콜도 수행할 수 있습니다.이는 수동적으로 [24]보호된 야오의 프로토콜을 액티브 케이스로 확장하는 BMR 프로토콜을 사용하여 수행됩니다.

Fairplay의 도입 이후 수년간 야오밍의 기본 프로토콜은 효율성 향상과 능동적 보안 기술의 형태로 많은 개선이 이루어졌습니다.여기에는 XOR 게이트를 훨씬 간단하게 평가할 수 있는 자유 XOR 방법, 2개의 입력으로 왜곡된 테이블의 크기를 [25]25%까지 줄이는 왜곡된 행 감소 등의 기술이 포함됩니다.

지금까지 능동적 보안을 획득하는 데 있어 가장 효과적이라고 생각되는 접근법은 가블링 기술과 "컷 앤 초이스" 패러다임의 조합에서 비롯됩니다.이 조합은 보다 효율적인 구성을 제공하는 것 같습니다.부정직한 동작에 관한 상기 문제를 피하기 위해 동일한 회로의 많은 가블링이 컨스트럭터에서 평가자에게 전송됩니다.그런 다음 약 절반(특정 프로토콜에 따라 다름)이 열려 일관성을 검사합니다. 그렇다면 열려 있지 않은 프로토콜의 대부분이 정확할 가능성이 높습니다.결과는 모든 평가의 다수결입니다.여기서는 대부분의 출력이 필요합니다.출력에 불일치가 있는 경우, 수신자는 송신자가 부정행위를 하고 있는 것을 알고 있습니다만, 그렇지 않으면 입력에 관한 정보가 누설되기 때문에 불평할 수 없습니다.

적극적인 보안을 위한 이 접근은 린델과 핑카스에 [26]의해 시작되었다.이 기술 Pinkas. 2009,[25]에 이, a를 계산하기 위해 약 20분 고급 암호화 표준(AdvancedEncryptionStandard)회로는 매우 복잡한(30,000명의의 및과 XOR게이트로),은 기능(또한 가진 어떤 잠재적인 응용 프로그램)의 최초의 적극적으로 안전한 양자 평가하도록 구현하였다알몬드2- 2의 확률을 얻으려면 160회선이 필요합니다.

많은 회선이 평가되기 때문에 당사자(수신기 포함)는 모든 반복에서 동일한 값이 사용되도록 입력에 전념할 필요가 있습니다.보고된 Pinkas 등의[25] 실험은 프로토콜의 병목 현상이 일관성 검사에 있다는 것을 보여준다.이들은 AES 회선을 평가하기 위해 다양한 값에 대한 약 6,553,600의 커밋을 인터넷을 통해 전송해야 했습니다.최근의[27] 결과에서는 능동적으로 안전한 Yao 기반 구현의 효율성이 더욱 향상되었으며 2- (\ 2의 부정 확률을 위해 필요한 회선 수는 40회선에 불과했습니다.이러한 개선은, 송신 회선상에서 컷 앤 선택을 실시하는 새로운 방법론으로부터 얻을 수 있습니다.

최근에는 코어가 많은 CPU에서 동작하도록 설계된 왜곡된 회로를 기반으로 한 고도의 병렬 구현에 중점을 두고 있습니다.Kreuter [28]등에서는 강력한 클러스터 컴퓨터의 512코어로 실행되는 구현에 대해 설명합니다.이러한 자원을 사용하여 4095비트 편집 거리 함수를 평가할 수 있습니다.이 함수의 회로는 약 60억 게이트로 구성됩니다.이를 달성하기 위해 그들은 Fairplay보다 더 잘 최적화된 커스텀 회로 컴파일러와 파이프라이닝과 같은 몇 가지 새로운 최적화를 개발했습니다. 파이프라이닝에서는 왜곡된 회로의 전송이 나머지 회로가 아직 생성되고 있을 때 시작됩니다.액티브 케이스에서는 512노드 클러스터 머신을 사용하여 AES를 계산하는 데 걸리는 시간이 블록당 1.4초, 노드 1개를 사용하여 115초로 단축되었습니다.Shelat과[29] Shen은 상용 하드웨어를 사용하여 블록당 0.52초로 개선했습니다.이 문서에서는 초당 21블록의 throughput에 대해 보고하고 있지만 블록당 지연 시간은 48초입니다.

한편, 다른 연구자 그룹은 유사한 수준의 병렬화를 달성하기 위해 소비자용 [30]GPU를 사용하는 것을 조사했습니다.OT 확장 및 기타 새로운 기술을 사용하여 GPU 고유의 프로토콜을 설계합니다.이 접근방식은 동일한 수의 코어를 사용하여 클러스터 컴퓨팅 구현과 동등한 효율성을 달성할 수 있습니다.그러나 저자는 약 50,000개의 게이트를 가진 AES 회선의 구현에 대해서만 보고한다.한편, 많은 사람들의 데스크톱 컴퓨터나 게임 콘솔에는 이미 유사한 디바이스가 있을 수 있기 때문에, 여기에 필요한 하드웨어에 훨씬 더 쉽게 접근할 수 있습니다.작성자는 표준 데스크톱에서 표준 GPU를 사용하여 AES 블록당 2.7초의 타이밍을 얻습니다.시큐러티가 비밀 보안과 같은 수준으로 저하되는 것을 허가하면, AES 블록당 0.30초의 실행 시간을 얻을 수 있습니다.패시브 시큐러티 케이스에서는,[31] 2억 5천만 게이트의 회선 처리와 초당 7500만 게이트의 레이트가 보고되고 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Ran Canetti, et al., "Adaptive Secure Multi-party", TOC/CIS 그룹, LCS, MIT(1996), 페이지 1.
  2. ^ A. Shamir, R. Rivest 및 L.Adleman, "Mental Poker", 기술 보고서 LCS/TR-125, Massachusetts Institute of Technology, 1979년 4월.
  3. ^ 앤드류 CYao, 안전한 계산을 위한 프로토콜(확장 추상화)
  4. ^ Andrew Chi-Chih Yao:비밀 생성 방법 및 교환 방법(확장 요약).FOCS 1986: 162-167 [1]
  5. ^ a b Oded Goldreich, Silvio Micali, Avi Wigderson:진정한 다수를 가진 프로토콜에 대한 완전성 정리나 멘탈 게임을 하는 방법.STOC 1987: 218-229 [2]
  6. ^ Zvi Galil, Stuart Haber, Moti Yung: 암호화 계산:보안 폴트 톨러런스 프로토콜 및 공개 키 모델.CRITO 1987: 135-155 [3]
  7. ^ David Chaum, Ivan Damgörd, Jeroen van de Graaf: 각 당사자의 입력 프라이버시와 결과의 정확성을 보장하는 멀티파티 계산. 87-119 [4]
  8. ^ a b 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 Killian:망각 전송에 대한 암호 작성.STOC 1988: 20-31 [5]
  10. ^ D. Chaum, C. Crepeau & I. Damgard. "Multiparty unconditionally secure protocols". Stoc 1988.
  11. ^ Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: 비암호화 폴트 톨러런스 분산 계산의 완전성 이론(확장 추상).STOC 1988: 1~10
  12. ^ Tal Rabin, Michael Ben-Or: 검증 가능한 비밀 공유 및 다당제 프로토콜(확장 추상화)STOC 1989: 73-85 [6]
  13. ^ Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: 완벽한 보안 메시지 전송.J. ACM 40 (1): 17-47(1993)[7]
  14. ^ Rafail Ostrovsky, Moti Yung:모바일 바이러스 공격에 대응하는 방법PODC 1991. 페이지 51-59 [8]
  15. ^ 클라우디오 올란디:멀티파티 계산은 실제로 유효합니까?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).{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)
  17. ^ Moti Yung: Mental Poker에서 핵심 비즈니스로:보안 컴퓨팅 프로토콜을 구현하는 이유와 방법ACM 2015 컴퓨터 및 통신 보안 회의: 1-2 https://dl.acm.org/citation.cfm?doid=2810103.2812701
  18. ^ 마이클 백스, 비르기트 피츠만, 그리고 마이클 웨이드너."안전한 반응 시스템을 위한 일반적인 구성 정리"암호학회의 이론, 페이지 336-354.스프링거, 베를린, 하이델베르크, 2004년
  19. ^ Y. Aumann & Y. Lindell. "Security against covert adversaries". TCC 2007.
  20. ^ 앤드류 C야오, "비밀을 생성하고 교환하는 방법", 제27회 컴퓨터 과학 기초 심포지엄의 제86회 진행, 페이지 162-167, 1986.
  21. ^ Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi (1988-01-01). Completeness theorems for non-cryptographic fault-tolerant distributed computation. ACM. pp. 1–10. doi:10.1145/62212.62213. ISBN 978-0897912648. S2CID 207554159.
  22. ^ I. Damgörd, V. Pastro, N. Smart 및 S. Zakarias, "다소 동형 암호화에 의한 복수 파티 계산", Crypto 2012, vol.스프링거 LNCS 7417, 페이지 643-662, 2012.
  23. ^ Iddo Bentov, Ranjit Kumaresan (2014). "How to Use Bitcoin to Design Fair Protocols" (PDF). Cryptology e Print (129): 1–38. Retrieved 9 October 2014.
  24. ^ a b A. Ben-David, N. N. Nisan, B.핑카스 페어플레이MP: 안전한 멀티파티 컴퓨팅을 위한 시스템," ACM CCS 2008, 페이지 257~266, 2008.
  25. ^ a b c B. Pinkas, T. Schneider, N. Smart 및 S.Williams, "안전한 양 당사자 컴퓨팅이 실용적입니다", Asiacrypt 2009, vol.Springer LNCS 5912, 페이지 250-267, 2009.
  26. ^ Y. 린델과 B.Pinkas, "악의가 있는 적들이 존재하는 상황에서 안전한 양 당사자 계산을 위한 효율적인 프로토콜", Eurocrypt 2007, vol.Springer LNCS 4515, 페이지 52-78, 2007.
  27. ^ Y. Lindell, "악의적이고 은밀한 적을 위한 빠른 컷 앤 초이스 기반 프로토콜", Crypto 2013, vol.스프링거 LNCS 8043, 1-17페이지, 2013.
  28. ^ B. Kreuter, a. shalet 및 C.H. Shen, "악의가 있는 적과 함께 10억 게이트 보안 계산", USENIX 보안 심포지엄 2012, 페이지 285-300, 2012.
  29. ^ A. Shelat과 C.-H. Shen, "최소한의 가정으로 빠른 양 당사자 보안 계산", ACM CCS 2013, 페이지 523–534, 2013.
  30. ^ T. Frederiksen 및 J. Nielsen, "GPU를 사용하여 빠르고 악의적으로 양 당사자 컴퓨팅을 보호합니다." "ACNS 2013, vol.Springer LNCS 7954, 339-356페이지, 2013.
  31. ^ Y. Huang, J. Katz, D.Evans, "대칭 컷 앤 초이스(cut-and-choose)", CRITO, vol.Springer LNCS 8043, 18-35페이지, 2013.

외부 링크

  • 백만장자 문제에 대한 간단한 설명
  • 복수 정당 계산에 관한 Helger Lipma의 링크
  • Nick Szabo, Wayback Machine의 "The God Protocols" (2006년 12월 30일 아카이브 완료)
  • EMP 툴킷 - 효율적인 멀티파티 계산 툴킷.기본적인 MPC 프리미티브 구현과 준정직 보안 및 악의적인 보안 프로토콜 구현이 포함됩니다.
  • 시큐어 분산 CSP(DisCSP) 솔버:애플릿 인터프리터를 갖춘 웹 애플리케이션으로, SMC 선언 언어에 근거해, 독자적인 시큐어 멀티 파티 계산을 설계 및 실행합니다.안전한 산술회로 평가 및 믹스넷을 사용합니다.
  • VMCrypt 확장 가능한 안전한 계산을 위한 Java 라이브러리.Lior Malka에 의해.
  • 페어플레이 프로젝트 - 함수가 높은 수준의 함수 기술 언어를 사용하여 정의되고 부울 회로의 안전한 평가를 위해 야오 프로토콜을 사용하여 평가되는 안전한 양자 계산을 위한 소프트웨어 패키지를 포함합니다.
  • SIMAP 프로젝트; SIMAP(Secure Information Management and Processing)는 덴마크 국립 연구 기관이 후원하는 프로젝트로서 시큐어 멀티 파티 계산 구현을 목표로 하고 있습니다.
  • 시큐어 멀티 파티 계산 언어 - '시큐어 멀티 파티 계산을 위한 도메인 고유의 프로그래밍 언어' 및 관련 암호화 실행 시간 개발을 위한 프로젝트입니다.
  • VIFF: Virtual Ideal Functionality Framework - 비동기 멀티파티 컴퓨팅용 프레임워크(LGPL에서 사용 가능한 코드).안전한 비교를 포함한 비밀 공유 값을 사용한 산술을 제공합니다.
  • MPyC: Python(및 Jupyter 노트북) - 맞춤형 Python 코루틴을 사용한 MPC용 오픈 소스 패키지.ID3 의사결정 트리, 리니어 프로그래밍, CNN/MLP 뉴럴 네트워크, AES, 단방향 해시 체인 등 고도의 애플리케이션을 지원합니다.2018년 5월 출시.
  • SCOLE-MAMBA MPC: LEUven의 안전한 계산 알고리즘 - SPDZ 패밀리를 포함한 다양한 MPC 프로토콜용 프레임워크(BSD에서 사용 가능한 코드).고정 소수점 및 부동 소수점 산술에 대한 보안 비교 및 지원을 포함하여 비밀 공유 값을 사용한 산술을 제공합니다.
  • 공유 마인드: 프라이버시를 침해하지 않고 기밀 데이터를 분석 - 프라이버시 보호 조작을 실행할 수 있는 분산 가상 머신.데이터 마이닝 도구용 개인 정보 보호 프로그래밍 언어를 사용합니다.개발자 도구 포함.
  • MPCLib: Multi-Party Computation Library - C# 및 C++로 작성된 라이브러리. 시큐어 멀티 파티 계산 프로토콜을 구현하기 위해 필요한 여러 구성 요소를 구현합니다.MPCLib에는 가상 네트워크에서 MPC 프로토콜을 시뮬레이션하는 데 사용할 수 있는 이산 이벤트 시뮬레이션 엔진이 있습니다.
  • SMC의 가상 파티 SMC의 가상 파티 프로토콜(Secure Multi Party Computation)
  • MPC Java 기반 구현 Michael 기반 MPC 프로토콜의 Java 기반 구현입니다.B, 샤피.G와 Avi.Welch-Berlekamp 에러 코드를 BCH 코드로 수정하는 W의 정리("비암호화 폴트 톨러런스 분산 계산에 대한 완전성 정리")여러 플레이어와 비잔틴 프로토콜을 사용한 "치터" 식별을 지원합니다.Erez Alon, Doron Friedland, Yael Smith가 작성했습니다.
  • SEPIA 비밀 공유를 사용하는 SMC용 Java 라이브러리.기본 동작은 다수의 병렬 호출에 최적화되어 있습니다(LGPL에서 사용 가능한 코드).
  • SMC on GitHub 소개
  • Myst Project - 안전한 멀티파티 키 생성, 서명 및 복호화를 구현하는 JavaCard 애플릿.
  • 주요 참고 문헌 보안 멀티파티 계산