En criptografía , una prueba de conocimiento es una prueba interactiva en la que el probador logra "convencer" a un verificador de que el probador sabe algo. Lo que significa que una máquina "sepa algo" se define en términos de cálculo. Una máquina 'sabe algo', si ese algo puede ser calculado, dada la máquina como entrada. Como el programa del prover no necesariamente escupe el conocimiento en sí mismo (como es el caso de las pruebas de conocimiento cero [1] ), se introduce una máquina con un programa diferente, llamado extractor de conocimiento, para capturar esta idea. Lo que más nos interesa es lo que se puede demostrar mediante el tiempo polinomial.máquinas acotadas. En este caso el conjunto de elementos de conocimiento se limita a un conjunto de testigos de alguna lengua en NP .
Dejar ser una declaración de lenguaje en NP, y el conjunto de testigos para x que deben aceptarse en la prueba. Esto nos permite definir la siguiente relación:.
Una prueba de conocimiento para la relación. con error de conocimiento es un protocolo de dos partes con un probador y un verificador con las siguientes dos propiedades:
- Integridad : si, entonces el probador quien sabe testigo por logra convencer al verificador de su conocimiento. Más formalmente:, es decir, dada la interacción entre el comprobador P y el verificador V, la probabilidad de que el verificador esté convencido es 1.
- Validez : la validez requiere que la probabilidad de éxito de un extractor de conocimiento en la extracción del testigo, dado acceso de Oracle a un probador posiblemente malintencionado , debe ser al menos tan alta como la probabilidad de éxito del probador para convencer al verificador. Esta Propiedad garantiza que ningún probador que no conozca al testigo podrá convencer al verificador.
Detalles sobre la definición
Esta es una definición más rigurosa de Validez : [2]
Dejar ser una relación testigo, el conjunto de todos los testigos de valor público , y el error de conocimiento. Una prueba de conocimiento es-Válido si existe una máquina de tiempo polinomial , dado acceso de Oracle a , de modo que para cada , es el caso que y
El resultado significa que la máquina de Turing no llegó a una conclusión.
El error de conocimiento denota la probabilidad de que el verificador podría aceptar , aunque el probador de hecho no conoce a un testigo . El extractor de conocimientose utiliza para expresar lo que se entiende por conocimiento de una máquina de Turing . Si puede extraer de , Nosotros decimos eso conoce el valor de .
Esta definición de la propiedad de validez es una combinación de las propiedades de validez y validez fuerte en. [2] Para pequeños errores de conocimiento, como por ejemplo o puede verse como más fuerte que la solidez de las pruebas interactivas ordinarias .
Relación con las pruebas interactivas generales
Para definir una prueba de conocimiento específica, no solo es necesario definir el idioma, sino también los testigos que debe conocer el verificador. En algunos casos, demostrar la membresía en un idioma puede ser fácil, mientras que calcular un testigo específico puede ser difícil. Esto se explica mejor con un ejemplo:
Dejar ser un grupo cíclico con generadoren el que se cree que resolver el problema del logaritmo discreto es difícil. Decidir la pertenencia al idioma es trivial, como cada es en . Sin embargo, encontrar al testigo tal que sostiene corresponde a resolver el problema del logaritmo discreto.
Protocolos
Protocolo de Schnorr
Una de las pruebas de conocimiento más simples y de uso frecuente, la prueba de conocimiento de un logaritmo discreto , se debe a Schnorr. [3] El protocolo está definido para un grupo cíclico de orden con generador .
Para demostrar el conocimiento de , el probador interactúa con el verificador de la siguiente manera:
- En la primera ronda, el prover se compromete con la aleatoriedad. ; por lo tanto el primer mensajetambién se llama compromiso .
- El verificador responde con un desafío. elegido al azar.
- Después de recibir , el probador envía el tercer y último mensaje (la respuesta ) modulo reducido el orden del grupo.
El verificador acepta, si .
Podemos ver que esta es una prueba de conocimiento válida porque tiene un extractor que funciona de la siguiente manera:
- Simule el probador para producir . El probador ahora está en estado.
- Generar valor aleatorio e introdúzcalo en el probador. Se produce.
- Rebobinar el prover al estado . Ahora genera un valor aleatorio diferente e introdúzcalo en el probador para obtener .
- Producción .
Desde , la salida del extractor es precisamente .
Este protocolo resulta ser de conocimiento cero , aunque esa propiedad no es necesaria para una prueba de conocimiento.
Protocolos sigma
Los protocolos que tienen la estructura de tres movimientos anterior (compromiso, desafío y respuesta) se denominan protocolos sigma [ cita requerida ] . La letra griegavisualiza el flujo del protocolo. Existen protocolos Sigma para probar varias afirmaciones, como las que pertenecen a logaritmos discretos. Usando estas pruebas, el probador no solo puede probar el conocimiento del logaritmo discreto, sino también que el logaritmo discreto tiene una forma específica. Por ejemplo, es posible probar que dos logaritmos de y con respecto a las bases y son iguales o cumplen alguna otra relación lineal . Para una y b elementos de, decimos que el probador demuestra el conocimiento de y tal que y . La igualdad corresponde al caso especial donde a = 1 y b = 0. Comose puede calcular trivialmente a partir deesto es equivalente a probar el conocimiento de una x tal que.
Esta es la intuición detrás de la siguiente notación, [4] que se usa comúnmente para expresar lo que se prueba exactamente mediante una prueba de conocimiento.
establece que el probador conoce una x que cumple la relación anterior.
Aplicaciones
Las pruebas de conocimiento son una herramienta útil para la construcción de protocolos de identificación y, en su variante no interactiva, esquemas de firma. Tales esquemas son:
También se utilizan en la construcción de firmas de grupo y sistemas de credenciales digitales anónimos .
Ver también
Referencias
- ^ Shafi Goldwasser , Silvio Micali y Charles Rackoff . La complejidad del conocimiento de los sistemas de prueba interactivos . Actas del 17º Simposio sobre Teoría de la Computación , Providence, Rhode Island. 1985. Draft. Abstracto extendido
- ^ a b Mihir Bellare , Oded Goldreich: Sobre la definición de pruebas de conocimiento . CRYPTO 1992: 390–420
- ^ CP Schnorr , Identificación y firmas eficientes para tarjetas inteligentes, en G Brassard, ed. Advances in Cryptology - Crypto '89, 239-252, Springer-Verlag , 1990. Lecture Notes in Computer Science, nr 435
- ^ https://www.researchgate.net/publication/243300730_Efficient_Group_Signature_Schemes_for_Large_Groups