El lema de bifurcación es cualquiera de varios lemas relacionados en la investigación de criptografía . El lema establece que si un adversario (típicamente una máquina probabilística de Turing ), con entradas extraídas de alguna distribución , produce una salida que tiene alguna propiedad con una probabilidad no despreciable , entonces con una probabilidad no despreciable, si el adversario se vuelve a ejecutar 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 la 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, entonces 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 la bifurcación fue generalizado posteriormente por Mihir Bellare y Gregory Neven. [4] El lema de la bifurcación se ha utilizado y 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áculos aleatorios. [2] [5] [6]
La versión generalizada del lema se establece a continuación. [4] Sea A un algoritmo probabilístico, con entradas ( x , h 1 , ..., h q ; r ) que genera un par ( J , y ), donde r se refiere a la cinta aleatoria de A (es decir, las elecciones aleatorias que hará A). Supongamos 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 extrae cada uno de los valores h i según la distribución uniforme . Sea acc la probabilidad de que en entradas distribuidas como se describe, la salida J de A sea mayor o igual a 1.
Luego podemos definir un "algoritmo de bifurcación" F A que procede de la siguiente manera, en la entrada x :
Sea frk la probabilidad de que F A genere un triple que comience con 1, dada una entrada x elegida aleatoriamente de IG . Entonces
La idea aquí es pensar que A se ejecuta dos veces en ejecuciones relacionadas, donde el proceso se " bifurca " en un punto determinado, cuando se han examinado algunas, pero no todas, las entradas. En la versión alternativa, las entradas restantes se regeneran pero se generan de la forma normal. El punto en el que el proceso se bifurca puede ser algo que solo queramos decidir más tarde, posiblemente en función del comportamiento de A la primera vez: es por eso que la declaración del lema elige el punto de bifurcación ( J ) en función de la salida de A . El requisito de que h J ≠ h' J es técnico y requerido por muchos usos del lema. (Tenga en cuenta que, dado que tanto h J como h' J se eligen aleatoriamente de H , entonces si h es grande, como suele ser el caso, la probabilidad de que los dos valores no sean distintos es extremadamente pequeña).
Por ejemplo, sea A un algoritmo para romper un esquema de firma digital en el modelo de Oracle aleatorio . Entonces x serían los parámetros públicos (incluida la clave pública) que A está atacando, y h i sería la salida del oráculo aleatorio en su i -ésima entrada distinta. El lema de la bifurcación es útil cuando sería posible, dadas dos firmas aleatorias diferentes del mismo mensaje, resolver algún problema difícil subyacente. Sin embargo, un adversario que falsifica una vez da lugar a uno que falsifica dos veces el mismo mensaje con una probabilidad no despreciable a través del lema de la 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 fue la J -ésima consulta única al oráculo aleatorio (se puede suponer que A consultará m en algún momento, si A tiene éxito con una probabilidad no despreciable). (Si A genera una falsificación incorrecta, consideramos que el resultado es (0, y ).)
Según el lema de la bifurcación, la probabilidad ( frk ) de obtener dos buenas falsificaciones y e y' en el mismo mensaje pero con diferentes resultados aleatorios del oráculo (es decir, con h J ≠ h' J ) no es despreciable cuando acc tampoco lo es. -despreciable. Esto nos permite demostrar que si el problema subyacente es realmente difícil, ningún adversario puede falsificar firmas.
Ésta es la esencia de la prueba dada por Pointcheval y Stern para un esquema de firma ElGamal modificado contra un adversario adaptativo.
La reducción proporcionada por el lema de la bifurcación no es estricta. Pointcheval y Stern propusieron argumentos de seguridad para firmas digitales y firmas ciegas utilizando Forking Lemma. [7] Claus P. Schnorr proporcionó un ataque a los esquemas de firmas ciegas de Schnorr, [8] con más de ejecuciones simultáneas (el caso fue estudiado y demostrado ser seguro por Pointcheval y Stern). Benhamouda, Lepoint, Raykova y Orrù mostraron en 2020 un ataque en tiempo polinomial, para ejecuciones concurrentes. Schnorr también sugirió mejoras para asegurar esquemas de firmas ciegas basados en problemas de logaritmos discretos . [9]
