Ecuaciones de campos ocultos

Sistema criptográfico de clave pública

Las ecuaciones de campos ocultos ( HFE ), también conocidas como función trampa HFE , son un criptosistema de clave pública que se introdujo en Eurocrypt en 1996 y fue propuesto por (en francés) Jacques Patarin siguiendo la idea del sistema Matsumoto e Imai. Se basa en polinomios sobre campos finitos de diferente tamaño para disfrazar la relación entre la clave privada y la clave pública . HFE es, de hecho, una familia que consta de HFE básico y versiones combinatorias de HFE. La familia de criptosistemas HFE se basa en la dificultad del problema de encontrar soluciones a un sistema de ecuaciones cuadráticas multivariadas (el llamado problema MQ), ya que utiliza transformaciones afines privadas para ocultar el campo de extensión y los polinomios privados . Las ecuaciones de campos ocultos también se han utilizado para construir esquemas de firma digital, por ejemplo, Quartz y Sflash. ^[1] ${\displaystyle \mathbb {F} _{q}}$

Antecedentes matemáticos

Una de las nociones centrales para entender cómo funcionan las ecuaciones de campos ocultos es ver que para dos campos de extensión sobre el mismo campo base se puede interpretar un sistema de polinomios multivariados en variables sobre como una función utilizando una base adecuada de sobre . En casi todas las aplicaciones los polinomios son cuadráticos, es decir, tienen grado 2. ^[2] Comenzamos con el tipo más simple de polinomios, es decir, los monomios, y mostramos cómo conducen a sistemas cuadráticos de ecuaciones. ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q^{m}}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q}}$

Consideremos un cuerpo finito , donde es una potencia de 2, y un cuerpo de extensión . Sea tal que para algún y mcd . La condición mcd es equivalente a exigir que la función en sea uno a uno y su inversa sea la función donde es la inversa multiplicativa de . ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q}$ ${\displaystyle K}$ ${\displaystyle 0<h<q^{n}}$ ${\displaystyle h=q^{\theta }+1}$ ${\displaystyle \theta }$ ${\displaystyle (h,q^{n}-1)=1}$ ${\displaystyle (h,q^{n}-1)=1}$ ${\displaystyle u\to u^{h}}$ ${\displaystyle K}$ ${\displaystyle u\to u^{h'}}$ ${\displaystyle h'}$ ${\displaystyle h\ {\bmod {q}}^{n}-1}$

Tome un elemento aleatorio . Defina por ${\displaystyle u\in \mathbb {F} _{q^{n}}}$ ${\displaystyle w\in \mathbb {F} _{q^{n}}}$

${\displaystyle w=u^{h}=u^{q^{\theta }}u\ \ \ \ (1)}$

Sea una base de como un espacio vectorial . Representamos con respecto a la base como y . Sea la matriz de la transformación lineal con respecto a la base , es decir tal que ${\displaystyle \beta _{1},...,\beta _{n}}$ ${\displaystyle K}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle u}$ ${\displaystyle u=(u_{1},...,u_{n})}$ ${\displaystyle w=(w_{1},...,w_{n})}$ ${\displaystyle A^{(k)}={a_{ij}^{(k)}}}$ ${\displaystyle u\to u^{q^{k}}}$ ${\displaystyle \beta _{1},...,\beta _{n}}$

${\displaystyle \beta _{i}^{q^{k}}=\sum _{j=1}^{n}a_{ij}^{k}\beta _{j},\ \ a_{ij}^{k}\in \mathbb {F} _{q}}$

para . Además, escribe todos los productos de los elementos base en términos de la base, es decir: ${\displaystyle 1\leq i,k\leq n}$

${\displaystyle \beta _{i}\beta _{j}=\sum _{l=1}^{n}m_{ijl}\beta _{l},\ \ m_{ijl}\in \mathbb {F} _{q}}$

para cada . El sistema de ecuaciones que es explícito en el y cuadrático en el se puede obtener desarrollando (1) e igualando a cero los coeficientes de los . ${\displaystyle 1\leq i,j\leq n}$ ${\displaystyle n}$ ${\displaystyle w_{i}}$ ${\displaystyle u_{j}}$ ${\displaystyle \beta _{i}}$

Elija dos transformaciones afines secretas y , es decir, dos matrices invertibles y con entradas en y dos vectores y de longitud sobre y defina y mediante: ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle n\times n}$ ${\displaystyle M_{S}=\{S_{ij}\}}$ ${\displaystyle M_{T}=\{T_{ij}\}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle v_{S}}$ ${\displaystyle v_{T}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle u=Sx=M_{S}x+v_{S}\ \ \ \ w=Ty=M_{T}y+v_{T}\ \ \ \ (2)}$

Al utilizar las relaciones afines en (2) para reemplazar con , el sistema de ecuaciones es lineal en y de grado 2 en . Al aplicar álgebra lineal, se obtendrán ecuaciones explícitas, una para cada uno de los polinomios de grado 2 en . ^[3] ${\displaystyle u_{j},w_{i}}$ ${\displaystyle x_{k},y_{l}}$ ${\displaystyle n}$ ${\displaystyle y_{l}}$ ${\displaystyle x_{k}}$ ${\displaystyle n}$ ${\displaystyle y_{l}}$ ${\displaystyle x_{k}}$

Criptosistema multivariante

La idea básica de la familia HFE de usar esto como un criptosistema multivariante es construir la clave secreta a partir de un polinomio en una incógnita sobre un campo finito (normalmente se usa el valor ). Este polinomio se puede invertir fácilmente sobre , es decir, es factible encontrar cualquier solución a la ecuación cuando dicha solución existe. La transformación secreta, ya sea descifrado y/o firma, se basa en esta inversión. Como se explicó anteriormente, se puede identificar con un sistema de ecuaciones que usa una base fija. Para construir un criptosistema, el polinomio debe transformarse de modo que la información pública oculte la estructura original y evite la inversión. Esto se hace viendo los campos finitos como un espacio vectorial sobre y eligiendo dos transformaciones afines lineales y . El triplete constituye la clave privada. El polinomio privado se define sobre . ^{[1] [4]} La clave pública es . A continuación se muestra el diagrama para MQ-trapdoor en HFE ${\displaystyle P}$ ${\displaystyle x}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle q=2}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle P(x)=y}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle (S,P,T)}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle (S,P,T)}$

${\displaystyle {\text{input}}x\to x=(x_{1},...,x_{n}){\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}{\text{output}}y}$

Polinomio HFE

El polinomio privado con grado sobre es un elemento de . Si los términos del polinomio tienen como máximo términos cuadráticos sobre entonces mantendrá pequeño el polinomio público. ^[1] El caso que consiste en monomios de la forma , es decir con 2 potencias de en el exponente es la versión básica de HFE , es decir se elige como ${\displaystyle P}$ ${\displaystyle d}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle \mathbb {F} _{q^{n}}[x]}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle P}$ ${\displaystyle x^{q^{s_{i}}+q^{t_{i}}}}$ ${\displaystyle q}$ ${\displaystyle P}$

${\displaystyle P(x)=\sum c_{i}x^{q^{s_{i}}+q^{t_{i}}}}$

El grado del polinomio también se conoce como parámetro de seguridad y cuanto mayor sea su valor, mejor para la seguridad, ya que el conjunto resultante de ecuaciones cuadráticas se asemeja a un conjunto de ecuaciones cuadráticas elegidas al azar. Por otro lado, un valor grande ralentiza el desciframiento. Dado que es un polinomio de grado como máximo el inverso de , denotado por se puede calcular en operaciones. ^[5] ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle P}$ ${\displaystyle d}$ ${\displaystyle P}$ ${\displaystyle P^{-1}}$ ${\displaystyle d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}}$

Cifrado y descifrado

La clave pública está dada por los polinomios multivariados sobre . Por lo tanto, es necesario transferir el mensaje desde para cifrarlo, es decir, suponemos que es un vector . Para cifrar el mensaje evaluamos cada uno en . El texto cifrado es . ${\displaystyle n}$ ${\displaystyle (p_{1},...,p_{n})}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle M}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}}$ ${\displaystyle M}$ ${\displaystyle (x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}}$ ${\displaystyle M}$ ${\displaystyle p_{i}}$ ${\displaystyle (x_{1},...,x_{n})}$ ${\displaystyle (p_{1}(x_{1},...,x_{n}),p_{2}(x_{1},...,x_{n}),...,p_{n}(x_{1},...,x_{n}))\in \mathbb {F} _{q}^{n}}$

Para entender el descifrado, expresemos el cifrado en términos de . Tenga en cuenta que estos no están disponibles para el remitente. Al evaluar en el mensaje, primero aplicamos , lo que da como resultado . En este punto , se transfiere de para que podamos aplicar el polinomio privado que es sobre y este resultado se denota por . Una vez más, se transfiere al vector y se aplica la transformación y el resultado final se produce a partir de . ${\displaystyle S,T,P}$ ${\displaystyle p_{i}}$ ${\displaystyle S}$ ${\displaystyle x'}$ ${\displaystyle x'}$ ${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{n}}}$ ${\displaystyle P}$ ${\displaystyle \mathbb {F} _{q^{n}}}$ ${\displaystyle y'\in \mathbb {F} _{q^{n}}}$ ${\displaystyle y'}$ ${\displaystyle (y_{1}',...,y_{n}')}$ ${\displaystyle T}$ ${\displaystyle y\in \mathbb {F} _{q^{n}}}$ ${\displaystyle (y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}}$

Para descifrar , los pasos anteriores se realizan en orden inverso. Esto es posible si se conoce la clave privada. El paso crucial en el desciframiento no es la inversión de y sino más bien los cálculos de la solución de . Como no es necesariamente una biyección, se puede encontrar más de una solución para esta inversión (existen como máximo d soluciones diferentes ya que es un polinomio de grado d). La redundancia denotada como se agrega en el primer paso al mensaje para seleccionar la correcta del conjunto de soluciones . ^{[1] [3] [6]} El diagrama siguiente muestra el HFE básico para cifrado. ${\displaystyle y}$ ${\displaystyle (S,P,T)}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle P(x')=y'}$ ${\displaystyle P}$ ${\displaystyle X'=(x_{1}',...,x_{d}')\in \mathbb {F} _{q^{n}}}$ ${\displaystyle P}$ ${\displaystyle r}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle X'}$

${\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}:P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y}$

Variaciones de HFE

Las ecuaciones de campo oculto tienen cuatro variantes básicas, a saber, +, -, v y f , y es posible combinarlas de diversas formas. El principio básico es el siguiente:

01. El signo + consiste en una mezcla lineal de las ecuaciones públicas con algunas ecuaciones aleatorias.

02. El signo - se debe a Adi Shamir y pretende eliminar la redundancia 'r' de las ecuaciones públicas.

03. El signo f consiste en fijar algunas variables de entrada de la clave pública. ${\displaystyle f}$

04. El signo v se define como una construcción a veces bastante compleja, de modo que la inversa de la función se puede encontrar solo si algunas v de las variables llamadas variables de vinagre son fijas. Esta idea se debe a Jacques Patarin.

Las operaciones anteriores preservan hasta cierto punto la solubilidad de la función.

HFE- y HFEv son muy útiles en los esquemas de firma, ya que evitan que se ralentice la generación de firmas y también mejoran la seguridad general de HFE, mientras que para el cifrado, tanto HFE- como HFEv darán lugar a un proceso de descifrado bastante lento , por lo que no se pueden eliminar demasiadas ecuaciones (HFE-) ni se deben añadir demasiadas variables (HFEv). Tanto HFE- como HFEv se utilizaron para obtener Quartz.

Para el cifrado, la situación es mejor con HFE+ ya que el proceso de descifrado toma la misma cantidad de tiempo, sin embargo la clave pública tiene más ecuaciones que variables. ^{[1] [2]}

Ataques de HFE

Hay dos ataques famosos contra HFE:

Recuperar la clave privada ( Shamir -Kipnis): el punto clave de este ataque es recuperar la clave privada como polinomios univariados dispersos sobre el campo de extensión . El ataque solo funciona para HFE básico y falla para todas sus variantes. ${\displaystyle \mathbb {F} _{q^{n}}}$

Bases rápidas de Gröbner (Faugère): La idea de los ataques de Faugère es utilizar un algoritmo rápido para calcular una base de Gröbner del sistema de ecuaciones polinómicas. Faugère superó el desafío HFE 1 en 96 horas en 2002, y en 2003 Faugère y Joux trabajaron juntos en la seguridad de HFE. ^[1]

Referencias

1. Christopher Wolf y Bart Preneel, Criptografía asimétrica: ecuaciones de campo ocultas
2. Nicolas T. Courtois Sobre criptosistemas de clave pública multivariados basados ​​únicamente en firmas
3. Ilia Toli Criptosistemas polinomiales ocultos
4. Jean-Charles Faugère y Antoine Joux , Criptoanálisis algebraico de sistemas criptográficos de ecuaciones de campo oculto (HFE) utilizando bases de Gröbner Archivado el 11 de noviembre de 2008 en Wayback Machine
5. Nicolas T. Courtois, "La seguridad de las ecuaciones de campo ocultas"
6. Jacques Patarin, Ecuaciones de campo oculto (HFE) y polinomio isomorfo (IP): dos nuevas familias de algoritmos asimétricos

• Nicolas T. Courtois, Magnus Daum y Patrick Felke, Sobre la seguridad de HFE, HFEv y cuarzo
• Andrey Sidorenko, Ecuaciones de campo oculto, Seminario EIDMA 2004 Technische Universiteit Eindhoven
• Yvo G. Desmet, Criptografía de clave pública (PKC) 2003, ISBN  3-540-00324-X