Combinatorical and Algebraic Structures Seminar

Session details

Date: 30.11.2010
Speaker: Alberto Pizzirani, University of Naples ``Federico II''
Title: The elliptic curve discrete logarithm problem in cryptography and an implementation of parallelized Pollard's rho algorithm with CUDA for ECDLP resolution
Abstract: Cryptography is essentially aimed at protecting data from unauthorized access. This is particularly important when data involve sensible informations and are transmitted on insecure channels. Typical examples are business via internet and the payment with a credit card. The data involved in such transactions are usually encrypted to make it harder for an attacker to retrieve secret informations. In the past, the key for encryption was the same for decryption raising a serious problem regarding key distribution. In 1976 W.Diffie and M.Hellman invented an agreement protocol that allows two users to exchange a secret key over an insecure channel without any prior contact. This event is commonly considered the birth of public-key cryptography. Then, relying on some hard mathematical problem, many cryptosystems have been proposed. However, since some attacks were able to solve such math problems in a reasonable amount of time most of these cryptosystems become insecure or simply impratical. Actually, three mathematical problems are still considered to be hard: the integer factorization problem (IFP), the discrete logarithm problem in the multiplicative group of a finite field (DLP) and in the group of points of an elliptic curve (ECDLP). There is no real proof that the aforementioned problems are intractable. However, a lot of work has been done to try to solve them efficiently. All these efforts amount to the development of subexponential-time algorithms for IFP and DLP, but none for ECDLP. Elliptic curve cryptography (ECC) became more and more attractive essentially for such a reason. Moreover, parameters of the ECC are usually much smaller than parameters of cryptosystems based on IFP and DLP. Consequently ECC has lower communication overhead. Even if no subexponential running time attack is known to work on generic instances of ECDLP problem, there are various methods (more or less efficient) to solve instances of the general DLP that can be applied to ECDLP. Some of them have deterministic running time, but, those with probabilistic running time (like Pollard's rho method) usually have a better trade off between space and time. In this seminar we will give the basic concepts on elliptic curves, their behaviour on finite fields, some simple applications in cryptographic protocols and we will describe an implementation for graphic processing units (GPUs) supporting NVIDIA CUDA architecture of a parallelized Pollard's rho attack on ECDLP, based upon recent results about the optimization of Pollard's method and enhanced by some ``ad-hoc'' choices for CUDA.
Slides: 20101130.pdf

Return to index.