# what is a discrete logarithmic assumption? how does it set-up trustless proofs?

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 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.

• Great question but this may be better suited for crypto.SE I think :) Feb 23, 2018 at 20:38
• @MeshCollider cheers Feb 23, 2018 at 20:44

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.

• Andrew rocks! If k is priv key, what is the pubkey? Feb 23, 2018 at 23:27
• The public key is `a` in both cases. `b` is the generator, also known as G.
– Ava Chow
Feb 23, 2018 at 23:57
• (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? Apr 16, 2021 at 18:32
• Apr 16, 2021 at 18:33