MPC 문제와 Yao의 왜곡 회로

MPC는 각자 비밀 입력 x_i를 보유한 n명의 참여자가 서로의 입력을 공개하지 않고 함께 f(x_1,...,x_n)을 계산할 수 있게 합니다. 마치 신뢰할 수 있는 제3자가 계산한 것과 같습니다.

Yao가 1982년에 제시한 백만장자 문제에서 Alice와 Bob은 재산을 공개하지 않고 누가 더 부자인지 알고 싶어 합니다. 신뢰할 수 있는 제3자는 없습니다. MPC는 암호학적 보장을 통해 이 문제를 해결합니다.

1. 기밀성: 참여자는 출력과 그 출력에서 추론할 수 있는 내용만 알아야 합니다. 2. 정확성: 일부 참여자가 부정하게 행동하더라도 출력은 정확해야 합니다. 3. 반정직한 공격자와 악의적인 공격자를 구분하는 여러 변형이 존재합니다.

모든 함수는 불리언 회로(AND, XOR, NOT 게이트)로 표현할 수 있습니다. MPC 프로토콜은 흔히 회로 수준에서 동작하며 각 게이트를 안전하게 평가합니다.

Alice(회로 작성자)는 각 와이어에 두 개의 무작위 레이블을 할당합니다. 하나는 0용이고 다른 하나는 1용입니다. Alice는 입력 와이어 레이블을 키로 사용하여 각 게이트의 진리표를 암호화합니다. Bob(평가자)은 OT를 통해 자신의 입력에 해당하는 레이블만 알아냅니다.

Bob은 난독화된 테이블(AND 게이트당 암호화 4개)을 받습니다. Bob은 자신의 입력 레이블을 사용하여 정확히 한 행을 복호화하고 출력 레이블을 얻습니다. 이 레이블이 0을 나타내는지 1을 나타내는지는 알 수 없습니다.

각 레이블에 무작위 선택 비트를 붙입니다. Bob은 선택 비트를 사용하여 네 개의 복호화를 모두 시도하는 대신 O(1)에 올바른 난독화 행을 찾습니다. 계산량이 4배 줄어듭니다.

Kolesnikov와 Schneider(2008)는 전역 오프셋 Δ를 선택하는 방법을 제안했습니다. 그러면 모든 와이어에 대해 label_1 = label_0 ⊕ Δ가 됩니다. XOR 게이트에는 암호화가 필요 없으므로 공짜가 되며, 대역폭을 약 30% 절약합니다.

Zahur 외(2015)의 방식에서는 각 AND 게이트에 암호문 2개만 필요합니다(기존 4개에서 감소). 자유 XOR과 결합하면 표준 난독화 회로의 대역폭이 절반으로 줄어듭니다.

고전적인 난독화 회로는 2자간 방식입니다. 다자간 확장 방식(예: BMR 프로토콜)은 모든 참여자가 난독화를 병렬로 수행하지만 O(n²)의 통신이 필요합니다. 작은 n에 실용적입니다.

Yao의 난독화 회로 프로토콜에서 Bob은 자신의 비밀 입력 비트에 해당하는 와이어 레이블을 어떻게 얻습니까?

MPC를 사용하면 참여자들이 입력을 공개하지 않고 함께 계산할 수 있습니다. 난독화 회로는 불리언 함수를 암호화된 진리표로 표현합니다. 최적화 기법(자유 XOR, 하프 게이트, 포인트 앤 퍼뮤트)을 사용하면 이를 실용적으로 구현할 수 있습니다. OT는 Bob의 입력 레이블을 비밀리에 전달합니다.