Experimental analysis of cheon’s algorithm against pairing-friendly curves

Tetsuya Izu, Masahiko Takenaka, Masaya Yasuda

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Let G be an additive group generated by an element G of prime order r. The discrete logarithm problem with auxiliary input (DLPwAI) is a problem to find α on inputs G, αG, αdG ∈ G for a positive integer d dividing r − 1. The infeasibility of DLPwAI ensures the security of some pairing-based cryptographic schemes. In 2006, Cheon proposed an algorithm for solving DLPwAI which works better than conventional algorithms. In this paper, we report our experimental results of Cheon’s algorithm on a pairing-friendly elliptic curve defined over GF(3127). Moreover, based on our experimental results, we estimate the required cost of Cheon’s algorithm to solve DLPwAI on some pairing-friendly elliptic curves over a finite field of characteristic 3. Our estimation implies that DLPwAI on a part of pairing-friendly curves can be solved at reasonable cost when the optimal parameter d is chosen.

Original languageEnglish
Pages (from-to)441-450
Number of pages10
JournalJournal of information processing
Publication statusPublished - 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


Dive into the research topics of 'Experimental analysis of cheon’s algorithm against pairing-friendly curves'. Together they form a unique fingerprint.

Cite this