Teorema de Riemann-Roch y divisores en criptografía, (Parte 2: Espacio proyectivo)

Como vimos anteriormente, lo que queremos es exprimir las propiedades de una curva algebraica a través de la geometría algebraica, en este caso de una curva elíptica o hiperelíptica.

Como lo mencioné al principio del post anterior, el grupo de una curva elíptica está fundamentado de manera "cochina" por (algunos) computólogos que implementan criptografía por el teorema de Bézout.

Siempre al definir una curva elíptica se define en su propiedad de grupo que un punto $latex (x,y)$ en la curva elíptica o hiperelíptica tiene como inverso a el punto $latex (x,-y)$ lo cual sucede al proyectarlo con un punto mágico que está en el infinito, esto es porque la curva elíptica realmente no vive en $latex \mathbb{R}^2$ como todos creen, realmente vive en otro espacio que es el que trataremos de explicar aquí, vive realmente en $latex \mathbb{P}^2_{\mathbb{C}}$, pronto veremos el por qué se les llama elípticas a través de otro nuevo espacio $latex \mathbb{C}/\Lambda$ y una función llamada $latex \wp$ de Weierstrass, pero eso aún está lejos de este post.

La respuesta elegante y limpia en vez de usar Bézout para justificar la estructura de grupo de una curva elíptica o hiperelíptica está a través del teorema de Riemann-Roch el cual trataremos de comprender a grandes rasgos, no olvides checar tu literatura

El teorema de Riemann-Roch une las propiedades algebraicas y topológicas de una curva, vamos a explorarlo un poco, aunque en esta primera parte del post definiremos primero lo que es el espacio proyectivo y algunas propiedades a través de ejemplos usando topología.

Como lo mencioné, vamos a hablar ahora del espacio proyectivo $latex \mathbb{P}^{n}_{\mathbb{K}}$, en el post anterior trabajamos en el espacio afín $latex \mathbb{A}^{n}_{\mathbb{K}}$ y definimos el campo de funciones, el cual jugará un papel imporante en Riemann-Roch

Recomiendo leer al menos la página de Wikipedia de geometría proyectiva así como el artículo del plano complejo proyectivo , aquí daré cierta intuición, ejemplos, definiciones y construcciones, para no dejar ese hueco.

Sea $latex V$ un espacio vectorial de dimensión finita sobre un campo $latex \mathbb{K}$ (de hecho para nuestros propósitos el espacio que tomaremos será $latex V=\mathbb{C}^2$) y considera la siguiente relación de equivalencia entre los vectores  $latex V\setminus \lbrace 0 \rbrace$:

$latex u\sim v \Leftrightarrow \exists \lambda \in \mathbb{K}^{*} \mid u=\lambda v$

Es decir, estamos diciendo que dos vectores $latex u$ y $latex v$ estarán en la misma partición (están relacionados) sí y sólo sí están en la misma linea que pasa por el origen, es decir, este espacio consta de todas las lineas que salen del origen bajo esta relación, con un ombligo, recuerda que quitamos al 0

Por lo que tenemos que si nuestro espacio vectorial  $latex V=\mathbb{C}^2$
$latex \mathbb{P}(V):=V\setminus \lbrace 0 \rbrace / \sim$

y para reducir notación:

$latex \mathbb{P}^{n}_{\mathbb{C}}:=\mathbb{P}(\mathbb{C}^{n+1})$

Por lo que a nosotros nos interesará trabajar en:

$latex \mathbb{P}^{2}_{\mathbb{C}}$

El cual es el plano proyectivo complejo.

Esta geometría realmente nace de la perspectiva a la hora de pintar un paisaje y quieres poder mostrar el horizonte en tu obra a pesar de que éste esté en el infinito.

De hecho, los puntos de $latex \mathbb{P}^{2}_{\mathbb{C}}$ son denotados como $latex [a:b:c]$

Ejemplo:

Como a mucha banda matemática y a mi, nos gustan los ejemplos para poder entender los conceptos abstractos, afortunadamente aquí sí hay algo en lo que todo el mundo es familiar.

Vamos a ver cómo se ve $latex \mathbb{P}^{1}_{\mathbb{R}}$, de hecho vamos a demostrar que este espacio es realmente homeomorfo al círculo $latex \mathbb{S}^1$

Este espacio se le llama linea proyectiva real y nace de considerar la relación de equivalencia mencionada inicialmente sobre $latex \mathbb{R}^2$.

Más formal:

Si $latex x,y\in \mathbb{R}^2$, tenemos que $latex x\sim y \Leftrightarrow x=\lambda y$ con $latex \lambda \in \mathbb{R}$ y:

$latex \mathbb{P}^{1}_{\mathbb{R}}=\mathbb{R}^2\setminus \lbrace 0 \rbrace / \sim$

Vamos a usar topología aquí para demostrar que $latex \mathbb{S}^1$ y $latex \mathbb{P}^{1}_{\mathbb{R}}$ son homeomorfos, de hecho la topología cociente aunque supongo que hay caminos tal vez más directos.

Consideremos:

$latex \psi:\mathbb{R}^2 \setminus \lbrace 0 \rbrace \rightarrow \mathbb{P}^1_{\mathbb{R}}$
$latex (x,y) \mapsto [x:y]$

Ahora, vamos a restringir esto a $latex \mathbb{S}^1$

es decir $latex \hat\psi = \psi\mid_{\mathbb{S}^1}$ por lo que tenemos que en $latex \hat\psi :\mathbb{S}^1 \rightarrow \mathbb{P}^1_{\mathbb{R}}$  $latex \hat\psi(x,y)=\hat\psi(-x,-y)$ es decir, a cada punto del círculo bajo la relación $latex \sim$ se reduce en la restricción al círculo a una relación más simple que le llamaremos $latex \hat\sim$ la cual definimos como $latex a,b\in \mathbb{S}^1$ entonces $latex a\hat\sim b\Leftrightarrow a=-b$

Es decir, la relación restringida al círculo nos dice que las antípodas están en la misma clase de equivalencia.

Entonces lo que basta demostrar es que $latex \tilde\psi:\mathbb{S}^1/\hat\sim \rightarrow \mathbb{S}^1$
es un homeomorfismo.

Consideremos el mapeo:

$latex \phi:\mathbb{S}^1 \rightarrow \mathbb{S}^1$

$latex (x,y) \mapsto (x^{2} - y^{2},2xy)$

Este mapeo está inspirado en $latex z\mapsto z^2$ en $latex \mathbb{C}$ pero viéndolo en $latex \mathbb{R}^2$ y restringido a $latex \mathbb{S}^1 \subset \mathbb{R}^2$

Este mapeo $latex \phi$ claramente es continuo y suprayectivo y $latex \phi$ pasa por el cociente bajo $latex \hat\sim$ o sea, respeta la relación de equivalencia $latex \hat\sim$ ya que si $latex z\in\mathbb{S}^1$ tenemos que $latex \phi(z)=\phi(-z) \Rightarrow z\hat\sim -z$

Usando la propiedad universal de la topología cociente con esta $latex \phi$ tenemos que $latex \tilde\psi:\mathbb{S}^1/\hat\sim \rightarrow \mathbb{S}^1$ es un homeomorfismo y es único.

Por lo que:

$latex \mathbb{P}^{1}_{\mathbb{R}}=\mathbb{R}^2\setminus \lbrace 0 \rbrace / \sim \cong \mathbb{S}^1$


Más ejemplos usuales existen , por ejemplo si nos tomamos $latex \mathbb{C}$ en vez de $latex \mathbb{R}$ ustedes pueden demostrar que la recta proyectiva compleja:

$latex \mathbb{P}^{1}_{\mathbb{C}} \cong \hat{\mathbb{C}}:=\mathbb{C}\cup \lbrace \infty \rbrace$

La cual es la esfera de Riemann, éste es un ejemplo fundamental en análisis complejo y geometría algebraica por ser una superficie de Riemann compacta, esto último es relevante ya que nos permite verla como una curva proyectiva algebraica.

Los espacios proyectivos complejos son una herramienta muy poderosa, ya que al agregar este punto $latex \infty$ en ciertos casos se puede definir la división por 0 haciendo que por ejemplo cualquier función racional meromorfa en los complejos sea extendida a una función continua sobre la la recta proyectiva compleja, mapeando sus polos al infinito y conservando continuidad.

En los espacios proyectivos suceden cosas interesantes, por ejemplo veremos que por la naturaleza del espacio en función de su relación de equivalencia, las ecuaciones algebraicas dentro de nuestro espacio proyectivo deberán ser homogéneas, o que existen un puntos que no están en el espacio vectorial en correspondencia con el proyectivo o que si definimos dos rectas paralelas en el espacio vectorial y lo transladamos al espacio proyectivo sí se intersectarán, de hecho TODAS las rectas del espacio proyectivo se intersectan en un punto 

Regresando a la analogía de las obras de pintura de paisajes, imagina ¿cómo pintarías la foto de unas vías del tren vistas de frente?, si observas bien las vías, éstas, pareciera que se intersectan en el horizonte.

Para terminar esto veamos lo que mencioné en negritas el penúltimo parrafo a éste.

Consideremos las soluciones (el conjunto de ceros) de un polinomio definido con sus variables en $latex \mathbb{P}^{n}_{\mathbb{K}}$ es decir, un punto en general sería con $latex n+1$ variables , $latex P=[x_0:...x_n]\in \mathbb{P}^{n}_{\mathbb{K}}$, estos puntos por como está definido el espacio proyectivo, están determinados por la multiplicación por un escalar $latex \lambda$, el cual da la relación de equivalencia, por lo que un polinomio con variables proyectivas deberán considerar esa restricción a la hora de considerar sus soluciones, estos polinomios se les llama homogéneos

Definición (polinomio homogéneo): Un polinomio:

$latex f(x_0,x_1,...,x_n) = \displaystyle \sum { a_{\eta_0...\eta_n}}x_{0}^{\eta_0}...x_{n}^{\eta_n}$

Se dice homogeneo de grado $latex d$ si TODOS sus monomios tienen el mismo grado $latex d=\sum_{i=0}^{n} \eta_i$

Por lo que si $latex f$ es homogéneo de grado $latex d$ entonces:

$latex f(\lambda x_0, ..., \lambda x_n)=\lambda^d f(x_0,...,x_n)$

Con esto tenemos que los polinomios homogéneos están bien definidos en el espacio proyectivo.

Ahora, lo que nos resta ver es una propiedad interesante, dos lineas siempre se intersectan en el plano proyectivo, y para esto lo que haremos un ejemplo, será transformar polinomios en dos variables complejas $latex \mathbb{C}^2$ a polinomios en $latex \mathbb{P}^2_{\mathbb{C}}$ a través de un proceso que se llama "homogenización" , y lo haremos con dos lineas paralelas, y veremos como es la intersección de sus imágenes.

La siguiente definición es para construir un polinomio cualquiera, a un polinomio homogéneo , es decir con monomios del mismo grado, esta operación es invertible.

Definición (homogeinización): Sea $latex p(x,y) \in \mathbb{C}[x,y]$, el polinomio correspondiente en $latex \mathbb{P}^2_{\mathbb{C}}$ es:

$latex p(x,y,z)=z^{n}p(\frac{x}{z},\frac{y}{z})$

Es fácil ver que el polinomio resultante de este proceso es realmente homogéneo.

Ejemplo (intersección de las imágenes bajo homogenización de dos rectas afines):

Sean
$latex x+y=2$
$latex x+y=3$

dos rectas definidas en $latex \mathbb{C}^2$

claramente son paralelas, homogeneizando tenemos que

$latex x+y=2z$
$latex x+y=3z$

por lo que tenemos que $latex [a:-a:0] \in \mathbb{P}^2_{\mathbb{C}}$ está en la linea al infinito y es solución de ambas ecuaciones,

nota que $latex [0:0:0]$ también es solución, pero éste punto no está definido en el espacio proyectivo por construcción.

Otro ejemplo serían dos circunferencias de radio distinto:


$latex x^2 + y^2 = 1$
$latex x^2 + y^2 = 2$

Claramente no se intersectan en el espacio afín complejo

Homogeneizando, tenemos que

$latex x^2 + y^2 -1 \mapsto z^2\Big ( \frac{x^2}{z^2}+\frac{y^2}{z^2}-1\Big )=x^2+y^2-z^2$

Similarmente con el otro polinomio, por lo que tenemos que intersectar en $latex \mathbb{P}^2_{\mathbb{C}}$

$latex x^2+y^2-z^2$   y   $latex x^2+y^2-2z^2$

y tenemos que todos los puntos de la forma $latex \lambda(\pm 1,\pm i,0)$ son soluciones, y si $latex \lambda \neq 0$

tenemos que $latex [\pm 1:\pm i:0]\in \mathbb{P}^2_{\mathbb{C}}$ es un punto en la linea al infinito que intersecta a ambas circunferencias proyectivas de distinto radio.

La relación con curvas elípticas será que éstas realmente hay que proyectivizarlas (homogeneizarlas) y al trabajar con ellas en criptografía es viéndolas en el espacio proyectivo, es decir para que todo funcione como queremos necesitamos la cerradura proyectiva, mas no el hecho de usar un punto cualquiera para darle estructura de grupo.


Con esto, y el post anterior estamos listos para la siguiente parte que será el teorema de Riemann-Roch


Eduardo Ruiz Duarte (beck)
twitter: @toorandom

Teorema de Riemann-Roch y divisores en criptografía (Parte 1: campos de funciones y gavillas sobre variedades)

En criptografía muchos han visto que se estudian las curvas elípticas y menos frecuentemente las curvas hiperelípticas, algunos recordarán la estructura de grupo que se le da a una curva elíptica $latex C$ con la usual regla de intersección de una recta con la curva haciendo uso abusivo del teorema de Bézout para fundamentar la estructura de grupo que hay en sus puntos, que más formalmente, es la estructura de grupo que hay en las clases de divisores formados por las sumas formales de ideales máximos de todos los subanillos del campo de funciones de $latex \mathbb{K}(C)$, este grupo es el grupo de Picard de orden 0 de la curva $latex C$ que es:

 $latex Pic^0(C) = Div^0(C)/Prin(C) \cong \mathbb{J}(C)$.

Esta manera de ver las cosas NO es para complicar lo ya existente, sino es con propósitos de poder exprimir más la teoría que lo respalda para poder investigarlo mejor y generalizarlo a otras curvas no elípticas.

La estructura de grupo de manera inocente o usual se puede ver en muchos textos pobres en matemáticas pero tal vez ricos en aplicaciones criptográficas como esto:

El propósito de este post será el poder resumirte la teoría que hay detrás.


Comencemos con unas definiciones, voy a suponer que quien me lee está familiarizado con la topología de Zariski la cual está definida por los conjuntos algebraicos como cerrados, de hecho estas definiciones son las interesantes para la topología de Zariski, y con esto pueden demostrar fácilmente las propiedades de espacio topológico.

Definición (ceros):
Sea $latex A:= \mathbb{K}[x_1,...,x_n]$ el anillo de polinomios en $latex n$ variables sobre el campo algebraicamente cerrado $latex \mathbb{K}$ y $latex J \subset \mathbb{K}[x_1,...,x_n]$ un ideal, entonces definimos el conjunto de ceros del ideal $latex J$ como:

$latex V(J):=\lbrace P\in \mathbb{A}^{n}_{\mathbb{K}} \mid f(P)=0$     $latex \forall f\in J\rbrace$


Definición (variedad afín): Un subconjunto $latex X\subset \mathbb{A}^n_{\mathbb{K}}$ es un conjunto algebraico (variedad afín) en el espacio afín $latex \mathbb{A}^n_{\mathbb{K}}$ si existe un $latex T\subset \mathbb{K}[x_1,...,x_n]$ tal que:

$latex X=V(T)$

Decimos que $latex X$ es un cerrado de Zariski, en la topología dada a  $latex \mathbb{A}^n_{\mathbb{K}}$.

Veámos primero lo que es el anillo de coordenadas de una variedad.

Definición (función polinomial en la variedad V): Una función polinomial es un mapeo $latex f:V \rightarrow \mathbb{K}$ tal que existe un $latex F\in \mathbb{K}[x_1,...,x_n]$ con $latex f(P)=F(P)$  $latex \forall P\in V$

Este polinomio $latex F$ no está únicamente determinado por los valores que toma en $latex V$ o sea si tenemos $latex F,G\in \mathbb{K}[x_1,...,x_n]$:


$latex F\mid_{V}=G\mid_{V} \Leftrightarrow (F-G)\mid_{V}=0 \Leftrightarrow F-G\in I(V)$

Donde:

$latex I(V):=\lbrace f\in \mathbb{K}[x_1,...,x_n] \mid f(P)=0$    $latex \forall P\in V\rbrace$



Esta definición de función polinomial y su relación de igualdad con otros polinomios, huele a una relación de equivalencia, por lo que vamos a suponer que lo es y se deja a quien lee para que lo demuestre y tenemos que:

Denotaremos ahora a $latex V$ como el conjunto algebraico $latex V(I)$ donde $latex I$ es ideal de $latex \mathbb{K}[x_1,...,x_n]$

Definición (anillo de coordenadas de una variedad): Un anillo de coordenadas de una variedad $latex V$ es:

$latex \mathbb{K}[V]:=\mathbb{K}[x_1,...,x_n]/I(V)$

Este anillo sabemos que es un dominio entero si $latex I(V)$ es un ideal primo, y esto naturalmente sucede si $latex V$ es irreducible , es decir no es union de otros cerrados de zariski


De lo anterior sobre funciones polinomiales y la última definición se puede demostrar que:

$latex K[V]=\lbrace f \mid f:V\rightarrow \mathbb{K}$ es una función polinomial $latex \rbrace$

Cabe notar que se le llama anillo de coordenadas porque las funciones que te dan la i-ésima coordenada de los elementos de $latex V$, $latex x_i$ son las generadoras de $latex \mathbb{K}[V]$

Es fácil ver que $latex \mathbb{K}[ \mathbb{A}^n_{\mathbb{K}}]=\mathbb{K}[x_1,...,x_n]$ y que el anillo $latex \mathbb{K}[V]$ juega el papel para $latex V$ como $latex \mathbb{K}[x_1,...,x_n]$ para $latex \mathbb{A}^n_{\mathbb{K}}$

Observaciónes sobre lo anterior con respecto a la topología de Zariski en $latex \mathbb{A}^n_{\mathbb{K}}$.

• Los ideales primos de $latex \mathbb{K}[V]$ están en correspondencia 1:1 con irreducibles $latex W\subset V$
• Los ideales máximos de  $latex \mathbb{K}[V]$ están en correspondencia 1:1 con los puntos de $latex V$
• Los ideales radicales de $latex \mathbb{K}[V]$ están en correspondencia 1:1 con los cerrados $latex W\subset V$

Definición (campo de funciones de V): El campo de funciones de $latex V$ es el campo de fracciones de $latex \mathbb{K}[V]$ y es denotado por $latex \mathbb{K}(V)$, las $latex f\in \mathbb{K}(V)$ se llaman funciones racionales sobre $latex V$

Definición (función regular en P): Una función $latex f\in \mathbb{K}(V)$ y $latex P\in V$ se dice que es regular en $latex P$ si $latex f=\frac{g}{h}$ con $latex h(P)\neq 0$, y definimos:

$latex dom(f):=\lbrace P\in V \mid f$ es regular en $latex P\rbrace$

Proposición: El conjunto:

$latex V_f:=\lbrace P\in V\mid f(P)\neq 0\rbrace$

es un abierto de $latex V$


Teorema: 

• $latex dom(f)$ es abierto y denso en $latex V$
• $latex dom(f)=V\Leftrightarrow f\in \mathbb{K}[V]$
• $latex V_g\subset dom(f) \Leftrightarrow f\in \mathbb{K}[V][1/g]$

Ahora, entraremos a un concepto central, para poder analizar una variedad localmente... para esto sabemos que un anillo local sólo tienen un ideal máximo, y tenemos que la siguiente definición

Definición (anillo de funciones regulares): El anillo de funciones regulares de $latex V$ localizado en el punto $latex P\in V$ es:

$latex O_{V,P}:=\lbrace f\in \mathbb{K}(V)\mid f$ es regular en $latex P\rbrace$

Es fácil demostrar que esto es en efecto un subanillo de $latex  \mathbb{K}(V)$ y que su único ideal máximo no deberá tener unidades por lo que su ideal máximo es:

$latex m_{P}:=\lbrace f/g \in \mathbb{K}(V)\mid f(P)=0, g(P)\neq 0 \rbrace$

Ahora vamos a la últma parte de este blog donde discutiremos la estructura de gavilla de una variedad

Estructura de gavilla de una variedad

Tenemos que el anillo $latex O_{V,P}$ es local y es un subanillo de $latex \mathbb{K}(V)$ y su ideal máximo es $latex m_{P}$, es fácil relacionar a $latex O_{V,P}$ con $latex \mathbb{K}[V]$ ya que con localización puedes demostrar que:

$latex \hat{m}_P=\lbrace f\in \mathbb{K}[V]\mid f(P)=0\rbrace=I(\lbrace P \rbrace)+I(V)\subset \mathbb{K}[V]$

Es máximo y:

$latex O_{V,P}=\mathbb{K}[V]_{\hat{m}_P}$


Es decir que $latex O_{V,P}$ es la localización del anillo de coordenadas de $latex V$ en el ideal máximo $latex \hat{m}_P$

Ahora vamos a definir el concepto final:

Definición-Teorema (estructura de gavilla en $latex O_{V}(U)$, germen y fibra ): Para todo abierto $latex U \subset V$ tenemos:

$latex O(U):=O_{V}(U):=\lbrace f\in \mathbb{K}(V) \mid f$ es regular en $latex U \rbrace$

Es una $latex \mathbb{K}-$álgebra con $latex O_{V}(\emptyset):=\lbrace 0 \rbrace$

Todos los $latex O_{V}(U)$ con $latex U\subset V$ forman una gavilla $latex O_V$ bajo la restricción de homomorfismos usual y el anillo $latex O_{V,P}$ es una fibra de la gavilla $latex O_V$  y los elementos $latex f\in O_{V,P}$ se les llama gérmenes de funciones y:

$latex O(V)=\mathbb{K}[V]$


La teoría de gavillas da una estructura rica a una variedad, en este caso , puede ser el de una curva elíptica o hiperelíptica

Saludos

Eduardo Ruiz Duarte (beck)
Twitter: @toorandom

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