Elliptic Curve Discrete Logarithm Problem (Applied Cryptography 101)

Welcome to this lecture in Alfred Menezes's "Crypto 101: Building Blocks" course, where we delve into the Elliptic Curve Discrete Logarithm Problem (ECDLP)—a fundamental hard problem in modern cryptography. The ECDLP underpins the security of many cryptographic systems, including those using Elliptic Curve Cryptography (ECC) for key exchange, digital signatures, and encryption.

In this video, we start by introducing the concept of point multiplication on elliptic curves and how it forms the basis of the ECDLP. You’ll learn about generator points and their critical role in defining elliptic curve groups. We explore why solving the ECDLP is computationally infeasible, making ECC a powerful tool for secure communications.

We also cover state-of-the-art algorithms used to solve the ECDLP, including Shanks' algorithm and Pollard's algorithm, both of which aim to efficiently find the discrete logarithm on elliptic curves. These algorithms are essential for understanding the security assumptions behind ECC-based systems, and we highlight their performance and practical implications for cryptographic protocol design.

This lecture provides essential knowledge for anyone interested in applied cryptography, cybersecurity, and security engineering. By the end of this video, you will understand the theoretical and practical aspects of the Elliptic Curve Discrete Logarithm Problem and its impact on modern cryptographic systems.

Lecture playlist:
https://www.youtube.com/playlist?list=PLA1qgQLL41SRsHMtsb4up5fTytDeHV_yJ

Course web page: https://cryptography101.ca/crypto101-building-blocks/
The slides are available on the course web page.

"Elliptic curve cryptography" chapter from "Textbook of Applied Cryptography": https://drive.google.com/file/d/1y30ccFhMI2_btwzCADyDmwSs8758tqlU/view

Other cryptography courses: https://cryptography101.ca

Slides
00:00 Introduction
00:27 Slide 309: Point multiplication
02:05 Slide 310: Generators
04:26 Slide 311: Example of an elliptic curve
05:23 Slide 312: Elliptic curve discrete logarithm problem
07:34 Slide 313: Algorithms for solving ECDLP (1)
08:28 Slide 314: Algorithms for solving ECDLP (2)
12:35 Slide 315: Algorithms for solving ECDLP (3)
15:33 Coming up