28
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ Why is it hard to factor numbers? - Because we don't know a fast way of doing so. I think it is the same here. We just don't know how to do it. Look at the points $g^x$, (usally written additively $nP$) and you won't see any pattern that could help you to construct the inverse of $f$. $\endgroup$ – Chris Wuthrich Nov 22 at 13:12
  • $\begingroup$ I should add that if $n=p$ or $n=p+1$ then we happen to know how to do it. $\endgroup$ – Chris Wuthrich Nov 22 at 13:13
  • 4
    $\begingroup$ Maybe it is worth mentioning that no such "theory" exists in the sense that nobody knows how to prove that the discrete logarithm problem is hard (e.g. If hard means "not solvable in polynomial time" such a proof would imply $P \neq NP$). It is justs something that everybody believes is the case. Of course that does not mean that one cannot find some kind of heuristic explanation of why it is hard. $\endgroup$ – Simon Henry Nov 22 at 16:53
  • 1
    $\begingroup$ Discrete logarithm (as well as integer factorization) have polynomial-time algorithms for quantum computers (of course we don't yet have quantum computers that can run these algorithms). We do not have polynomial-time algorithms for quantum computers to solve problems that are known to be NP-complete. This suggests strongly that discrete logarithm and integer factorization are not NP-complete. So even if we could prove $P \ne NP$, it would not prove that discrete logarithm is hard. $\endgroup$ – Robert Israel Nov 22 at 17:42
  • 12
    $\begingroup$ Over on cstheory , Peter Shor writes "there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far." cstheory.stackexchange.com/a/5098/6508 I think the same is true of discrete log. $\endgroup$ – DES-SupportsMonicaAndTransfolk Nov 22 at 18:04
29
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I may be wrong (or misunderstood you), but I have always thought that index calculus is the attack on DLP that you described here. See my answer in Math.SE for an example run of index calculus in $\Bbb{F}_{2^{10}}$. $\endgroup$ – Jyrki Lahtonen Nov 24 at 14:31
22
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
-13
$\begingroup$

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 !

$\endgroup$
  • 26
    $\begingroup$ Didn't they make a fast primality test, not a fast factorization algorithm? $\endgroup$ – Jesse Silliman Nov 22 at 16:25
  • 12
    $\begingroup$ And long before the fast primality test, there was a fast probabilistic primality test en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test . No one was basing security on the difficulty of prime testing, since probabilistic methods appear to be as good as deterministic ones in practice. $\endgroup$ – DES-SupportsMonicaAndTransfolk Nov 22 at 16:39
  • 9
    $\begingroup$ " I think the feeling is that the discrete logarithm problem is NP hard" This is very likely not the case. Discrete log is in BQP and we're pretty sure that no NP-hard problem is in that class. Discrete log is also in NP intersect co-NP and we're reasonably confident no NP-hard problem is in that intersection also. If it were, the polynomial hierarchy would collapse which would be almost as surprising as P = NP. $\endgroup$ – JoshuaZ Nov 22 at 19:51
  • $\begingroup$ DL has also been shown to be in quasi-polynomial time for multiplicative groups of finite fields of (fixed) characteristic. If DL were NP-hard I imagine this would violate assumptions like ETH and SETH, but am not an expert. $\endgroup$ – Mark Nov 25 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.