¿Existe alguna teoría de por qué (para Bitcoin) el problema del logaritmo discreto es tan difícil de resolver?

Question

Tenga en cuenta que soy miembro activo y colaborador en el sitio hermano https://bitcoin.stackexchange.com mientras estudio Bitcoin y como persona que estudió matemáticas hace 10 años hay una cosa que sigo preguntando a la gente y estoy recibiendo respuestas insatisfactorias.

¿Por qué es tan difícil el problema del logaritmo discreto (en particular en el caso del bitcoin)?

En Bitcoin tomamos una curva elíptica como los ceros de $E: y^2 = x^3 + 7$ en $F_p$ con:

 p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

que tiene una bonita representación como $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

Elegimos un punto generador (con la codificación estándar en hexadecimal):

g = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Sirve para seleccionar un subgrupo cíclico $C$ de cofactor $h=1$ y orden $n$ con

n=115792089237316195423570985008687907852837564279074904382605163141518161494337

Ya sabemos que existe un homomorfismo de grupo

$f: F_n \rightarrow C$ con $x\mapsto g^x$

En particular, por nuestra construcción sabemos que $f$ tiene que ser biyectivo pero aparentemente es muy difícil dar una construcción analítica del mapa inverso.

En Bitcoin / Informática elegimos $p$ y $g$ de tal manera que $n$ lo suficientemente grande como para que con puro cálculo de fuerza bruta no podamos resolver el logaritmo discreto. Pero, ¿por qué no podemos construir un mapa inverso explícitamente?

¿Podría alguien explicar por qué es tan difícil construir una forma analítica cerrada?

Answer 1

Sí. Hablaré de por qué el registro discreto de curva elíptica es más difícil que el registro discreto ordinario.

Supongamos que tenemos $g, h$ y quiere encontrar $n$ tal que $g^n = h$ .

Los métodos habituales para resolver el problema del logaritmo discreto en $\mathbb{Z} / p \mathbb{Z}$ (en lugar de en una curva elíptica) es calcular $g^k \mod p$ para muchos valores $k$ y buscar potencias que resulten ser suaves (todos los factores primos son pequeños, digamos en los 1000 primeros primos). Del mismo modo, calcule $h^l \mod p$ para muchos valores diferentes $l$ .

Por ejemplo, podemos encontrar que $g^{35976} = 2^4 \times 17 \times 23$ , $g^{37} = 2^4$ , $h^{999} = 17$ y $h^{8867} = 2^6 \times 23$ . Si reunimos suficientes relaciones entre potencias de $g, h$ y primos fijos, entonces podemos usar álgebra lineal para encontrar alguna potencia de $h$ que es igual a una potencia de $g$ :

$$g^{35976 \times 2 + 37} = 2^{12} \times 17^2 \times 23^2 = h^{8867 \times 2 + 999 \times 2}$$

y ya está, porque podemos elevar ambos lados a una potencia adecuada (la inversa multiplicativa del exponente de $h$ mod $\phi(p)$ ) para obtener $g^n = h$ .

Pero para las curvas elípticas, no tenemos nociones de "pequeños puntos primos" ni un algoritmo eficiente para "factorizar" un punto como una combinación de "pequeños puntos primos", por lo que la misma estrategia no funciona.

Ha habido intentos llamados "cálculo de índices" para encontrar un enfoque análogo para las curvas elípticas, pero nada que supere a Pollard rho.

Answer 2

Como muchos han dicho, la razón por la que la gente cree que el factoring y el registro discreto en $\mathbb F_p^*$ son duros, y que el registro discreto en $E(\mathbb F_p)$ es aún más difícil, es porque mucha gente inteligente ha trabajado en estos problemas, y conocemos los mejores algoritmos que han ideado. ECDLP es delicado, hay ciertas curvas elípticas en las que ECDLP es más fácil. El campo y la curva de bitcoin se eligen cuidadosamente. Si quieres una referencia que discuta algunas formas naturales en las que uno podría intentar resolver ECDLP, como el cálculo de índices, y por qué no funcionan, hay un artículo mío: Elevación y logaritmos discretos de curva elíptica, Áreas seleccionadas de la criptografía (SAC 2008), Lecture Notes in Computer Science 5381 Springer-Verlag, Berlín, 2009, 82-102. También podría interesarte el hecho de que en "curvas elípticas de dimensiones superiores" (llamadas variedades abelianas), si la dimensión es moderadamente grande en comparación con el tamaño del campo, existe un algoritmo de cálculo de índices que funciona.

Answer 3

Como se comenta en las dos respuestas, Pollard Rho es el algoritmo más conocido para logaritmos discretos en un grupo cíclico genérico (en el que no se utiliza ninguna otra estructura especial, y no existe tal estructura especial, por ejemplo, susceptible de cálculo de índices).

El llamado paso de bebé paso de gigante también puede utilizarse con la misma complejidad temporal $O(\sqrt{n})$ donde $|G|=n,$ como Pollard Rho. Por desgracia, el bsgs también necesita memoria del mismo orden, mientras que Pollard Rho requiere una memoria insignificante.

Por lo tanto, si $p$ tiene tamaño $b$ bits, la complejidad temporal tanto para Pollard Rho como para bsgs es $O(2^{b/2}),$ y, por tanto, sigue siendo exponencial en tamaño de entrada $b.$ El bsgs se basa en una idea muy ingeniosa, véase más abajo:

Entrada: $x=g^k,$ donde $g$ es un generador de un grupo cíclico multiplicativo de tamaño $n$ , digamos $\mathbb{Z}_p^\ast$ para simplificar. El objetivo es recuperar $k,$ y $g$ es público al igual que $p$ y la operación de grupo. Sea $m=\lceil \sqrt{n}~\rceil.$

Etapa 1. Precálculo: Formar la lista $$L=\{(j,g^{jm}):j=0,1,\ldots,m-1\}$$ y almacenarlo ordenado en el segundo componente (o podría utilizar una tabla hash y una búsqueda para encontrar una entrada en el paso 2 a continuación). Complejidad: $O(\sqrt{n}\log n)$ tiempo (con la clasificación hash la complejidad del tiempo sería $O(\sqrt{n})$ pero generalmente se necesita memoria adicional para controlar las colisiones en ese caso) y $O(\sqrt{n})$ memoria.

Piense en los elementos de $G$ en un $\lceil m\rceil \times \lceil m \rceil$ (con algunas repeticiones al final): $$ \begin{array}{cccccc} 1 & g & g^2 & g^3 &\cdots & g^{m-1} \\ g^m & g^{m+1} & g^{m+2} & g^{m+3} & \cdots & g^{2m-1} \\ \vdots & & & & \vdots\\ g^{m(m-1)} & g^{m(m-1)+1} & \cdots & g^{n-1} & 1 & \cdots\\ \end{array} $$

Segundo paso. Fase en línea Tenga en cuenta que la lista $L$ tiene las entradas de la primera columna ordenados como enteros . Ahora, forme los elementos $x,xg,\ldots, xg^i,\ldots,$ secuencialmente y buscar en $L$ hasta que el elemento se encuentre en $L$ (claramente esto está garantizado, siempre y cuando continuemos hasta que $xg^{m-1}$ ya que esta operación abarca dos filas consecutivas de la matriz a partir de $x$ y terminando en $x g^m$ que está por debajo de $x$ y una posición a la izquierda).

Cuando encontramos un elemento en $L,$ en el $i_0$ iteración del paso 2, sabemos que $$ xg^{i_0-1}=g^{j_0m} $$ donde $i_0,j_0$ son conocidos. Resolviendo obtenemos $x=g^{j_0 m-i_0+1}$ así que $k=j_0 m-i_0+1\pmod n.$

Tenga en cuenta que si tiene un nuevo $x,$ puede repetir el paso 2.

Un último comentario que puede ser de interés. Hace unos 6 años se avanzó bastante en los algoritmos DLP para campos de orden compuesto con exponentes especiales (cito una pregunta de intercambio de pilas criptográficas ici más abajo):

Un trabajo reciente de Göloglu, Granger, McGuire y Zumbrägel: Solución de un DLP de 6120 bits en un ordenador de sobremesa parece "demostrar una DLP romper en el campo finito de $2^{6120}$ elementos, utilizando un único núcleo-mes". Se refieren a un artículo de 2012 de Antoine Joux: Cálculo de índices más rápido para el caso de primos medios. Aplicación a campos finitos de 1175 bits y 1425 bits. por allanar el camino que exploran. En 2013 Joux publicó Un nuevo algoritmo de cálculo de índices con complejidad $L(1/4+o(1))$ en característica muy pequeña y muy recientemente anunciado él "es capaz de calcular logaritmos discretos en $GF(2^{6168})=GF({(2^{257})}^{24})$ utilizando menos de 550 CPU.horas".

Esto pone en peligro algunos esquemas criptográficos basados en el emparejamiento que dependen de la dureza de DLP en campos de característica 2, pero no los esquemas basados en campos primos, ya sean DLP clásicos de campos de residuos enteros o DLP de curvas elípticas.

Answer 4

Déjame intentarlo. Por el momento, es probablemente cierto que, resolver el problema del logaritmo discreto lleva demasiado tiempo como para hacerlo de forma que sea útil para romper una blockchain. Digo probablemente cierto en el sentido de que no hay nadie que admita que puede resolver el problema de manera eficiente. Creo que la sensación es que el problema del logaritmo discreto es NP difícil, pero no se ha demostrado. Si no estás familiarizado con NP hard, puedes buscarlo en wikipedia o puedes entenderlo como que el problema es demasiado difícil de resolver por fuerza bruta en un ordenador. Así que creo que la respuesta a tu pregunta es que los matemáticos creen que el problema es difícil, pero no pueden demostrar que lo sea.
Hay un cuento con moraleja, MUY relevante para el bitcoin que os contaré. Durante años la gente pensó que el problema de factorizar números muy grandes en primos era "demasiado difícil". El cifrado de clave pública se basaba en el hecho de que un número grande no se podía factorizar de forma eficiente (tiempo polinómico). Entonces, de la nada, un profesor del IIT y un par de sus estudiantes anunciaron un algoritmo de tiempo polinómico para factorizar números enteros. Además, la demostración era elemental, en el sentido de que cualquier estudiante de matemáticas podría entenderla. Hay que preguntarse cuántas personas empleadas por su versión de la NSA dijeron "joder, se ha descubierto el pastel" cuando se anunció esto. Lo mismo podría ocurrir con el cifrado de curvas elípticas. No es imposible que haya alguien que sepa cómo romper blockchain, pero que esté esperando el momento adecuado para "anunciar" al mundo que puede romper blockchain. Mientras que el bitcoin es grande, ¡imagina cuánto dinero hay en romper el cifrado irresoluble de un gran banco!