Sobre la técnica de prueba de las firmas de brecha de Boneh-Lynn-Shacham

8

En el documento "Firmas cortas del emparejamiento de Weil" de Boneh, Lynn y Shacham, estaba revisando la prueba de seguridad como cualquier otra firma.

Pero la técnica utilizada en este artículo es bastante única. En lugar de utilizar la interacción normal de retador y adversario, han dividido la prueba en 6 juegos donde cada juego se extiende secuencialmente de los juegos anteriores.

No estoy seguro de por qué han utilizado este enfoque en lugar del juego normal. ¿Este tipo de prueba de seguridad ayuda a reducir la probabilidad más fácilmente o simplemente la han dado desde un punto de vista "fácil de leer y comprender"?

¡Gracias!

reference-request cr.crypto-security Maverickgugu
fuente

Respuestas:

11

La técnica de "saltar" de un juego a otro y demostrar la seguridad a través de una "secuencia de juegos" no es nueva. En particular, hay varios documentos que analizan estas técnicas y las ejemplifican a través de varias pruebas de seguridad. Los ejemplos famosos son:

Con respecto a su pregunta, uso una cita del último artículo citado anteriormente:

En una prueba de salto de juego, observamos que un atacante que se ejecuta en un entorno de ataque particular tiene una probabilidad desconocida de éxito. Luego, modificamos lentamente el entorno de ataque hasta que se pueda calcular la probabilidad de éxito del atacante. También limitamos el aumento en la probabilidad de éxito del atacante causado por los cambios en el entorno de ataque. Por lo tanto, podemos deducir un límite para la probabilidad de éxito del atacante en el entorno original.

Por lo tanto, la razón para usar varios juegos es que en cada juego, simplificamos el cálculo de alguna probabilidad desconocida, sin alterarlo de manera significativa. Esto continúa hasta llegar a un juego en el que el cálculo de la probabilidad es bastante fácil.

MS Dousti
fuente
Gracias por las referencias !! Voy a comentar después de estudiar a través de estos documentos para una mejor imagen. Pero para mantenerlo más abstracto, ¿se pueden convertir tales pruebas secuenciales basadas en juegos en una sola prueba de juego y calcular la probabilidad como un todo?
Maverickgugu
@Maverickgugu: ¡De nada! Repasar su pregunta: a veces es posible convertir varios juegos en uno, pero la prueba se vuelve más complicada. (Si recuerdo correctamente, la primera o la segunda referencia citada en mi respuesta menciona uno de esos juegos). Pero en general, tal prueba puede volverse muy compleja e incluso imposible de llevar a cabo. Creo que puedes resolver esto intentando fusionar los 6 juegos en la prueba Boneh-Lynn-Shacham, y ver por ti mismo dónde surge el problema.
MS Dousti
@Sadiq Dousti: En el artículo de Shoup mencionó "Además, incluso cuando esta técnica es aplicable, es solo una herramienta para organizar una prueba: las ideas reales para una construcción criptográfica y un análisis de seguridad deben venir de otra parte". Con ese argumento, intenté condensar los 6 juegos a 1 en la prueba Boneh-Lynn-Shacham y no puedo encontrar ninguna dificultad en la fusión. Sentí que simplemente estaba combinando claramente todas las condiciones adicionales y los eventos de falla que dan la probabilidad final. ¿Me pueden ayudar con alguna información sutil que me estoy perdiendo?
Maverickgugu
@Maverickgugu: envíeme la prueba combinada por correo electrónico. Puedes encontrar mi información de contacto aquí .
MS Dousti
2

La idea de usar una secuencia de juegos como parte de una prueba reduccionista de seguridad es anterior a las referencias dadas (está implícito en el trabajo que data de principios de los 80 si no antes, y explícito al menos a fines de los 90).

usuario686
fuente
Si puedo sugerir una mejora, puede agregar algunos ejemplos como trabajos en los que la idea de "secuencia de juegos" está implícita (mi respuesta ya cubre algunos de los ejemplos explícitos).
MS Dousti