¿Cómo demostrarle a un amigo que tengo una solución para resolver (sin revelarlo)? [cerrado]

Puede usar una prueba de conocimiento cero para demostrar que tiene una solución para una clase general de problemas . (Por ejemplo: "Puedo encontrar de manera eficiente la factorización principal de cualquier número. No te diré cómo lo hago, pero demostraré mi habilidad factorizando rápidamente cualquier número que me lances"). Sin embargo, aquí, la solución es cómo resolvió el problema; es tautológico decir que no puedes mostrar cómo resolviste el problema sin revelar cómo resolviste el problema.

Podrías declarar tu solución de forma secreta pero segura a través del compromiso criptográfico . Por ejemplo, publicas un hash de tu solución y luego publicas tu solución. Eso le permite probar que tuvo la solución por lo menos mientras el hash haya sido público. Sin embargo, solo queda claro que el secreto que ha confirmado es una solución válida después de hacer público el secreto. (Este enfoque le permitirá a Paul comparar su (no) respuesta con la suya, simplemente comparar hashes, utilizando un formato estándar, pero no demostrará nada a Ollie).

Para Ollie, necesita alguna forma de demostrar una solución a un problema diferente que se relacione con el problema real de alguna manera demostrable. Consideré brevemente algún tipo de cifrado completamente homomórfico , pero no veo cómo podría demostrar el problema de forma homomórfica que 1) no permite que su amigo lo descifre y 2) todavía le permite a su amigo verificar el resultado. Por ejemplo, considere un intento de una prueba iterativa de conocimiento cero con un esquema homomórfico que pueda cifrar ( Enc ) con una clave pública y descifrar ( Dec ) con una clave privada:

1. Muestra a tu amigo Enc(1) , Enc(5) , Enc(6) y Enc(7) en un orden aleatorio, y muestra por separado el Enc(21) . En este punto, su amigo puede detener estos pasos, solicitar la clave privada y verificar que no está mintiendo acerca de los valores de los números. (Esto evita que utilices los valores incorrectos, ya que probablemente te atraparían si jugaras suficientes veces).

2. Realice las operaciones matemáticas necesarias en los primeros cuatro valores cifrados para producir 21. (Este paso proporciona las operaciones necesarias, que son subóptimas, pero no revela qué valores van con qué operaciones). En este punto Ya no podemos darle la clave de descifrado a su amigo, o él podrá ver la solución completa.

3. Realice una prueba de igualdad homomórfica del resultado del paso 2 contra el Enc(21) del paso 1. Esto produce un booleano encriptado.

No hay forma de permitir que su amigo descifre el booleano sin que también le permita descifrar cualquier otro valor, lo que revelaría su solución por completo. Por lo tanto, no hay forma de verificar a su amigo la corrección de su solución.

Solo hay 7680 expresiones posibles que usan exactamente una vez cada uno de los cuatro valores, y operadores binarios en una lista de cuatro operadores binarios posibles. Algunas de estas expresiones son, de hecho, duplicadas entre sí, ya que dos de los operadores (suma y multiplicación) son conmutativos. Puedes decirle a Ollie y Paul que son bastardos perezosos.

Este pequeño número de candidatos invalida la mayoría de los esfuerzos criptográficos, ya que una prueba de conocimiento cero siempre es relativa a un problema fundamental: una prueba ZK es una prueba en la que demuestra que conoce una solución sin proporcionar al verificador ninguna información < em> que no pudo obtener por sí mismo . Aquí, probar todas las soluciones posibles es simplemente demasiado fácil, por lo que Ollie y Paul ya pueden obtener por sí mismos toda la información que se va a obtener.

(Además, de acuerdo con mis propios cálculos, no hay solución. Por lo tanto, la solución al rompecabezas debe ser algún tipo de juego de palabras o laguna, que por naturaleza evade el análisis matemático).

Editar: hubo un error en mi programa (maldita conversión silenciosa double a int ; no hay ninguna advertencia de GCC incluso con -W -Wall ). De hecho, hay una solución, la encontrada por @Gudradain (y es única). Para aquellos interesados en tales cosas, aquí está mi programa horrible .

Una solución alternativa que podría pensar sería escribir un sitio web de código abierto. El sitio está configurado para aceptar un tipo de fórmula, por ejemplo, uno que contenga uno o más de ()/*+= (en cualquier cantidad y cualquier orden) y 1 , 5 , 6 y 7 deben aparecer solo una vez. La fórmula de entrada se almacenará en un archivo o base de datos, se evaluará la fórmula y se mostrará el resultado. Entonces el amigo puede ver que tienes una solución que realmente da como resultado 21.

Luego está el problema de alojar el sitio web. Si lo aloja, puede modificar el código. Si su amigo lo alberga, podría echar un vistazo a la fórmula almacenada. Sin embargo, estaría seguro de que no le estás haciendo una broma. No es ventajoso simplemente decirle que en realidad es una solución, pero ahora puede estar 100% seguro. Solo que ahora tienes que confiar en él para que no eche un vistazo a la solución.

No estoy seguro de que haya mejores soluciones, esto es lo mejor que puedo encontrar.

Creo que esto es además de la pregunta, pero en su totalidad: si desea comprobar si tiene la misma respuesta sin revelarse la respuesta, puede usar una función de hash. Si ejecuta sha-256 sobre ambas respuestas, el hash resultante debe ser idéntico. Sin embargo, asegúrate de usar el mismo formato (espaciado, orden de las cosas, etc.), quizás puedas dar algunos hashes para comparar.

Podrías compartir el hash de la respuesta.

1. almacena la respuesta en un archivo estático. cat >answer.txt

2. hash este archivo sha1sum answer.txt .

3. comparte el hash resultante con tu amigo.

Una vez alcanzado el tiempo de espera del rompecabezas, podría mostrar su archivo y re calcular el hash. ¡Deben coincidir!