<p>The discrete logarithm problem is a cryptography concept that underlies the basis of much of modern cryptography.</p>

<p>In general the discrete logarithm problem states that for the equation <pre><code>b<sup>k</sup> (mod p) = a</pre></code> where <code>b</code>, <code>a</code>, and <code>p</code> are known values and <code>p</code> is prime, finding <code>k</code> is hard.</p>

<p>This is hard because of modular arithmetic; in order to find k, you would need to brute force it. Furthermore, there are an infinite number of solutions because you don't know how many times <code>p</code> <code>b^k</code> is. The values <code>b</code> and <code>p</code> are also specifically chosen values which make this problem harder as some values (especially lower values and non-prime values) are easy to solve (easy in that it doesn't take much time but the time complexity is still the same).</p>

<p>Although there is no proof that the discrete logarithm problem is actually hard, but it is believed to be hard as no one has found a way to actually compute the logarithm quickly.</p>

<p>But Bitcoin actually uses a slightly different version of this problem known as the Elliptic Curve Discrete Logarithm Problem (ECDLP). With EC math, <code>b</code> is actually a point on an elliptic curve, it has an <code>x</code> and a <code>y</code> value. Rather than raising <code>b</code> to some number <code>k</code>, you actually do EC scalar multiplication with some number <code>k</code>, so it is </p>

<pre><code>bk (mod p) = a
</code></pre>

<p>What this boils down do is adding <code>b</code> to itself <code>k</code> times, and the security comes from the fact that it is hard to figure out what two points were added together to get a third point.</p>

<p>The process of adding an EC curve point to itself means that you find a tangent line to the point, extend the line to where it intersects the curve, and the invert the <code>y</code> value of that point. Doing this, and reversing it, over the real numbers isn't that hard, but EC cryptography is done over a finite field of order <code>p</code> which is a large prime, which means that all values are <code>(mod p)</code> so, when you graph the curve, it's all over place in your graph. This means that, given a point on the curve, it is hard to figure out what other points were added to get to that point so it is thus hard to reverse this process.</p>

<p>In both ECDLP and the normal DLP, <code>k</code> is the private key and solving either discrete log problem would result in you finding the private key <code>k</code>.</p>

<p>There are algorithms such as Shors algorithm which can allow quantum computers to solve the discrete log problem.</p>

<hr>

<p>Note that this stuff is hard and I am not a cryptography expert. This is just how I understood things and it may not be necessarily correct or make sense.</p>

CC BY-SA 3.0
2018-02-23T23:27:04.497Z
Andrew rocks! If k is priv key, what is the pubkey?
pebwindkraft
CC BY-SA 3.0
2018-02-23T23:57:27.600Z
The public key is `a` in both cases. `b` is the generator, also known as G.
Ava Chow
CC BY-SA 4.0
2021-04-16T18:32:06.240Z
(I would like to add a comment, but this reputation barrier doesn't let me do it) My question to @Andrew Chow is: What is the meaning of (mod p) in the equation that you just mention above?
Diving
CC BY-SA 4.0
2021-04-16T18:33:15.250Z
See https://en.wikipedia.org/wiki/Modular_arithmetic
Pieter Wuille
CC BY-SA 3.0
2018-02-23T22:41:53.770Z
2018-02-23T22:41:53.770Z
Ava Chow
<p>pending proposal of bulletproofs as a zk proof for confidential transactions relies on fiat-shamir heuristic to be non-interactive via creating a digital signature on interactive proof of knowledge and as cited in [bootle, wuille, maxwell et al] "Bulletproofs: Short Proofs for Confidential Transactions and More" paper also rely on <em>discrete logarithmic assumption</em> be a trustless proof (unlike snarks). this led to my question above as im not well-versed on this topic and would like to learn more about this, more specifically in its relation to setting up bulletproofs.</p>

CC BY-SA 3.0
2018-02-23T20:38:08.947Z
Great question but this may be better suited for crypto.SE I think :)
meshcollider
CC BY-SA 3.0
2018-02-23T20:44:56.590Z
@MeshCollider cheers
zenonzoomzoomzoom
<cryptography>
what is a discrete logarithmic assumption? how does it set-up trustless proofs?
zenonzoomzoomzoom
# what is a discrete logarithmic assumption? how does it set-up trustless proofs?

(Asked by: username_0 on 2018-02-23)

pending proposal of bulletproofs as a zk proof for confidential transactions relies on fiat-shamir heuristic to be non-interactive via creating a digital signature on interactive proof of knowledge and as cited in [bootle, username_5, maxwell et al] "Bulletproofs: Short Proofs for Confidential Transactions and More" paper also rely on *discrete logarithmic assumption* be a trustless proof (unlike snarks). this led to my question above as im not well-versed on this topic and would like to learn more about this, more specifically in its relation to setting up bulletproofs.

**Tags:** cryptography

> **Comments:**
> **username_1**: Great question but this may be better suited for crypto.SE I think :)  
> **username_0**: @MeshCollider cheers  

---

## 1 answers

### Answer by username_2 on 2018-02-23. Score: 3

The discrete logarithm problem is a cryptography concept that underlies the basis of much of modern cryptography.

In general the discrete logarithm problem states that for the equation

```
bk (mod p) = a
```

where `b`, `a`, and `p` are known values and `p` is prime, finding `k` is hard.

This is hard because of modular arithmetic; in order to find k, you would need to brute force it. Furthermore, there are an infinite number of solutions because you don't know how many times `p` `b^k` is. The values `b` and `p` are also specifically chosen values which make this problem harder as some values (especially lower values and non-prime values) are easy to solve (easy in that it doesn't take much time but the time complexity is still the same).

Although there is no proof that the discrete logarithm problem is actually hard, but it is believed to be hard as no one has found a way to actually compute the logarithm quickly.

But Bitcoin actually uses a slightly different version of this problem known as the Elliptic Curve Discrete Logarithm Problem (ECDLP). With EC math, `b` is actually a point on an elliptic curve, it has an `x` and a `y` value. Rather than raising `b` to some number `k`, you actually do EC scalar multiplication with some number `k`, so it is

```
bk (mod p) = a

```

What this boils down do is adding `b` to itself `k` times, and the security comes from the fact that it is hard to figure out what two points were added together to get a third point.

The process of adding an EC curve point to itself means that you find a tangent line to the point, extend the line to where it intersects the curve, and the invert the `y` value of that point. Doing this, and reversing it, over the real numbers isn't that hard, but EC cryptography is done over a finite field of order `p` which is a large prime, which means that all values are `(mod p)` so, when you graph the curve, it's all over place in your graph. This means that, given a point on the curve, it is hard to figure out what other points were added to get to that point so it is thus hard to reverse this process.

In both ECDLP and the normal DLP, `k` is the private key and solving either discrete log problem would result in you finding the private key `k`.

There are algorithms such as Shors algorithm which can allow quantum computers to solve the discrete log problem.

---

Note that this stuff is hard and I am not a cryptography expert. This is just how I understood things and it may not be necessarily correct or make sense.

> **Comments:**
> **username_3**: Andrew rocks! If k is priv key, what is the pubkey?  
> **username_2**: The public key is `a` in both cases. `b` is the generator, also known as G.  
> **username_4**: (I would like to add a comment, but this reputation barrier doesn't let me do it) My question to @Andrew username_2 is: What is the meaning of (mod p) in the equation that you just mention above?  
> **username_5**: See https://en.wikipedia.org/wiki/Modular_arithmetic  

---

