Cálculo multipartito seguro: Secure multi-party computation

La computación segura de múltiples partes (también conocida como computación segura , computación de múltiples partes (MPC) o computación que preserva la privacidad ) es un subcampo de la criptografía con el objetivo de crear métodos para que las partes calculen conjuntamente una función sobre sus entradas mientras se mantienen esas Entradas privadas. A diferencia de las tareas criptográficas tradicionales, donde la criptografía garantiza la seguridad e integridad de la comunicación o el almacenamiento y el adversario está fuera del sistema de los participantes (un fisgón del remitente y el receptor), la criptografía en este modelo protege la privacidad de los participantes entre sí.

La base para la computación segura de múltiples partes comenzó a fines de la década de 1970 con el trabajo en el póquer mental, un trabajo criptográfico que simula juegos / tareas computacionales a distancia sin requerir un tercero confiable. Tenga en cuenta que, tradicionalmente, la criptografía se trataba de ocultar contenido, mientras que este nuevo tipo de cálculo y protocolo se trata de ocultar información parcial sobre los datos mientras se computa con los datos de muchas fuentes y producir resultados correctamente.

Historia

Los protocolos de propósito especial para tareas específicas comenzaron a fines de la década de 1970. Más tarde, la computación segura se introdujo formalmente como computación segura de dos partes (2PC) en 1982 (para el llamado Problema de los Millonarios , un problema específico que es un predicado booleano), y en general (para cualquier computación factible) en 1986 por Andrew Yao . El área también se conoce como Evaluación de función segura (SFE). El caso bipartidista fue seguido por una generalización al pluripartidismo por parte de Goldreich, Micali y Wigderson. El cálculo se basa en el intercambio secreto de todas las entradas y pruebas de conocimiento cero para un caso potencialmente malintencionado, donde la mayoría de los jugadores honestos en el caso del adversario malintencionado aseguran que se detecta el mal comportamiento y el cálculo continúa con la persona deshonesta eliminada o su entrada revelada. Este trabajo sugirió el esquema general muy básico a seguir esencialmente por todos los futuros protocolos multipartitos para la informática segura. Este trabajo introdujo un enfoque, conocido como paradigma GMW, para compilar un protocolo de computación de múltiples partes que es seguro contra adversarios semi-honestos a un protocolo que es seguro contra adversarios malintencionados. Este trabajo fue seguido por el primer protocolo seguro robusto que tolera el comportamiento defectuoso gentilmente sin revelar el resultado de nadie a través de un trabajo que inventó para este propósito la "idea de compartir las acciones" de uso frecuente y un protocolo que permite a una de las partes ocultar su entrada incondicionalmente. . El paradigma de GMW se consideró ineficaz durante años debido a los enormes gastos generales que aporta al protocolo base. Sin embargo, se demuestra que es posible lograr protocolos eficientes, y hace que esta línea de investigación sea aún más interesante desde una perspectiva práctica. Los resultados anteriores corresponden a un modelo en el que el adversario se limita a cálculos de tiempo polinomial y observa todas las comunicaciones, por lo que el modelo se denomina "modelo computacional". Además, se demostró que el protocolo de transferencia inconsciente estaba completo para estas tareas. Los resultados anteriores establecieron que es posible bajo las variaciones anteriores lograr un cálculo seguro cuando la mayoría de los usuarios son honestos.

La siguiente pregunta a resolver fue el caso de los canales de comunicación seguros donde la comunicación punto a punto no está disponible para el adversario; en este caso se demostró que se pueden lograr soluciones con hasta 1/3 de las partes comportándose mal y siendo maliciosas, y las soluciones no aplican herramientas criptográficas (ya que se dispone de comunicación segura). Agregar un canal de transmisión permite que el sistema tolere hasta la mitad de una minoría que se porta mal, mientras que las limitaciones de conectividad en el gráfico de comunicación se investigaron en el libro Perfectly Secure Message Transmission.

A lo largo de los años, la noción de protocolos multipartitos de propósito general se convirtió en un área fértil para investigar las propiedades de los problemas básicos y generales del protocolo, como la componibilidad universal o el adversario móvil como en el intercambio proactivo de secretos .

Desde finales de la década de 2000, y ciertamente desde 2010 en adelante, el dominio de los protocolos de propósito general se ha movido para abordar las mejoras de eficiencia de los protocolos con aplicaciones prácticas en mente. Se han propuesto protocolos cada vez más eficientes para MPC, y MPC ahora se puede considerar como una solución práctica para varios problemas de la vida real (especialmente aquellos que solo requieren el intercambio lineal de los secretos y principalmente operaciones locales en las acciones con pocas interacciones entre las partes. ), como la votación distribuida, las licitaciones y subastas privadas, el intercambio de funciones de firma o descifrado y la recuperación de información privada . La primera aplicación práctica y a gran escala de la computación multipartita (demostrada en un problema de subasta real) tuvo lugar en Dinamarca en enero de 2008. Obviamente, se necesitan nociones e investigaciones teóricas y construcciones aplicadas (por ejemplo, condiciones para mover MPC a parte del día a día del negocio fue defendido y presentado en).

Definición y descripción general

En una MPC, un número dado de los participantes, p ₁ , p ₂ , ..., p _N , cada uno tiene los datos privados , respectivamente d ₁ , d ₂ , ..., D _N . Los participantes quieren calcular el valor de una función pública en esos datos privados: F (d ₁ , d ₂ , ..., d _N ) mientras mantienen en secreto sus propias entradas.

Por ejemplo, suponga que tenemos tres partes, Alice, Bob y Charlie, con las respectivas entradas x, yyz que denotan sus salarios. Quieren averiguar cuál es el salario más alto de los tres, sin revelarse entre sí cuánto gana cada uno de ellos. Matemáticamente, esto se traduce en computación:

F (x, y, z) = max (x, y, z)

Si hubiera alguien externo de confianza (digamos, tenían un amigo en común, Tony, que sabían que podía guardar un secreto), cada uno podría decirle su salario a Tony, él podría calcular el máximo y decirle ese número a todos ellos. El objetivo de MPC es diseñar un protocolo en el que, al intercambiar mensajes solo entre ellos, Alice, Bob y Charlie aún puedan aprender F (x, y, z) sin revelar quién hace qué y sin tener que depender de Tony. No deberían aprender más al participar en su protocolo de lo que aprenderían al interactuar con un Tony incorruptible y perfectamente digno de confianza.

En particular, todo lo que las partes pueden aprender es lo que pueden aprender de los resultados y de sus propias aportaciones. Así en el ejemplo anterior, si la salida es z , entonces aprende Charlie que su z es el valor máximo, mientras que Alice y Bob aprenden (si x , y y z son distintos), que su entrada no es igual al máximo, y que el máximo retenido es igual a z . El escenario básico se puede generalizar fácilmente para que las partes tengan varias entradas y salidas, y la función genere diferentes valores para diferentes partes.

Hablando informalmente, las propiedades más básicas que un protocolo de computación multipartita pretende asegurar son:

• Privacidad de entrada: No se puede inferir información sobre los datos privados en poder de las partes a partir de los mensajes enviados durante la ejecución del protocolo. La única información que se puede inferir sobre los datos privados es la que se pueda inferir al ver la salida de la función únicamente.
• Corrección: Cualquier subconjunto adecuado de partes colusorias contradictorias que estén dispuestas a compartir información o desviarse de las instrucciones durante la ejecución del protocolo no debería poder obligar a las partes honestas a generar un resultado incorrecto. Este objetivo de corrección se presenta en dos formas: o las partes honestas tienen la garantía de calcular la salida correcta (un protocolo "robusto") o abortan si encuentran un error (un protocolo MPC "con aborto").

Existe una amplia gama de aplicaciones prácticas, que van desde tareas simples como lanzar una moneda a otras más complejas como subastas electrónicas (por ejemplo, calcular el precio de compensación del mercado), votación electrónica o minería de datos para preservar la privacidad. Un ejemplo clásico es el problema de los millonarios: dos millonarios quieren saber quién es más rico, de tal manera que ninguno de los dos conoce el valor neto del otro. Una solución a esta situación es esencialmente evaluar de forma segura la función de comparación.

Definiciones de seguridad

Un protocolo de computación de múltiples partes debe ser seguro para ser efectivo. En la criptografía moderna, la seguridad de un protocolo está relacionada con una prueba de seguridad. La prueba de seguridad es una prueba matemática en la que la seguridad de un protocolo se reduce a la seguridad de sus primitivas subyacentes. Sin embargo, no siempre es posible formalizar la verificación de seguridad del protocolo criptográfico en base al conocimiento de la parte y la corrección del protocolo. Para los protocolos MPC, el entorno en el que opera el protocolo está asociado con el Paradigma Mundo Real / Mundo Ideal. No se puede decir que las partes no aprendan nada, ya que necesitan aprender el resultado de la operación, y el resultado depende de las entradas. Además, la corrección de la salida no está garantizada, ya que la corrección de la salida depende de las entradas de las partes, y se debe suponer que las entradas están dañadas.

El Paradigma Mundo Real / Mundo Ideal establece dos mundos: (i) En el modelo del mundo ideal, existe una parte de confianza incorruptible a quien cada participante del protocolo envía su entrada. Esta parte de confianza calcula la función por sí misma y envía el resultado apropiado a cada parte. (ii) Por el contrario, en el modelo del mundo real, no hay una parte de confianza y todo lo que las partes pueden hacer es intercambiar mensajes entre sí. Se dice que un protocolo es seguro si uno no puede aprender más sobre las aportaciones privadas de cada parte en el mundo real de lo que podría aprender en el mundo ideal. En el mundo ideal, no se intercambian mensajes entre las partes, por lo que los mensajes intercambiados en el mundo real no pueden revelar ninguna información secreta.

El paradigma del mundo real / mundo ideal proporciona una simple abstracción de las complejidades de MPC para permitir la construcción de una aplicación con el pretexto de que el protocolo MPC en su núcleo es en realidad una ejecución ideal. Si la aplicación es segura en el caso ideal, también lo es cuando se ejecuta un protocolo real.

Los requisitos de seguridad de un protocolo MPC son estrictos. No obstante, en 1987 se demostró que cualquier función puede ser computada de forma segura, con seguridad para adversarios malintencionados y los demás trabajos iniciales mencionados anteriormente. A pesar de estas publicaciones, MPC no fue diseñado para ser lo suficientemente eficiente como para usarse en la práctica en ese momento. El MPC incondicional o teóricamente seguro de la información está estrechamente relacionado y se basa en el problema del intercambio de secretos y, más específicamente, el intercambio de secretos verificables (VSS), que muchos protocolos MPC seguros utilizan contra adversarios activos.

A diferencia de las aplicaciones criptográficas tradicionales, como el cifrado o la firma, se debe asumir que el adversario en un protocolo MPC es uno de los jugadores que participan en el sistema (o que controlan las partes internas). Esa parte o partes corruptas pueden coludirse para violar la seguridad del protocolo. Sea el número de partes en el protocolo y el número de partes que pueden ser contradictorias. Los protocolos y soluciones para el caso de (es decir, cuando se asume una mayoría honesta) son diferentes de aquellos en los que no se hace tal suposición. Este último caso incluye el caso importante del cómputo de dos partes donde uno de los participantes puede estar corrompido, y el caso general donde un número ilimitado de participantes está corrompido y se confabula para atacar a los participantes honestos. ${\ Displaystyle n}$${\ Displaystyle t}$${\ Displaystyle t <n / 2}$

Los adversarios a los que se enfrentan los diferentes protocolos se pueden clasificar de acuerdo con su voluntad de desviarse del protocolo. Básicamente, hay dos tipos de adversarios, cada uno de los cuales da lugar a diferentes formas de seguridad (y cada uno encaja en diferentes escenarios del mundo real):

• Seguridad semihonesta (pasiva): en este caso, se supone que las partes corruptas simplemente cooperan para recopilar información del protocolo, pero no se desvían de la especificación del protocolo. Este es un modelo de adversario ingenuo, que proporciona una seguridad débil en situaciones reales. Sin embargo, los protocolos que logran este nivel de seguridad evitan la filtración involuntaria de información entre partes (que de otro modo colaborarían) y, por lo tanto, son útiles si esta es la única preocupación. Además, los protocolos del modelo semi-honesto son bastante eficientes y, a menudo, son un primer paso importante para lograr niveles más altos de seguridad.
• Seguridad maliciosa (activa): en este caso, el adversario puede desviarse arbitrariamente de la ejecución del protocolo en su intento de hacer trampa. Los protocolos que logran seguridad en este modelo proporcionan una garantía de seguridad muy alta. En el caso de la mayoría de las partes que se portan mal: Lo único que puede hacer un adversario en el caso de una mayoría deshonesta es hacer que las partes honestas “aborten” habiendo detectado trampas. Si las partes honestas obtienen resultados, se les garantiza que es correcto. Siempre se preserva su privacidad.

La seguridad contra adversarios activos generalmente conduce a una reducción de la eficiencia que conduce a la seguridad encubierta, una forma relajada de seguridad activa. La seguridad encubierta captura situaciones más realistas, en las que los adversarios activos están dispuestos a hacer trampa, pero solo si no los atrapan. Por ejemplo, su reputación podría dañarse, impidiendo la colaboración futura con otras partes honestas. Por lo tanto, los protocolos que son seguros de manera encubierta proporcionan mecanismos para garantizar que, si algunas de las partes no siguen las instrucciones, se notará con alta probabilidad, digamos 75% o 90%. En cierto modo, los adversarios encubiertos son aquellos que se ven obligados a actuar pasivamente debido a preocupaciones externas no criptográficas (por ejemplo, comerciales). Este mecanismo establece un puente entre ambos modelos con la esperanza de encontrar protocolos que sean lo suficientemente eficientes y seguros en la práctica.

Como muchos protocolos criptográficos , la seguridad de un protocolo MPC puede basarse en diferentes supuestos:

• Puede ser computacional (es decir, basado en algún problema matemático, como la factorización) o incondicional, es decir, depender de la indisponibilidad física de los mensajes en los canales (generalmente con alguna probabilidad de error que puede hacerse arbitrariamente pequeña).
• El modelo podría suponer que los participantes usan una red sincronizada , donde un mensaje enviado en un "tick" siempre llega al siguiente "tick", o que existe un canal de transmisión seguro y confiable, o que existe un canal de comunicación seguro entre cada par de participantes donde un adversario no puede leer, modificar o generar mensajes en el canal, etc.

El conjunto de partes honestas que pueden ejecutar una tarea computacional está relacionado con el concepto de estructura de acceso . Las estructuras del adversario pueden ser estáticas, donde el adversario elige a sus víctimas antes del inicio del cálculo multipartidista, o dinámicas, donde elige a sus víctimas durante el curso de la ejecución del cálculo multipartidista, lo que dificulta la defensa. Una estructura de adversario se puede definir como una estructura de umbral o como una estructura más compleja. En una estructura de umbral, el adversario puede corromper o leer la memoria de varios participantes hasta cierto umbral. Mientras tanto, en una estructura compleja puede afectar a ciertos subconjuntos predefinidos de participantes, modelando diferentes posibles colusiones.

Protocolos

Existen grandes diferencias entre los protocolos propuestos para el cálculo de dos partes (2PC) y el cálculo de múltiples partes (MPC). Además, a menudo para protocolos de importancia especial se debe diseñar un protocolo especializado que se desvíe de los genéricos (votaciones, subastas, pagos, etc.)

Computación bipartita

La configuración de dos partes es particularmente interesante, no solo desde la perspectiva de las aplicaciones, sino también porque se pueden aplicar técnicas especiales en la configuración de dos partes que no se aplican en el caso de múltiples partes. De hecho, el cálculo seguro de múltiples partes (de hecho, el caso restringido de la evaluación de funciones seguras, donde solo se evalúa una única función) se presentó por primera vez en la configuración de dos partes. El trabajo original se cita a menudo como perteneciente a uno de los dos artículos de Yao; aunque los documentos en realidad no contienen lo que ahora se conoce como el protocolo de circuito distorsionado de Yao .

El protocolo básico de Yao es seguro contra adversarios semi-honestos y es extremadamente eficiente en términos de número de rondas, que es constante e independiente de la función objetivo que se evalúa. La función se ve como un circuito booleano, con entradas en binario de longitud fija. Un circuito booleano es una colección de puertas conectadas con tres tipos diferentes de cables: cables de entrada de circuito, cables de salida de circuito y cables intermedios. Cada puerta recibe dos cables de entrada y tiene un solo cable de salida que puede desplegarse (es decir, pasar a múltiples puertas en el siguiente nivel). La evaluación simple del circuito se realiza evaluando cada puerta por turno; suponiendo que las puertas se hayan ordenado topológicamente. La puerta se representa como una tabla de verdad de modo que para cada posible par de bits (los que provienen de la puerta de los cables de entrada) la tabla asigna un bit de salida único; que es el valor del cable de salida de la puerta. Los resultados de la evaluación son los bits obtenidos en los cables de salida del circuito.

Yao explicó cómo distorsionar un circuito (ocultar su estructura) para que dos partes, emisor y receptor, puedan aprender la salida del circuito y nada más. En un nivel alto, el emisor prepara el circuito distorsionado y lo envía al receptor, quien sin darse cuenta evalúa el circuito, aprendiendo las codificaciones correspondientes tanto a su salida como a la del emisor. Luego, simplemente devuelve las codificaciones del remitente, lo que permite que el remitente calcule su parte de la salida. El remitente envía el mapeo de las codificaciones de salida del receptor a bits al receptor, lo que permite que el receptor obtenga su salida.

Con más detalle, el circuito distorsionado se calcula como sigue. El ingrediente principal es un esquema de cifrado simétrico de doble clave. Dada una puerta del circuito, cada valor posible de sus cables de entrada (0 o 1) se codifica con un número aleatorio (etiqueta). Los valores resultantes de la evaluación de la puerta en cada uno de los cuatro posibles pares de bits de entrada también se reemplazan con etiquetas aleatorias. La tabla de verdad distorsionada de la puerta consta de cifrados de cada etiqueta de salida utilizando sus etiquetas de entrada como claves. La posición de estos cuatro cifrados en la tabla de verdad es aleatoria, por lo que no se filtra información sobre la puerta.

Para evaluar correctamente cada puerta confusa, el esquema de cifrado tiene las siguientes dos propiedades. En primer lugar, los rangos de la función de cifrado bajo dos claves distintas son inconexos (con una probabilidad abrumadora). La segunda propiedad dice que se puede verificar de manera eficiente si un texto cifrado determinado se ha cifrado con una clave determinada. Con estas dos propiedades, el receptor, después de obtener las etiquetas para todos los cables de entrada del circuito, puede evaluar cada puerta averiguando primero cuál de los cuatro textos cifrados se ha cifrado con sus claves de etiqueta, y luego descifrando para obtener la etiqueta del cable de salida. . Esto se hace de manera inconsciente, ya que todo lo que el receptor aprende durante la evaluación son codificaciones de los bits.

Los bits de entrada del remitente (es decir, los creadores de circuitos) pueden enviarse simplemente como codificaciones al evaluador; mientras que las codificaciones del receptor (es decir, los evaluadores de circuitos) correspondientes a sus bits de entrada se obtienen mediante un protocolo de transferencia ajena (OT) 1 de 2 . Un protocolo OT 1-de-2, permite al remitente, en posesión de dos valores C1 y C2, enviar el solicitado por el receptor (valor ba en {1,2}) de tal forma que el remitente lo haga no sabe qué valor se ha transferido, y el receptor solo aprende el valor consultado.

Si uno está considerando adversarios malintencionados, es necesario proporcionar más mecanismos para garantizar el comportamiento correcto de ambas partes. Por construcción, es fácil mostrar seguridad para el remitente si el protocolo OT ya es seguro contra un adversario malintencionado, ya que todo lo que el receptor puede hacer es evaluar un circuito distorsionado que no alcanzaría los cables de salida del circuito si se desviara de las instrucciones. . La situación es muy diferente por parte del remitente. Por ejemplo, puede enviar un circuito confuso incorrecto que calcula una función que revela la entrada del receptor. Esto significaría que la privacidad ya no se mantiene, pero dado que el circuito está distorsionado, el receptor no podría detectarlo. Sin embargo, es posible aplicar de manera eficiente pruebas de conocimiento cero para que este protocolo sea seguro contra adversarios malintencionados con una pequeña sobrecarga en comparación con el protocolo semi-honesto.

Protocolos multipartitos

La mayoría de los protocolos MPC, a diferencia de los protocolos 2PC y especialmente bajo la configuración incondicional de canales privados, utilizan el intercambio secreto. En los métodos basados ​​en el intercambio secreto, las partes no juegan papeles especiales (como en Yao, de creador y evaluador). En cambio, los datos asociados con cada cable se comparten entre las partes y luego se usa un protocolo para evaluar cada puerta. La función ahora se define como un "circuito" sobre un campo finito, a diferencia de los circuitos binarios utilizados para Yao. En la literatura, dicho circuito se denomina circuito aritmético y consta de “puertas” de suma y multiplicación en las que los valores sobre los que se opera se definen en un campo finito.

El intercambio de secretos le permite a uno distribuir un secreto entre varias partes al distribuir acciones a cada parte. Se utilizan comúnmente dos tipos de esquemas de intercambio secreto; Compartir secretos de Shamir y compartir secretos aditivos. En ambos casos, las acciones son elementos aleatorios de un campo finito que se suman al secreto del campo; intuitivamente, la seguridad se logra porque cualquier conjunto de acciones no calificado parece distribuido aleatoriamente.

Los esquemas de intercambio secreto pueden tolerar que un adversario controle hasta t partes de un total de n , donde t varía según el esquema, el adversario puede ser pasivo o activo, y se hacen diferentes suposiciones sobre el poder del adversario. El esquema de intercambio de secretos de Shamir es seguro contra un adversario pasivo cuando y un adversario activo cuando logra la seguridad de la teoría de la información, lo que significa que incluso si el adversario tiene un poder computacional ilimitado, no puede aprender ninguna información sobre el secreto subyacente a una acción. El protocolo BGW, que define cómo calcular la suma y la multiplicación de los recursos compartidos secretos, se utiliza a menudo para calcular funciones con los recursos compartidos secretos de Shamir. Los esquemas aditivos de intercambio de secretos pueden tolerar que el adversario controle a todas las partes menos una, es decir , mientras mantiene la seguridad contra un adversario pasivo y activo con un poder computacional ilimitado. Algunos protocolos requieren una fase de configuración, que solo puede ser segura contra un adversario limitado computacionalmente. ${\ Displaystyle t <{\ frac {n} {2}}}$${\ Displaystyle t <{\ frac {n} {3}}}$${\ Displaystyle t <n}$

Varios sistemas han implementado varias formas de MPC con esquemas de intercambio secreto. El más popular es SPDZ, que implementa MPC con acciones secretas aditivas y es seguro contra adversarios activos.

Otros protocolos

En 2014, se describió un "modelo de equidad en el cálculo seguro en el que una parte contraria que aborta al recibir la salida se ve obligada a pagar una multa monetaria mutuamente predefinida" para la red Bitcoin o para la lotería justa.

Prácticos sistemas MPC

Se han realizado muchos avances en los sistemas 2PC y MPC en los últimos años.

Protocolos basados ​​en Yao

Uno de los principales problemas al trabajar con protocolos basados ​​en Yao es que la función que se va a evaluar de forma segura (que podría ser un programa arbitrario) debe representarse como un circuito, que generalmente consta de puertas XOR y AND. Dado que la mayoría de los programas del mundo real contienen bucles y estructuras de datos complejas, esta no es una tarea trivial. El sistema Fairplay fue la primera herramienta diseñada para abordar este problema. Fairplay consta de dos componentes principales. El primero de ellos es un compilador que permite a los usuarios escribir programas en un lenguaje simple de alto nivel y generar estos programas en una representación de circuito booleano. El segundo componente puede entonces distorsionar el circuito y ejecutar un protocolo para evaluar de forma segura el circuito distorsionado. Además del cálculo de dos partes basado en el protocolo de Yao, Fairplay también puede llevar a cabo protocolos de múltiples partes. Esto se hace usando el protocolo BMR, que extiende el protocolo pasivamente seguro de Yao al caso activo.

En los años posteriores a la introducción de Fairplay, se han creado muchas mejoras en el protocolo básico de Yao, en forma de mejoras de eficiencia y técnicas de seguridad activa. Estos incluyen técnicas como el método XOR libre, que permite una evaluación mucho más simple de las puertas XOR, y la reducción de filas distorsionadas, reduciendo el tamaño de las tablas distorsionadas con dos entradas en un 25%.

El enfoque que hasta ahora parece ser el más fructífero en la obtención de seguridad activa proviene de una combinación de la técnica de distorsión y el paradigma de “cortar y elegir”. Esta combinación parece hacer construcciones más eficientes. Para evitar los problemas antes mencionados con respecto a la conducta deshonesta, se envían muchos destellos del mismo circuito del constructor al evaluador. Luego, aproximadamente la mitad de ellos (dependiendo del protocolo específico) se abren para verificar la consistencia y, de ser así, la gran mayoría de los que no están abiertos son correctos con una alta probabilidad. El resultado es el voto mayoritario de todas las evaluaciones. Tenga en cuenta que aquí se necesita la salida mayoritaria. Si hay desacuerdo en las salidas, el receptor sabe que el remitente está haciendo trampa, pero no puede quejarse, ya que de lo contrario esto filtraría información sobre su entrada.

Este enfoque de seguridad activa fue iniciado por Lindell y Pinkas. Esta técnica fue implementada por Pinkas et al. en 2009, esto proporcionó la primera evaluación de dos partes activamente segura del circuito estándar de cifrado avanzado (AES), considerado una función no trivial altamente compleja (que consta de alrededor de 30,000 puertas AND y XOR) (también con algunas aplicaciones potenciales) , lo que toma alrededor de 20 minutos para calcular y requiere 160 circuitos para obtener una probabilidad de trampa. ${\ Displaystyle 2 ^ {- 40}}$

Como se evalúan muchos circuitos, las partes (incluido el receptor) deben comprometerse con sus entradas para garantizar que en todas las iteraciones se utilicen los mismos valores. Los experimentos de Pinkas et al. informaron muestran que el cuello de botella del protocolo radica en las comprobaciones de coherencia. Tuvieron que enviar por la red alrededor de 6.553.600 compromisos a varios valores para evaluar el circuito AES. En resultados recientes, la eficiencia de las implementaciones basadas en Yao activamente seguras se mejoró aún más, requiriendo solo 40 circuitos, y mucho menos compromisos, para obtener la probabilidad de hacer trampa. Las mejoras provienen de nuevas metodologías para realizar cortar y elegir en los circuitos transmitidos. ${\ Displaystyle 2 ^ {- 40}}$

Más recientemente, se ha centrado en implementaciones altamente paralelas basadas en circuitos confusos, diseñados para ejecutarse en CPU con muchos núcleos. Kreuter y col. describen una implementación que se ejecuta en 512 núcleos de una potente computadora en clúster. Usando estos recursos, pudieron evaluar la función de distancia de edición de 4095 bits , cuyo circuito comprende casi 6 mil millones de puertas. Para lograr esto, desarrollaron un compilador de circuitos personalizado y mejor optimizado que Fairplay y varias optimizaciones nuevas, como la canalización, mediante la cual la transmisión del circuito distorsionado a través de la red comienza mientras el resto del circuito aún se está generando. El tiempo para calcular AES se redujo a 1,4 segundos por bloque en el caso activo, utilizando una máquina de clúster de 512 nodos, y 115 segundos utilizando un nodo. Shelat y Shen mejoran esto, utilizando hardware básico, a 0,52 segundos por bloque. El mismo documento informa sobre un rendimiento de 21 bloques por segundo, pero con una latencia de 48 segundos por bloque.

Mientras tanto, otro grupo de investigadores ha investigado el uso de GPU de nivel de consumidor para lograr niveles similares de paralelismo. Utilizan extensiones OT y algunas otras técnicas novedosas para diseñar su protocolo específico de GPU. Este enfoque parece lograr una eficiencia comparable a la implementación de la computación en clúster, utilizando un número similar de núcleos. Sin embargo, los autores solo informan sobre una implementación del circuito AES, que tiene alrededor de 50.000 puertas. Por otro lado, el hardware requerido aquí es mucho más accesible, ya que es posible que ya se encuentren dispositivos similares en las computadoras de escritorio o consolas de juegos de muchas personas. Los autores obtienen un tiempo de 2,7 segundos por bloque AES en un escritorio estándar, con una GPU estándar. Si permiten que la seguridad disminuya a algo parecido a la seguridad encubierta, obtienen un tiempo de ejecución de 0,30 segundos por bloque AES. En el caso de la seguridad pasiva hay informes de procesamiento de circuitos con 250 millones de puertas, ya una tasa de 75 millones de puertas por segundo.

Ver también

• Moneda digital
• Cifrado homomórfico
• Póquer mental
• Protocolo de intercambio justo multipartidista
• Transferencia ajena
• Geometría computacional que preserva la privacidad
• El problema de los millonarios de Yao

Referencias

enlaces externos

• Una descripción simple del problema del millonario
• Enlaces de Helger Lipmaa sobre computación multipartita
• Nick Szabo, "Los protocolos de Dios" en la Wayback Machine (archivado el 30 de diciembre de 2006)
• EMP-toolkit - Kit de herramientas de cálculo multipartito eficiente. Incluye la implementación de primitivas MPC básicas, así como protocolos con seguridad semihonesta y maliciosa.
• Solucionadores de CSP distribuidos seguros (DisCSP) : una aplicación web con un intérprete de subprograma para diseñar y ejecutar su propio cómputo multiparte seguro y completo (basado en el lenguaje declarativo SMC). Utiliza sistemas de evaluación de circuitos aritméticos seguros y redes mixtas.
• VMCrypt Una biblioteca de Java para un cálculo seguro escalable. Por Lior Malka.
• The Fairplay Project : incluye un paquete de software para el cálculo seguro de dos partes, donde la función se define utilizando un lenguaje de descripción de funciones de alto nivel y se evalúa utilizando el protocolo de Yao para la evaluación segura de circuitos booleanos.
• El proyecto SIMAP ; Secure Information Management and Processing (SIMAP) es un proyecto patrocinado por la Agencia Nacional de Investigación Danesa destinado a implementar la Computación Segura Multiparte.
• Secure Multiparty Computation Language : proyecto para el desarrollo de un 'lenguaje de programación específico de dominio para el cálculo seguro de múltiples partes' y el tiempo de ejecución criptográfico asociado.
• VIFF: Virtual Ideal Functionality Framework - Marco para cálculos asincrónicos de múltiples partes (código disponible bajo LGPL ). Ofrece aritmética con valores compartidos secretos, incluida una comparación segura.
• MPyC : Computación multipartita segura en Python (y cuadernos de Jupyter ): paquete de código abierto para MPC que utiliza un tipo personalizado de corrutinas de Python, que admite aplicaciones avanzadas como árboles de decisión ID3, programación lineal, redes neuronales CNN / MLP, AES, unidireccional cadenas de hachís y muchas más. Lanzado en mayo de 2018.
• SCALE-MAMBA MPC: Algoritmos de cálculo seguro de LEuven - Marco para varios protocolos MPC, incluida la familia SPDZ (código disponible bajo BSD ). Ofrece aritmética con valores compartidos secretos que incluyen comparación segura y soporte para aritmética de coma fija y coma flotante.
• Sharemind: analice datos confidenciales sin comprometer la privacidad : una máquina virtual distribuida con la capacidad de ejecutar operaciones que preservan la privacidad. Tiene un lenguaje de programación que preserva la privacidad para herramientas de minería de datos. Incluye herramientas de desarrollo.
• MPCLib: biblioteca de computación multipartita: una biblioteca escrita en C # y C ++ que implementa varios bloques de construcción necesarios para implementar protocolos de computación seguros de múltiples partes. MPCLib tiene un motor de simulación de eventos discretos que se puede utilizar para simular protocolos MPC en redes virtuales.
• Fiestas virtuales en SMC Un protocolo para fiestas virtuales en SMC (cálculo seguro de múltiples partes)
• Implementación basada en Java MPC Una implementación basada en Java del protocolo MPC basada en el teorema de Michael.B, Shafi.G y Avi.W ("Teoremas de completitud para el cálculo distribuido no criptográfico tolerante a fallas") con código de corrección de errores de Welch-Berlekamp algoritmo a códigos BCH. Soporta múltiples jugadores e identificación de "tramposos" con protocolo bizantino. Por Erez Alon, Doron Friedland y Yael Smith.
• SEPIA Una biblioteca java para SMC que utiliza el intercambio secreto. Las operaciones básicas están optimizadas para un gran número de invocaciones paralelas (código disponible bajo la LGPL ).
• Introducción a SMC en GitHub
• Myst Project : subprograma JavaCard que implementa la generación, firma y descifrado de claves multiparte seguras.
• Bibliografía esencial Computación multipartita segura