Existe un homomorfismo entre dos grupos si existe un mapeo que preserva la estructura entre los dos grupos.

Supongamos que tenemos dos estructuras de datos algebraicas $(A,\square)$ y $(B, \blacksquare)$, donde el operador binario de $A$ es $\square$ y el operador binario de $B$ es $\blacksquare$.

Un homomorfismo de $A$ a $B$ existe si y solo si existe una función $\phi: A\rightarrow B$ tal que

En otras palabras, si $a_i \square a_j = a_k$, entonces $\phi(a_i) \blacksquare \phi(a_j) = \phi(a_k)$.

Ten en cuenta que un homomorfismo es unidireccional. La función $\phi$ toma elementos en $A$ y los mapea a elementos en $B$. No tenemos ningún requisito sobre “ir hacia atrás”.

Primero mostraremos algunos ejemplos simples, proporcionaremos algunas aclaraciones y luego presentaremos ejemplos más complejos.

Ejemplos simples de Homomorfismos

Todos los números enteros bajo la suma a todos los números enteros pares bajo la suma

Sea $A$ el conjunto de todos los números enteros bajo la suma, y sea $B$ el conjunto de todos los números enteros pares bajo la suma. Está claro que tanto $A$ como $B$ son grupos.

Sea $\phi(x)=2x$

Vemos que $\phi$ define un homomorfismo de $A$ a $B$ porque lo siguiente es cierto para cualquier par de números enteros $a_i$ y $a_j$

Todas las cadenas bajo la concatenación a todos los enteros iguales o mayores a cero

Por ejemplo, sea $A$ el Monoide de todas las cadenas (incluida la cadena vacía) bajo la concatenación, y sea $B$ el Monoide de todos los números enteros iguales o mayores a cero bajo la suma.

Existe un homomorfismo de $A$ a $B$ porque existe una función $\phi$ que mapea cadenas a números enteros iguales o mayores a cero y preserva la siguiente propiedad

En este caso, $\phi$ es la longitud de la cadena. Por ejemplo:

Aquí, tenemos

Todos los números reales bajo la suma a todas las matrices $n\times m$ de números reales bajo la suma

Algunos homomorfismos pueden parecer bastante triviales una vez que les agarras el truco. Este es un ejemplo de tal homomorfismo. En este caso, nuestra función $\phi$ simplemente repite el número real $n\times m$ veces. Por ejemplo, si $n=3$ y $m=2$, entonces $\phi(8.8)$ sería:

A modo de ejemplo, $\phi(8.8 + 0.2)=\phi(8.8)+\phi(0.2)$ porque

Aclaraciones sobre los Homomorfismos

• $\phi$ debe funcionar con cada par posible de elementos de $A$ (incluidos pares del mismo elemento). Sin embargo, no necesita “acceder” a todos los elementos de $B$. Por ejemplo, un homomorfismo que mapea cada elemento en $A$ al elemento neutro en $B$ es un homomorfismo válido, pero no uno útil. Se le llama homomorfismo trivial.
• Si elegimos dos conjuntos arbitrarios con un operador binario, un homomorfismo no existirá necesariamente.
• Puede haber un homomorfismo de $A$ a $B$, pero no necesariamente de $B$ a $A$.
• Si hay un homomorfismo de $A$ a $B$ y de $B$ a $A$, y $\phi$ es el mapeo de $A$ a $B$, la inversa de $\phi$ puede no ser necesariamente un mapeo válido para el homomorfismo de $B$ a $A$.

Más ejemplos de homomorfismos

Números enteros bajo la suma a potencias enteras de $b$ bajo la multiplicación

Supongamos que tenemos el grupo $A=(\mathbb{Z},+)$ (el conjunto de todos los números enteros bajo la suma) y el grupo $B$, que es el conjunto de todas las potencias enteras de $b$ bajo la multiplicación, es decir, $B=(b^i\space:\space i\in\mathbb{Z}, \times)$. Podemos establecer arbitrariamente $b=2$ para que el ejemplo sea más fácil de imaginar.

Existe un homomorfismo de $A$ a $B$, definido por $\phi(x)=b^x$. Por las reglas del álgebra,

Para entender por qué se cumple esta relación, considera que

Números enteros bajo la suma a potencias enteras de $b$ bajo la multiplicación módulo un número primo

Esto es muy similar al ejemplo anterior, con la adición de un módulo. Dejamos como ejercicio para el lector identificar la función $\phi$ que define el homomorfismo.

Matrices $n\times m$ bajo la suma a números enteros bajo la suma

En este caso, $\phi$ simplemente suma todos los elementos de una matriz. Por qué funciona esto se deja como ejercicio para el lector.

Matrices $2\times2$ de números enteros bajo la multiplicación a números enteros bajo la multiplicación

Existe un homomorfismo del primer al segundo Monoide porque $\phi$ es el determinante de la matriz y se cumple la siguiente regla:

donde $X,Y,Z$ son matrices enteras de $2\times2$. Por qué estas dos estructuras de datos algebraicas son Monoides y no grupos se deja como ejercicio para el lector.

El grupo de los números racionales (excluyendo los números racionales donde el denominador es un múltiplo de $p$) a la suma módulo $p$

Este concepto ya se enseñó en nuestro artículo sobre campos finitos, pero no usamos el término “homomorfismo” para describirlo.

Sea $A$ el grupo de todos los números racionales cuyos denominadores no son un múltiplo de $p$, bajo la suma. Sea $B$ el campo finito módulo $p$.

Existe un homomorfismo del grupo $A$ al grupo $B$. $\phi$ es

O en Python:

Copy
p = 11
def phi(num, den):
    return num * pow(den, -1, p) % p

Por ejemplo:

• $1/3 + 3/5 = 14/15$
• $1/3$ es congruente con $6 \pmod {17}$
• $3/5$ es congruente con $4 \pmod {17}$
• $4 + 6\equiv10 \pmod {17}$
• $14/15\equiv 10 \pmod {17}$

Decir que $1/3$ es congruente con $6 \pmod {17}$ es equivalente a la afirmación $\phi(1/3)=6$.

El Monoide de los números racionales (excluyendo los números racionales donde el denominador es múltiplo de $p$) a la multiplicación módulo $p$ (excluyendo el cero)

Usemos el mismo ejemplo de arriba, pero con la multiplicación. La función $\phi$ sigue siendo la misma.

• $1/3 * 3/5 = 1/5$
• $1/3$ es congruente con $6 \pmod {17}$
• $3/5$ es congruente con $4 \pmod {17}$
• $4 \times 6\equiv7 \pmod {17}$
• $1/5\equiv 7 \pmod {17}$

Ejercicios para el lector

Encuentra un homomorfismo para los siguientes pares de estructuras de datos algebraicas. Si te quedas atascado (o simplemente no quieres resolver el problema), puedes buscar la respuesta en Google o consultar con un chatbot.

1. Números reales bajo la suma a polinomios con coeficientes reales bajo la suma.
2. Polinomios con coeficientes reales a números reales bajo la suma. Pista: aunque esto se parece al problema 1, la función $\phi$ no tendrá ninguna relación con la respuesta del problema anterior.
3. Números reales positivos mayores que cero bajo la multiplicación a todos los números reales bajo la suma.

Cifrado Homomórfico

Si $\phi$ es computacionalmente difícil de invertir, entonces $\phi$ cifra homomórficamente los elementos de $A$.

Sea $A$ todos los números enteros bajo la suma, y $B$ el grupo objetivo y $\blacksquare$ el operador binario de $B$.

Suma de Conocimiento Cero, ejemplo 1

Supongamos que deseamos probar a un verificador que hemos calculado $2 + 3=5$. Le daríamos al verificador $(x, y, 5)$ donde $x=\phi(2), y= \phi(3)$ y el verificador comprobaría que:

Ten en cuenta que el cifrado homomórfico implica que el verificador conoce la función $\phi$.

Suma de Conocimiento Cero, ejemplo 2

Un probador hace la afirmación: “Tengo dos números $a$ y $b$, y $b$ es cinco veces $a$”. El probador envía $\phi(a)$ y $\phi(b)$ al verificador, y el verificador comprueba que

Recuerda, la “multiplicación” aquí no es el operador binario, es simplemente una forma abreviada de la suma repetida.

En estos ejemplos, nota que no dijimos nada sobre qué son los elementos de $B$ ni qué es $\blacksquare$. $B$ puede ser un objeto matemático aterrador, y $\blacksquare$ puede ser un operador matemático aterrador, pero eso no importa.

Esta es la belleza del álgebra abstracta: no necesitamos saberlo. Siempre y cuando tenga las propiedades que nos importan, podemos razonar sobre su comportamiento incluso si no sabemos nada sobre la implementación.

Motivación

Vale, genial; entendemos los grupos y los homomorfismos, pero ¿cómo nos ayuda esto? La razón por la que hice todo el esfuerzo de explicar esto es porque quiero que entiendas la siguiente afirmación:

“Los puntos de la curva elíptica en un campo finito bajo la suma son un grupo cíclico finito y los números enteros bajo la suma son homomórficos a este grupo”.

Probablemente no sepas qué son los puntos de la curva elíptica o qué significa sumarlos, pero sí sabes:

1. El conjunto de los puntos de la curva elíptica bajo la suma produce otro punto de la curva elíptica.
2. El operador binario que toma dos puntos de la curva elíptica y devuelve otro punto de la curva elíptica es asociativo.
3. El conjunto de puntos de la curva elíptica contiene un elemento neutro.
4. El grupo de la curva elíptica tiene un elemento neutro, el cual es único.
5. Cada punto de la curva elíptica tiene un inverso tal que al sumar un punto y su inverso se produce el elemento neutro.
6. Debido a que el grupo es cíclico, cada punto de la curva elíptica puede ser generado aplicando repetidamente el operador binario a algún elemento generador.
7. Debido a que el grupo de puntos de la curva elíptica es cíclico, también es un grupo abeliano.
8. Debido a que es un grupo finito, el orden es finito.
9. Debido al homomorfismo, tenemos una idea sólida de cómo se comporta el operador binario para los puntos de la curva elíptica. Podemos usar el operador binario de los puntos de la curva elíptica para “sumar enteros” en cierto sentido.

Incluso si no sabes qué son los puntos de la curva elíptica, ¡ya sabes nueve cosas sobre ellos!

Así que sean lo que sean estos extraños objetos llamados “puntos de la curva elíptica”, sabes cómo se comportan y que tienen las mismas propiedades que los grupos que discutimos anteriormente.

Lo creas o no, ya has recorrido el 90% del camino para comprender las curvas elípticas. Es mucho más fácil darle sentido a las curvas elípticas al comprender su similitud con otras estructuras familiares que tratar de entender su extraña matemática desde cero.

Esto es similar a que te diga que Ethereum usa “Patricia Merkle trees” para almacenar el estado. Puede que no sepas qué es un “Patricia tree” o un “Merkle tree”, pero sí sabes:

• Tiene una raíz.
• Probablemente puedas acceder a los elementos en tiempo logarítmico, o al menos esa es la intención.
• Algo útil se almacena en las hojas.
• Existe algún algoritmo para recorrer el árbol y acceder a una hoja que te interese.

Por lo tanto, cuando te digo que los puntos de la curva elíptica bajo la suma forman un grupo, ya deberías saber qué tener en cuenta cuando aprendas sobre ese tema.

Nuevamente, los grupos no necesitan ser matemáticas incomprensibles. Has trabajado con grupos de forma intuitiva como programador. Ahora tienes una palabra concreta para describir este fenómeno recurrente.

Es mucho más eficiente decir “grupo” que decir “este es un conjunto con una manera de combinar elementos asociativamente y todos los elementos tienen bla bla bla”.

Sé que esto puede parecer una gran desviación del tema, pero confía en mí, comprender el término “homomorfismo” nos permite describir de manera concisa un concepto que veremos con regularidad. También resultará útil nuevamente cuando discutamos sobre los Programas Aritméticos Cuadráticos. Los homomorfismos aparecen con frecuencia en el mundo ZK.

Imagina intentar hablar sobre estructuras de datos de árboles sin una palabra para “raíces” u “hojas”. Eso sería inmensamente frustrante.

Resumen

Un homomorfismo de $A$ a $B$ existe si y solo si existe una función $\phi$ que toma un elemento de $A$ y devuelve un elemento de $B$ y $\phi(a_i \square a_j)=\phi(a_i)\blacksquare\phi(a_j)$ para todos los $a_i$ y $a_j$ en $A$, donde $\square$ es el operador binario de $A$ y $\blacksquare$ es el operador binario de $B$. La existencia de $\phi$ es suficiente para que el homomorfismo exista.

Los homomorfismos no son necesariamente bidireccionales. Solo se requiere que funcionen en una dirección, de $A$ a $B$.

Si $\phi: A \rightarrow B$ es computacionalmente difícil de invertir, entonces $\phi$ cifra homomórficamente los elementos de $A$. Eso significa que podemos validar afirmaciones sobre cálculos en $A$ usando elementos en $B$.

La buena noticia es que hemos terminado con nuestro tratamiento del álgebra abstracta, y ahora tenemos una base sólida para avanzar hacia las curvas elípticas.