¿Qué es la computación segura multipartita?
Nombre: Wang Lezhang
ID de estudiante: 19011110177
/p/68116569
/p/25770963
/p/59108808
La teoría de la Computación Segura Multipartita (MPC: Secure Muti-Party Computation) fue desarrollada por el Sr. Yao Qizhi para resolver el problema de proteger la información privada entre un grupo de participantes que desconfían mutuamente y la ausencia de un tercero de confianza. Un marco teórico propuesto bajo la premisa de los problemas de computación colaborativa. La informática segura multipartita puede garantizar simultáneamente la privacidad de la entrada y la exactitud del cálculo. Utiliza la teoría matemática para garantizar que la información de entrada de todas las partes que participan en el cálculo no quede expuesta sin un tercero de confianza y, al mismo tiempo, Se pueden obtener resultados de cálculo precisos.
Ya en 1982, el Sr. Yao Qizhi propuso el famoso problema del millonario de Yao en su artículo "Protocolos para la computación segura", y también introdujo la computación segura bilateral por primera vez. problema y se verificó su viabilidad. Dos millonarios, Alice y Bob, quieren concluir quién es más rico sin ningún tercero de confianza y sin revelar su riqueza.
A continuación presentamos la exquisita solución del profesor Yao:
Supongamos que el hombre rico Wang tiene activos por mil millones y Li tiene activos por j mil millones. Wang elige una clave pública que le permite a Li pasar el mensaje cifrado.
Primero, Li seleccionó un número entero grande aleatorio x, lo cifró con la clave pública de Wang y obtuvo el texto cifrado K. Li envía k-j a Wang.
Después de que Wang recibió el texto cifrado c=k-j, descifró c+1, c+2,..., c+10 y obtuvo diez números. Luego seleccione un número primo p de tamaño apropiado y registre los restos después de dividir estos diez números por p como d1, d2,..., d10.
.Nota: Estos diez números deberían parecer completamente aleatorios. La clave es que la ecuación dj=x mod p se cumple.
Finalmente, Wang realizó las siguientes operaciones en esta cadena de números: los primeros i números permanecieron sin cambios, cada número posterior se incrementó en uno y luego se envió de regreso a Li.
Después de una operación tan complicada, Li comprueba el número j. Si es igual a x mod p, significa que este número no se ha sumado en uno, por lo que i >= j. De lo contrario, entonces i < j.
Lo maravilloso de este proceso es que una vez completado el acuerdo, Wang no conoce el valor específico de j y Li no conoce el valor de i, pero ambas partes saben quién tiene más riqueza. Esta es la informática segura multipartita. En términos generales, cuando A solo conoce x y B solo conoce y, ambas partes pueden cooperar para calcular una función f (x, y). Cuando se completa el protocolo, solo los valores de la función son públicos y ninguna de las partes conoce los valores de entrada de la otra.
A partir de los ejemplos anteriores, encontramos las características de la informática segura multipartita:
1. Dos o más partes participan en cálculos basados en sus respectivas entradas de datos privados o secretos.
2. Ninguna de las partes participantes está dispuesta a permitir que ningún otro tercero conozca su información ingresada.
Antes de la aparición de la informática segura multipartita, la estrategia para resolver los problemas anteriores era asumir que existía un proveedor de servicios confiable o que había un tercero confiable. Pero en el entorno volátil y malicioso actual, esto es extremadamente arriesgado. Por lo tanto, la computación multipartita segura se ha vuelto cada vez más importante como tecnología que puede resolver el problema de la computación colaborativa que preserva la privacidad entre un grupo de participantes que desconfían mutuamente.
En la actualidad, Internet ha completado la transformación de la era de TI a la era de DT, y los datos se han convertido en la competitividad central de las empresas en la era de DT. Como nueva energía, los datos sólo pueden generar valor si fluyen. Sin embargo, la mayoría de las empresas son muy cautelosas a la hora de compartir datos debido a cuestiones como la seguridad de los datos y la privacidad personal. MPC tiene una importante importancia teórica y práctica para romper los silos de datos y lograr un intercambio controlable de datos.
Las soluciones MPC se pueden dividir principalmente en dos tipos: las basadas en Garbled Circuit (GC) y las basadas en el intercambio de secretos.
Transferencia ajena (Transferencia ajena)
Primero, se introduce un protocolo informático multipartito seguro básico: Transferencia ajena (OT).
Veamos un ejemplo: supongamos que una agencia de viajes tiene información de viaje sobre N atracciones. Xiao Tao quiere visitar la atracción A entre ellas y espera comprar información relevante de la agencia de viajes para hacer su tarea de viaje. Pero Xiaotao se preocupa mucho por su privacidad y no quiere revelar su destino a la agencia de viajes. Por lo tanto, ambas partes esperan que esta transacción pueda cumplir con las siguientes condiciones de privacidad:
Xiaotao no quiere revelar la información "Voy a la atracción A" a la agencia de viajes
; La agencia de viajes solo quiere vender a Xiaotao la información que Xiaotao pagó para comprar sin revelar la información N-1 que Xiaotao no compró;
A primera vista, esta condición de privacidad parece insatisfactoria: la agencia de viajes solo necesita proporcionar la información de la atracción A cuando vaya a Xiaotao, definitivamente comprenderá la información de que "Xiaotao está prestando atención a la atracción A" a menos que la agencia de viajes proporcione toda la N información, pero esto va en contra de la información; intereses de la agencia de viajes;
Pero la OT mágica puede permitir que las transacciones se completen en tales "condiciones imposibles". En resumen, en el protocolo OT, la agencia de viajes cifra los N datos de su propiedad utilizando un algoritmo de cifrado y parámetros acordados por ambas partes, y luego los envía a Xiaotao para que pueda descifrar la información de A del texto cifrado, y el otro N; -1 datos de información no se pueden descifrar.
Además de usarse directamente para construir soluciones MPC, OT también es la piedra angular de muchas soluciones MPC, como GC.
Circuitos confusos
Sabemos que cualquier función está representada en última instancia por sumadores, multiplicadores, palancas de cambio, selectores y otros circuitos dentro del lenguaje informático, y estos circuitos, en última instancia, pueden estar compuestos por sólo dos puertas lógicas, AND y XOR. Un circuito de puerta es en realidad una tabla de verdad. Por ejemplo, la tabla de verdad de una puerta AND es:
Por ejemplo, la celda inferior derecha indica que cuando ambos cables de entrada (cable) son 1, el cable de salida. =1: es decir 1 Y 1 = 1.
Supongamos que ciframos cada cable con una clave diferente y cambiamos la tabla de verdad a esta:
Por ejemplo, la celda inferior derecha indica que si las entradas de la puerta son b y d , luego genere la f cifrada (las claves son b y d). Esta puerta sigue siendo la misma desde la perspectiva del flujo de control, excepto que la entrada y la salida están cifradas, y la salida debe descifrarse usando la entrada correspondiente, y la f descifrada puede usarse como entrada de la puerta posterior. Este método de cifrado se llama "Circuito confuso (GC)".
Al cifrar todas las puertas del circuito en orden, obtendremos una función representada por GC. Esta función recibe entrada cifrada y genera el resultado cifrado.
Suponga que hay dos participantes A y B, cada uno de los cuales proporciona datos a y b, y espera calcular de forma segura la función acordada F (a, b), y luego un proceso de protocolo de cálculo seguro de dos partes basado en GC can La descripción informal es la siguiente:
Los estudiantes cuidadosos definitivamente señalarán: ¿Cómo puede A acceder a la entrada b de B en el paso 4? ¿No viola esto el supuesto de computación multipartita segura? Aquí debe usar OT, A desempeña el papel de Remitente y B desempeña el papel de Receptor. Deje que B obtenga Encrypt (b) de A sin revelar el contenido de b a A. Como se muestra en la figura:
Cabe señalar que el proceso anterior es solo una descripción aproximada del método GC original. Hay muchas optimizaciones detalladas, como Point & Permute, Free XOR, Half Gates, etc. En el seguimiento de GC Con el progreso de la investigación en los últimos años, el desempeño de GC es casi práctico. Tomando como ejemplo la distancia de Hamming de dos vectores de millones de dimensiones (el escenario de la aplicación es encontrar similitudes entre dos datos sin filtrar el contenido de los datos entre sí), un cálculo bipartito tan seguro se puede completar en aproximadamente 1,5 segundos. .
Modelo de seguridad de computación multipartita segura
Modelo de comportamiento semihonesto y modelo de comportamiento malicioso
Los estudiantes más cuidadosos preguntarán además: "¿Cómo garantizar que A da ¿Es el
de B un GC correcto? Por ejemplo, A y B están de acuerdo en un tamaño mayor que a y b, y están de acuerdo en F(a,b)=a>b?1:0, pero A puede hacerlo El GC de otra función, como F (a, b) = el primer bit de b, obviamente infringirá la privacidad de B, pero dado que la función se envía a B en forma de GC, B no tiene. manera de descubrir esto. ¿Problema?"
Este es de hecho un problema de seguridad. De hecho, GC también tiene otros problemas de seguridad, como fallas selectivas. Antes de presentar la solución, debemos definir el modelo de seguridad de la computación multipartita segura.
El modelo de seguridad del cálculo multipartito seguro incluye contenido desde múltiples perspectivas. En el contexto anterior, nos centramos en el "modelo de comportamiento", es decir, qué comportamientos pueden realizar los participantes para obtener la privacidad de otros. fiestas. Los modelos de comportamiento comunes incluyen "semihonesto" y "malicioso". El primero supone que todos los participantes siguen fielmente los pasos del protocolo y solo quieren inferir la privacidad de otras partes a través del contenido del protocolo, mientras que el segundo supone que los participantes malintencionados no siguen el contenido del protocolo para obtener la privacidad de otras partes.
Para utilizar una analogía vaga con el póquer, un jugador semihonesto intentará inferir las manos de otros a partir de su propia mano y de las cartas que ha jugado, pero aún así sigue las reglas del póquer A; El jugador malicioso utilizará todo tipo de trucos, como cambiar cartas y robar cartas.
Se puede ver que los problemas planteados al comienzo de esta sección pertenecen a la categoría de comportamiento malicioso, y solo se puede decir que el GC original es seguro bajo el modelo de comportamiento semi-honesto y no puede resistir. Ataques de comportamiento malicioso. Hay muchas mejoras en el esquema GC que pueden lograr seguridad bajo el modelo de comportamiento malicioso, pero todas requieren un gran costo de rendimiento: aún tomando como ejemplo la distancia de Hamming de dos vectores de millones de dimensiones, el método más rápido también es 10 segundos+, que es más de 7 veces más lento que el esquema semi-honesto equivalente. De hecho, después de nuestra investigación, si realmente queremos implementar productos MPC que admitan datos a gran escala, básicamente solo podemos considerar soluciones semi-honestas. Esto afecta seriamente la practicidad de la computación multipartita segura.
Algunas aplicaciones de informática segura multipartidaria
Desempeñan un papel importante en elecciones electrónicas, votación electrónica, subastas electrónicas, intercambio de secretos, firmas de umbral y otros escenarios.
Conclusión
La formulación y la respuesta del problema millonario ilustran vívidamente los desafíos que enfrenta la informática segura multipartita y las ideas para resolver el problema, que han atraído gran atención por parte del mundo académico. comunidad. Cuatro años más tarde, el Sr. Yao Qizhi logró otro gran avance en 1986, propuso una solución universal basada en circuitos de confusión, que verificó aún más la viabilidad universal de los cálculos seguros multipartitos y sentó las bases teóricas para la criptografía informática moderna. Desde entonces, gracias a nuevas investigaciones e innovaciones realizadas por académicos como Oded Goldreich y Shafi Goldwasser, la computación segura multipartita se ha convertido gradualmente en una rama importante de la criptografía moderna.