Discrete Log Problem (DLP)

1 min read

The Discrete Log Problem (DLP) describes the fact that there is currently no known method for calculating point division on an elliptic curve. Point multiplication, the function used to derive public keys from private keys, is calculated easily enough, but its inverse is not.

This unique property gives elliptic curve cryptography its security. However, the Discrete Log Problem is not proven to be impossible. Rather, after much investigation, no solution has yet been discovered, leading cryptographers to assume its security.

Bitcoin relies on the Discrete Log Problem for its security as well. Bitcoin uses the elliptic curve secp256k1 to implement its public key cryptography. Private keys are large, random numbers. A private key sk is multiplied by a publicly defined Generator Point G to obtain a different point on the curve P, the public key. Thanks to the Discrete Log Problem, this multiplication cannot be reversed, so a public key cannot be used to reveal a private key.

The impossibility of point division also enables this scheme to support digital signature schemes such as ECDSA and Schnorr. A digital signature proves that the producer knows a private key and is committing to a certain message without revealing the private key.