Problema MPC e circuiti cifrati di Yao

MPC consente a n partecipanti, ciascuno in possesso dell'input privato x_i, di calcolare congiuntamente f(x_1,...,x_n) senza rivelarsi reciprocamente i propri input, come se il calcolo fosse eseguito da una terza parte fidata.

Il problema dei milionari di Yao del 1982: Alice e Bob vogliono sapere chi è più ricco senza rivelare la propria ricchezza. Non esiste alcuna terza parte fidata. MPC risolve il problema con garanzie crittografiche.

1. Riservatezza: i partecipanti apprendono solo l'output e ciò che possono dedurne. 2. Correttezza: l'output è corretto anche se alcuni partecipanti sono compromessi. 3. Esistono varianti per avversari semi-onesti e malevoli.

Qualsiasi funzione può essere espressa come circuito booleano, composto da porte AND, XOR e NOT. I protocolli MPC operano spesso a livello di circuito, valutando ogni porta in modo sicuro.

Alice (garbler) assegna due etichette casuali a ciascun filo: una per 0 e una per 1. Cifra la tabella della verità di ogni porta usando le etichette dei fili di ingresso. Bob (evaluator) apprende le etichette dei propri input tramite Oblivious Transfer.

Bob riceve tabelle garbled, con 4 cifrature per ogni porta AND. Decifra esattamente una riga usando le etichette dei propri input e ottiene l'etichetta di output, senza sapere se rappresenta 0 o 1.

Si associ un "select bit" casuale a ogni etichetta. Bob usa i select bit per trovare la riga garbled corretta in O(1), invece di provare tutte e quattro le decifrature. Il calcolo si riduce di 4×.

Kolesnikov e Schneider (2008): si scelga un offset globale Δ. Quindi, per ogni filo, label_1 = label_0 ⊕ Δ. Le porte XOR diventano gratuite, perché non richiedono cifratura, con un risparmio di circa il 30% sulla larghezza di banda.

Zahur et al. (2015): ogni porta AND richiede soltanto 2 testi cifrati, invece di 4. In combinazione con Free-XOR, questa tecnica dimezza la larghezza di banda dei circuiti garbled standard.

I circuiti garbled classici coinvolgono 2 partecipanti. Le estensioni multipartitiche, ad esempio il protocollo BMR, parallelizzano il garbling tra tutti i partecipanti, ma richiedono una comunicazione O(n²). Sono pratiche per valori piccoli di n.

Nel protocollo del circuito garbled di Yao, come ottiene Bob le etichette dei fili corrispondenti ai bit del proprio input privato?

MPC consente ai partecipanti di calcolare congiuntamente senza rivelare gli input. I circuiti garbled codificano le funzioni booleane come tabelle della verità cifrate. Le ottimizzazioni (Free-XOR, Half-Gates, Point-and-Permute) li rendono pratici. OT fornisce privatamente a Bob le etichette dei suoi input.