Protocollo GMW e oblivious transfer

Il protocollo Goldreich-Micali-Wigderson (GMW) valuta i circuiti booleani usando condivisioni di segreti basate su XOR. Il valore di ogni filo viene suddiviso tra tutti i partecipanti, che interagiscono porta per porta.

Il partecipante i possiede la condivisione s_i tale che s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w, cioè il vero valore del filo. Le porte XOR sono gratuite: ogni partecipante applica localmente XOR alle proprie condivisioni.

Per una porta AND sui fili a,b, il calcolo di (a_1⊕a_2)(b_1⊕b_2) si espande in termini incrociati. La valutazione del termine incrociato a_i·b_j tra partecipanti i≠j richiede Oblivious Transfer.

In un OT 1-su-2, il mittente possiede i messaggi (m_0, m_1), mentre il destinatario possiede il bit di scelta c. Il destinatario riceve m_c; il mittente non apprende nulla su c e il destinatario non apprende nulla su m_{1-c}.

Basato su Diffie-Hellman: il destinatario genera due chiavi pubbliche, ma conosce il logaritmo discreto di una sola. Il mittente cifra ciascun messaggio con una chiave. Il destinatario decifra soltanto il testo cifrato scelto.

Ishai et al. (2003): a partire da k OT di base, si generano m >> k OT usando soltanto operazioni con chiavi simmetriche. L'estensione IKNP riduce il costo dell'OT a circa 3 chiamate ad AES per OT dopo una configurazione iniziale eseguita una sola volta.

Ogni porta AND richiede un OT per ogni coppia di partecipanti. Con l'estensione OT, precalcolare tutti gli OT in una fase offline consente alla fase online di limitarsi a un singolo scambio XOR per porta.

GMW semi-onesto può essere reso sicuro contro i partecipanti malevoli usando prove a conoscenza zero o OT cut-and-choose. Il costo aumenta di 3-8×, ma vengono garantite la sicurezza contro i partecipanti che tentano di barare.

MASCOT (Keller et al.) estende OT per produrre triple AND autenticate nel modello malevolo, abilitando il protocollo SPDZ, trattato nella lezione successiva.

EMP-toolkit e MOTION implementano GMW con l'estensione OT. Raggiungono milioni di porte AND al secondo tra due partecipanti su una LAN, rendendo praticabili applicazioni reali.

Perché le porte XOR nel protocollo GMW non richiedono comunicazione tra i partecipanti?

GMW usa condivisioni di segreti tramite XOR sui circuiti booleani. Le porte XOR sono gratuite, mentre le porte AND richiedono OT. L'estensione OT rende l'OT economico. La sicurezza contro i partecipanti malevoli aggiunge prove a conoscenza zero o cut-and-choose. Librerie come EMP raggiungono prestazioni pratiche per applicazioni reali.