Problem MPC i ukryte obwody Yao

MPC umożliwia n uczestnikom, z których każdy posiada prywatne dane wejściowe x_i, wspólne obliczenie f(x_1,...,x_n) bez ujawniania sobie nawzajem tych danych — tak, jakby obliczenia wykonywała zaufana strona trzecia.

Problem milionerów Yao z 1982 roku: Alice i Bob chcą ustalić, kto jest bogatszy, nie ujawniając swojego majątku. Nie korzystają przy tym z zaufanej strony trzeciej. MPC rozwiązuje ten problem z gwarancjami kryptograficznymi.

1. Prywatność: uczestnicy poznają tylko wynik oraz informacje, które mogą z niego wywnioskować. 2. Poprawność: wynik jest prawidłowy, nawet jeśli niektórzy uczestnicy są skorumpowani. 3. Istnieją warianty dla przeciwników półuczciwych i złośliwych.

Każdą funkcję można wyrazić jako obwód boolowski (bramki AND, XOR, NOT). Protokoły MPC często działają na poziomie obwodu, bezpiecznie obliczając wartość każdej bramki.

Alice (garbler) przypisuje każdemu przewodowi dwie losowe etykiety: jedną dla wartości 0 i jedną dla wartości 1. Szyfruje tabelę prawdy każdej bramki za pomocą etykiet przewodów wejściowych. Bob (evaluator) poznaje wyłącznie etykiety odpowiadające jego danym wejściowym dzięki Oblivious Transfer.

Bob otrzymuje garblowane tabele (4 szyfrogramy na bramkę AND). Odszyfrowuje dokładnie jeden wiersz za pomocą swoich etykiet wejściowych i otrzymuje etykietę wyjściową — nie wiedząc, czy reprezentuje ona 0, czy 1.

Do każdej etykiety dołącz losowy „bit wyboru”. Bob używa bitów wyboru, aby znaleźć właściwy wiersz garblowanej tabeli w czasie O(1), zamiast próbować wszystkich czterech odszyfrowań. Zmniejsza to koszt obliczeń 4×.

Kolesnikov i Schneider (2008): wybierz globalne przesunięcie Δ. Następnie dla każdego przewodu zachodzi label_1 = label_0 ⊕ Δ. Bramki XOR stają się bezpłatne (nie wymagają szyfrowania), co pozwala zaoszczędzić około 30% przepustowości.

Zahur i in. (2015): każda bramka AND wymaga tylko 2 szyfrogramów (wcześniej 4). W połączeniu z Free-XOR rozwiązanie to zmniejsza o połowę przepustowość standardowych obwodów garblowanych.

Klasyczne obwody garblowane są przeznaczone dla 2 stron. Rozszerzenia wielostronne (np. protokół BMR) równoleglą garblowanie między wszystkimi uczestnikami, ale wymagają komunikacji O(n²). Są praktyczne dla małej liczby n.

W protokole obwodu garblowanego Yao, jak Bob uzyskuje etykiety przewodów odpowiadające jego prywatnym bitom wejściowym?

MPC umożliwia uczestnikom wspólne obliczenia bez ujawniania danych wejściowych. Obwody garblowane kodują funkcje boolowskie jako zaszyfrowane tabele prawdy. Optymalizacje (Free-XOR, Half-Gates, Point-and-Permute) sprawiają, że rozwiązanie jest praktyczne. OT dostarcza Bobowi prywatnie etykiety jego danych wejściowych.