Agotador simulador de protocolos de conocimiento cero en el modelo aleatorio de Oracle

En un artículo titulado "Sobre la negabilidad en la cadena de referencia común y el modelo aleatorio de Oracle", Rafael Pass escribe:

Observamos que al probar la seguridad de acuerdo con la definición estándar de conocimiento cero en el modelo RO [Random Oracle], el simulador tiene dos ventajas sobre un simulador de modelo simple, a saber,

El simulador puede ver en qué valores las partes consultan el oráculo.
El simulador puede responder a estas consultas de la forma que elija, siempre y cuando las respuestas "se vean" bien.

La primera técnica, a saber, la capacidad de "monitorear" las consultas a la RO, es muy común en todos los trabajos que se refieren al concepto de conocimiento cero en el modelo de RO.

Ahora, considere la definición de conocimiento negro de caja negra ( PPT significa máquina de Turing probabilística y de tiempo polinomial ):

$\exists$ un simulador PPT , tal que (posiblemente engañando) verificador PPT , entrada común , y randomness , los siguientes son indistinguibles: $S$ $\forall$ $V^*$ $\forall$ $x\in L$ $\forall$ $r$

la vista de mientras interactúa con el probador en la entrada y usa la aleatoriedad ; $V^*$ $P$ $x$ $r$
la salida de en las entradas y , cuando se da acceso de recuadro negro para . $S$ $x$ $r$ $S$ $V^*$

Aquí, quiero exhibir un verificador de trampa , cuyo trabajo es agotar cualquier simulador que intente monitorear las consultas de RO: $V'$

Sea el simulador garantizado por el cuantificador existencial en la definición de conocimiento cero de caja negra, y sea un polinomio que limite el tiempo de ejecución de en la entrada . Suponga que intenta monitorear las consultas de al RO. $S$ $q(|x|)$ $S$ $x$ $S$ $V^*$

Ahora, considere una trampa , que primero consulta el RO por veces (en entradas arbitrarias de su elección), y luego actúa arbitrariamente maliciosamente. $V'$ $q(|x|)+1$

Obviamente, agota el simulador . Una forma simple de es rechazar ese comportamiento malicioso, pero de esa manera, un distintivo puede distinguir fácilmente la interacción real de la simulada. (Dado que en la interacción real, el probador no puede monitorear las consultas de y, por lo tanto, no lo rechazará por el simple hecho de que consulta demasiado). $V'$ $S$ $S$ $P$ $V'$ $V'$

¿Cuál es la solución para el problema anterior?

Editar:

Una buena fuente para estudiar ZK en el modelo RO es:

Martin Gagné, A Study of the Random Oracle Model, Ph.D. Tesis, Universidad de California, Davis , 2008, 109 páginas. Disponible en ProQuest: http://gradworks.umi.com/33/36/3336254.html

En particular, proporciona definiciones de ZK de caja negra en el Modelo RO en la sección 3.3 (página 20), atribuido a Yung y Zhao:

Moti Yung y Yunlei Zhao. Cero conocimiento interactivo con oráculos aleatorios restringidos. En Theory of Cryptography - TCC 2006 , LNCS 3876, pp. 21-40, 2006.

cc.complexity-theory cr.crypto-security oracles black-box MS Dousti
fuente

Creo que podría significar "exhaustivo" en lugar de "agotador".

Dave Clarke

Siento disentir. Quise decir que encontré una manera de "agotar" el simulador de protocolos ZK ... No existe el simulador "exhaustivo".

MS Dousti

Culpa mía. Leo agotador como un adjetivo, no como un verbo.

Dave Clarke

Respuestas:

Hay una pregunta de por qué uno querría definir ZK de caja negra en el modelo de oráculo aleatorio. Existen al menos dos razones por las cuales las personas sugirieron la definición de conocimiento de caja negra cero:

1) Para un resultado positivo, cuando dices que un simulador es "conocimiento de caja negra cero", automáticamente te da un buen límite en su tiempo de ejecución (es decir, en lugar de ) y también puede ser útil saber que el simulador no "mira las entrañas de y no le importa si $poly(|x|) \cdot time(V*)$ $poly(time(V*))$ $V*$ $V*$ se implementa usando RAM, circuito, etc. ... Si bien un simulador de modelo de oráculo aleatorio puede ser eficiente, obviamente no es un recuadro negro, porque se supone que de alguna manera debe ver la ejecución de y comprenderlo cuando está evaluando Una función hash. Por esta razón, hay un sentido en el que no tiene sentido decir que un simulador de modelo de oráculo aleatorio es "caja negra". $V*$ $V*$

2) Para un resultado negativo, las personas usan el "simulador de caja negra" para capturar una gran clase de técnicas de prueba. En este caso, puede definir el simulador de caja negra también en el modelo de oráculo aleatorio y la definición que tiene sentido es lo que dijo David. De hecho, para un resultado negativo, incluso no en el modelo de oráculo aleatorio, es mejor si el resultado se cumple incluso si permite el tiempo de ejecución del simulador . De hecho, aunque no siempre se indica, los resultados negativos que conozco tienen esta propiedad, ya que el verificador de trampa es típicamente un algoritmo polinomial fijo que ejecuta algunas funciones pseudoaleatorias, mientras que el simulador puede tener cualquier tiempo de ejecución polinomial. $poly(time(V*))$ $V*$

Boaz Barak
fuente

¿Lo mismo vale para la "simulación universal" ZK? Después de todo, el ZK de caja negra es un tipo de ZK de simulación universal, cuyo tiempo de ejecución se fija antes de que se determine . (Sin embargo, la ZK sin caja negra es un tipo de ZK de simulación universal, en la que S puede ver las "tripas" de V *)

V *

$V*$

MS Dousti

Por favor vea la pregunta editada para algunas referencias.

MS Dousti

Para un simulador universal (sin caja negra), se debe permitir el tiempo de ejecución polinomial en el tiempo de ejecución de ya que de lo contrario el simulador no tiene tiempo para invocar . Pero, en general, el punto que estaba señalando es que el "conocimiento de caja negra cero" no es una definición canónica, sino más bien una herramienta, y esa herramienta se puede usar de manera diferente en el contexto de resultados positivos o negativos para que los resultados sean más significativos.

V^{*}

$V^{*}$

V^{*}

$V^{*}$

Boaz Barak el

Retrasé la respuesta a tu comentario ya que quería leer más. En particular, leí el artículo de Yung y Zhao (citado anteriormente), y noté que usaron ZK de recuadro negro en el modelo RO para un resultado positivo, mientras que usted dijo "no tiene sentido decir que un modelo de oráculo aleatorio simulador es 'caja negra' ". ¿Es su resultado filosóficamente problemático, o deberíamos relajar la definición de caja negra?

MS Dousti

Aquí está mi opinión sobre el problema. Recientemente no he leído ningún documento que trate sobre el conocimiento cero de caja negra en el modelo de oráculo aleatorio (RO), así que solo estoy adivinando lo que significan y no lo que está escrito allí. La respuesta corta (supongo) es que BB-ZK en el modelo RO debería permitir que el simulador se ejecute a tiempo polinomial en | x | y el número de consultas RO emitidas por V *, el verificador de trampa.

Tratemos de justificar esa suposición. Una observación inicial es que el término "pruebas de conocimiento cero de caja negra en el modelo de oráculo aleatorio" necesita una mirada más cercana para definirlo adecuadamente. Los simuladores de caja negra están definidos para funcionar con cualquier oráculo (es decir, el verificador de trampa como una caja negra), y su única interfaz es a través de la entrada / salida del oráculo. Si solo aumentamos este modelo para dar un RO a todas las partes (tal vez al permitir que sus circuitos tengan puertas RO), entonces obtenemos un modelo donde el simulador no puede programar el RO - en una consulta de oráculo, todo (incluidas las consultas RO) sucede "dentro" del oráculo V *, y luego devuelve su siguiente mensaje. Si queremos permitir la programación de RO, entonces necesitamos modificar las interfaces: el simulador ahora obtiene un oráculo de entrada / salida para V * y no un oráculo aleatorio. En cada llamada al oráculo V *, en lugar de producir el siguiente mensaje, el oráculo puede producir la siguiente consulta al RO, y el simulador puede darle la respuesta del RO llamando nuevamente al oráculo. Ahora esto permite la programación de RO, y también podemos permitir que el tiempo de ejecución del simulador dependa de la cantidad de consultas a la RO.

Cualquier exploración adicional del significado de estas definiciones se deja al lector. Estoy pensando sintácticamente.

David Cash
fuente

Gracias por la respuesta David. Independientemente de la capacidad del simulador para programar el RO, debería poder "monitorearlos". Por lo tanto, cada consulta de oráculo de V * desperdicia el tiempo de M al menos en tiempo. Su gran idea es cambiar el modelo para "dejar que el simulador se ejecute a tiempo en el polinomio en | x | y el número de consultas RO emitidas por V *". Ese no es el modelo estándar, pero lo veo como una solución razonable. Sin embargo, creo que los "gigantes" de la comunidad deben reconocer primero la autenticidad de dicho modelo ...

MS Dousti

¿Puedes citar una fuente que defina con precisión "el modelo estándar"? (Ese término se usa a menudo como sinónimo de "no hay oráculos aleatorios u otras modificaciones similares en el modelo de cómputo", pero no creo que esto sea lo que quisiste decir). Mi expectativa es que he bosquejado la definición de lo que se consideraría estándar, y si no, entonces podemos resolverlo sin ningún "gigante" que certifique activamente nuestro razonamiento.

David Cash

Claro, por "modelo estándar" quise decir la "definición estándar" de ZK bajo el modelo RO. Puede consultar el documento de Rafael Pass (citado en la pregunta), o su tesis de maestría (titulada "Variantes alternativas de pruebas de conocimiento cero"), o el documento de Wee en AsiaCrypt 2009 ("Conocimiento cero en el modelo aleatorio de Oracle, revisado") . Ninguno de ellos definió ZK "caja negra" en el modelo RO (todos mencionaron la entrada auxiliar ZK), aunque ninguno se refirió al "polinomio de ejecución en tiempo en | x | y al número de consultas RO realizadas por V *". Por lo tanto, creo que está presentando una nueva definición (¡Google!)

MS Dousti

Por favor vea la pregunta editada para algunas referencias.

MS Dousti