Iteration functions for Pollard's rho on elliptic curve groups

Date

2016-05

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Pollard's Rho method is one way to solve the discrete log problem (DLP) in Elliptic Curve Groups. It relies on the use of an iterative mapping that behaves like a random mapping. In this paper, we will discuss some alternative iteration functions to Pollard's original suggestion. We will then compare the different iteration functions to Pollard's by examining the expected value of the number of iterations, or steps, each iteration function requires for completion in elliptic curve groups of prime order ≈104,105,and106. We will compare the expected value of each iteration function to the performance expected of an iteration function chosen at random. This analysis will be performed in order to identify possible iteration functions that may perform better than Pollard's original, the random case, or both most of the time. Finally, we then describe an algorithm to compute Pollard's Rho in parallel, which dramatically decreases the run time to solve the DLP in large elliptic curve groups.

Description

Keywords

Cryptography, Cryptology, Pollard, Pollard's rho, Elliptic curve group, Elliptic curve groups, Elliptic curve, Iteration functions, Random walk

Citation