Document Type

Article

Publication Date

7-29-2011

First Advisor

Joshua Holden

Abstract

The discrete logarithm problem, and its adaptation to elliptic curves, called the elliptic curve discrete logarithm problem (ECDLP) is an open problem in the field of number theory, and its applications to modern cryptographic algorithms are numerous. This paper focuses on a statistical analysis of a modification to the ECDLP, called the x-ECDLP, where one is only given the xcoordinate of a point, instead of the entire point. Focusing only on elliptic curves whose field of definition is smaller than the number of points, this paper attempts to find a statistical indication of underlying structure (or lack thereof) in the ECDLP. Using functional graphs, this translates into discovering certain structure in the functional graphs induced by the ECDLP on a wide range of elliptic curves, and comparing these statistics to what would be expected of a random functional graph. A lack of randomness may translate into an exploitable structure in the ECDLP that would undermine the security of cryptographic algorithms based on this problem. In addition to providing an extensive list of data for small primes, this paper details a generating function for the number of elliptic curve functional graphs (ECFGs).

Comments

MSTR 11-01

Download

Included in

Number Theory Commons

Share

COinS