El lema de bifurcación es cualquiera de varios lemas relacionados en la investigación de la criptografía . El lema establece que si un adversario (típicamente una máquina de Turing probabilística ), en entradas extraídas de alguna distribución , produce una salida que tiene alguna propiedad con probabilidad no despreciable , entonces con probabilidad no despreciable, si el adversario se vuelve a ejecutar en nuevas entradas pero con la misma cinta aleatoria , su segunda salida también tendrá la propiedad.
Este concepto fue utilizado por primera vez por David Pointcheval y Jacques Stern en "Pruebas de seguridad para esquemas de firma", publicado en las actas de Eurocrypt 1996. [1] [2] En su artículo, el lema de bifurcación se especifica en términos de un adversario que ataca un esquema de firma digital instanciado en el modelo de oráculo aleatorio . Muestran que si un adversario puede falsificar una firma con una probabilidad no despreciable, existe una probabilidad no despreciable de que el mismo adversario con la misma cinta aleatoria pueda crear una segunda falsificación en un ataque con un oráculo aleatorio diferente. [3] El lema de bifurcación fue posteriormente generalizado por Mihir Bellare.y Gregory Neven. [4] El lema de bifurcación se ha utilizado y se ha generalizado aún más para demostrar la seguridad de una variedad de esquemas de firma digital y otras construcciones criptográficas basadas en oráculo aleatorio. [2] [5] [6]
Declaración del lema
La versión generalizada del lema se expresa de la siguiente manera. [4] Sea A un algoritmo probabilístico, con entradas ( x , h 1 , ..., h q ; r ) que produce un par ( J , y ), donde r se refiere a la cinta aleatoria de A (es decir, las elecciones aleatorias que A tomará). Suponga además que IG es una distribución de probabilidad de la que se extrae x , y que H es un conjunto de tamaño h del que se extraen cada uno de los valores de h i de acuerdo con la distribución uniforme . Sea acc la probabilidad de que en las entradas distribuidas como se describe, la salida J de A sea mayor o igual que 1.
Entonces podemos definir un "algoritmo de bifurcación" F A que procede de la siguiente manera, en la entrada x :
- Escoja una cinta aleatorio r para A .
- Escoja h 1 , ..., h q uniformemente de H .
- Ejecute A en la entrada ( x , h 1 , ..., h q ; r ) para producir ( J , y ).
- Si J = 0, devuelve (0, 0, 0).
- Escoja h ' J , ..., h' q uniformemente de H .
- Ejecute A en la entrada ( x , h 1 , ..., h J −1 , h ' J , ..., h ' q ; r ) para producir ( J ', y ').
- Si J ' = J y h J ≠ h' J , devuelve (1, y , y '); de lo contrario, devuelve (0, 0, 0).
Sea frk la probabilidad de que F A produzca un triple comenzando con 1, dada una entrada x elegida aleatoriamente de IG . Luego
Intuición
La idea aquí es pensar que A se ejecuta dos veces en ejecuciones relacionadas, donde el proceso se " bifurca " en un cierto punto, cuando se han examinado algunas pero no todas las entradas. En la versión alternativa, las entradas restantes se vuelven a generar pero se generan de la forma normal. El punto en el cual los tenedores de proceso pueden ser algo que sólo queremos decidir más tarde, posiblemente basado en el comportamiento de una de la primera vez: esta es la razón por la declaración lema elige el punto de ramificación ( J ) basándose en la salida de la A . El requisito de que h J ≠ h ' J es técnico requerido por muchos usos del lema. (Tenga en cuenta que, dado que tanto h J como h ' J se eligen al azar de H , entonces si h es grande, lo que sería normal, la probabilidad de que los dos valores no sean distintos es extremadamente pequeña).
Ejemplo
Por ejemplo, sea A un algoritmo para romper un esquema de firma digital en el modelo de oráculo aleatorio . Entonces x serían los parámetros públicos (incluida la clave pública) A está atacando, y h i sería la salida del oráculo aleatorio en su i- ésima entrada distinta. El lema de bifurcación es útil cuando sería posible, dadas dos firmas aleatorias diferentes del mismo mensaje, resolver algún problema difícil subyacente. Un adversario que falsifica una vez, sin embargo, da lugar a uno que falsifica dos veces el mismo mensaje con una probabilidad no despreciable a través del lema de bifurcación. Cuando A intenta falsificar un mensaje m , consideramos que la salida de A es ( J , y ) donde y es la falsificación, y J es tal que m era la J -ésima consulta única al oráculo aleatorio (se puede suponer que A consultará m en algún momento, si A va a tener éxito con una probabilidad no despreciable). (Si A produce una falsificación incorrecta, consideramos que la salida es (0, y )).
Por el lema de bifurcación, la probabilidad ( frk ) de obtener dos buenas falsificaciones y e y ' en el mismo mensaje pero con diferentes salidas de oráculo aleatorias (es decir, con h J ≠ h' J ) no es despreciable cuando acc tampoco es -despreciable. Esto nos permite demostrar que si el problema subyacente es realmente difícil, ningún adversario puede falsificar firmas.
Esta es la esencia de la prueba dada por Pointcheval y Stern para un esquema de firma de ElGamal modificado contra un adversario adaptativo.
Problemas conocidos con la aplicación del lema de bifurcación
La reducción proporcionada por el lema de bifurcación no es una reducción estricta. Pointcheval y Stern propusieron argumentos de seguridad para las firmas digitales y la firma ciega utilizando el lema de bifurcación. [7] Claus P. Schnorr proporcionó un ataque a los esquemas de firmas ciegas de Schnorr, [8] con más deejecuciones concurrentes (el caso estudiado y probado como seguro por Pointcheval y Stern). Un ataque de tiempo polinomial, porejecuciones simultáneas, fue mostrado en 2020 por Benhamouda, Lepoint, Raykova y Orrù. Schnorr también sugirió mejoras para asegurar esquemas de firmas ciegas basados en problemas de logaritmos discretos . [9]
Referencias
- ^ Ernest Brickell , David Pointcheval , Serge Vaudenay y Moti Yung , " Validaciones de diseño para esquemas de firma basados en logaritmos discretos ", Tercer taller internacional sobre práctica y teoría en criptosistemas de clave pública, PKC 2000, Melbourne , Australia , 18-20 de enero de 2000 , págs. 276-292.
- ^ a b Adam Young y Moti Yung, "Criptografía maliciosa: Exposición de la criptovirología", Wiley Press, 2004, págs. 344.
- ^ David Pointcheval y Jacques Stern , " Pruebas de seguridad para esquemas de firmas ", Avances en criptología - EUROCRYPT '96, Zaragoza , España , 12-16 de mayo de 1996, págs. 387-398.
- ^ a b Mihir Bellare y Gregory Neven, " Firmas múltiples en el modelo llano de clave pública y un lema de bifurcación general ", Actas de la 13a Conferencia de la Asociación de Maquinaria de Computación (ACM) sobre Seguridad de Computadoras y Comunicaciones (CCS), Alejandría, Virginia , 2006, págs. 390–399.
- ↑ Ali Bagherzandi, Jung Hee Cheon, Stanislaw Jarecki: Firmas múltiples seguras bajo la suposición de logaritmo discreto y un lema de bifurcación generalizado. 449-458
- ^ Javier Herranz, Germán Sáez: bifurcando lemas para esquemas de firmas en anillo. 266-279
- ^ David Pointcheval y Jacques Stern, "Argumentos de seguridad para firmas digitales y firmas ciegas", REVISTA DE CRIPTOLOGÍA , volumen 13, págs. 361-396, 2000. Disponible en Internet .
- ^ CPSchnorr, "Seguridad de firmas de registros discretos ciegos contra ataques interactivos", Actas de ICICS 2001, LNCS vol. 2229 , págs. 1-13, 2001. Disponible en Internet. Archivado el 13 de junio de 2011 en Wayback Machine .
- ^ CP Schnorr, "Mejorar la seguridad de las firmas DL ciegas perfectas", Ciencias de la información, Elsevier, vol. 176, págs. 1305--1320, 2006. Disponible en Internet. Archivado el 13 de junio de 2011en Wayback Machine.