GMW 프로토콜과 망각 전송

Goldreich-Micali-Wigderson(GMW) 프로토콜은 XOR 비밀 분할을 사용하여 불리언 회로를 평가합니다. 각 와이어 값은 모든 참여자에게 분할되며, 참여자들은 게이트별로 상호작용합니다.

참여자 i는 s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w(실제 와이어 값)가 되도록 분할 s_i를 보유합니다. XOR 게이트는 공짜입니다. 각 참여자가 자신의 분할을 로컬에서 XOR하면 됩니다.

와이어 a,b에 대한 AND 게이트의 경우 (a_1⊕a_2)(b_1⊕b_2)를 계산하면 교차항으로 전개됩니다. 참여자 i≠j 사이의 교차항 a_i·b_j을 평가하려면 OT가 필요합니다.

1-out-of-2 OT에서 송신자는 메시지 (m_0, m_1)를 보유하고 수신자는 선택 비트 c를 보유합니다. 수신자는 m_c를 얻고, 송신자는 c에 대해 아무것도 알 수 없으며, 수신자는 m_{1-c}에 대해 아무것도 알 수 없습니다.

디피-헬먼을 기반으로 합니다. 수신자는 두 개의 공개 키를 생성하며, 그중 하나의 이산 로그만 알고 있습니다. 송신자는 각 메시지를 하나의 키로 암호화합니다. 수신자는 자신이 선택한 암호문만 복호화합니다.

Ishai 외(2003)는 k개의 기본 OT로부터 대칭 키 연산만 사용하여 k보다 훨씬 큰 m개의 OT를 생성하는 방법을 제안했습니다. IKNP 확장을 사용하면 일회성 설정 후 OT당 약 3회의 고급 암호화 표준 호출만으로 OT 비용을 줄일 수 있습니다.

각 AND 게이트에는 참여자 쌍마다 하나의 OT가 필요합니다. OT 확장을 사용하면 오프라인 단계에서 모든 OT를 미리 계산할 수 있으므로 온라인 단계에서는 게이트마다 한 번의 XOR 교환만 수행하면 됩니다.

반정직한 GMW는 영지식 증명이나 선택 및 공개 OT를 사용하여 악의적 공격자에 대해서도 안전하도록 만들 수 있습니다. 비용은 3~8배 증가하지만 부정행위를 하는 참여자에 대한 보안을 보장합니다.

MASCOT(Keller 외)는 OT를 확장하여 악의적 모델에서 인증된 AND 트리플을 생성하고, 이를 통해 SPDZ 프로토콜을 사용할 수 있게 합니다. SPDZ는 다음 수업에서 다룹니다.

EMP 도구 모음과 MOTION은 OT 확장을 사용하여 GMW를 구현합니다. 두 참여자 사이의 LAN에서 초당 수백만 개의 AND 게이트를 처리할 수 있어 실제 애플리케이션을 구현할 수 있습니다.

GMW 프로토콜에서 XOR 게이트가 참여자 간 통신을 필요로 하지 않는 이유는 무엇입니까?

GMW는 불리언 회로에서 XOR 비밀 분할을 사용합니다. XOR 게이트는 공짜이고 AND 게이트에는 OT가 필요합니다. OT 확장은 OT를 저렴하게 만듭니다. 악의적 보안을 위해 영지식 증명이나 선택 및 공개를 추가합니다. EMP와 같은 라이브러리는 실제 애플리케이션에 필요한 실용적인 처리량을 제공합니다.