Elliptic Curve Cryptography: Discrete Log Problem & Quadratic Residues

The Study guide: https://ecc-study-guide.magicinternetmath.com/guide.pdf

In this episode of Magic Internet Math, Rob and Brady discuss the discrete log problem and its importance to Bitcoin's security.

Key Topics:

• Discrete Log Problem
• Modular Arithmetic
• Elliptic Curve Cryptography
• Quantum Computing
• Bitcoin Transactions

Summary:

Rob and Brady revisit the math study guide, now nearing its end. They reflect on their journey through modular arithmetic, inverses, and groups, emphasizing their importance in understanding elliptic curve cryptography. They highlight that a deep understanding of group structures is essential to ensure the validity of point manipulations on the curve, which cannot be brute-forced. They stress the need to understand the underlying math to defend against potential attacks that exploit a lack of knowledge in this area.

The pair dive into the discrete log problem (DLP), calling it the "big boss" of arithmetic and a crucial element in Bitcoin's security. They note its relevance in the context of quantum computing threats. They explain that the DLP relies on the asymmetry between easily calculating a public key from a private key and the computational infeasibility of reversing the process. It's also described as a form of digital physics, requiring immense computational force to "open the door" and reverse engineer the private key from the public key. The computational cost of solving the DLP is measured using Big O notation, with algorithms like Shanks and Pollard's row reducing the complexity to O(√N), still a significant hurdle.

The hosts use a small modular arithmetic example to illustrate the DLP, emphasizing the difficulty of guessing the power needed to reach a specific point on the elliptic curve. They stress the importance of understanding logarithms, describing them as simply powers. They use the mnemonic PEMDAS to explain the order of operations, highlighting the inverse relationship between exponentiation and logarithms.

The discussion transitions to the "discrete" aspect of the discrete log problem, explaining that it implies a lack of continuity, making it impossible to infer proximity to the solution. This contrasts with Bitcoin mining, where there are multiple valid solutions. The discrete nature of the DLP forces trial-and-error approaches, making it computationally hard and ugly on purpose. They mention that the best algorithms currently can only reduce the search space to the square root of N.