← Volver a la Bitácora

Computación multipartita (MPC): el dilema del millonario

Computación multipartita (MPC): el dilema del millonario

1982. Un matemático chino, Andrew Yao, presenta en una conferencia de computación un trabajo corto de cinco páginas. La primera frase plantea un problema que parece un chiste:

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth.

Dos millonarios quieren saber quién tiene más. Ninguno quiere decir cuánto tiene.

La solución de siempre es un notario. Los dos le cuentan su fortuna, el notario compara y anuncia el resultado. Funciona, pero ahora hay alguien que sabe las dos cifras. Ese alguien puede hablar, puede ser sobornado, le pueden robar los papeles.

Yao propone otra cosa: un procedimiento matemático para hacer la comparación sin que nadie, ni siquiera un notario, vea los números.

Así nace un campo que hoy se llama computación segura multipartita, o MPC por sus siglas en inglés. La idea es esta: varias partes, cada una con un dato secreto, calculan algo juntas. Al final, cada una conoce el resultado y nada más.

Slide: dos gatos ninja con bolsas de dinero, y el pensamiento de uno: ¿tendrá más que yo?

Con un mazo de cartas

Suena imposible, pero se puede hacer en una mesa con un mazo de cartas. Se necesitan tréboles (♣), corazones (♥) y dos personas. Todas las cartas van boca abajo todo el tiempo.

Slide: el gato ninja baraja un mazo sobre la mesa de madera

Digamos que la fortuna más grande posible es 5. Alicia tiene 3. Bob tiene 4.

Alicia arma una fila de cinco cartas: tantos tréboles como su fortuna, y el resto corazones. Su fila es ♣♣♣♥♥. Una rampa que dice “hasta acá llego”.

Slide: el gato ninja alinea tres tréboles y dos corazones sobre cinco cartas boca abajo

Bob hace algo parecido. Arma otra fila de cinco, todos tréboles, pero en vez de completar con corazones como Alicia, pone un solo corazón en la posición de su fortuna: ♣♣♣♥♣. Un puntero que dice “acá estoy”.

Slide: la tira de Bob con un solo corazón en la cuarta posición

Las dos filas se intercalan, una carta de Alicia, una de Bob, siempre boca abajo. Al final se agregan dos cartas de relleno.

Slide: el gato ninja entrelaza las dos tiras de cartas y marca dos cartas falsas al final

Después se corta el mazo. Una vez, diez veces, las que se quiera. Cada corte cambia dónde empieza la fila, pero no el orden de las cartas entre sí. Ahora nadie sabe cuál es la primera.

Slide: el gato ninja corta el mazo en el aire con la espada

Se dan vuelta solo las cartas de Bob hasta encontrar su corazón. Se mira la carta que está justo a su izquierda. Esa carta es de Alicia, y está en la misma posición que la fortuna de Bob.

Slide: el gato ninja con lupa mira la carta a la izquierda del corazón de Bob

Si es corazón, la rampa de Alicia ya se había terminado: Alicia tiene menos que Bob. Si es trébol, Alicia tiene igual o más.

Acá sale corazón. Alicia tiene menos. Ninguno de los dos supo el número del otro.

El secreto está en el corte. Si Bob pudiera elegir dónde cortar, sabría dónde empieza la fila y podría deducir la fortuna de Alicia. Como el corte es al azar, no puede. El azar ocupa el lugar del notario.

De las cartas a las computadoras

1986. Yao publica un segundo trabajo. Las computadoras no barajan, así que propone otra forma de hacer lo mismo: los circuitos garblados.

Cualquier cálculo se puede escribir como un circuito de compuertas lógicas, las piezas más chicas con las que piensa una computadora. Una de las partes arma el circuito y cifra cada compuerta, de modo que funcione sin mostrar qué entra ni qué sale. La otra parte lo recorre a ciegas, compuerta por compuerta, y al final obtiene el resultado. Nada más.

Slide: el gato ninja frente a una máquina de caños y cajas fuertes con compuertas AND, XOR y válvulas

Desde entonces se le agregaron cuarenta años de mejoras, pero la idea es la misma. Y tiene una condición: lo que se quiere calcular tiene que poder escribirse como circuito.

Slide: la tabla comparativa entre el truco de cartas y la versión criptográfica

El precio

El MPC es lento. Mucho más lento que mandarle los datos a un servidor y que haga la cuenta. Cada compuerta cifrada viaja por la red, y un cálculo serio tiene millones.

Por eso no se usa para todo. Se usa cuando el dato no puede salir, por ley, por contrato o por prudencia. Ahí la alternativa a lo lento es que no se haga.

Hay tres formas de calcular con datos ajenos:

Cómo se calculaVelocidadQuién ve el datoCuántas partes
La nube comúnaltael servidor, todouna
El cifrado homomórficomuy bajanadieun solo dueño del dato
El MPCbajanadievarias, conectadas

El MPC es el único de los tres donde el secreto no está completo en ningún lugar. Y el único donde las partes tienen que estar conectadas y acordar de antemano qué van a calcular.

Dinamarca, 2008

El primer uso real del MPC no fue en un banco ni en el ejército. Fue en el campo.

Enero de 2008. La Unión Europea reforma el mercado del azúcar, y Dinamarca tiene que redistribuir los contratos de producción de remolacha entre sus agricultores. La forma justa es una subasta donde cada uno ofrece lo que quiere sin que los demás vean su oferta. Ni la empresa azucarera ni la asociación de productores quieren mostrar sus números al otro, y ninguno quiere un intermediario con todas las ofertas.

Así que la subasta se hace con MPC. Sale el precio de cierre. Ninguna oferta individual se ve nunca.

Slide: el gato ninja de detective en un mercado de verduras, con un repollo gigante a un costado

Boston, sueldos de verdad

El segundo caso es el problema de Yao con sueldos reales.

En Boston, un consejo de mujeres trabajadoras quiere medir cuánto menos cobran las mujeres y las personas no blancas. Necesita los sueldos de muchas empresas que compiten entre sí por la misma gente. Ninguna va a entregar su planilla de sueldos.

Con la Universidad de Boston arman el cálculo con MPC. En 2016 participan 69 empresas con 112.600 empleados. Los sueldos nunca se juntan en una base de datos. Sale un solo número público: la brecha.

Lo repiten seis veces entre 2015 y 2023. En la última, la muestra cubre al 17 % de los trabajadores de la región.

El gato y su sombra

Slide: el gato ninja y su propia sombra, con un as de corazones sobre la mesa

«La verdadera privacidad no consiste en esconderse del mundo, sino en colaborar con él sin tener que entregar lo que es tuyo.»

Cifrar es esconder un dato para que nadie lo lea. El MPC hace otra cosa: te deja usar el dato con otros sin entregarlo.

Es la misma idea que vuelve en toda esta serie. PeerDAS verifica un bloque sin descargarlo. Ğ1 verifica que alguien es una persona sin un registro central. Una dirección stealth cobra sin que nadie pueda unir al que paga con el que cobra. Siempre lo mismo: hacer algo con la información sin poseerla.

Hoy el cálculo con datos ajenos se hace casi siempre como en la primera escena: se entrega el dato y se confía en el otro. Es más rápido, y funciona mientras el otro cumpla.

Yao encontró en 1982 una tercera salida, con dos millonarios inventados y un mazo de cartas: no tener que confiar en nadie.