비밀 공유를 사용한 SPDZ 및 산술 MPC

불리언 MPC는 비트(XOR/AND)에서 동작합니다. 산술 MPC는 정수나 필드 원소에서 동작하며 덧셈과 곱셈을 직접 지원합니다. 기계 학습과 통계 애플리케이션에 더 적합합니다.

값 x ∈ Z_p는 x = x_1 + x_2 + ... + x_n mod p로 분할됩니다. 분할된 값의 덧셈은 공짜입니다. 각 참여자가 자신의 분할을 로컬에서 더하면 되므로 통신이 필요하지 않습니다.

분할 [a]와 [b]를 곱하기 위해 참여자들은 Beaver 트리플([a_t], [b_t], [c_t])을 미리 분배받습니다. 여기서 c_t = a_t·b_t입니다. 온라인 곱셈에는 한 번의 통신 라운드만 필요합니다.

SPDZ(Damgård 외, 2012) = "부분 동형 암호 기반 분산 영지식"입니다. 오프라인 단계에서는 SHE를 통해 인증된 트리플을 생성합니다. 온라인 단계에서는 덧셈 비밀 분할 평가를 빠르게 수행합니다.

각 분할에는 MAC이 함께 제공됩니다. MAC(x_i) = α·x mod p이며, α는 전역 비밀 키입니다. 이를 통해 악의적인 참여자가 들키지 않고 자신의 분할을 변조하는 것을 막습니다.

SPDZ의 오프라인 단계에서는 준동형 암호(BGV/BFV)를 사용합니다. 참여자들은 자신의 분할을 준동형적으로 곱하여 인증된 Beaver 트리플을 생성합니다. 이 단계는 계산량이 많지만 병렬화할 수 있습니다.

트리플 ([a],[b],[c])와 입력 [x],[y]가 주어졌다고 합시다. d=x-a와 e=y-b를 공개합니다(마스킹되어 있으므로 정보가 누설되지 않습니다). 그러면 [x·y] = [c] + d·[b] + e·[a] + d·e입니다. 통신은 한 라운드만 필요합니다.

MASCOT은 SHE 오프라인 단계를 OT 확장으로 대체하여 작은 필드에서 더 빠르게 트리플을 생성합니다. 2자간 SPDZ에서 선호되는 오프라인 방식입니다.

여러 병원이 기록을 공유하지 않고 환자의 평균 연령을 계산합니다. 각 병원은 자신의 데이터를 산술 분할로 인코딩합니다. SPDZ는 합계와 개수를 평가하며, 참여자들은 비율만 알게 됩니다.

SPDZ-2k(Cramer 외, 2018)는 기계 학습에 적합한 고정소수점 산술을 위해 Z_{2^k}로 확장됩니다. MP-SPDZ 라이브러리는 2명의 참여자가 LAN에서 초당 100만 회의 곱셈을 수행하는 성능을 보입니다.

산술 MPC에서 Beaver 곱셈 트리플의 목적은 무엇입니까?

산술 MPC는 Z_p에서 덧셈 분할을 사용합니다. 덧셈은 공짜이고, 곱셈은 한 라운드에서 Beaver 트리플을 사용하여 수행합니다. SPDZ는 악의적 보안을 위해 MAC을 추가합니다. MASCOT은 빠른 트리플 생성을 위해 OT를 사용합니다. MP-SPDZ는 이러한 기법을 실제 환경에서 사용할 수 있게 합니다.