«Vários hospitais oncológicos desejam combinar sequências genômicas de seus pacientes para realizar um estudo estatístico de associação (GWAS), mas leis de privacidade (LGPD / GDPR / HIPAA) proíbem estritamente que um único byte de dado bruto saia de cada hospital.» «Bancos comerciais concorrentes querem rastrear conjuntamente redes de lavagem de dinheiro interbancária sem jamais revelar suas listas de clientes ou grafos de transações internas.»

À primeira vista, isso parece logicamente impossível: para avaliar uma função $f(x_1, x_2, \dots, x_n)$, não seria indispensável que uma terceira parte confiável (Trusted Third Party, TTP) reunisse primeiro todas as entradas $x_i$ em texto simples? Contudo, no final da década de 1980, a criptografia moderna provou um teorema extraordinário: mesmo sem nenhuma terceira parte confiável, múltiplos participantes que desconfiam uns dos outros podem avaliar conjuntamente qualquer função computável $f(x_1, \dots, x_n)$ de modo que todos descubram o resultado exato sem que ninguém aprenda um único bit adicional sobre a entrada secreta $x_i$ dos demais.

Essa disciplina é chamada de Computação Multipartidária Segura (Secure Multi-Party Computation, MPC). Neste artigo, partimos de dois experimentos mentais clássicos para deduzir os dois motores matemáticos fundamentais da MPC: o compartilhamento de segredos por limiar $(t, n)$ de Adi Shamir (interpolação de Lagrange, protocolo BGW e triplas de Beaver) e a abordagem de circuitos booleanos via transferência inconsciente ($\text{OT}_1^2$) de Rabin e circuitos embaralhados (Garbled Circuits) de Yao.

1. Dois experimentos mentais paradoxais: «A média salarial sem chefe» e «O Problema dos Milionários de Yao»

1.1 Experimento mental 1: Calcular a média salarial sem revelar nenhum salário individual

Três engenheiros $A, B$ e $C$ querem descobrir sua média salarial anual $\bar{x} = \frac{x_A + x_B + x_C}{3}$ sem que nenhum deles descubra o salário individual $x_A, x_B$ ou $x_C$ dos outros dois. Usando compartilhamento aditivo de segredos (mascaramento One-Time Pad), eles conseguem isso apenas com papel e caneta:

1. Máscara aleatória e primeiro sussurro ($A \to B$): Os três escolhem um módulo público grande $M$ (por exemplo, $M = 10^9$). O engenheiro $A$ sorteia secretamente um número aleatório uniforme $r \xleftarrow{\$} \mathbb{Z}_M$, soma seu salário $x_A$ e sussurra apenas $s_1 = (x_A + r) \bmod M$ para $B$. Como $r$ é uniforme em $\mathbb{Z}_M$, $s_1$ também é perfeitamente uniforme independentemente do valor de $x_A$: pelo teorema de Shannon sobre o One-Time Pad, a informação mútua é $I(X_A; S_1) = 0$. $B$ aprende literalmente zero bits sobre $x_A$.
2. Somas sucessivas ($B \to C \to A$): $B$ soma seu próprio salário $x_B$ e sussurra $s_2 = (x_A + x_B + r) \bmod M$ para $C$; $C$ soma $x_C$ e devolve $s_3 = (x_A + x_B + x_C + r) \bmod M$ para $A$.
3. Remoção da máscara: $A$ subtrai seu número aleatório $r$ módulo $M$, obtém a soma exata $S = x_A + x_B + x_C$ e anuncia a média $\bar{x} = S / 3$.

[!NOTE] Por que são necessários pelo menos 3 participantes ($n \ge 3$)? Se houvesse apenas duas pessoas ($A$ e $B$), mesmo que um anjo incorruptível revelasse apenas a média $\bar{x} = \frac{x_A + x_B}{2}$, $A$ calcularia imediatamente $x_B = 2\bar{x} - x_A$. Isso não é uma falha do protocolo, mas uma propriedade matemática da própria função. A MPC garante que nenhum bit extra vaze além do que é logicamente dedutível da própria entrada e da saída final.

1.2 Experimento mental 2: O «Problema dos Milionários» de Andrew Yao (1982)

A adição é linear, mas e quanto a uma comparação não linear? Em 1982, o cientista da computação Andrew Chi-Chih Yao (futuro vencedor do Prêmio Turing) publicou “Protocols for Secure Computations”, propondo o famoso Problema dos Milionários: dois milionários, Alice ($x$ milhões de dólares) e Bob ($y$ milhões de dólares), desejam calcular apenas o bit booleano $f(x, y) = [x > y] \in \{0, 1\}$ (quem é mais rico?) sem revelar o valor de $x$ ou $y$, nem mesmo a diferença $x - y$.

2. Formalização matemática da segurança: O paradigma de simulação Ideal/Real

Para provar rigorosamente a ausência de vazamento de informações, Goldreich, Micali e Wigderson (GMW 1987) estabeleceram o paradigma de simulação Mundo Ideal / Mundo Real:

  flowchart TD
    subgraph IdealWorld["Mundo Ideal (Ideal World): Padrão absoluto de privacidade"]
        direction TB
        PA1["Parte P1 (Entrada secreta x1)"] -->|"Canal privado seguro"| TTP["Funcionalidade Ideal Incorruptível F"]
        PA2["Parte P2 (Entrada secreta x2)"] -->|"Canal privado seguro"| TTP
        PAn["Parte Pn (Entrada secreta xn)"] -->|"Canal privado seguro"| TTP
        TTP -->|"Retorna apenas y = f(x1,...,xn)"| Out1["Todos descobrem apenas y (Zero vazamento intermediário)"]
        Out1 --> Sim["Simulador S (Fabrica transcrição falsa usando apenas entradas corrompidas e y)"]
    end

    subgraph RealWorld["Mundo Real (Real World): Protocolo criptográfico Π"]
        direction TB
        RB1["Parte P1 (Entrada secreta x1)"] <-->|"Cifras e partes aleatórias"| RB2["Parte P2 (Entrada secreta x2)"]
        RB2 <-->|"Cifras e partes aleatórias"| RBn["Parte Pn (Entrada secreta xn)"]
        RB1 <-->|"Cifras e partes aleatórias"| RBn
        RB2 --> View["Visão completa View_A(x1,...,xn) observada pelo adversário A"]
    end

    Sim <-->|"Distribuições de probabilidade indistinguíveis (View_A ≈ Sim)"| View

Distingue-se entre adversários semi-honestos (Semi-Honest / Passive), que seguem o protocolo mas analisam os registros, e adversários maliciosos (Malicious / Active), que adulteram mensagens ativamente.

3. Motor 1: Compartilhamento de segredos por limiar $(t, n)$ de Shamir, interpolação de Lagrange e BGW / SPDZ

3.1 Polinômios sobre $\mathbb{F}_p$ e reconstrução de Lagrange

Com $t - 1$ partes ou menos, todo segredo candidato $s' \in \mathbb{F}_p$ é exatamente equiprovável ($H(S \mid \text{Shares}_{t-1}) = H(S)$, segurança incondicional em teoria da informação).

3.2 Protocolo BGW e triplas de multiplicação de Beaver

4. Motor 2: Transferência inconsciente ($\text{OT}_1^2$) de Rabin e circuitos garbled de Yao

Para comparações binárias ($x > y$), a abordagem de circuitos booleanos opera em um número constante $O(1)$ de rodadas:

  flowchart TD
    subgraph Step1["1. Alice (Garbler): Criptografia do circuito booleano"]
        W["Gerar para cada fio w_i duas chaves AES aleatórias de 128 bits (k_i^0, k_i^1)"] --> G["Criptografia dupla das 4 linhas da tabela-verdade: Enc(k_a^α, k_b^β, k_c^g(α,β))"]
        G --> P["Permutar aleatoriamente as 4 cifras de cada porta lógica (Garbled Table)"]
    end

    subgraph Step2["2. Transferência de chaves via Transferência Inconsciente 1-de-2 (OT_1^2)"]
        P -->|"Enviar tabelas garbled + chave ativa de Alice k_a^x"| Eval["Bob (Evaluator)"]
        BobIn["Bit secreto de entrada de Bob y ∈ {0,1}"] --> OT["Transferência Inconsciente 1-de-2 (OT_1^2)"]
        W -->|"Par de chaves candidatas (k_b^0, k_b^1)"| OT
        OT -->|"Bob recebe APENAS k_b^y (Alice não aprende nada sobre y)"| Eval
    end

    subgraph Step3["3. Bob (Evaluator): Avaliação cega porta por porta"]
        Eval --> Dec["Descriptografar exatamente 1 das 4 linhas por porta com (k_a^x, k_b^y) -> chave k_c^z"]
        Dec --> Out["Traduzir a chave do fio de saída final para o resultado z = f(x,y)"]
    end

Mediante a transferência inconsciente 1-de-2 ($\text{OT}_1^2$) de Michael Rabin, Bob obtém apenas a chave $k_b^y$ correspondente ao seu bit secreto $y$ sem que Alice descubra $y$. As três otimizações modernas — Point-and-Permute (bits de cor apontando diretamente a linha a descriptografar), Free-XOR ($k_i^1 = k_i^0 \oplus \Delta$, tornando todas as portas XOR livres de cifras e de operações AES) e Half-Gates (reduzindo cada porta AND a apenas 2 cifras) — aceleraram os circuitos garbled em mais de $1000$ vezes.

5. Implementação completa em Python: Shamir Secret Sharing e triplas de Beaver sobre $\mathbb{F}_p$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import secrets
from typing import List, Tuple

PRIME = (1 << 61) - 1  # Primo de Mersenne de 61 bits p = 2^61 - 1

def mod_inv(a: int, p: int = PRIME) -> int:
    return pow(a % p, -1, p)

def shamir_share(secret: int, t: int, n: int, p: int = PRIME) -> List[Tuple[int, int]]:
    coeffs = [secret % p] + [secrets.randbelow(p) for _ in range(t - 1)]
    shares = []
    for i in range(1, n + 1):
        y = 0
        for c in reversed(coeffs):
            y = (y * i + c) % p
        shares.append((i, y))
    return shares

def lagrange_reconstruct(shares: List[Tuple[int, int]], p: int = PRIME) -> int:
    secret = 0
    k = len(shares)
    for i in range(k):
        xi, yi = shares[i]
        num, den = 1, 1
        for j in range(k):
            if i != j:
                xj, _ = shares[j]
                num = (num * (-xj)) % p
                den = (den * (xi - xj)) % p
        secret = (secret + yi * num * mod_inv(den, p)) % p
    return secret

def mpc_add(sa, sb, p=PRIME):
    return [(xa, (ya + yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_sub(sa, sb, p=PRIME):
    return [(xa, (ya - yb) % p) for (xa, ya), (_, yb) in zip(sa, sb)]

def mpc_scalar_mul(c, sa, p=PRIME):
    return [(xa, (c * ya) % p) for xa, ya in sa]

def mpc_add_const(c, sa, p=PRIME):
    return [(xa, (ya + c) % p) for xa, ya in sa]

def generate_beaver_triple(t: int, n: int, p: int = PRIME):
    u, v = secrets.randbelow(p), secrets.randbelow(p)
    return shamir_share(u, t, n, p), shamir_share(v, t, n, p), shamir_share((u * v) % p, t, n, p)

def mpc_beaver_mul(sx, sy, triple, t: int, p: int = PRIME):
    su, sv, sw = triple
    d = lagrange_reconstruct(mpc_sub(sx, su, p)[:t], p)
    e = lagrange_reconstruct(mpc_sub(sy, sv, p)[:t], p)
    res = mpc_add(mpc_add(sw, mpc_scalar_mul(d, sv, p), p), mpc_scalar_mul(e, su, p), p)
    return mpc_add_const((d * e) % p, res, p)

if __name__ == "__main__":
    t, n = 3, 5
    salaries = [85000, 92000, 78000]
    shared = [shamir_share(s, t, n) for s in salaries]
    total_shares = shared[0]
    for s in shared[1:]:
        total_shares = mpc_add(total_shares, s)
    print("Soma salarial total reconstruída:", lagrange_reconstruct(total_shares[:t]))

6. Comparativo das Tecnologias de Aprimoramento de Privacidade (PETs) e aplicações reais

Desde o histórico leilão duplo de beterraba açucareira na Dinamarca em 2008 até o estudo de disparidade salarial de Boston (BWWC), a verificação de senhas vazadas no Google Chrome e Apple iCloud (Private Set Intersection, PSI), os estudos genômicos inter-hospitalares (Secure GWAS) e as carteiras criptográficas MPC por limiar (Fireblocks, Coinbase), a MPC substitui a confiança institucional pela certeza matemática.