El lema de la bifurcación es uno de varios lemas relacionados en la investigación criptográfica . El lema establece que si un adversario (normalmente una máquina de Turing probabilística ), 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 con 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 enuncia de la siguiente manera. [4] Sea A un algoritmo probabilístico, con entradas ( x , h 1 , ..., h q ; r ) que produce como salida 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 extraen cada uno de los valores h i de acuerdo con 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.
Podemos entonces 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 produzca un triple que comience con 1, dada una entrada x elegida aleatoriamente de IG . Entonces
La idea aquí es pensar en A como si se ejecutara dos veces en ejecuciones relacionadas, donde el proceso " se bifurca " en un punto determinado, cuando se ha examinado parte de la entrada, pero no toda. En la versión alternativa, las entradas restantes se vuelven a generar, pero se generan de la manera 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 el enunciado del lema elige el punto de ramificación ( J ) en función de la salida de A . El requisito de que h J ≠ h' J es un requisito técnico requerido por muchos usos del lema. (Obsérvese 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 oráculo aleatorio . Entonces x serían los parámetros públicos (incluyendo 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 bifurcación es útil cuando sería posible, dadas dos firmas aleatorias diferentes del mismo mensaje, resolver algún problema subyacente difícil. Sin embargo, un adversario que falsifica una vez da lugar a uno que falsifica dos veces en el mismo mensaje con una probabilidad no despreciable a través del lema de bifurcación. Cuando A intenta falsificar en 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 la salida es (0, y ).)
Por el lema de la bifurcación, la probabilidad ( frk ) de obtener dos falsificaciones buenas 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 lo es. Esto nos permite demostrar que si el problema subyacente difícil es realmente difícil, entonces ningún adversario puede falsificar firmas.
Esta 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 bifurcación no es estricta. Pointcheval y Stern propusieron argumentos de seguridad para las firmas digitales y las firmas ciegas 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 de ejecuciones concurrentes (el caso estudiado y demostrado como seguro por Pointcheval y Stern). Benhamouda, Lepoint, Raykova y Orrù mostraron en 2020 un ataque de tiempo polinomial para ejecuciones concurrentes. Schnorr también sugirió mejoras para asegurar los esquemas de firmas ciegas basados en el problema del logaritmo discreto . [9]
