MPC 애플리케이션: 비공개 집합 교집합 및 머신러닝

MPC는 이론을 실제로 전환합니다. 비공개 집합 교집합(PSI)과 개인정보 보호 기계 학습은 오늘날 산업 현장에서 가장 널리 배포된 MPC 애플리케이션에 속합니다.

PSI에서 Alice는 집합 A를, Bob은 집합 B를 보유합니다. 두 사람은 A\B나 B\A의 원소를 서로 알지 못한 채 A∩B를 계산합니다. Google과 Apple의 접촉자 추적, 광고 사기 탐지, 위협 정보 공유 등에 사용됩니다.

두 집합을 해시한 뒤 비교하는 방식은 집합이 작을 때 안전하지 않습니다. 공격자가 모든 원소를 시도할 수 있기 때문입니다. 안전한 PSI에서는 교집합의 크기조차 숨겨야 하며, 또는 교집합만 공개해야 합니다.

망각 PRF(OPRF)를 사용하면 Bob은 Alice의 원소를 알지 못한 채 해당 원소에 PRF를 적용합니다. Alice는 각 x∈A에 대해 PRF(k, x)를 얻습니다. 그런 다음 Bob이 y∈B에 대해 미리 계산한 PRF(k, y)와 비교합니다.

회로 PSI는 MPC 회로 내부에서 교집합을 계산하므로, 어떤 항목들이 교집합에 포함되는지 공개하지 않고도 교집합의 원소에 대해 추가 계산(예: 구매 금액 합산)을 수행할 수 있습니다.

PPML은 여러 당사자의 데이터를 사용해 학습하거나 추론을 실행합니다. 연합 학습은 데이터를 로컬에 유지하고, MPC는 한 단계 더 나아가 the 모델이나 집계된 그래디언트조차 비밀 공유합니다.

Google의 2017년 안전한 집계 프로토콜에서는 각 client가 자신의 그래디언트 업데이트를 비밀 공유합니다. 서버는 합계만 재구성합니다. 개별 업데이트는 서버를 포함한 누구에게도 노출되지 않습니다.

CrypTen(Facebook/Meta)과 MOTION은 비밀 공유된 입력에서 PyTorch 방식의 신경망을 실행할 수 있도록 지원합니다. 선형 계층은 비용이 낮지만, 비선형성(ReLU)을 처리하려면 불리언 표현과 산술 표현 간 변환이 필요합니다.

ReLU(x) = max(0,x)는 x와 0을 비교해야 하므로 비선형적이고 비산술적인 연산입니다. 이는 가블드 회로나 비트 분해를 사용해 수행하며, PPML에서 the 가장 큰 비용을 차지합니다.

애플의 Private Relay는 PSI를 사용합니다. 메타는 비공개 광고 측정에 MPC를 사용합니다. IETF PRIO 프로토콜(파이어폭스 텔레메트리에서 사용)은 비밀 공유된 집계 통계를 사용합니다.

OPRF 기반 PSI에서는 어느 당사자가 PRF key를 보유하며, 다른 당사자는 무엇을 알게 됩니까?

PSI를 사용하면 당사자들이 OPRF를 통해 집합의 교집합을 비공개로 계산할 수 있습니다. 회로 PSI를 사용하면 교집합 데이터에 대해 추가 계산을 수행할 수 있습니다. PPML은 연합 학습 집계와 암호화된 입력에 대한 모델 추론에 MPC를 사용합니다. ReLU는 the PPML 비용에서 가장 큰 병목입니다.