다자간 보안 컴퓨팅
보안 정의

다자간 계산 프로토콜이 효과적이려면 안전해야 한다. 현대 암호화에서 프로토콜의 보안은 보안 증명과 관련이 있다. 보안 증명은 프로토콜의 보안이 기본 기본 요소의 보안으로 축소되는 수학적 증명이다. 그럼에도 불구하고 당사자의 지식과 프로토콜 정확성을 기반으로 암호화 프로토콜 보안 검증을 공식화하는 것이 항상 가능한 것은 아니다. MPC 프로토콜의 경우 프로토콜이 작동하는 환경은 현실 세계/이상 세계 패러다임과 연관된다. 당사자는 작업의 출력을 배워야 하고 출력은 입력에 따라 달라지므로 아무것도 배우지 않는다고 말할 수 없다. 또한 출력의 정확성은 당사자의 입력에 따라 달라지며 입력이 올바른 것으로 가정해야 하기 때문에 출력의 정확성이 보장되지 않는다.
현실 세계/이상 세계 패러다임은 두 가지 세계를 명시한다. (i) 이상 세계 모델에는 각 프로토콜 참가자가 입력을 보내는 부패할 수 없는 신뢰할 수 있는 당사자가 존재한다. 이 신뢰할 수 있는 당사자는 자체적으로 함수를 계산하고 적절한 출력을 각 당사자에게 다시 보낸다. (ii) 반면, 실제 모델에서는 신뢰할 수 있는 당사자가 없으며 당사자가 할 수 있는 일은 서로 메시지를 교환하는 것뿐이다. 이상적인 세계에서 배울 수 있는 것보다 현실 세계에서 각 당사자의 개인적인 입력에 대해 더 이상 배울 수 없는 경우 프로토콜이 안전하다고 한다. 이상적인 세계에서는 당사자 간에 메시지가 교환되지 않으므로 현실 세계에서 교환된 메시지는 어떠한 비밀 정보도 드러낼 수 없다.
현실 세계/이상 세계 패러다임은 MPC 프로토콜의 핵심이 실제로 이상적인 실행이라는 가정하에 애플리케이션을 구축할 수 있도록 MPC의 복잡성에 대한 간단한 추상화를 제공한다. 이상적인 경우에 애플리케이션이 안전하다면 실제 프로토콜이 대신 실행될 때도 안전한다.
MPC 프로토콜의 보안 요구 사항은 엄격한다. 그럼에도 불구하고 1987년에는 악의적인 적에 대한 보안을 통해 모든 기능을 안전하게 계산할 수 있다는 것이 입증되었으며 앞서 언급한 기타 초기 작업이 수행되었다. 이러한 연구 결과에도 불구하고 MPC는 당시 실제로 사용할 수 있을 만큼 효율적으로 설계되지 않았다. 무조건적으로 또는 정보 이론적으로 안전한 MPC는 비밀 공유 문제, 특히 많은 보안 MPC 프로토콜이 활동 중인 공격자에 대해 사용하는 검증 가능한 비밀 공유 (VSS) 문제를 기반으로 하며 밀접하게 관련되어 있다.
암호화나 서명과 같은 전통적인 암호화 애플리케이션과 달리 MPC 프로토콜의 공격자는 시스템에 참여하는(또는 내부 당사자를 제어하는) 플레이어 중 하나라고 가정해야 한다. 해당 부패한 당사자는 프로토콜의 보안을 위반하기 위해 공모할 수 있다. 프로토콜의 당사자 수를  n , 적대적일 수 있는 당사자의 수를  t로 정의하겠다. 프로토콜 및 솔루션은  t<n/2 (즉, 정직한 다수가 가정되는 경우)와 그러한 가정이 이루어지지 않는 경우에 다르게 정리된다. 후자의 경우에는 2PC(Two-party computation)에서 중요한 문제인 참가자 중 한 사람이 타락할 수 있는 경우를 포함한다. 그리고, 무제한의 참가자가 타락하고 공모하여 정직한 참가자를 공격하는 일반적인 경우가 포함된다.
다양한 프로토콜에 직면한 공격자는 프로토콜에서 얼마나 벗어나려는 의지에 따라 분류될 수 있다. 본질적으로 두 가지 유형의 공격자가 있으며, 각각은 서로 다른 형태의 보안을 제공한다(그리고 각각은 서로 다른 실제 시나리오에 적합하다).
반정직(수동) 보안: 이 경우 손상된 당사자는 단지 프로토콜에서 정보를 수집하기 위해 협력할 뿐 프로토콜 사양에서 벗어나지 않는다고 가정한다. 이는 실제 상황에서 보안이 취약한 순진한 공격 모델이다. 그러나 이 수준의 보안을 달성하는 프로토콜은 (협력하는 경우라면) 당사자 간의 우발적인 정보 유출을 방지하므로 이것이 유일한 관심사인 경우 유용한다. 또한 반정직 모델의 프로토콜은 매우 효율적이며 더 높은 수준의 보안을 달성하기 위한 중요한 첫 번째 단계인 경우가 많다.
악성(능동) 보안: 이 경우 공격자는 부정 행위를 시도하기 위해 프로토콜 실행에서 임의로 벗어날 수 있다. 이 모델에서 보안을 달성하는 프로토콜은 매우 높은 보안 보장을 제공한다. 잘못된 행동을 하는 다수의 당사자의 경우: 부정직한 다수의 경우 공격자가 할 수 있는 유일한 일은 부정 행위를 감지한 정직한 당사자가 "중단"하도록 만드는 것이다. 정직한 당사자가 결과를 얻으면 그것이 정확하다는 것이 보장된다. 그들의 개인정보는 항상 보호된다.
활동적인 공격자에 대한 보안은 일반적으로 효율성 감소로 이어진다. 비밀 보안(covert secrity)는 보안 정의를 약화시키는 대신 더 큰 효율성을 허용하는 것을 목표로 하는 대안이다. 이는 적들이 잡히지 않은 경우에만 적극적으로 속이려고 하는 상황에 적용할 수 있다. 예를 들어, 그들의 평판이 손상되어 향후 다른 정직한 당사자와의 협력이 방해받을 수 있다. 따라서 은밀하게 보안되는 프로토콜은 일부 당사자가 지침을 따르지 않을 경우 75% 또는 90%라는 높은 확률로 발견될 수 있도록 보장하는 메커니즘을 제공한다. 어떤 면에서, 은밀한 공격자는 외부의 비암호화(예: 비즈니스) 문제로 인해 수동적으로 행동할 수밖에 없는 적극적인 공격자이다. 이 메커니즘은 실제로 충분히 효율적이고 안전한 프로토콜을 찾기 위해 두 모델 사이에 가교를 설정한다.
많은 암호화 프로토콜 과 마찬가지로 MPC 프로토콜의 보안은 다양한 가정에 의존할 수 있다.
이는 계산적일 수도 있고(즉, 인수분해와 같은 일부 수학적 문제 기반) 무조건적일 수도 있다. 즉, 채널에서 메시지를 물리적으로 사용할 수 없는 것에 의존한다(일반적으로 임의적으로 작게 만들 수 있는 일부 오류 확률이 있음).
모델은 참가자가 "틱"에 전송된 메시지가 항상 다음 "틱"에 도착하는 동기화된 네트워크를 사용하거나 안전하고 신뢰할 수 있는 브로드캐스트 채널이 존재하거나 모든 쌍 사이에 보안 통신 채널이 존재한다고 가정할 수 있다. 적이 채널 등에서 메시지를 읽거나, 수정하거나 생성할 수 없는 참가자.
계산 작업을 실행할 수 있는 정직한 당사자 집합은 액세스 구조 개념과 관련이 있다. 공격 구조는 적이 다자간 계산을 시작하기 전에 희생자를 선택하는 정적 구조일 수도 있고, 다자간 계산을 실행하는 동안 희생자를 선택하여 방어를 더욱 어렵게 만드는 동적 구조일 수도 있다. 적대적 구조는 임계 구조 또는 더 복잡한 구조로 정의될 수 있다. 임계값 구조에서 공격자는 특정 임계값까지 여러 참가자의 메모리를 손상시키거나 읽을 수 있다. 한편, 복잡한 구조에서는 미리 정의된 참가자의 특정 하위 집합에 영향을 미쳐 다양한 공모 가능성을 모델링할 수 있다.