Criptografía basada en emparejamientos

La criptografía basada en emparejamientos es el uso de un emparejamiento entre elementos de dos grupos criptográficos con un tercer grupo mediante una asignación.${\displaystyle e:G_{1}\times G_{2}\to G_{T}}$construir o analizar sistemas criptográficos .

La siguiente definición se utiliza comúnmente en la mayoría de los trabajos académicos. ^{[ 1 ]}

Dejar${\displaystyle \mathbb {F} _{q}}$sea ​​un cuerpo finito sobre números primos${\displaystyle q}$,${\displaystyle G_{1},G_{2}}$dos grupos cíclicos aditivos de orden primo${\displaystyle q}$, y${\displaystyle G_{T}}$otro grupo cíclico de orden${\displaystyle q}$escrito de forma multiplicativa. Un emparejamiento es un mapa:${\displaystyle e:G_{1}\times G_{2}\rightarrow G_{T}}$, que satisface las siguientes propiedades:

Bilinealidad

${\displaystyle \forall a,b\in \mathbb {F} _{q}^{*},P\in G_{1},Q\in G_{2}:\ e\left(aP,bQ\right)=e\left(P,Q\right)^{ab}}$

No degeneración

Si${\displaystyle P}$genera${\displaystyle G_{1}}$y${\displaystyle Q}$genera${\displaystyle G_{2}}$, entonces${\displaystyle e(P,Q)}$genera${\displaystyle G_{T}}$(es decir,${\displaystyle e(P,Q)\neq 1}$).

Computabilidad

Existe un algoritmo eficiente para calcular${\displaystyle e}$.

Si se utiliza el mismo grupo para los dos primeros grupos (es decir,${\displaystyle G_{1}=G_{2}}$), el emparejamiento se llama simétrico y es una correspondencia de dos elementos de un grupo a un elemento de un segundo grupo.

Algunos investigadores clasifican las instancias de emparejamiento en tres (o más) tipos básicos:

1. ${\displaystyle G_{1}=G_{2}}$;
2. ${\displaystyle G_{1}\neq G_{2}}$pero existe un homomorfismo computable eficientemente${\displaystyle \phi:G_{2}\a G_{1}}$;
3. ${\displaystyle G_{1}\neq G_{2}}$y no existen homomorfismos computables eficientemente entre${\displaystyle G_{1}}$y${\displaystyle G_{2}}$. ^{[ 2 ]}

Si son simétricos, los emparejamientos pueden utilizarse para reducir un problema difícil de un grupo a un problema diferente, generalmente más fácil, en otro grupo.

Por ejemplo, en grupos equipados con una función de mapeo bilineal como el emparejamiento de Weil o el emparejamiento de Tate , se cree que las generalizaciones del problema computacional de Diffie-Hellman (CDH) son inviables, mientras que el problema decisional de Diffie-Hellman (DDH), más simple, se puede resolver fácilmente utilizando la función de emparejamiento . Al primer grupo se le denomina a veces Grupo de Brecha debido a la supuesta diferencia de dificultad entre estos dos problemas en el grupo. ^{[ 3 ]}

Para ilustrarlo, dejemos${\displaystyle e:G\times G\to G_{T}}$sea ​​un emparejamiento bilineal simétrico, no degenerado y computable eficientemente, donde${\displaystyle G}$es un grupo multiplicativo con generador${\displaystyle g}$. Consideremos un ejemplo del problema CDH: dado${\displaystyle g}$,${\displaystyle g^{x}}$, y${\displaystyle g^{y}}$, el objetivo es calcular${\displaystyle g^{xy}}$La función de emparejamiento${\displaystyle e}$no nos ayuda directamente a calcular${\displaystyle g^{xy}}$, lo que deja el problema CDH presumiblemente intratable. Sin embargo, dada una solución candidata${\displaystyle g^{z}}$, podemos comprobar si${\displaystyle g^{z}=g^{xy}}$(resolviendo así el problema de la displasia del desarrollo de la cadera) sin saberlo${\displaystyle x}$,${\displaystyle y}$, o${\displaystyle z}$, comprobando si:

${\displaystyle e(g^{x},g^{y})=e(g,g^{z})}$

Utilizando la propiedad bilineal, podemos extraer los exponentes:

${\displaystyle e(g^{x},g^{y})=e(g,g)^{xy}}$y${\displaystyle e(g,g^{z})=e(g,g)^{z}}$

Desde${\displaystyle G_{T}}$es un grupo de orden primo, la igualdad${\displaystyle e(g,g)^{xy}=e(g,g)^{z}}$implica${\displaystyle xy\equiv z{\pmod {q}}}$, validando la respuesta candidata.

Aunque se utilizaron por primera vez para el criptoanálisis , ^{[ 4 ]} los emparejamientos también se han utilizado para construir muchos sistemas criptográficos para los que no se conoce otra implementación eficiente, como el cifrado basado en identidad o los esquemas de cifrado basados ​​en atributos .

La criptografía basada en emparejamientos se utiliza en el esquema de compromiso criptográfico KZG y se ejemplifica en el esquema de firma digital BLS . ^{[ 3 ]}

En junio de 2012, el Instituto Nacional de Tecnologías de la Información y las Comunicaciones (NICT), la Universidad de Kyushu y Fujitsu Laboratories Limited mejoraron el límite anterior para calcular con éxito un logaritmo discreto en una curva elíptica supersingular de 676 bits a 923 bits. ^{[ 5 ]}

En 2016, el algoritmo Extended Tower Number Field Sieve (exTNFS) ^{[ 6 ]} permitió reducir la complejidad de encontrar logaritmos discretos en algunos grupos de emparejamientos resultantes. Existen varias variantes del algoritmo de tamiz de campo de números de torre múltiple y extendido que amplían la aplicabilidad y mejoran la complejidad del algoritmo. En 2019 se publicó una descripción unificada de todos estos algoritmos con mejoras adicionales. ^{[ 7 ]} En vista de estos avances, varios trabajos ^{[ 8 ] [ 9 ]} proporcionaron estimaciones concretas revisadas sobre los tamaños de clave de los criptosistemas seguros basados ​​en emparejamientos.

• Conferencia sobre criptografía basada en emparejamientos
• Biblioteca PBC de Ben Lynn