Multi-party computation (MPC)

Autor - Gelois & Israel - Jun '25

Introducción

El Cómputo Multipartito Seguro (MPC) es un protocolo criptográfico que permite a múltiples partes realizar cálculos sobre datos sin revelar su información entre sí. En otras palabras (y de forma más sencilla), es un truco criptográfico que permite que personas u organizaciones trabajen juntas y obtengan resultados específicos, manteniendo la información de cada uno privada y segura.

Utiliza cifrado y secret sharing (compartición secreta) para garantizar la privacidad y seguridad durante el proceso de cómputo. En este enfoque, un dato se divide en "fragmentos" y se distribuye entre los participantes. La información sigue protegida porque ningún fragmento individual revela nada útil. Solo cuando se combinan suficientes fragmentos se puede reconstruir el dato original o proceder con el cálculo de forma segura.

Gracias a estas técnicas, MPC permite realizar cálculos manteniendo la privacidad, permitiendo a las partes colaborar en análisis de datos sin comprometer la confidencialidad de su información.

Cada protocolo válido de MPC debe cumplir dos requisitos específicos:

• Privacidad en caso de comportamientos deshonestos: Si los participantes revelan su información secreta o descartan las reglas durante el cálculo, el protocolo MPC no permitirá que los participantes deshonestos obliguen a las partes honestas a revelar su información confidencial ni influir en el resultado.

• Imposibilidad de deducir los secretos: Ningún participante puede deducir la información secreta de los demás a partir de la ejecución del protocolo. Esto significa que el resultado del cálculo no da ninguna pista sobre la información privada que cada participante posee.

Conceptos Clave y Operaciones

Los protocolos MPC generalmente operan a través de los siguientes pasos:

1. Distribución de entradas: Cada participante divide su entrada en múltiples fragmentos y los distribuye entre todas las partes.

2. Cómputo: Las partes realizan cálculos sobre los fragmentos sin reconstruir los datos originales. Esto puede incluir operaciones aritméticas o funciones más complejas.

3. Reconstrucción del resultado: Tras completar el cálculo, los participantes combinan sus fragmentos para generar el resultado final, que puede verificarse públicamente sin revelar ninguna entrada privada.

Beneficios de MPC

• Terceros no tienen acceso a los datos: Los datos no son vulnerables a terceros o inteligencia externa. MPC reduce la dependencia de proveedores externos al mantener los datos y cálculos seguros dentro de las redes internas de las organizaciones.

• Preserva la usabilidad y privacidad: MPC facilita cálculos colaborativos sin enmascarar variables. La confidencialidad se mantiene intacta sin sacrificar la precisión.

• Datos permanecen cifrados: Las inferencias se realizan sobre datos cifrados

• Alta precisión y exactitud: Los resultados cumplen y superan los estándares de precisión exigidos por los clientes.

• Resistente a la computación cuántica: Los datos se cifran durante su uso al dividirse y distribuirse entre participantes (mediante "compartición de secretos"), lo que los protege contra ataques cuánticos.

Limitaciones de MPC

• Sobrecarga computacional: Para garantizar la seguridad, se deben generar números aleatorios durante el cálculo . Esta generación requiere recursos computacionales adicionales, lo que puede ralentizar el proceso.

• Altos costos de comunicación entre participantes: La compartición de secretos implica comunicación constante entre todos los actores, aumentando los costos en comparación con el cálculo en texto plano.

• Suposición previa de participantes maliciosos: Para implementar MPC de forma segura, se debe predecir y asumir la proporción de actores maliciosos en el cálculo conjunto.

Comprendiendo fundamentos matemáticos

Two-party Computation Protocols vs Multi-party Computation Protocols

Imagina que tú y tus amigos pertenecen a una empresa reconocida donde se les asigno un salario individual, y quieren saber el promedio de sueldos en su empresa, pero sin decir cuál es el suyo por temas de confindencialidad.

SMPC permite que un conjunto de n participantes, cada uno con datos privados (d₁, d₂, …, dn) -> esto sería sus salarios indivuales, pueda calcular una función pública F(d₁, d₂, …, dn) -> que sería el resultado promedio de salarios, sin que ninguno de los participantes pueda conocer la información de los demás.

Es importante definir ciertos términos para enteder los fundamentos:

"Ofuscar" significa ocultar o volver algo difícil de entender, especialmente para proteger su significado original.

Analogía útil: Imagina un examen de opción múltiple donde las respuestas no son (A, B, C), sino (X9#, P2$, K5&). Solo el profesor sabe qué letra corresponde a cada símbolo. Así funciona la ofuscación: esconde el significado, pero preserva la función.

En seguridad: Ofuscar no es cifrar (que requiere una clave matemática), sino enmascarar la estructura para que, sin contexto, sea inútil.

Ahora bien el protocolo de MPC cambia significativamente según el tipo y número de tales participantes en un sistema:

Two-party Computation Protocols

Los protocolos de computación segura entre dos partes permiten que dos entidades colaboren para calcular una función sin revelar sus entradas privadas. El enfoque clave es el uso de circuitos garbleados.

El circuito garbleado es un protocolo criptográfico que permite a dos partes calcular una función de manera segura sin revelar sus entradas privadas ni depender de un tercero de confianza. El proceso se basa en modelar la función como un circuito booleano, donde cada puerta lógica (como AND, OR, XOR) se ofuscan reemplazando sus entradas y salidas con etiquetas aleatorias (como códigos secretos), para que solo se pueda evaluar correctamente sin exponer información adicional. Así solo quien tiene las claves correctas puede "descifrar" la lógica oculta, evitando que un atacante entienda los datos reales.

Componentes Clave

• Circuito Booleano: Representa la función mediante puertas lógicas interconectadas, donde cada entrada y salida es un bit (0 o 1).

• Transferencia Oblivious (OT): Permite que una parte obtenga información específica sin que la otra sepa qué dato fue seleccionado. Esto es crucial para que el evaluador reciba las claves correctas sin revelar sus entradas.

Funcionamiento del Protocolo

• Generación del Circuito Garbleado (Garbler):

  1. Ofusca cada puerta asignando etiquetas aleatorias a las entradas y salidas.

  2. Crea una tabla de cifrado donde solo la combinación correcta de etiquetas descifra el resultado válido.

• Evaluación (Evaluator):

  1. Usa Transferencia Oblivious para obtener las etiquetas correspondientes a sus entradas.

  2. Descifra selectivamente las puertas usando las etiquetas, propagando los resultados hasta obtener la salida final.

Optimizaciones

• Point-and-Permute: Reduce el esfuerzo de descifrado al usar bits de selección para identificar la fila correcta en cada puerta.

• Free-XOR: Permite calcular puertas XOR sin coste adicional, aprovechando relaciones predefinidas entre etiquetas.

• Garbled Row Reduction (GRR): Minimiza el tamaño de las tablas garbleadas eliminando filas redundantes.

• Half Gates: Reduce a solo dos cifrados por puerta AND, manteniendo compatibilidad con Free-XOR.

Estas técnicas permiten que el protocolo sea eficiente y seguro, ideal para aplicaciones como subastas privadas, comparaciones confidenciales o análisis de datos sin comprometer la privacidad.

El concepto detrás de un protocolo de circuitos garbleados es sencillo pero poderoso. En esencia, el circuito garbleado actúa como una caja negra segura: ejecuta la lógica deseada, pero oculta todos los detalles internos.

Ahora se lo ejemplificará de forma sencilla. Imagina dos partes, Alicia y Bruno, que quieren calcular una función sin revelar sus entradas privadas. Para lograrlo, usan un Circuito Garbleado, que funciona así:

1. Representación de la Función Primero, la función que quieren calcular (que puede ser una fórmula matemática o código en un lenguaje de programación) se convierte en un circuito booleano.

2. Garbling (Ofuscación del Circuito) Alicia (el "garbleador") encripta u ofusca el circuito. Pero a diferencia de un cifrado tradicional (que protege datos), aquí se encripta la función misma. Cada puerta y entrada se reemplaza con etiquetas aleatorias (claves de evaluación), de modo que solo con las claves correctas se puede descifrar el resultado correcto.

3. Evaluación del Circuito Mediante un protocolo llamado Transferencia Oblivious (OT), Bruno obtiene las claves necesarias sin que Alicia sepa qué claves eligió. Con estas claves, Bruno evalúa el circuito garbleado sin entender las entradas originales ni los valores intermedios. Al final, solo el resultado de la función se revela, manteniendo todo lo demás en secreto.

Multi-party Computation Protocols

Existen varias técnicas desarrolladas para la construcción de protocolos de computación multipartita segura, cada una con características diferentes. Algunas de las técnicas utilizadas en MPC son las siguientes:

1. Shamir Secret Sharing: es un método que divide un secreto (ej: una clave privada) en múltiples shares o "partes".

• Notación: (t, n)

  • n = Total de partes generadas.

  • t = Umbral mínimo para reconstruir el secreto.

💡 Ejemplo: En un esquema (3, 4), se crean 4 partes y se necesitan al menos 3 para recuperar el secreto.

El siguiente diagrama ilustra el principio subyacente de un esquema de compartición de secretos {3,4}:

¿Cómo funciona?

1. Crear un Polinomio Secreto

El dealer genera un polinomio aleatorio de grado t-1:

$$f(x) = s + a_1x + a_2x^2 + \cdots + a_{t-1}x^{t-1}$$

$$s = Secreto \ ( \ valor \ en \ f(0)).$$

$$a_1, a_2, ... = Coeficientes \ aleatorios.$$

1. Generar las Partes (Shares)

Cada participante

$$P_i \ \ recibe \ un \ punto \ \ ( \ i, f(i)).$$

💡 Ejemplo: para (3,4):

Participante	Punto (x, y)
P1 (uno)	(1, f(1))
P2 (dos)	(2, f(2))
P3 (tres)	(3, f(3))
P4 (cuatro)	(4, f(4))

1. Reconstruir el Secreto

Con al menos t puntos, usamos interpolación de Lagrange para hallar

$$f(0)=s (para conocer el secreto)$$

$$s = \sum_{i=1}^{t} y_i \cdot \prod_{\substack{j=1 \\ j \neq i}}^{t} \frac{0 - x_j}{x_i - x_j}$$

Ejemplo Numérico (t=2, n=3)

• Secreto: s = 7

• Polinomio: f(x) = 7 + 3x (grado 1)

Partes generadas:

$$P1:(1,10)→f(1)=7+3∗1=10$$

$$P2:(2,13)→f(2)=7+3∗2=13$$

$$P3:(3,16)→f(3)=7+3∗3=16$$

Reconstrucción con P1 y P2:

s=10⋅0−21−2+13⋅0−12−1=10⋅2+13⋅(−1)=7

$$s = 10 \cdot \frac{0-2}{1-2} + 13 \cdot \frac{0-1}{2-1} = 10 \cdot 2 + 13 \cdot (-1) = 7$$

Solo conociendo "cierta parte" del secreto, nos es posible reconstruir el polinonmio completo.

Por qué es seguro?

• ❌ Con t-1 partes: Infinitos polinomios posibles → Imposible adivinar s.

• ✅ Con t partes: Solo un único polinomio posible → Secreto exacto.

Analogía: Como un rompecabezas donde necesitas suficientes piezas para ver la imagen completa. 🧩

⚠️ Nota: En la práctica, los cálculos se realizan en un campo finito (ej: GF( p )) para evitar números no enteros.

Ahora vamos a recapitular para explicar ciertos conceptos técnicos:

Compartición de Entradas

Cada participante comparte su entrada utilizando el esquema de compartición de secretos de Shamir. El circuito se proporciona como entrada para el cálculo. Cada parte mantiene su entrada privada añadiendo un número aleatorio (masking), y al final, después de obtener el resultado, se elimina este valor aleatorio (conocido solo por esa parte), revelando el resultado correcto.

Cada participante divide su secreto en partes. Todos juntas pueden reconstruirlo, pero individualmente no ven nada.

Evaluación del Circuito (Gate-by-Gate)

El circuito se evalúa puerta por puerta, procesando las operaciones en secuencia desde las entradas hasta las salidas. Las operaciones básicas son suma y multiplicación sobre los shares distribuidos.

Las operaciones se hacen por partes: sumas son fáciles (locales), multiplicaciones requieren colaboración.

Ejemplo de cálculo para el participante

$$i$$

• Suma:

$$óc(i)=a(i)+b(i) ( local ,sin comunicación)$$

• Multiplicación:

$$óc(i)=a(i)⋅b(i) ( requiere recombinación de shares)$$

Intersección de Conjuntos Privados (PSI)

Protocolo eficiente para que dos partes encuentren elementos comunes en sus conjuntos sin revelar los elementos no compartidos. Útil incluso en entornos con adversarios maliciosos.

Dos partes comparan sus datos cifrados. Solo descubren qué elementos tienen en común.

MPC con Mayoría Honesta

La función puede representarse mediante un circuito booleano o aritmético cuando hay mayoría honesta. En esquemas de compartición de secretos (MPC), se usa un campo finito

$$Zp ( con p>n)$$

para el circuito aritmético, el cual es Turing completo.

Funciona cuando la mayoría es confiable. Los datos se dividen en partes y se procesan de forma segura entre todos.

Claves:

Seguro si los adversarios corruptos son minoría

$$(t<n/2)$$

Usa aritmética modular en

$$Zp$$

MPC con Mayoría Deshonesta Cuando los adversarios pueden superar en número a los honestos, se requieren protocolos avanzados como:

• Transferencia Oblivious (GMW).

• Circuitos Cifrados (Yao).

• TinyOT (optimizado para eficiencia).

Protege los datos incluso si hay más participantes maliciosos que honestos, usando técnicas avanzadas como circuitos cifrados.

Características:

• Resistencia a colusión: Seguridad incluso si la mayoría es corrupta.

• Overhead computacional: Más costoso que mayoría honesta.

Criptografía Umbral Permite realizar operaciones criptográficas (ej: firmas) sin que ningún participante tenga la clave secreta completa. Basado en esquemas como RSA umbral:

$$y=x^e mod.n$$

(Donde x es el mensaje y e la clave pública).

Nadie tiene la clave completa; se necesita un grupo mínimo para autorizar operaciones, evitando robos o fraudes.

Beneficios:

• Tolerancia a fallos: Basta con un subconjunto de partes (ej: 3 de 5) para firmar.

• Seguridad distribuida: Ningún actor individual puede robar la clave.

Comparativa: Mayoría Honesta vs. Deshonesta

Criterio	Mayoría Honesta	Mayoría Deshonesta
Seguridad	Resistente a t<n/2 corruptos	Tolerancia a t≥n/2 corruptos
Protocolos típicos	Shamir, BGW	GMW, Circuitos Cifrados
Eficiencia	Alta (menos overhead)	Baja (más pasos interactivos)
Usos comunes	Firmas umbrales, MPC básico	Mixnets, votaciones electrónicas

Recapitulacion de MPC

El cómputo multipartito es una técnica criptográfica que permite a varias partes, cada una en posesión de fragmentos de datos privados, participar en el cálculo de un resultado específico utilizando algoritmos basados en MPC. Este resultado específico se calcula combinando sus datos sin revelar la naturaleza ni el contenido de sus entradas, ni cualquier otra información secreta relacionada con el proceso.

En términos más simples, MPC reúne entidades separadas que tienen piezas de información que, cuando se combinan, pueden revelar un secreto, firmar un mensaje o aprobar una transacción. Es importante destacar que MPC logra esto sin revelar detalles sobre la información que posee cada individuo.

Es relevante mencionar que en MPC, los datos distribuidos entre múltiples participantes no representan el secreto si simplemente se combinan. En cambio, estos fragmentos de información sirven como entradas para participar en el cálculo deseado.

SMPC emplea primitivas criptográficas como:

• Compartición secreta (por ejemplo, Shamir’s Secret Sharing).

• Cifrado homomórfico (por ejemplo, Paillier, ElGamal).

• Pruebas de conocimiento cero (por ejemplo, zk-SNARKs, zk-STARKs).