«Varios hospitales oncológicos desean combinar las secuencias genómicas de sus pacientes para realizar un estudio estadístico de asociación (GWAS), pero las leyes de privacidad (RGPD / HIPAA) prohíben estrictamente que un solo byte de datos clínicos salga de cada hospital». «Bancos comerciales competidores quieren rastrear conjuntamente redes de lavado de dinero interbancario sin revelar jamás sus listas de clientes ni sus grafos de transacciones internas».

A primera vista, esto parece lógicamente imposible: para evaluar una función $f(x_1, x_2, \dots, x_n)$, ¿no es imprescindible que un tercero de confianza (Trusted Third Party, TTP) reúna primero todas las entradas $x_i$ en texto plano? Sin embargo, a finales de los años ochenta, la criptografía moderna demostró un teorema extraordinario: incluso sin ningún tercero de confianza, múltiples participantes que desconfían entre sí pueden evaluar conjuntamente cualquier función computable $f(x_1, \dots, x_n)$ de modo que todos conozcan el resultado exacto sin que nadie descubra ni un solo bit adicional sobre la entrada secreta $x_i$ de los demás.

Esta disciplina se denomina Computación Multiparte Segura (Secure Multi-Party Computation, MPC). En este artículo partimos de dos experimentos mentales clásicos para deducir los dos motores matemáticos fundamentales de MPC: la compartición de secretos por umbral $(t, n)$ de Adi Shamir (interpolación de Lagrange, protocolo BGW y tripletas de Beaver) y el enfoque de circuitos booleanos mediante la transferencia inconsciente ($\text{OT}_1^2$) de Rabin y los circuitos cifrados (Garbled Circuits) de Yao.

1. Dos experimentos mentales paradójicos: «El salario medio sin jefe» y «El problema de los millonarios de Yao»

1.1 Experimento mental 1: Calcular el salario medio sin revelar ningún salario individual

Tres ingenieros $A, B$ y $C$ quieren conocer su salario anual medio $\bar{x} = \frac{x_A + x_B + x_C}{3}$ sin que ninguno descubra el salario individual $x_A, x_B$ o $x_C$ de los otros dos. Mediante la compartición aditiva de secretos (enmascaramiento One-Time Pad), pueden lograrlo usando solo papel y lápiz:

1. Máscara aleatoria y primer susurro ($A \to B$): Los tres acuerdan un módulo público grande $M$ (por ejemplo, $M = 10^9$). El ingeniero $A$ elige en secreto un número aleatorio uniforme $r \xleftarrow{\$} \mathbb{Z}_M$, le suma su salario $x_A$ y susurra únicamente $s_1 = (x_A + r) \bmod M$ a $B$. Como $r$ es uniforme en $\mathbb{Z}_M$, $s_1$ también está perfectamente distribuido de forma uniforme sin importar cuánto gane $A$: por el teorema de Shannon sobre la libreta de un solo uso, la información mutua es $I(X_A; S_1) = 0$. $B$ aprende literalmente cero bits sobre $x_A$.
2. Sumas sucesivas ($B \to C \to A$): $B$ suma su propio salario $x_B$ y susurra $s_2 = (x_A + x_B + r) \bmod M$ a $C$; $C$ suma $x_C$ y entrega $s_3 = (x_A + x_B + x_C + r) \bmod M$ de vuelta a $A$.
3. Eliminación de la máscara: $A$ resta su número aleatorio $r$ módulo $M$, obtiene la suma exacta $S = x_A + x_B + x_C$ y anuncia el promedio $\bar{x} = S / 3$.

[!NOTE] ¿Por qué se necesitan al menos 3 participantes ($n \ge 3$)? Si solo participaran dos personas ($A$ y $B$), aunque un ángel incorruptible les revelara únicamente el promedio $\bar{x} = \frac{x_A + x_B}{2}$, $A$ deduciría de inmediato $x_B = 2\bar{x} - x_A$. Esto no es un fallo del protocolo, sino una propiedad matemática de la propia función. MPC garantiza que no se filtre ni un bit más allá de lo que se deduce lógicamente de la propia entrada y del resultado final.

1.2 Experimento mental 2: El «problema de los millonarios» de Andrew Yao (1982)

La suma es lineal, pero ¿qué ocurre con una comparación no lineal? En 1982, el científico de la computación Andrew Chi-Chih Yao (posterior Premio Turing) publicó “Protocols for Secure Computations”, planteando el famoso problema de los millonarios: dos millonarios, Alice ($x$ millones de dólares) y Bob ($y$ millones de dólares), desean calcular únicamente el bit booleano $f(x, y) = [x > y] \in \{0, 1\}$ (¿quién es más rico?) sin revelar el valor de $x$ ni de $y$, ni siquiera su diferencia $x - y$.

2. Formalización matemática de la seguridad: El paradigma de simulación Ideal/Real

Para demostrar rigurosamente la ausencia de fugas de información, Goldreich, Micali y Wigderson (GMW 1987) establecieron el paradigma de simulación Mundo Ideal / Mundo Real:

  flowchart TD
    subgraph IdealWorld["Mundo Ideal (Ideal World): Estándar absoluto de privacidad"]
        direction TB
        PA1["Parte P1 (Entrada secreta x1)"] -->|"Canal privado seguro"| TTP["Funcionalidad Ideal Incorruptible F"]
        PA2["Parte P2 (Entrada secreta x2)"] -->|"Canal privado seguro"| TTP
        PAn["Parte Pn (Entrada secreta xn)"] -->|"Canal privado seguro"| TTP
        TTP -->|"Devuelve solo y = f(x1,...,xn)"| Out1["Todos conocen solo y (Cero fugas intermedias)"]
        Out1 --> Sim["Simulador S (Fabrica transcripción falsa usando solo entradas corruptas e y)"]
    end

    subgraph RealWorld["Mundo Real (Real World): Protocolo criptográfico Π"]
        direction TB
        RB1["Parte P1 (Entrada secreta x1)"] <-->|"Textos cifrados y fragmentos aleatorios"| RB2["Parte P2 (Entrada secreta x2)"]
        RB2 <-->|"Textos cifrados y fragmentos aleatorios"| RBn["Parte Pn (Entrada secreta xn)"]
        RB1 <-->|"Textos cifrados y fragmentos aleatorios"| RBn
        RB2 --> View["Vista completa View_A(x1,...,xn) observada por el adversario A"]
    end

    Sim <-->|"Distribuciones de probabilidad indistinguibles (View_A ≈ Sim)"| View

Se distingue entre adversarios semihonestos (Semi-Honest / Passive), que siguen las reglas pero analizan los registros, y adversarios maliciosos (Malicious / Active), que alteran mensajes activamente.

3. Motor 1: Compartición de secretos por umbral $(t, n)$ de Shamir, interpolación de Lagrange y BGW / SPDZ

3.1 Polinomios sobre $\mathbb{F}_p$ y reconstrucción de Lagrange

Con $t - 1$ fragmentos o menos, todo secreto candidato $s' \in \mathbb{F}_p$ es exactamente igual de probable ($H(S \mid \text{Shares}_{t-1}) = H(S)$, seguridad incondicional en teoría de la información).

3.2 Protocolo BGW y tripletas de multiplicación de Beaver

4. Motor 2: Transferencia inconsciente ($\text{OT}_1^2$) de Rabin y circuitos garbled de Yao

Para comparaciones binarias ($x > y$), el enfoque de circuitos booleanos opera en un número constante $O(1)$ de rondas:

  flowchart TD
    subgraph Step1["1. Alice (Garbler): Cifrado del circuito booleano"]
        W["Generar para cada cable w_i dos claves AES aleatorias de 128 bits (k_i^0, k_i^1)"] --> G["Doble cifrado de las 4 filas de la tabla de verdad: Enc(k_a^α, k_b^β, k_c^g(α,β))"]
        G --> P["Permutar aleatoriamente los 4 textos cifrados de cada compuerta (Garbled Table)"]
    end

    subgraph Step2["2. Transferencia de claves vía Transferencia Inconsciente 1-de-2 (OT_1^2)"]
        P -->|"Enviar tablas garbled + clave activa de Alice k_a^x"| Eval["Bob (Evaluator)"]
        BobIn["Bit secreto de entrada de Bob y ∈ {0,1}"] --> OT["Transferencia Inconsciente 1-de-2 (OT_1^2)"]
        W -->|"Par de claves candidatas (k_b^0, k_b^1)"| OT
        OT -->|"Bob recibe SOLO k_b^y (Alice no aprende nada sobre y)"| Eval
    end

    subgraph Step3["3. Bob (Evaluator): Evaluación ciega compuerta por compuerta"]
        Eval --> Dec["Descifrar exactamente 1 de las 4 filas por compuerta con (k_a^x, k_b^y) -> clave k_c^z"]
        Dec --> Out["Traducir la clave del cable de salida final al resultado z = f(x,y)"]
    end

Mediante la transferencia inconsciente 1-de-2 ($\text{OT}_1^2$) de Michael Rabin, Bob obtiene únicamente la clave $k_b^y$ correspondiente a su bit secreto $y$ sin que Alice descubra $y$. Las tres optimizaciones modernas —Point-and-Permute (bits de color que señalan directamente la única fila a descifrar), Free-XOR ($k_i^1 = k_i^0 \oplus \Delta$, que hace que todas las compuertas XOR requieran cero textos cifrados y cero operaciones AES) y Half-Gates (que reduce cada compuerta AND a solo 2 textos cifrados)— aceleraron los circuitos garbled más de $1000$ veces.

5. Implementación completa en Python: Shamir Secret Sharing y tripletas 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("Suma salarial total reconstruida:", lagrange_reconstruct(total_shares[:t]))

6. Comparativa de Tecnologías de Mejora de la Privacidad (PETs) y aplicaciones reales

Desde la histórica subasta doble de remolacha azucarera en Dinamarca en 2008 hasta el estudio de brecha salarial de Boston (BWWC), la verificación de contraseñas filtradas en Google Chrome y Apple iCloud (Private Set Intersection, PSI), los estudios genómicos interhospitalarios (Secure GWAS) y las billeteras criptográficas MPC por umbral (Fireblocks, Coinbase), la MPC está reemplazando la confianza institucional por certeza matemática.