Demostraciones de conocimiento nulo interactivas usando grafos

  1. Hernández Goya, Candelaria
  2. Caballero Gil, Pino
Book:
III Jornadas de Informática. Actas: El Puerto de Santa María (Cádiz), 14 al 18 de julio 1.997 [sic]
  1. Torres Cantero, Juan Carlos (dir. congr.)

Publisher: [Sevilla?] : Asociación Española de Informática y Automática,[1997]

ISBN: 84-8498-463-X

Year of publication: 1997

Pages: 187-196

Congress: Jornadas de Informática (3. 1997. Puerto de Santa María)

Type: Conference paper

Abstract

El problema que se pretende resolver con este trabajo es el de demostrar que se tiene determinada información, como por ejemplo un password, sin enseñarla ni proporcionar ninguna pista sobre ella. Para ello se presentan tres protocolos interactivos conocidos como Demostraciones de Conocimiento Nulo (DNC), y la información a demostrar es la solución de algún problema de la Teoría de Grafos como, por ejemplo, el isomorfismo de grafos y los circuitos hamiltorianos. Los protocolos se han diseñado tomando como modelo la técnica de "corte y elección" (cut and choose) y, aunque se han clasificado en dos bloques según la herramienta usada . En el primer caso la base es la dificultad del problema del isomorfismo de grafos, y en el segundo se utilizan cifrados de clave pública.