Prueba de conocimiento cero de la igualdad

Question

Alice y Bob eligen en secreto un número entero entre 1 y 10, a et b . Quieren saber (con alta probabilidad) si a es igual a b sin revelar ninguna otra información. ¿Pueden?

Answer 1

A la manera típica de los matemáticos, permítanme explicar cómo reducir su problema a uno más difícil, a saber, el cifrado homomórfico. ( Editar : Debería haber aclarado que el problema de construir esquemas de encriptación homomórficos, al menos en la medida que se requiere aquí, está efectivamente resuelto).

Supongamos que Charlie es un tercero "honesto pero curioso" (es decir, se puede confiar en que Charlie realice los cálculos con honestidad, pero no se le debe permitir conocer $a$ ou $b$ ): Espero que no sea irracional asumir la existencia de Charlie. Alice y Bob le piden a Charlie que establezca un cifrado homomórfico esquema y darles la clave pública. Alice y Bob encriptan cada uno su entero utilizando esta clave pública, y comparten el resultado (encriptado), pero no se lo dan a Charlie. A continuación, utilizan las propiedades homomórficas del esquema para calcular el valor (cifrado) del "si $a=b$ entonces $1$ si no $0$ "(como función booleana, no requiere un gran número de multiplicaciones de bits, por lo que las propiedades homomórficas requeridas no son demasiado difíciles de obtener). Ambos pueden realizar el cálculo. Envían el resultado a Charlie para descifrarlo, y Charlie puede devolver el resultado. Así, al final, Alice, Bob y Charlie saben cada uno si $a=b$ pero no cuáles son los números, excepto los que ellos mismos eligieron.

Editar 2: Según el comentario de Pace Nielsen, debería haber aclarado que este tipo de encriptación no es determinista: no hay sólo un texto cifrado para cada uno de los valores del 1 al 10, hay un número enorme, y ni Alice ni Bob pueden descifrar el valor del otro simplemente probando todas las posibilidades.

Por supuesto, esto deja un montón de preguntas sin respuesta, como si podemos arreglar que Charlie no sepa si $a=b$ o prescindir por completo de Charlie (probablemente se pueda hacer algo con un cifrado funcional o un cifrado homomórfico con una clave secreta que sea dividir entre Alice y Bob, pero normalmente hay muchas suposiciones de honestidad que pueden no ser obvias). Tal vez más insidiosamente, no sé cómo asegurarse de que Alice no seleccione un número fuera del rango permitido (un número que esencialmente devolvería un "no" a cualquier comparación con un número honestamente elegido por Bob).

Answer 2

Esta respuesta parcial es desde la perspectiva de la teoría de la información: Esto no puede hacerse con un número reducido de rondas de conversación. Supongamos que los jugadores reciben un número entre 1 y $n$ y quieren saber la respuesta con probabilidad $1-\epsilon$ . Si el número de rondas en su conversación es menor que $\log^*\min\{n, 1/\epsilon\}$ debe haber una revelación de información adicional. Esto se desprende de [arXiv:1304.1217] Aunque la reducción necesita algunas explicaciones. Aquí $\log^*$ es el logaritmo iterado función.

Cuando se permite un número ilimitado de rondas, la igualdad puede determinarse con probabilidad 1 revelando una cantidad muy pequeña de información (independiente de $n$ ). Lo bueno de la información 0 es que es 0 sin importar cómo la midamos, pero para la información distinta de cero tenemos que especificar cómo la medimos.

Existe un protocolo fijo P tal que para cualquier $(a,b)\in [n]\times[n]$ las partes se enteran de si $a=b$ con probabilidad 1 y para cualquier distribución $\mu$ en $[n]\times[n]$ , si $(A,B)\sim \mu$ ,

$$ I(A;\Pi\,|\, B) + I(B;\Pi\,|\,A) < 4.5, $$

donde $\Pi$ es una variable aleatoria que denota su conversación. Este protocolo es de ECCC:TR11-123 Proposición 3.21.

Answer 3

Usted está preguntando al problema del millonario socialista . Hay varias soluciones al problema, entre ellas la de que se muestra en la página de Wikipedia utilizando el intercambio de claves Diffie-Hellman-Merkle para el cálculo seguro multipartito.

La tabla que lo describe es un poco difícil de copiar en mathoverflow, pero puedes echar un vistazo al diagrama del protocolo:

Answer 4

Creo que esta tarea puede resolverse sin necesidad de un "tercero honesto pero curioso" siempre que Alice y Bob se comprometan a realizar el siguiente protocolo completo:

Alice y Bob comparten un gran número primo $p > 5$ y calcular $a^\prime = a^p\,\mathrm{mod}\,10$ et $b^\prime = b^p\,\mathrm{mod}\,10$ respectivamente. Sus números resultantes serán iguales si y sólo si sus números originales eran iguales, es decir, $a^\prime = b^\prime$ si y sólo si $a = b$ . Luego corren Protocolo seguro multipartito de Yao para el problema de los millonarios dos veces, para comprobar primero si $a^\prime \geq b^\prime$ y si $b^\prime \geq a^\prime$ . (No se revela ninguna otra información a través de este protocolo.) Si la respuesta a ambas preguntas es sí entonces $a^\prime = b^\prime$ y por lo tanto $a = b$ . Si la respuesta es no a una de estas preguntas, entonces $a^\prime > b^\prime$ ou $b^\prime > a^\prime$ y por lo tanto $a \neq b$ . Debido a la exponenciación primaria, ninguna de las partes puede saber si $a > b$ ou $b > a$ .

Answer 5

(EDIT: Dado que el espacio de la muestra es tan pequeño Alice sólo sería capaz de reintentar 1..10 y descifrar esto)

Como desarrollador de software, así es como intentaría resolver el problema:

Alice y Bob hacen un hash de sus números con algo como scrypt; luego se envían mutuamente el hash resultante.

Intentan rehacer sus números usando la función de comprobación de scrypt; si la comprobación pasa entonces tienen el mismo número.

Detalles:

Scrypt genera una sal aleatoria y luego hace el hash del número + la sal y luego vuelve a hacer el hash X veces (X es configurable pero == mucho) [O algo así]

Alice habrá generado una sal diferente a la de Bob. El hash de scrypt incluye la sal aleatoria y el número de rondas de hashing

Alice, utilizando su número, la sal de Bob y el número de rondas, puede volver a ejecutar el algoritmo hash; si obtiene el mismo hash resultante, entonces los números (muy probablemente*) son los mismos. Bob puede hacer lo mismo.

Para que lo sepas, así es como las contraseñas "debería" se almacene en una base de datos.

* Podría haber una colisión de hash, pero es muy poco probable.