Analysis of a method to eliminate fruitless cycles for Pollard’s rho method with skew Frobenius mapping over a Barreto-Naehrig curve

摘要

Pollard’s rho method is one of the most efficient methods for solving elliptic curve discrete logarithm problem (ECDLP) in elliptic curve cryptography. Pollard’s rho method with skew Frobenius mapping can solve ECDLP over a Barreto-Naehrig (BN) curve efficiently. Pollard’s rho method may result in an unsolvable cycle called a fruitless cycle. When a random walk pass results in a fruitless cycle, the random walk pass must restart with a different starting point. However, an effective method for eliminating the fruitless cycle has been not proposed yet.This paper proposes a method for eliminating the fruitless cycle in Pollard’s rho method with skew Frobenius mapping. In addition, the authors apply the proposed method to a BN curve with 17-bit parameters and confirm the effectiveness.