Problema de MPC e circuitos embaralhados de Yao

MPC permite que n participantes, cada um com uma entrada privada x_i, calculem conjuntamente f(x_1,...,x_n) sem revelar suas entradas uns aos outros — como se um terceiro confiável tivesse feito o cálculo.

O problema dos milionários de Yao, de 1982: Alice e Bob querem descobrir quem é mais rico sem revelar seu patrimônio. Não há um terceiro confiável. A MPC resolve isso com garantias criptográficas.

1. Privacidade: os participantes descobrem apenas a saída e o que podem inferir dela. 2. Correção: a saída está correta mesmo quando alguns participantes são corrompidos. 3. Existem variantes para adversários semimaliciosos e maliciosos.

Qualquer função pode ser expressa como um circuito booleano (portas AND, XOR e NOT). Os protocolos de MPC geralmente operam no nível do circuito, avaliando cada porta com segurança.

Alice (criadora do embaralhamento) atribui dois rótulos aleatórios a cada fio: um para 0 e outro para 1. Ela cifra a tabela-verdade de cada porta usando os rótulos dos fios de entrada. Bob (avaliador) descobre apenas os rótulos correspondentes às suas entradas por meio de Transferência Oblívia.

Bob recebe tabelas embaralhadas (4 cifragens por porta AND). Ele decifra exatamente uma linha usando seus rótulos de entrada, obtendo o rótulo de saída — sem descobrir se ele representa 0 ou 1.

Anexe um "bit de seleção" aleatório a cada rótulo. Bob usa os bits de seleção para encontrar a linha embaralhada correta em O(1), em vez de tentar as quatro decifrações. Isso reduz a computação em 4×.

Kolesnikov e Schneider (2008): escolha um deslocamento global Δ. Então label_1 = label_0 ⊕ Δ para cada fio. As portas XOR tornam-se gratuitas (não é necessária nenhuma cifragem), economizando aproximadamente 30% da largura de banda.

Zahur et al. (2015): cada porta AND requer apenas 2 textos cifrados (em vez de 4). Combinada com o XOR livre, essa técnica reduz pela metade a largura de banda dos circuitos embaralhados padrão.

Os circuitos embaralhados clássicos são para duas partes. As extensões multipartidárias (por exemplo, o protocolo BMR) paralelizam o embaralhamento entre todos os participantes, mas exigem comunicação O(n²). São viáveis para n pequeno.

No protocolo de circuito embaralhado de Yao, como Bob obtém os rótulos dos fios correspondentes aos bits de sua entrada privada?

A MPC permite que os participantes calculem conjuntamente sem revelar as entradas. Os circuitos embaralhados codificam funções booleanas como tabelas-verdade cifradas. As otimizações (XOR livre, meias-portas, apontar e permutar) tornam esses circuitos viáveis na prática. A OT fornece os rótulos das entradas de Bob de forma privada.