Is there any theory why (for Bitcoin) the discrete logarithm problem is so hard to solve?

Question

Note I am an active member and contributor at the sister site https://bitcoin.stackexchange.com while studying Bitcoin and as a person who studied mathematics 10 years ago there is one thing I kept asking people and I am getting unsatisfying answers.

Why is the discrete logarithm problem (in particular in the case of bitcoin) so hard?

In Bitcoin we take a an elliptic curve as the zeros of $E: y^2 = x^3 + 7$ over $F_p$ with:

 p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

which has a nice representation as $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$

The we chose a generator point (with the standard encoding in hex):

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

This is used to select a cyclic subgroup $C$ of cofactor $h=1$ and order $n$ with

n=115792089237316195423570985008687907852837564279074904382605163141518161494337

We already know there is a group homomorphism

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

In particular by our construction we know that $f$ has to be bijective but apparently it is very hard to give an analytical construction of the inverse map.

In Bitcoin / Computer science we chose $p$ and $g$ in such a way to make $n$ large enough that with pure brute force calculation we won't be able to solve the discrete logarithm. But why can't we construct an inverse map explicitly?

Would anyone here please share some insights why the construction of an analytic closed form for this is so hard?

Answer 1

Yes. I'll talk about why elliptic curve discrete log is harder than ordinary discrete log.

Suppose we have $g, h$ and want to find $n$ such that $g^n = h$.

The usual methods for solving the discrete logarithm problem in $\mathbb{Z} / p \mathbb{Z}$ (as opposed to on an elliptic curve) is to compute $g^k \mod p$ for lots of values $k$ and look for powers which happen to be smooth (all prime factors being small, say in the first 1000 primes). Similarly, compute $h^l \mod p$ for lots of different values $l$.

For instance, we might find that $g^{35976} = 2^4 \times 17 \times 23$, $g^{37} = 2^4$, $h^{999} = 17$, and $h^{8867} = 2^6 \times 23$. If we gather enough relations between powers of $g, h$ and fixed primes, then we can use linear algebra to find some power of $h$ which equals a power of $g$:

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

and then we're basically done, because we can raise both sides to an appropriate power (the multiplicative inverse of the exponent of $h$ mod $\phi(p)$) to get $g^n = h$.

But for elliptic curves, we have no notions of 'small prime points' nor an efficient algorithm to 'factorise' a point as a combination of 'small prime points', so the same strategy doesn't work.

There have been attempts called 'index calculus' to find an analogous approach for elliptic curves, but nothing that beats Pollard rho.

Answer 2

As many people have said, the reason that people believe that factoring and discrete log in $\mathbb F_p^*$ are hard, and that discrete log in $E(\mathbb F_p)$ is even harder, is because a lot of smart people have worked on these problems, and we know the best algorithms they've come up with. ECDLP is delicate, there are certain elliptic curves on which ECDLP is easier. The bitcoin field and curve are carefully chosen. If you'd like a reference that discusses some natural ways that one might try to solve ECDLP, such as index calculus, and why they don't work, there's an article of mine: Lifting and elliptic curve discrete logarithms, Selected Areas of Cryptography (SAC 2008), Lecture Notes in Computer Science 5381, Springer-Verlag, Berlin, 2009, 82-102. You might also be interested in the fact that on "higher dimensional elliptic curves" (called abelian varieties), if the dimension if moderately large compared to the size of the field, then there is an index calculus algorithm that works.

Answer 3

As commented by the two answers, Pollard Rho is the best known algorithm for discrete logarithms in a generic cyclic group (where no other special structure is used, and no such special structure, e.g., amenability to index calculus).

The so called baby step giant step algorithm can also be used with essentially the same time complexity $O(\sqrt{n})$ where $|G|=n,$ as Pollard Rho. Unfortunately the bsgs needs memory of the same order as well, while Pollard Rho requires negligible memory.

So, if $p$ has size $b$ bits, the time complexity for both Pollard Rho and bsgs is $O(2^{b/2}),$ and thus still exponential in input size $b.$ The bsgs is based on a very neat idea, see below:

Input: $x=g^k,$ where $g$ is a generator of a multiplicative cyclic group of size $n$, say $\mathbb{Z}_p^\ast$ for simplicity. The goal is to recover $k,$ and $g$ is public as well as $p$ and the group operation. Let $m=\lceil \sqrt{n}~\rceil.$

Step 1. Precomputation: Form the list $$L=\{(j,g^{jm}):j=0,1,\ldots,m-1\}$$ and store it sorted on the second component (or you could use a hash table and a lookup to find an entry in step 2 below). Complexity: $O(\sqrt{n}\log n)$ time (with hash sorting time complexity would be $O(\sqrt{n})$ but generally additional memory is needed to control collisions in that case) and $O(\sqrt{n})$ memory.

Think of the elements of $G$ in a $\lceil m\rceil \times \lceil m \rceil$ array (with some repeats at the end): $$ \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} $$

Step 2. Online Phase Note that the list $L$ has the entries in the first column sorted as integers. Now, form the elements $x,xg,\ldots, xg^i,\ldots,$ sequentially and lookup in $L$ until the element is found in $L$ (clearly this is guaranteed, as long as we continue until $xg^{m-1}$, since this operation spans two consecutive rows of the array starting at $x$ and ending at $x g^m$ which is below $x$ and one position to the left).

When we find an element in $L,$ at the $i_0$th iteration of Step 2, we then know $$ xg^{i_0-1}=g^{j_0m} $$ where $i_0,j_0$ are known. Solving we get $x=g^{j_0 m-i_0+1}$ so $k=j_0 m-i_0+1\pmod n.$

Note that if you have a new $x,$ you can just repeat Step 2.

One final comment which may be of interest. About 6 years ago there was quite a lot of progress in the DLP algorithms for composite order fields with special exponents (I am quoting a cryptography stack exchange question here below):

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using just a single core-month". They credit a 2012 paper by Antoine Joux: Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite field for paving the way they explore. In 2013 Joux published A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, and very recently announced he "is able to compute discrete logarithms in $GF(2^{6168})=GF({(2^{257})}^{24})$ using less than 550 CPU.hours".

This puts some pairing-based cryptographic schemes relying on the hardness of DLP in fields of characteristic 2 at risk, but not prime field based schemes, be it classical integer residue field DLP or elliptic curve DLP.

Answer 4

Let me take a stab. At the moment, it is probably true that, solving the discrete logarithm problem takes too long to be done in any way that would be useful to break a blockchain. I say probably true in the sense that there is no one who will admit that they can solve the problem efficiently. I think the feeling is that the discrete logarithm problem is NP hard, but it hasn't been proved. If you are not familiar with NP hard, you can either look it up in wikipedia or you can take it to mean the problem is too hard to solve by brute force on a computer. So I think the answer to your question is that mathematicians think the problem is hard, but cannot prove that it is so hard.
There is a cautionary tale, VERY relevant to bitcoin I will tell you. For years people thought that the problem of factoring very large numbers into primes was 'too hard'. Public key encryption was based on the fact that a large number couldn't be factored efficiently (polynomial time). Then, out of the blue, an IIT professor and a couple of his students announced a polynomial time algorithm for factoring integers. Further the proof was elementary in the sense that a decent undergraduate math major could understand it. One has to wonder how many people employed by their version of the NSA said, "damn, the cat's out of the bag" when this was announced. The same could happen for elliptic curve encryption. It is not impossible that there is someone who knows how to break blockchain, but is waiting for the correct moment to 'announce' to the world that he can break blockchain. While bitcoin is large, imagine how much money there is in breaking a major banks unsolvable encryption !