5

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 :) – MeshCollider Feb 23 '18 at 20:38
  • @MeshCollider cheers – zenonzoomzoomzoom Feb 23 '18 at 20:44
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.

  • Andrew rocks! If k is priv key, what is the pubkey? – pebwindkraft Feb 23 '18 at 23:27
  • 1
    The public key is a in both cases. b is the generator, also known as G. – Andrew Chow Feb 23 '18 at 23:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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