stringtranslate.com

Computación segura entre múltiples partes

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

Las bases para la computación multipartita segura comenzaron a fines de la década de 1970 con el trabajo sobre el póquer mental, un trabajo criptográfico que simula tareas de juego/computación a distancia sin requerir un tercero de confianza. Tradicionalmente, la criptografía consistía en ocultar contenido, mientras que este nuevo tipo de computación y protocolo trata de ocultar información parcial sobre los datos mientras se computa con los datos de muchas fuentes y se producen resultados correctos. A fines de la década de 1980, Michael Ben-Or, Shafi Goldwasser y Avi Wigderson, e independientemente David Chaum, Claude Crépeau e Ivan Damgård, habían publicado artículos que mostraban "cómo calcular de forma segura cualquier función en el entorno de canales seguros".

Historia

Los protocolos de propósito especial para tareas específicas comenzaron a fines de la década de 1970. [2] 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 . [3] [4] El área también se conoce como Evaluación de Función Segura (SFE). El caso de dos partes fue seguido por una generalización al multipartidismo por Oded Goldreich, Silvio Micali y Avi Wigderson. El cálculo se basa en compartir en secreto todas las entradas y pruebas de conocimiento cero para un caso potencialmente malicioso, donde la mayoría de los jugadores honestos en el caso del adversario malicioso aseguran que se detecte el mal comportamiento y el cálculo continúa con la persona deshonesta eliminada o su entrada revelada. Este trabajo sugirió el esquema general básico que deben seguir esencialmente todos los futuros protocolos multipartidarios para la computación segura. [5] Este trabajo introdujo un enfoque, conocido como paradigma GMW, para compilar un protocolo de computación multipartidaria que es seguro contra adversarios semi-honestos a un protocolo que es seguro contra adversarios maliciosos. Este trabajo fue seguido por el primer protocolo seguro robusto que tolera el comportamiento defectuoso con gracia sin revelar la salida de nadie a través de un trabajo que inventó para este propósito la idea de "participación de acciones" [6] utilizada a menudo y un protocolo que permite a una de las partes ocultar su entrada incondicionalmente. [7] El paradigma GMW se consideró ineficiente durante años debido a los enormes gastos generales que aporta al protocolo base. Sin embargo, se demuestra que es posible lograr protocolos eficientes, [8] y hace que esta línea de investigación sea aún más interesante desde una perspectiva práctica. Los resultados anteriores se encuentran en un modelo donde el adversario está limitado a cálculos de tiempo polinomial y observa todas las comunicaciones, y por lo tanto el modelo se llama "modelo computacional". Además, se demostró que el protocolo de transferencia inconsciente es completo para estas tareas. [9] Los resultados anteriores establecen que es posible, bajo las variaciones mencionadas, lograr un cálculo seguro cuando la mayoría de los usuarios son honestos.

La siguiente cuestión 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 con mal comportamiento y maliciosas, y las soluciones no aplican herramientas criptográficas (ya que la comunicación segura está disponible). [10] [11] Agregar un canal de transmisión permite que el sistema tolere hasta la mitad de la minoría con mal comportamiento, [12] mientras que las restricciones de conectividad en el gráfico de comunicación se investigaron en el libro Transmisión de mensajes perfectamente segura. [13]

Con el paso de los años, el concepto de protocolos multipartidarios de propósito general se convirtió en un área fértil para investigar cuestiones básicas y generales sobre las propiedades de los protocolos, como la componibilidad universal o el adversario móvil , como en el intercambio proactivo de secretos . [14]

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 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 puede considerarse como una solución práctica para varios problemas de la vida real (especialmente aquellos que solo requieren compartir linealmente los secretos y principalmente operaciones locales en las acciones sin muchas interacciones entre las partes), como votación distribuida, pujas y subastas privadas, compartir funciones de firma o descifrado y recuperación de información privada . [15] La primera aplicación práctica y a gran escala de la computación multipartidaria fue la ejecución de una subasta doble electrónica en la Subasta de remolacha azucarera danesa , que tuvo lugar en enero de 2008. [16] Obviamente, se necesitan nociones e investigaciones teóricas y construcciones aplicadas (por ejemplo, las condiciones para mover MPC a parte de los negocios diarios se defendieron y presentaron en [17] ).

En 2020, varias empresas que trabajan con computación multipartita segura fundaron la alianza MPC con el objetivo de "acelerar el conocimiento, la aceptación y la adopción de la tecnología MPC".

Definición y descripción general

En un MPC, un número determinado de participantes, p 1 , p 2 , ..., p N , tienen cada uno datos privados , respectivamente d 1 , d 2 , ..., d N . Los participantes quieren calcular el valor de una función pública sobre esos datos privados: F(d 1 , d 2 , ..., d N ) mientras mantienen sus propias entradas en secreto.

Por ejemplo, supongamos que tenemos tres partes: Alice, Bob y Charlie, con entradas x, y y z que representan sus respectivos salarios. Quieren averiguar cuál es el salario más alto de los tres, sin revelarse mutuamente cuánto gana cada uno. Matemáticamente, esto se traduce en que deben calcular:

F(x, y, z) = máx(x, y, z)

Si hubiera una parte externa de confianza (por ejemplo, si tuvieran un amigo en común, Tony, del que supieran que podía guardar un secreto), cada uno de ellos podría decirle a Tony cuál es su salario, él podría calcular el máximo y decirles esa cifra a todos ellos. El objetivo de MPC es diseñar un protocolo en el que, intercambiando mensajes únicamente entre ellos, Alice, Bob y Charlie puedan aprender F(x, y, z) sin revelar quién gana 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 confiable.

En particular, todo lo que las partes pueden aprender es lo que pueden aprender de la salida y de su propia entrada. Así, en el ejemplo anterior, si la salida es z , Charlie aprende 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 obtenido es igual a z . El escenario básico se puede generalizar fácilmente a un caso en el que las partes tienen varias entradas y salidas, y la función genera diferentes valores para diferentes partes.

Hablando de manera informal, las propiedades más básicas que un protocolo de computación multipartito pretende garantizar son:

Existen numerosas aplicaciones prácticas, que van desde tareas sencillas como el lanzamiento de una moneda hasta otras más complejas como las subastas electrónicas (por ejemplo, calcular el precio de equilibrio del mercado), la votación electrónica o la minería de datos que preserva 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 ellos conozca el patrimonio neto del otro. Una solución a esta situación es, en esencia, evaluar de forma segura la función de comparación.

Definiciones de seguridad

Un protocolo de computación multipartidaria 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 donde la seguridad de un protocolo se reduce a la seguridad de sus primitivos subyacentes. Sin embargo, no siempre es posible formalizar la verificación de seguridad del protocolo criptográfico en función del conocimiento de las partes y la corrección del protocolo. Para los protocolos MPC, el entorno en el que opera el protocolo está asociado con el paradigma del mundo real/mundo ideal. [18] 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 del resultado no está garantizada, ya que la corrección del resultado depende de las entradas de las partes, y se debe asumir que las entradas son correctas.

El paradigma del mundo real/mundo ideal plantea dos mundos: (i) En el modelo del mundo ideal, existe una parte confiable incorruptible a la que cada participante del protocolo envía su entrada. Esta parte confiable calcula la función por sí misma y envía de vuelta la salida apropiada a cada parte. (ii) Por el contrario, en el modelo del mundo real, no hay una parte confiable y todo lo que las partes pueden hacer es intercambiar mensajes entre sí. Se dice que un protocolo es seguro si no se puede aprender más sobre las entradas privadas de cada parte en el mundo real de lo que se 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 ofrece una abstracción simple de las complejidades de MPC para permitir la construcción de una aplicación bajo la premisa 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, entonces también es segura cuando se ejecuta un protocolo real en su lugar.

Los requisitos de seguridad de un protocolo MPC son estrictos. No obstante, en 1987 se demostró que cualquier función puede calcularse de forma segura, con seguridad para adversarios maliciosos [5] y los otros trabajos iniciales mencionados anteriormente. A pesar de estas publicaciones, MPC no fue diseñado para ser lo suficientemente eficiente como para ser utilizado en la práctica en ese momento. El MPC incondicionalmente seguro 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 suponer que el adversario en un protocolo MPC es uno de los participantes del sistema (o partes internas que lo controlan). 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 adversarias. Los protocolos y soluciones para el caso de (es decir, cuando se supone 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 corrupto, y el caso general donde un número ilimitado de participantes están corruptos y coludidos para atacar a los participantes honestos.

Los adversarios a los que se enfrentan los distintos protocolos se pueden clasificar según su disposición a 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 se adapta a diferentes escenarios del mundo real):

La seguridad contra adversarios activos suele conducir a una reducción de la eficiencia. La seguridad encubierta [19] es una alternativa que pretende permitir una mayor eficiencia a cambio de debilitar la definición de seguridad; es aplicable a situaciones en las que los adversarios activos están dispuestos a hacer trampa, pero solo si no son descubiertos. Por ejemplo, su reputación podría verse dañada, impidiendo la colaboración futura con otras partes honestas. Por lo tanto, los protocolos que son encubiertamente seguros proporcionan mecanismos para garantizar que, si alguna de las partes no sigue las instrucciones, entonces se notará con alta probabilidad, digamos 75% o 90%. En cierto modo, los adversarios encubiertos son activos 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 depender de diferentes supuestos:

El conjunto de partes honestas que pueden ejecutar una tarea computacional está relacionado con el concepto de estructura de acceso . Las estructuras adversarias pueden ser estáticas, donde el adversario elige a sus víctimas antes del inicio del cómputo multipartidista, o dinámicas, donde elige a sus víctimas durante el curso de la ejecución del cómputo multipartidista, lo que dificulta la defensa. Una estructura adversaria puede definirse 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 un número de participantes hasta cierto umbral. Mientras tanto, en una estructura compleja puede afectar a ciertos subconjuntos predefinidos de participantes, modelando diferentes colusiones posibles.

Protocolos

Existen diferencias importantes entre los protocolos propuestos para la computación entre dos partes (2PC) y la computación entre múltiples partes (MPC). Además, a menudo para protocolos de propósito especial de importancia se debe diseñar un protocolo especializado que se desvíe de los genéricos (votación, subastas, pagos, etc.)

Cálculo entre dos partes

El entorno de dos partes es particularmente interesante, no solo desde una perspectiva de aplicaciones, sino también porque se pueden aplicar técnicas especiales en el entorno de dos partes que no se aplican en el caso de múltiples partes. De hecho, el cálculo multipartito seguro (de hecho, el caso restringido de evaluación de función segura, donde solo se evalúa una única función) se presentó por primera vez en el entorno de dos partes. El trabajo original se cita a menudo como perteneciente a uno de los dos artículos de Yao; [20] aunque los artículos en realidad no contienen lo que ahora se conoce como el protocolo de circuito ilegible 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, pasarse a múltiples puertas en el siguiente nivel). La evaluación simple del circuito se realiza evaluando cada puerta por turno; asumiendo que las puertas han sido ordenadas topológicamente. La puerta se representa como una tabla de verdad de modo que para cada par posible 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, el emisor y el 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 y aprende las codificaciones correspondientes a su salida y a la del emisor. Luego, simplemente envía de vuelta las codificaciones del emisor, lo que permite que el emisor calcule su parte de la salida. El emisor envía la asignación de las codificaciones de salida del receptor a bits al receptor, lo que permite que el receptor obtenga su salida.

En más detalle, el circuito ilegible se calcula de la siguiente manera. 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 (ya sea 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 pares posibles de bits de entrada también se reemplazan con etiquetas aleatorias. La tabla de verdad ilegible 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 ninguna información sobre la puerta.

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

Los bits de entrada del emisor (es decir, los creadores del circuito) se pueden enviar simplemente como codificaciones al evaluador, mientras que las codificaciones del receptor (es decir, los evaluadores del circuito) 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 emisor que posee dos valores C1 y C2 enviar el solicitado por el receptor (un valor en {1,2}) de tal manera que el emisor no sabe qué valor se ha transferido y el receptor solo conoce el valor consultado.

Si se tienen en cuenta adversarios maliciosos, es necesario proporcionar mecanismos adicionales para garantizar el comportamiento correcto de ambas partes. Por construcción, es fácil demostrar la seguridad para el remitente si el protocolo OT ya es seguro contra adversarios maliciosos, ya que todo lo que puede hacer el receptor es evaluar un circuito ilegible que no podría llegar a los cables de salida del circuito si se desviara de las instrucciones. La situación es muy diferente en el lado del remitente. Por ejemplo, puede enviar un circuito ilegible incorrecto que calcule una función que revele la entrada del receptor. Esto significaría que la privacidad ya no se mantiene, pero como el circuito está ilegible, el receptor no podría detectarlo. Sin embargo, es posible aplicar de manera eficiente pruebas de conocimiento cero para hacer que este protocolo sea seguro contra adversarios maliciosos con una pequeña sobrecarga en comparación con el protocolo semihonesto. [8]

Protocolos multipartidistas

La mayoría de los protocolos MPC, a diferencia de los protocolos 2PC y especialmente en la configuración incondicional de canales privados, utilizan el uso compartido de secretos. En los métodos basados ​​en el uso compartido de secretos, las partes no desempeñan funciones especiales (como en Yao, de creador y evaluador). En cambio, los datos asociados con cada cable se comparten entre las partes y luego se utiliza un protocolo para evaluar cada compuerta. La función ahora se define como un "circuito" sobre un campo finito, a diferencia de los circuitos binarios utilizados para Yao. Este tipo de circuito se denomina circuito aritmético en la literatura y consiste en "compuertas" de suma y multiplicación donde los valores sobre los que se opera se definen sobre un campo finito.

El intercambio de secretos permite distribuir un secreto entre varias partes mediante la distribución de partes a cada una de ellas. Se utilizan habitualmente dos tipos de esquemas de intercambio de secretos: el intercambio de secretos Shamir y el intercambio de secretos aditivo. En ambos casos, las partes son elementos aleatorios de un campo finito que se suman al secreto del campo; intuitivamente, se logra la seguridad porque cualquier conjunto de partes que no cumplan los requisitos parece distribuido aleatoriamente.

Los esquemas de compartición de secretos pueden tolerar que un adversario controle hasta t partes de un total de n partes, 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 compartición de secretos Shamir es seguro contra un adversario pasivo cuando y un adversario activo cuando al mismo tiempo que logra una seguridad teórica de la información, lo que significa que incluso si el adversario tiene un poder computacional ilimitado, no puede obtener ninguna información sobre el secreto subyacente a una parte. El protocolo BGW, [21] que define cómo calcular la suma y la multiplicación en partes secretas, se usa a menudo para calcular funciones con partes secretas Shamir. Los esquemas de compartición de secretos aditivos pueden tolerar que el adversario controle a todas las partes menos una, es decir , al mismo tiempo que mantienen 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 computacionalmente limitado.

Varios sistemas han implementado diversas formas de MPC con esquemas de intercambio de secretos. El más popular es SPDZ, [22] que implementa MPC con intercambios de secretos aditivos y es seguro contra adversarios activos.

Otros protocolos

En 2014 se describió un "modelo de equidad en computación segura en el que una parte adversaria que aborta al recibir la salida se ve obligada a pagar una multa monetaria predefinida mutuamente" para la red Bitcoin o para la lotería justa, y se ha implementado con éxito en Ethereum . [23] [24]

Sistemas MPC prácticos

Se han logrado 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 normalmente consta de puertas XOR y AND. Dado que la mayoría de los programas del mundo real contienen bucles y estructuras de datos complejas, se trata de una tarea muy no trivial. El sistema Fairplay [25] 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 sencillo 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 de la computación bipartita basada en el protocolo de Yao, Fairplay también puede llevar a cabo protocolos multipartitos. Esto se hace utilizando el protocolo BMR [25] , que extiende el protocolo pasivo seguro de Yao al caso activo.

En los años posteriores a la introducción de Fairplay, se han realizado muchas mejoras al protocolo básico de Yao, tanto en forma de mejoras de eficiencia como de técnicas de seguridad activa. Estas 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 ilegibles, que reduce el tamaño de las tablas ilegibles con dos entradas en un 25 %. [26]

El enfoque que hasta ahora parece ser el más fructífero para obtener seguridad activa proviene de una combinación de la técnica de garbling y el paradigma de "cortar y elegir". Esta combinación parece generar construcciones más eficientes. Para evitar los problemas antes mencionados con respecto al comportamiento deshonesto, se envían muchos garblings del mismo circuito desde el constructor al evaluador. Luego, alrededor de la mitad de ellos (dependiendo del protocolo específico) se abren para verificar la consistencia y, si es así, una gran mayoría de los no abiertos son correctos con alta probabilidad. El resultado es el voto mayoritario de todas las evaluaciones. Aquí se necesita el resultado mayoritario. Si hay desacuerdo sobre los resultados, el receptor sabe que el remitente está haciendo trampa, pero no puede quejarse porque de lo contrario se filtraría información sobre su entrada.

Este enfoque para la seguridad activa fue iniciado por Lindell y Pinkas. [27] Esta técnica fue implementada por Pinkas et al. en 2009, [26] Esto proporcionó la primera evaluación activamente segura de dos partes del circuito Estándar de cifrado avanzado (AES), considerado como una función no trivial (también con algunas aplicaciones potenciales) altamente compleja (que consta de alrededor de 30 000 puertas AND y XOR), que toma alrededor de 20 minutos para calcularse y requiere 160 circuitos para obtener una probabilidad de trampa.

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. publicados [26] muestran que el cuello de botella del protocolo reside en las comprobaciones de consistencia. Tuvieron que enviar por la red alrededor de 6.553.600 compromisos con varios valores para evaluar el circuito AES. En resultados recientes [28], la eficiencia de las implementaciones basadas en Yao con seguridad activa mejoró aún más, requiriendo solo 40 circuitos y una cantidad mucho menor de compromisos para obtener la probabilidad de engaño. Las mejoras provienen de nuevas metodologías para realizar cortes y elecciones en los circuitos transmitidos.

Más recientemente, se ha puesto el foco en implementaciones altamente paralelas basadas en circuitos ilegibles, diseñados para ejecutarse en CPU con muchos núcleos. Kreuter et al. [29] describen una implementación que se ejecuta en 512 núcleos de un potente ordenador en clúster. Utilizando 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 circuito personalizado, mejor optimizado que Fairplay y varias optimizaciones nuevas, como la canalización, mediante la cual la transmisión del circuito ilegible 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 en clúster de 512 nodos, y 115 segundos utilizando un nodo. Shelat y Shen [30] mejoran esto, utilizando hardware básico, a 0,52 segundos por bloque. El mismo artículo 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. [31] Utilizan extensiones de transferencia inconscientes 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 computación en clúster, utilizando una cantidad 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 una computadora de 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 y a una velocidad de 75 millones de puertas por segundo. [32]

Implementaciones de análisis de datos de computación multipartita segura

Una de las principales aplicaciones de la computación multipartita segura es permitir el análisis de datos en poder de múltiples partes o el análisis ciego de datos por parte de terceros sin permitir que el custodio de los datos comprenda el tipo de análisis de datos que se está realizando.

Sistemas de demostración y producción

Bibliotecas de software

Véase también

Referencias

  1. ^ Evans, David; Kolesnikov, Vladimir; Rosulek, Mike (2018). "Una introducción pragmática a la computación multipartita segura" (PDF) . securecomputation.org . Archivado desde el original (PDF) el 2024-08-12 . Consultado el 19 de octubre de 2024 .
  2. ^ A. Shamir, R. Rivest y L. Adleman, "Mental Poker", Informe técnico LCS/TR-125, Instituto Tecnológico de Massachusetts, abril de 1979.
  3. ^ Andrew C. Yao, Protocolos para cálculos seguros (resumen ampliado)
  4. ^ Andrew Chi-Chih Yao: Cómo generar e intercambiar secretos (resumen ampliado). FOCS 1986: 162-167 [1]
  5. ^ de Oded Goldreich, Silvio Micali, Avi Wigderson: Cómo jugar a cualquier juego mental o Un teorema de completitud para protocolos con mayoría honesta. STOC 1987: 218-229 [2]
  6. ^ Zvi Galil , Stuart Haber, Moti Yung: Computación criptográfica: protocolos seguros tolerantes a fallos y el modelo de clave pública. CRYPTO 1987: 135-155 [3]
  7. ^ David Chaum , Ivan Damgård , Jeroen van de Graaf: Cálculos multipartidarios que garantizan la privacidad de los datos aportados por cada parte y la exactitud del resultado. 87-119 [4]
  8. ^ ab Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de octubre de 2020). "¿Es práctico el paradigma GMW clásico? El caso de 2PC activamente seguro no interactivo". Actas de la Conferencia ACM SIGSAC de 2020 sobre seguridad informática y de las comunicaciones . CCS '20. Evento virtual, EE. UU.: Association for Computing Machinery. págs. 1591–1605. doi :10.1145/3372297.3423366. ISBN 978-1-4503-7089-9. Número de identificación del sujeto  226228208.
  9. ^ Joe Kilian: Fundamentos de la criptografía en la transferencia inconsciente. STOC 1988: 20-31 [5]
  10. ^ D. Chaum, C. Crepeau e I. Damgard. "Protocolos multipartidarios incondicionalmente seguros". Stoc 1988 .
  11. ^ Michael Ben-Or, Shafi Goldwasser, Avi Wigderson: Teoremas de completitud para computación distribuida tolerante a fallas no criptográficas (resumen ampliado). STOC 1988: 1-10
  12. ^ Tal Rabin , Michael Ben-Or: Intercambio de secretos verificables y protocolos multipartidarios con mayoría honesta (resumen ampliado). STOC 1989: 73-85 [6]
  13. ^ Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung: Transmisión de mensajes perfectamente segura. J. ACM 40(1): 17-47 (1993)[7]
  14. ^ Rafail Ostrovsky, Moti Yung: Cómo resistir los ataques de virus móviles. PODC 1991. págs. 51-59 [8]
  15. ^ Claudio Orlandi: ¿Es útil en la práctica el cómputo multipartidista?, ICASSP 2011
  16. ^ Peter Bogetoft , Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach y Tomas Toft (2008). "La computación multipartita se pone en marcha". Archivo ePrint de criptología (Informe 2008/068).{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  17. ^ Moti Yung: Del póquer mental al negocio principal: ¿por qué y cómo implementar protocolos de computación seguros? Conferencia ACM sobre seguridad informática y de comunicaciones 2015: 1-2 https://dl.acm.org/citation.cfm?doid=2810103.2812701
  18. ^ Michael Backes, Birgit Pfitzmann y Michael Waidner. "Un teorema de composición general para sistemas reactivos seguros". En Theory of Cryptography Conference, págs. 336-354. Springer, Berlín, Heidelberg, 2004.
  19. ^ Y. Aumann y Y. Lindell. "Seguridad contra adversarios encubiertos". TCC 2007 .
  20. ^ Andrew C. Yao, "Cómo generar e intercambiar secretos", SFCS '86, Actas del 27º Simposio Anual sobre Fundamentos de la Ciencia de la Computación, págs. 162-167, 1986.
  21. ^ Ben-Or, Michael; Goldwasser, Shafi; Wigderson, Avi (1 de enero de 1988). "Teoremas de completitud para computación distribuida tolerante a fallos no criptográfica". Actas del vigésimo simposio anual de la ACM sobre teoría de la computación - STOC '88 . ACM. págs. 1–10. doi :10.1145/62212.62213. ISBN . 978-0897912648. Número de identificación del sujeto  207554159.
  22. ^ I. Damgård, V. Pastro, N. Smart y S. Zakarias, "Computación multipartita a partir de cifrado algo homomórfico", Crypto 2012, vol. Springer LNCS 7417, págs. 643-662, 2012.
  23. ^ Iddo Bentov, Ranjit Kumaresan (2014). "Cómo usar Bitcoin para diseñar protocolos justos" (PDF) . Cryptology e Print (129): 1–38 . Consultado el 9 de octubre de 2014 .
  24. ^ Mikhail Kalinin, Danny Ryan, Vitalik Buterin (2021). «EIP-3675: Actualizar el consenso a Proof-of-Stake». Propuestas de mejora de Ethereum . Consultado el 16 de octubre de 2023 .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
  25. ^ ab A. Ben-David, N. Nisan y B. Pinkas, "FairplayMP: un sistema para computación multipartita segura", ACM CCS 2008, págs. 257–266, 2008.
  26. ^ abc B. Pinkas, T. Schneider, N. Smart y S. Williams, "La computación segura entre dos partes es práctica", Asiacrypt 2009, vol. Springer LNCS 5912, págs. 250–267, 2009.
  27. ^ Y. Lindell y B. Pinkas, "Un protocolo eficiente para computación segura entre dos partes en presencia de adversarios maliciosos", Eurocrypt 2007, vol. Springer LNCS 4515, págs. 52-78, 2007.
  28. ^ Y. Lindell, "Protocolos rápidos de corte y selección para adversarios maliciosos y encubiertos", Crypto 2013, vol. Springer LNCS 8043, págs. 1-17, 2013.
  29. ^ B. Kreuter, A. Shalet y C.-H. Shen, "Computación segura de mil millones de puertas con adversarios maliciosos", Simposio de seguridad USENIX 2012, págs. 285-300, 2012.
  30. ^ A. Shelat y C.-H. Shen, "Computación segura y rápida entre dos partes con suposiciones mínimas", ACM CCS 2013, págs. 523–534, 2013.
  31. ^ T. Frederiksen y J. Nielsen, "Computación bipartita rápida y maliciosamente segura usando la GPU", ACNS 2013, vol. Springer LNCS 7954, págs. 339–356, 2013.
  32. ^ Y. Huang, J. Katz y D. Evans, "Computación segura y eficiente entre dos partes mediante corte y selección simétricos", CRYPTO, vol. Springer LNCS 8043, págs. 18-35, 2013.
  33. ^ "Informe del Boston Women's Workforce Council" (PDF) . Boston Women's Workforce Council. Enero de 2017. Consultado el 14 de febrero de 2024 .
  34. ^ "BPC se asocia con el condado de Allegheny en un nuevo proyecto de datos que preserva la privacidad | Centro de políticas bipartidistas".
  35. ^ Hart, NR; Archer, DW; Dalton, E. (marzo de 2019). "Compartir datos con privacidad preservada para decisiones políticas basadas en evidencia" (PDF) . Bipartisan Policy Center . Consultado el 14 de febrero de 2024 .
  36. ^ Informe técnico de Galois 2018
  37. ^ "Ruta Cincuenta". 25 de agosto de 2023.
  38. ^ "SCAPI: La biblioteca API de computación segura | BIU Cyber ​​Center".
  39. ^ https://palisade-crypto.org/ [ URL básica ]
  40. ^ https://mp-spdz.readthedocs.io [ URL básica ]

Lectura adicional

Enlaces externos