Cómputo verificables (o cómputo verificado o verificado computación ) permite a un ordenador para descargar el cómputo de alguna función, a otros quizás no se confía clientes , manteniendo al mismo tiempo los resultados verificables. Los otros clientes evalúan la función y devuelven el resultado con una prueba de que el cálculo de la función se realizó correctamente. La introducción de esta noción se produjo como resultado del fenómeno cada vez más común de " subcontratar " la computación a usuarios que no son de confianza en proyectos como SETI @ home.y también al creciente deseo de los clientes débiles de subcontratar tareas computacionales a un servicio de computación más poderoso como en la computación en nube . El concepto se remonta al trabajo de Babai et al., [1] y ha sido estudiado bajo varios términos, que incluyen "verificación de cálculos" (Babai et al.), "Delegación de cálculos", [2] "cálculo certificado", [3 ] y computación verificable. El término computación verificable en sí fue formalizado por Rosario Gennaro, Craig Gentry y Bryan Parno, [4] y se hace eco de la "computación certificada" de Micali. [3]
Motivación y visión general
El creciente deseo de subcontratar tareas computacionales de un dispositivo computacional relativamente débil (cliente) a un servicio de computación más poderoso (trabajador), y el problema de trabajadores deshonestos que modifican el software de su cliente para devolver resultados plausibles sin realizar el trabajo real [5] motivados la formalización de la noción de Computación Verificable. [4]
La computación verificable no solo se ocupa de obtener el resultado de la función subcontratada en la entrada del cliente y la prueba de su corrección, sino también de que el cliente pueda verificar la prueba con un esfuerzo computacional significativamente menor que computar la función desde cero.
Se ha prestado mucha atención a verificar el cálculo de las funciones realizadas por trabajadores que no son de confianza, incluido el uso de coprocesadores seguros , [6] [7] Módulos de plataforma confiable (TPM), [8] pruebas interactivas , [9] [10] pruebas probabilísticamente verificables , [11] [12] argumentos eficientes, [13] [14] y las pruebas CS de Micali. [15] Estas verificaciones son interactivas y requieren que el cliente interactúe con el trabajador para verificar la prueba de corrección, [13] [14] o son protocolos no interactivos que se pueden probar en el modelo de oráculo aleatorio . [15]
Verificación por replicación
El cálculo verificado más grande ( SETI @ home ) utiliza la verificación por replicación.
El proceso de verificación de SETI @ home involucra una máquina cliente y muchas máquinas trabajadoras. La máquina cliente envía unidades de trabajo idénticas a varias computadoras (al menos 2).
Cuando no se devuelven suficientes resultados en un período de tiempo razonable (debido a que las máquinas se apagaron accidentalmente, fallas en la comunicación, etc.) o los resultados no coinciden, debido a errores de cálculo, trampa al enviar datos falsos sin realmente hacer el trabajo, etc. . — Entonces la máquina cliente envía más unidades de trabajo idénticas a otras máquinas trabajadoras. Una vez que se acuerda un quórum mínimo (a menudo 2) de los resultados, el cliente asume que esos resultados (y otros resultados idénticos para esa unidad de trabajo) son correctos. El cliente otorga crédito a todas las máquinas que arrojaron los resultados correctos.
Cálculo verificable
Gennaro y col. [4] definió la noción de esquema de cálculo verificable como un protocolo entre dos partes de tiempo polinomial para colaborar en el cálculo de una función F: {0,1} n → {0,1} m . Este esquema consta de tres fases principales:
- Preprocesamiento . Esta etapa la realiza una vez el cliente para calcular alguna información auxiliar asociada a F. Parte de esta información es pública para ser compartida con el trabajador mientras que el resto es privada y se mantiene con el cliente.
- Preparación de entrada . En esta etapa, el cliente calcula alguna información auxiliar sobre la entrada de la función. Parte de esta información es pública, mientras que el resto es privada y se guarda con el cliente. La información pública se envía al trabajador para que calcule F en los datos de entrada.
- Cálculo y verificación de salida . En esta etapa, el trabajador utiliza la información pública asociada con la función F y la entrada, que se calculan en las dos fases anteriores, para calcular una salida codificada de la función F en la entrada proporcionada. Este resultado luego se devuelve al cliente para verificar su corrección calculando el valor real de la salida decodificando el resultado devuelto por el trabajador utilizando la información privada calculada en las fases anteriores.
La noción definida de esquema de cálculo verificable minimiza la interacción entre el cliente y el trabajador en exactamente dos mensajes, donde un solo mensaje se envía de cada parte a la otra parte durante las diferentes fases del protocolo. [4]
Un esquema de ejemplo basado en encriptación totalmente homomórfica
Gennaro y col. [4] definió un esquema de cálculo verificable para cualquier función F utilizando el circuito confuso de Yao [16] [17] combinado con un sistema de cifrado totalmente homomórfico .
Este esquema de cálculo verificable VC se define como sigue: [4]
VC = (KeyGen, ProbGen, Compute, Verify) consta de cuatro algoritmos de la siguiente manera:
- KeyGen (F, λ) → (PK, SK) : El algoritmo de generación de claves aleatorias genera dos claves, pública y privada, basándose en el parámetro de seguridad λ. La clave pública codifica la función de destino F y se envía al trabajador para calcular F. Por otro lado, el cliente mantiene la clave secreta en privado.
- ProbGenSK (x) → (σx, τx) : El algoritmo de generación de problemas codifica la entrada de función x en dos valores, público y privado, utilizando la clave secreta SK. El valor público σx se le da al trabajador para que calcule F (x), mientras que el cliente mantiene privado el valor secreto τx.
- Calcular (PK, σx) → σy : El trabajador calcula un valor codificado σy de la salida de la función y = F (x) utilizando la clave pública PK del cliente y la entrada codificada σx.
- Verificar SK (τx, σy) → y ∪ ⊥ : El algoritmo de verificación convierte la salida codificada del trabajador σy en la salida real de la función F usando tanto la clave secreta SK como la “decodificación” secreta τx. Produce y = F (x) si σy representa una salida válida de F en x, o genera ⊥ en caso contrario.
El protocolo del esquema de cálculos verificables definido por Gennaro et al. [4] funciona de la siguiente manera:
La función F debería representarse como un circuito booleano en el que se aplicaría el algoritmo de generación de claves . El algoritmo de generación de claves ejecuta el procedimiento de distorsión de Yao sobre este circuito booleano para calcular las claves pública y secreta. La clave pública (PK) está compuesta por todos los textos cifrados que representan el circuito distorsionado, y la clave secreta (SK) está compuesta por todas las etiquetas de cables aleatorias. La clave secreta generada se utiliza luego en el algoritmo de generación de problemas. Este algoritmo genera primero un nuevo par de claves públicas y secretas para el esquema de cifrado homomórfico , y luego usa estas claves con el esquema homomórfico para cifrar los cables de entrada correctos, representados como la clave secreta del circuito distorsionado. Los textos cifrados producidos representan la codificación pública de la entrada (σx) que se le da al trabajador, mientras que el cliente mantiene privada la clave secreta (τx). Después de eso, el trabajador aplica los pasos de cálculo del protocolo de Yao sobre los textos cifrados generados por el algoritmo de generación de problemas. Esto se hace descifrando recursivamente los textos cifrados de la puerta hasta llegar a los valores finales del cable de salida (σy). Las propiedades homomórficas del esquema de cifrado permiten al trabajador obtener un cifrado del cable de salida correcto. Finalmente, el trabajador devuelve los textos cifrados de la salida al cliente, quien los descifra para calcular la salida real y = F (x) o ⊥.
La definición del esquema de cálculo verificable establece que el esquema debe ser correcto y seguro. La corrección del esquema se logra si el algoritmo de generación de problemas produce valores que permiten a un trabajador honesto calcular valores de salida codificados que se verificarán con éxito y corresponderán a la evaluación de F en esas entradas. Por otro lado, un esquema de cálculo verificable es seguro si un trabajador malintencionado no puede convencer al algoritmo de verificación de que acepte una salida incorrecta para una función F dada y la entrada x.
Computación práctica verificable
Aunque se demostró que la computación verificable es posible en teoría (usando encriptación totalmente homomórfica o mediante pruebas probabilísticamente verificables ), la mayoría de las construcciones conocidas son muy costosas en la práctica. Recientemente, algunos investigadores han buscado hacer práctica la computación verificable. Uno de esos esfuerzos es el trabajo de los investigadores de UT Austin . [18] Los autores comienzan con un sistema de argumentos basado en pruebas comprobables probabilísticamente y reducen sus costos en un factor de 10 20 . También implementaron sus técnicas en el sistema Pepper . Los autores señalan que "nuestra conclusión hasta ahora es que, como herramienta para construir sistemas seguros, los PCP y los sistemas de argumentos no son una causa perdida".
Se ha estudiado el área general, que ahora incluye una serie de implementaciones de diferentes grupos. [19]
Referencias
- ^ Babai, László; Fortnow, Lance; Levin, Leonid A .; Szegedy, Mario (1 de enero de 1991). Comprobación de cálculos en tiempo polilogarítmico . Actas del Vigésimo Tercer Simposio Anual ACM sobre Teoría de la Computación . STOC '91. Nueva York, NY, EE. UU .: ACM. págs. 21–32. CiteSeerX 10.1.1.42.5832 . doi : 10.1145 / 103418.103428 . ISBN 978-0897913973.
- ^ Goldwasser, Shafi ; Kalai, Yael Tauman ; Rothblum, Guy N. (1 de enero de 2008). Delegación de computación: pruebas interactivas para muggles . Actas del cuadragésimo simposio anual de ACM sobre teoría de la computación . STOC '08. Nueva York, NY, EE. UU .: ACM. págs. 113-122. doi : 10.1145 / 1374376.1374396 . ISBN 9781605580470.
- ^ a b Micali, S. (1 de enero de 2000). "Pruebas computacionalmente sólidas". Revista SIAM de Computación . 30 (4): 1253–1298. CiteSeerX 10.1.1.207.8277 . doi : 10.1137 / S0097539795284959 . ISSN 0097-5397 .
- ^ a b c d e f g Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31 de agosto de 2010). Computación verificable no interactiva: outsourcing de computación para trabajadores que no son de confianza . CRYPTO 2010 . doi : 10.1007 / 978-3-642-14623-7_25 .
- ^ Molnar, D. (2000). "El problema SETI @ Home". Encrucijada de ACM . 7 (1).
- ^ Smith, S .; Weingart, S. (1999). "Construyendo un coprocesador seguro programable de alto rendimiento". Redes informáticas . 31 (8): 831–960. CiteSeerX 10.1.1.22.8659 . doi : 10.1016 / S1389-1286 (98) 00019-X .
- ^ Yee, B. (1994). Utilización de coprocesadores seguros (tesis doctoral). Universidad de Carnegie mellon.
- ^ Trusted Computing Group (julio de 2007). Especificación principal del módulo de plataforma confiable . 1.2, Revisión 103.
- ^ L. Babai (1985). "Intercambiar teoría de grupos por aleatoriedad". En Proceedings of the ACM Symposium on Theory of Computing (STOC) , Nueva York, NY, EE. UU., Págs. 421–429
- ^ S. Goldwasser, S. Micali y C. Rackoff (1989). "La complejidad del conocimiento de los sistemas de prueba interactivos". SIAM Journal on Computing , 18 (1), págs. 186–208
- ^ S. Arora y S. Safra (1998). "Pruebas probabilísticamente comprobables: una nueva caracterización de NP". Revista de la ACM , 45 , págs. 501-555
- ^ O. Goldreich (1998). Criptografía moderna, pruebas probabilísticas y pseudoaleatoriedad. Serie de algoritmos y combinatoria, 17 , Springer
- ↑ a b J. Kilian (1992). "Una nota sobre pruebas y argumentos eficientes de conocimiento cero (resumen ampliado)". En Actas del Simposio ACM sobre Teoría de la Computación (STOC)
- ↑ a b J. Kilian (1995). "Argumentos eficientes mejorados (versión preliminar)". En Proceedings of Crypto , Londres, Reino Unido, págs. 311–324. Springer-Verlag
- ↑ a b S. Micali (1994). "Pruebas de CS (resumen ampliado)". En Proceedings of the IEEE Symposium on Foundations of Computer Science , págs. 436-453.
- ^ A. Yao (1982). "Protocolos para cálculos seguros". En Proceedings of the IEEE Symposium on Foundations of Computer Science , págs. 160-164
- ^ A. Yao (1986). "Cómo generar e intercambiar secretos". En Proceedings of the IEEE Symposium on Foundations of Computer Science , págs. 162-167
- ^ Setty, Srinath; McPherson, Richard; Blumberg, Andrew J .; Walfish, Michael (febrero de 2012). Hacer que los sistemas de argumentos para la computación subcontratada sean prácticos (a veces) . Simposio de seguridad de redes y sistemas distribuidos (NDSS) 2012.
- ^ Walfish, Michael; Blumberg, Andrew J. (1 de enero de 2015). "Verificación de cálculos sin volver a ejecutarlos" . Comun. ACM . 58 (2): 74–84. doi : 10.1145 / 2641562 . ISSN 0001-0782 .