Why index calculus does not work for elliptic curve cryptography

Charagkionis, Petros (2025) Why index calculus does not work for elliptic curve cryptography. Bachelor's Thesis, Mathematics.

Preview	Text BachelorProject-16.pdf Download (1MB) | Preview
	Text Toestemming.pdf Restricted to Registered users only Download (175kB)

Abstract

This thesis investigates the feasibility of adapting the Index Calculus algorithm to address the Elliptic Curve Discrete Logarithm Problem (ECDLP), extending its application from finite fields to elliptic curves. While the Index Calculus method is effective for solving the Discrete Logarithm Problem (DLP) in finite fields, its adaptation to elliptic curves reveals significant challenges due to structural differences between finite fields and elliptic curve groups. These differences, particularly in the group structure and the growth of heights, prevent Index Calculus from being an effective solution to the ECDLP. The thesis also includes a detailed proof of an asymptotic formula for the number of rational points on elliptic curves of bounded height, highlighting implications on the hardness of the ECDLP. To support the validity of this approach, an error analysis has been conducted to justify the use of the approximation, demonstrating to an extent its relevance and reliability. The results underscore the robustness of elliptic curve cryptography and provide a deeper understanding of the computational hardness of the ECDLP. Additionally, the limitations of Index Calculus in this context reinforce the need for alternative methods, such as generic algorithms like Baby-Step Giant-Step and Pollard's rho, which have an exponential time complexity.

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Muller, J.S. and Kilicer, P.
Degree programme:	Mathematics
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	14 Jan 2025 08:18
Last Modified:	14 Jan 2025 08:18
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/34556

Actions (login required)

View Item