Ecuaciones de campo oculto

Las ecuaciones de campos ocultos ( HFE ), también conocidas como función de puerta trasera HFE , son un criptosistema de clave pública que se presentó en Eurocrypt en 1996 y fue propuesto por Jacques Patarin (en francés) siguiendo la idea del sistema de Matsumoto e Imai. Se basa en polinomios sobre campos finitos.${\displaystyle \mathbb {F} _{q}}$de diferente tamaño para disimular 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 campo oculto también se han utilizado para construir esquemas de firma digital, por ejemplo, Quartz y Sflash. ^{[ 1 ]}

Una de las nociones centrales para entender cómo funcionan las ecuaciones de campo oculto es ver que para dos campos de extensión${\displaystyle \mathbb {F} _{q^{n}}}$${\displaystyle \mathbb {F} _{q^{m}}}$sobre el mismo campo de base${\displaystyle \mathbb {F} _{q}}$uno puede interpretar un sistema de${\displaystyle m}$polinomios multivariados en${\displaystyle n}$variables sobre${\displaystyle \mathbb {F} _{q}}$como función${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{m}}}$mediante el uso de una base adecuada de${\displaystyle \mathbb {F} _{q^{n}}}$encima${\displaystyle \mathbb {F} _{q}}$. 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, a saber, los monomios, y mostramos cómo conducen a sistemas de ecuaciones cuadráticas.

Consideremos un campo finito.${\displaystyle \mathbb {F} _{q}}$, dónde${\displaystyle q}$es una potencia de 2 y un campo de extensión${\displaystyle K}$de grado n. Sea${\displaystyle 0<h<q^{n}}$de tal manera que${\displaystyle h=q^{\theta }+1}$para algunos${\displaystyle \theta }$y mcd${\displaystyle (h,q^{n}-1)=1}$La condición mcd${\displaystyle (h,q^{n}-1)=1}$es equivalente a exigir que el mapa${\displaystyle u\to u^{h}}$en${\displaystyle K}$es uno a uno y su inverso es el mapa${\displaystyle u\to u^{h'}}$dónde${\displaystyle h'}$es el inverso multiplicativo de${\displaystyle h\ {\bmod {q}}^{n}-1}$.

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

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

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

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

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

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

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

Elige dos transformaciones afines secretas ${\displaystyle S}$y${\displaystyle T}$, es decir, dos invertibles${\displaystyle n\times n}$matrices${\displaystyle M_{S}=\{S_{ij}\}}$y${\displaystyle M_{T}=\{T_{ij}\}}$con entradas en${\displaystyle \mathbb {F} _{q}}$y dos vectores${\displaystyle v_{S}}$y${\displaystyle v_{T}}$de longitud${\displaystyle n}$encima${\displaystyle \mathbb {F} _{q}}$y definir${\displaystyle x}$y${\displaystyle y}$a través de:

${\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 la${\displaystyle u_{j},w_{i}}$con${\displaystyle x_{k},y_{l}}$, el sistema de${\displaystyle n}$Las ecuaciones son lineales en el${\displaystyle y_{l}}$y de grado 2 en el${\displaystyle x_{k}}$Aplicando álgebra lineal se obtendrá${\displaystyle n}$ecuaciones explícitas, una para cada${\displaystyle y_{l}}$como polinomios de grado 2 en el${\displaystyle x_{k}}$. ^{[ 3 ]}

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

${\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}$

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

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

El título${\displaystyle d}$El valor 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 elegido al azar. Por otro lado, un valor grande${\displaystyle d}$ralentiza el descifrado. Dado que${\displaystyle P}$es un polinomio de grado como máximo${\displaystyle d}$lo contrario de${\displaystyle P}$, denotado por${\displaystyle P^{-1}}$se puede calcular en${\displaystyle d^{2}(\ln d)^{O(1)}n^{2}\mathbb {F} _{q}}$operaciones. ^{[ 5 ]}

La clave pública la proporciona el${\displaystyle n}$polinomios multivariados${\displaystyle (p_{1},...,p_{n})}$encima${\displaystyle \mathbb {F} _{q}}$Por lo tanto, es necesario transmitir el mensaje.${\displaystyle M}$de${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q}^{n}}$para cifrarlo, es decir, asumimos que${\displaystyle M}$es un vector${\displaystyle (x_{1},...,x_{n})\in \mathbb {F} _{q}^{n}}$Para cifrar el mensaje${\displaystyle M}$evaluamos cada uno${\displaystyle p_{i}}$en${\displaystyle (x_{1},...,x_{n})}$El texto cifrado es${\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${\displaystyle S,T,P}$. Tenga en cuenta que estos no están disponibles para el remitente. Al evaluar el${\displaystyle p_{i}}$en el mensaje que aplicamos primero${\displaystyle S}$, Resultando en${\displaystyle x'}$. En este punto${\displaystyle x'}$se transfiere desde${\displaystyle \mathbb {F} _{q^{n}}\to \mathbb {F} _{q^{n}}}$así podemos aplicar el polinomio privado${\displaystyle P}$que está terminado${\displaystyle \mathbb {F} _{q^{n}}}$y este resultado se denota por${\displaystyle y'\in \mathbb {F} _{q^{n}}}$. Una vez más,${\displaystyle y'}$se transfiere al vector${\displaystyle (y_{1}',...,y_{n}')}$y la transformación${\displaystyle T}$se aplica y el resultado final${\displaystyle y\in \mathbb {F} _{q^{n}}}$se produce a partir de${\displaystyle (y_{1},...,y_{n})\in \mathbb {F} _{q}^{n}}$.

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

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

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

01. El signo + consiste en la 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 algunos${\displaystyle f}$variables de entrada de la clave pública, esta variante a veces se denomina p de proyección.

04. El signo v se define como una construcción, a veces bastante compleja, de tal manera que la inversa de la función solo se puede hallar si se fijan algunas variables v, denominadas variables vinagre. Esta idea se debe a Jacques Patarin.

05. El símbolo IP significa perturbación interna, que consiste en añadir un polinomio cuadrático aleatorio a las ecuaciones secretas. Sin embargo, el polinomio cuadrático aleatorio se compone de una función lineal de rango pequeño, lo que permite invertirla.

06. La variante LL' consiste en añadir una combinación lineal aleatoria de un pequeño número de productos de mapeo lineal a cada ecuación pública. Está diseñada para usarse en modo cifrado.

Las operaciones anteriores preservan en cierta medida la resolubilidad de la función mediante el método de la puerta trasera.

HFE- y HFEv resultaron útiles en esquemas de firma, ya que evitan la ralentización de la generación de firmas y mejoran la seguridad general de HFE. En cambio, para el cifrado, tanto HFE- como HFEv conllevan un proceso de descifrado bastante lento , por lo que no se pueden eliminar demasiadas ecuaciones (HFE-) ni añadir demasiadas variables (HFEv). Tanto HFE- como HFEv se utilizaron para obtener Quartz. Sin embargo, debido al nuevo ataque Min-Ranks de Ding, Petzoldt y Tao, estos esquemas quedaron obsoletos. ^{[ 7 ]}

Para las firmas, ahora se recomienda usar HFE IP- o HFE IPv. ^{[ 8 ]} De hecho, la variante IP es muy eficaz contra ciertos tipos de ataques de rango mínimo (rango mínimo S), mientras que las variantes v o - son eficaces contra todos los demás ataques (principalmente ataques de rango mínimo T o ataques de base de Gröbner).

Para el cifrado, el único esquema recomendado actualmente es HFE LL'. ^{[ 9 ]}

Existen dos ataques famosos contra HFE:

Recuperación de 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.${\displaystyle \mathbb {F} _{q^{n}}}$El ataque solo funciona para HFE básico y falla para todas sus variantes.

Bases de Gröbner rápidas (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 resolvió el desafío HFE 1 en 96 horas en 2002, y en 2003 Faugère y Joux colaboraron en la seguridad de HFE. ^{[ 1 ]}

• Nicolas T. Courtois, Magnus Daum y Patrick Felke, Sobre la seguridad de HFE, HFEv y Quartz
• 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