Criptografía asimétrica combinatoria-algebraica no usual con bases de Gröbner

Siempre me ha gustado investigar estructuras algebraicas con el fin de poder ver si puedo sumergir criptografía asimétrica dura ahí, generalmente ésta basada en el problema de logaritmo discreto en curvas algebraicas; considero que es mi área favorita de trabajo y posiblemente a lo que me vaya a dedicar el resto de mi vida, pero aquí vamos a ver algo diferente que podría o no ser seguro en su implementación pero no deja de ser interesante.


Primero vamos a analizar un caso particular de un esquema de cifrado con polinomios y luego veremos cómo generalizarlo y definiendo con bases de Gröbner.

Vamos a utilizar cualquier $latex \mathbb{F}-algebra$ de tipo finito, i.e. finitamente generada, con grado de trascendencia $latex n$ veamos cómo funciona esto.

Construcción del algoritmo de cifrado:

Sea $latex \mathbb{F}$ un campo finito y $latex T=\lbrace t_{i}\rbrace_{i=1}^{n}$ un conjunto de variables.


Queremos que $latex A$ reciba un mensaje $latex m\in \mathbb{F}$ de $latex B$ cifrado.

• $latex A$ va a escoger un vector aleatorio $latex y\in \mathbb{F}^{n}$ como llave privada

• $latex A$ escoge polinomios como llave pública $latex P=\lbrace q_j \rbrace \subseteq \mathbb{F}[T]$ tal que $latex q_j(y)=0$ $latex \forall j$

         Es fácil generar polinomios con los ceros que necesitamos, por ejemplo si
         ya tenemos la llave privada $latex y$ tomas $latex q_j = \hat {q}_j - \hat{q}_j(y)$ con $latex \hat{q}_j \in \mathbb{F}[T]$.
         Lo que no es tan fácil es escogerlos seguros y álgebraicamente independientes, pero hay métodos.

•  $latex B$ quiere mandar el mensaje $latex m\in \mathbb{F}$ a $latex A$ por lo que se toma un elemento del ideal generado por la llave pública $latex P$ que es $latex (P) \subset \mathbb{F}[T]$:

   $latex p = \displaystyle \sum { h_j q_j } $

En otras palabras escoge $latex \lbrace h_j \rbrace \subset \mathbb{F}[T]$ y genera el polinomio $latex p$

• $latex B$ le manda a $latex A$ el polinomio multivariable        

$latex c=p+m$


Este esquema de cifrado funciona ya que $latex A$ va a poder obtener $latex m\in \mathbb{F}$ ya que conoce los ceros de los generadores del ideal $latex (P)\in \mathbb{F}[T]$ por lo tanto conoce los ceros de $latex p$ independientemente de los $latex \lbrace h_j \rbrace$ , por lo que usando su llave privada $latex y$ tenemos que $latex A$ puede calcular fácilmente

$latex c(y)=p(y)+m=m$


Nota que este esquema de cifrado es probabilístico y no determinístico, i.e. en cada
ocasión que se cifra $latex m$ es diferente ya que depende de los elementos del ideal de la llave pública que se tomen.

Su seguridad también depende de los ceros del conjunto algebraico generado por $latex B$, en este caso cada cero sería $latex y=(y_1,y_2,...,y_n)$ y cualquier cero en la intersección de las hipersuperficies funcionaría, su seguridad depende de la solución de sistemas de ecuaciones algebraicos no lineales de grado arbitrario , es decir, en dimensión grande y con un número grande de polinomios generadores independientes del ideal de la llave pública, es POSIBLE tener criptografía segura, digo posible porque no se ha demostrado que su solución NO sea en tiempo polinomial, pero creo que podría ser más seguro si usamos la teoría de bases de Gröbner.

Generalización:

Veamos unas definiciones que vienen de la teoría de bases de Gröbner para poder intentar una generalización, las cuales incluyen la reducción módulo otro polinomio multivariable, donde los monomios deberán estar ordenados bajo cierto orden lexicográfico.

Definición (módulo polinomio multivariable): Decimos que $latex f$ reduce a $latex h$ módulo $latex g$ parcialmente si $latex a_{i}X^{i}$ es un monomio de $latex f$ que es divisible por el término líder de $latex g$ ,$latex lt(g)$ (líder bajo el órden con el que organicemos nuestros polinomios como el lexicográfico por grado) y que sucede que:

$latex h=f-\frac{a_{i}X^{i}}{lt(g)}g$

Donde escribimos que $latex f \equiv h \bmod g$

Definición (módulo un conjunto de polinomios): Sea $latex G=\lbrace g_1,...,g_l \rbrace \subset \mathbb{F}[T]$ y sea $latex f\in \mathbb{F}[T]$, entonces decimos que $latex f$ se reduce a $latex h$ módulo $latex G$ ($latex f \equiv h \bmod G$) si tenemos la sucesión $latex h_0=f, ..., h_k=h$ tal que $latex h_j \equiv h_{j+1} \bmod g$ para algún $latex g\in G$

Definición (base de Gröbner): Sea $latex F=\lbrace g_1, ..., g_l \rbrace \subset \mathbb{F}[T]$ un conjunto finito de polinomios en $latex m=|T|$ variables e $latex I\subset \mathbb{F}[T]$ el ideal generado por $latex F$, decimos que $latex F$ es una base de Gröbner para el ideal $latex I$ si para todo $latex 0\neq f\in I$ se tiene que $latex lt(g_k)\mid lt(f)$ para algún $latex g_k\in F$


Teorema: F es una base de Gröbner para un ideal $latex I\subset \mathbb{F}[T]$ $latex \Leftrightarrow$ $latex \forall f \in I$ $latex f\equiv 0 \bmod F$

Con este último teorema nos resulta TRIVIAL el poder construir ideales aleatorios (finitos, anillos noetherianos) y su base de Gröbner asociada.

Regresando al esquema de cifrado original y rehaciéndolo con esto:

$latex A$ escoge una base de Gröbner $latex G=\lbrace g_1,...,g_l\rbrace$ de un ideal $latex I \subset \mathbb{F}[T]$, la llave privada de $latex A$ es $latex G$.

Sea $latex S\subset \mathbb{F}[T]$ el conjunto de TODOS los polinomios que no pueden ser reducidos módulo $latex G$ (ve las definiciones anteriores), este $latex S$ realmente sería el conjunto de representantes del anillo $latex \mathbb{F}[T]/I$ como ya se lo habrán imaginado, ahora supón que $latex S$ es público, aunque $latex G$ no lo sea, tenemos que todo mensaje $latex m \in \mathbb{F}$ es un elemento de $latex S$.

Un ejemplo:


 Sea $latex T=\lbrace t_1,...,t_n\rbrace$ y $latex y \in \mathbb{F}^n$ un punto secreto, $latex A$ toma como base de gröbner $latex G=\lbrace t_1-y_1, ..., t_n - y_n\rbrace$  en este caso tenemos que $latex S=\mathbb{F}[T]/(G)\cong \mathbb{F}$ es el campo de las constantes.

Ahora $latex A$ escoge un conjunto como llave pública $latex P=\lbrace q_j \rbrace \subset I=(G)$, esto es fácil ya que  podría tomar un $latex \hat{q}_j\in \mathbb{F}[T]$ arbitrario y calcular $latex q_j = \hat{q}_j - \overline{q}_j$ donde $latex \overline{q}_j \in S$ y $latex \hat{q}_j \equiv \overline{q}_j \bmod G$

Consideremos el ideal $latex J=(P)$ y $latex m\in S$, entonces $latex B$ le cifrará a $latex A$ el mensaje $latex m$ escogiendo al azar un elemento de $latex J$, ya que la llave pública de $latex A$ es $latex P$ y $latex J=(P)$:

$latex p=\displaystyle \sum h_{j}q{j} \in J$

$latex B$ le manda a $latex A$ $latex c=p+m$

$latex A$ al recibir $latex c$ sólo tendría que reducirlo módulo la base de Gröbner $latex G$ 

En este ejemplo cuando $latex G=\lbrace t_i - y_i \rbrace$ sería el caso particular que vimos en el principio.


Esta criptografía es rara y no es usada ni considerada AÚN SEGURA debido a que falta demostrar que tan dificil es el problema en términos de complejidad.


Espero les haya gustado

Eduardo Ruíz Duarte (beck)
@toorandom