Hispanopedia WikiLa computación verificable (o computación verificada ) permite que un ordenador delegue el cálculo de alguna función a otros clientes , posiblemente no confiables , manteniendo 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 surgió como resultado del fenómeno cada vez más común de la " externalización " de cálculos a usuarios no confiables en proyectos como SETI@home y también del creciente deseo de permitir que los dispositivos computacionalmente débiles externalicen tareas computacionales a un servicio de computación más potente, como en la computación en la nube . El concepto se remonta al trabajo de Babai et al., [ 1 ] y se ha estudiado bajo varios términos, incluyendo "computaciones de verificación" (Babai et al.), "computaciones de delegación", [ 2 ] "computación certificada", [ 3 ] y computación verificable. El término computación verificable 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 descripción general
El creciente deseo de externalizar tareas computacionales de un dispositivo computacional relativamente débil (cliente) a un servicio computacional más potente (trabajador), y el problema de los trabajadores deshonestos que modifican el software de su cliente para devolver resultados plausibles sin realizar el trabajo real [ 5 ] motivaron 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 externalizada con 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 si tuviera que calcular la función desde cero.
Se ha dedicado una atención considerable a la verificación del cálculo de funciones realizadas por trabajadores no confiables, incluyendo el uso de coprocesadores seguros , [ 6 ] [ 7 ] Módulos de Plataforma Confiable (TPM), [ 8 ] pruebas interactivas , [ 9 ] [ 10 ] pruebas verificables probabilísticamente , [ 11 ] [ 12 ] argumentos eficientes, [ 13 ] [ 14 ] y pruebas CS de Micali. [ 15 ] Estas verificaciones son interactivas, lo que requiere que el cliente interactúe con el trabajador para verificar la prueba de corrección, [ 13 ] [ 14 ] o son protocolos no interactivos que pueden probarse en el modelo de oráculo aleatorio . [ 15 ]
Verificación por replicación
El mayor cálculo verificado ( SETI@home ) utiliza la verificación por replicación.
El proceso de verificación SETI@home involucra una máquina cliente y varias máquinas de trabajo. La máquina cliente envía unidades de trabajo idénticas a varias computadoras (al menos 2).
Cuando no se obtienen suficientes resultados en un tiempo razonable (debido a apagados accidentales de las máquinas, fallos de comunicación, etc.) o los resultados no coinciden (debido a errores de cálculo, fraude mediante el envío de datos falsos sin realizar el trabajo, etc.), la máquina cliente envía más unidades de trabajo idénticas a otras máquinas de trabajo. Una vez que un mínimo de resultados coinciden (generalmente 2), el cliente asume que dichos resultados (y otros resultados idénticos para esa unidad de trabajo) son correctos. El cliente otorga crédito a todas las máquinas que devolvieron los resultados correctos.
Cálculo verificable
Gennaro et al. [ 4 ] definieron la noción de esquema de computación 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 el cliente una sola vez para calcular información auxiliar asociada a F. Parte de esta información es pública y se comparte con el trabajador, mientras que el resto es privada y se conserva con el cliente.
- Preparación de la entrada . En esta etapa, el cliente calcula 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 mantiene en poder del cliente. La información pública se envía al trabajador para calcular F con los datos de entrada.
- Cálculo y verificación de la salida . En esta etapa, el trabajador utiliza la información pública asociada a la función F y a la entrada, calculadas en las dos fases anteriores, para calcular una salida codificada de la función F sobre la entrada proporcionada. Este resultado se devuelve al cliente para verificar su corrección, calculando el valor real de la salida mediante la decodificación del resultado devuelto por el trabajador utilizando la información privada calculada en las fases anteriores.
La noción definida de esquema de computación verificable minimiza la interacción entre el cliente y el trabajador a exactamente dos mensajes, donde se envía un solo mensaje de cada parte a la otra durante las diferentes fases del protocolo. [ 4 ]
Un ejemplo de esquema basado en cifrado totalmente homomórfico
Gennaro et al. [ 4 ] definieron un esquema de computación verificable para cualquier función F utilizando el circuito ofuscado de Yao [ 16 ] [ 17 ] combinado con un sistema de cifrado totalmente homomórfico .
Este esquema de cálculo verificable VC se define de la siguiente manera: [ 4 ]
VC = (KeyGen, ProbGen, Compute, Verify) consta de cuatro algoritmos como se indica a continuación:
- KeyGen(F, λ) → (PK, SK) : El algoritmo de generación de claves aleatorias genera dos claves, pública y privada, en función del parámetro de seguridad λ. La clave pública codifica la función objetivo F y se envía al trabajador para que la calcule. Por otro lado, el cliente mantiene la clave secreta en privado.
- ProbGen(SK, x) → (σx, τx) : El algoritmo de generación de problemas codifica la función de entrada x en dos valores, público y privado, utilizando la clave secreta SK. El valor público σx se le proporciona al trabajador para que calcule F(x), mientras que el valor secreto τx permanece privado para el cliente.
- Compute(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 del cliente PK 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 utilizando tanto la clave secreta SK como la "decodificación" secreta τx. Devuelve y = F(x) si σy representa una salida válida de F en x, o ⊥ 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 debe representarse como un circuito booleano sobre el cual se aplicaría el algoritmo de generación de claves . Este algoritmo ejecuta el procedimiento de ofuscación de Yao sobre dicho circuito para calcular las claves pública y secreta. La clave pública (PK) se compone de todos los textos cifrados que representan el circuito ofuscado, y la clave secreta (SK) se compone de todas las etiquetas de cable aleatorias. La clave secreta generada se utiliza posteriormente en el algoritmo de generación de problemas. Este algoritmo primero genera un nuevo par de claves pública y secreta para el esquema de cifrado homomórfico , y luego utiliza estas claves con dicho esquema para cifrar los cables de entrada correctos, representados como la clave secreta del circuito ofuscado. Los textos cifrados producidos representan la codificación pública de la entrada (σx) que se entrega al trabajador, mientras que la clave secreta (τx) permanece privada para el cliente. Posteriormente, 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 logra descifrando recursivamente los textos cifrados de las puertas hasta llegar a los valores finales de los cables 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 de esquema de computación verificable establece que este 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 correctamente y corresponderán a la evaluación de F sobre esas entradas. Por otro lado, un esquema de computación verificable es seguro si un trabajador malintencionado no puede convencer al algoritmo de verificación de aceptar una salida incorrecta para una función F y una entrada x dadas.
Computación práctica verificable
Aunque se ha demostrado que la computación verificable es posible en teoría (mediante cifrado totalmente homomórfico o pruebas verificables probabilísticamente ), la mayoría de las construcciones conocidas resultan muy costosas en la práctica. Recientemente, algunos investigadores han explorado cómo hacer que la computación verificable sea práctica. Un ejemplo de ello es el trabajo de investigadores de la Universidad de Texas en Austin . [ 18 ] Los autores parten de un sistema de argumentos basado en pruebas verificables probabilísticamente y reducen sus costes en un factor de 10²⁰ . También implementaron sus técnicas en el sistema Pepper . Los autores señalan que «Nuestra conclusión hasta el momento es que, como herramienta para construir sistemas seguros, las PCP y los sistemas de argumentos no son una causa perdida».
Se ha inspeccionado toda la zona, que ahora incluye varias implementaciones de diferentes grupos. [ 19 ]
En la década de 2010, las técnicas de computación verificables experimentaron un aumento en las aplicaciones prácticas de la tecnología blockchain . [ 20 ]
Referencias
- ↑ Babai, László; Fortnow, Lance; Levin, Leonid A.; Szegedy, Mario (1991-01-01). "Checking computations in polylogarithmic time". Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 . New York, NY, US: ACM. pp. 21– 32. CiteSeerX 10.1.1.42.5832 . doi : 10.1145/103418.103428 . ISBN 978-0897913973. S2CID 16965640 .
- ↑ Goldwasser, Shafi ; Kalai, Yael Tauman ; Rothblum, Guy N. (1 de enero de 2008). «Delegating computation». Actas del cuadragésimo simposio anual de la 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. S2CID 47106603 .
- 1 2 Micali, S. (2000-01-01). "Pruebas computacionalmente sólidas". SIAM Journal on Computing . 30 (4): 1253– 1298. CiteSeerX 10.1.1.207.8277 . doi : 10.1137/S0097539795284959 . ISSN 0097-5397 .
- 1 2 3 4 5 6 7 Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31 de agosto de 2010). Computación verificable no interactiva: externalización de la computación a trabajadores no confiables . CRYPTO 2010. doi : 10.1007 /978-3-642-14623-7_25 .
- ↑ Molnar, D. (2000). "El problema de SETI@Home". ACM Crossroads . 7 (1).
- ↑ Smith, S.; Weingart, S. (1999). "Construcción de un coprocesador seguro programable de alto rendimiento". Computer Networks . 31 (8): 831– 960. CiteSeerX 10.1.1.22.8659 . doi : 10.1016/S1389-1286(98)00019-X .
- ↑ Yee, B. (1994). Uso de coprocesadores seguros (tesis doctoral). Universidad Carnegie Mellon.
- ↑ Trusted Computing Group (julio de 2007). Especificación principal del módulo de plataforma segura . 1.2, Revisión 103.
- ↑ L. Babai (1985). "Intercambiando la teoría de grupos por la aleatoriedad". En Actas del Simposio ACM sobre Teoría de la Computación (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), pp. 186–208
- ↑ S. Arora y S. Safra (1998). "Pruebas verificables probabilísticamente: una nueva caracterización de NP." Journal of the ACM , 45 , pp. 501-555
- ↑ O. Goldreich (1998). Criptografía moderna, pruebas probabilísticas y pseudorandomness. Serie Algorithms and Combinatorics, 17 , Springer
- 1 2 J. Kilian (1992). "Una nota sobre pruebas y argumentos de conocimiento cero eficientes (resumen extendido)". En Actas del Simposio ACM sobre Teoría de la Computación (STOC)
- 1 2 J. Kilian (1995). "Argumentos eficientes mejorados (versión preliminar)". En Actas de Crypto , Londres, Reino Unido, págs. 311–324. Springer-Verlag
- 1 2 S. Micali (1994). "Pruebas CS (resumen extendido)". En Actas del Simposio IEEE sobre Fundamentos de la Informática , págs. 436-453.
- ↑ A. Yao (1982). "Protocolos para cálculos seguros". En Actas del Simposio IEEE sobre Fundamentos de la Informática , págs. 160-164.
- ↑ A. Yao (1986). "Cómo generar e intercambiar secretos". En Actas del Simposio IEEE sobre Fundamentos de la Informática , págs. 162-167.
- ↑ Setty, Srinath; McPherson, Richard; Blumberg, Andrew J.; Walfish, Michael (febrero de 2012). Cómo hacer prácticos (a veces) los sistemas de argumentación para la computación externalizada . Simposio sobre seguridad de redes y sistemas distribuidos (NDSS) 2012.
- ↑ Walfish, Michael; Blumberg, Andrew J. (2015-01-01). "Verificación de cálculos sin volver a ejecutarlos" . Commun. ACM . 58 (2): 74– 84. doi : 10.1145/2641562 . ISSN 0001-0782 .
- ↑ Šimunić, Silvio; Bernaca, Dalen; Lenac, Kristijan (2021). «Aplicaciones informáticas verificables en Blockchain» . Acceso IEEE . 9 : 156729– 156745. Código bibliográfico : 2021IEEEA...9o6729S . doi : 10.1109/ACCESS.2021.3129314 . S2CID 244923818 .
{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
- Comunicación segura
- computación distribuida
