Protocolo GMW e transferência oblivious

O protocolo Goldreich-Micali-Wigderson (GMW) avalia circuitos booleanos usando compartilhamentos secretos por XOR. O valor de cada fio é dividido entre todos os participantes, que interagem porta por porta.

O participante i detém a parte s_i tal que s_1 ⊕ s_2 ⊕ ... ⊕ s_n = w (o valor verdadeiro do fio). As portas XOR não exigem comunicação: cada participante aplica XOR localmente às suas partes.

Para uma porta AND nos fios a,b: o cálculo de (a_1⊕a_2)(b_1⊕b_2) se expande em termos cruzados. Avaliar o termo cruzado a_i·b_j entre participantes i≠j exige Transferência Oblívia.

Em uma OT de 1 entre 2, o emissor possui as mensagens (m_0, m_1), e o receptor possui o bit de escolha c. O receptor recebe m_c; o emissor não descobre nada sobre c; o receptor não descobre nada sobre m_{1-c}.

Baseado em Diffie-Hellman: o receptor gera duas chaves públicas de modo que conhece o logaritmo discreto de apenas uma delas. O emissor cifra cada mensagem usando uma das chaves. O receptor decifra apenas o texto cifrado que escolheu.

Ishai et al. (2003): a partir de k OTs básicos, gere m >> k OTs usando apenas operações com chaves simétricas. A extensão IKNP reduz o custo da OT para aproximadamente 3 chamadas AES por OT após uma configuração única.

Cada porta AND precisa de uma OT por par de participantes. Com a extensão de OT, pré-calcular todas as OTs durante a fase de preparação permite que a fase de execução consista em uma única troca de XOR por porta.

O GMW semimalicioso pode se tornar seguro contra participantes maliciosos usando provas de conhecimento zero ou OT de corte e escolha. O custo aumenta de 3 a 8 vezes, mas há garantia de segurança contra participantes que trapaceiam.

MASCOT (Keller et al.) estende a OT para produzir triplas AND autenticadas no modelo malicioso, possibilitando o protocolo SPDZ — abordado na próxima lição.

EMP-toolkit e MOTION implementam GMW com extensão de OT. Elas alcançam milhões de portas AND por segundo entre dois participantes em uma LAN, tornando viáveis aplicações reais.

Por que as portas XOR do protocolo GMW não exigem comunicação entre os participantes?

GMW usa compartilhamentos secretos por XOR em circuitos booleanos. As portas XOR não têm custo de comunicação; as portas AND precisam de OT. A extensão de OT torna a OT econômica. A segurança contra participantes maliciosos acrescenta provas de conhecimento zero ou corte e escolha. Bibliotecas como EMP alcançam uma vazão prática para aplicações reais.