Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves

Hiromasa Miura; Ken Ikuta; Sho Joichi; Takuya Kusaka; Yasuyuki Nogami

doi:10.1109/ITC-CSCC.2019.8793449

Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves

Hiromasa Miura, Ken Ikuta, Sho Joichi, Takuya Kusaka, Yasuyuki Nogami

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

This paper focuses on the computational security of elliptic curve discrete logarithm (ECDLP), which can evaluate by an actual attack. The authors apply Pollard's rho method to a Barreto-Naehrig curve with minimum parameters for solving an ECDLP. An analysis of the structure for all combinations of a select of seed and starting points are given. Then, we propose the method for selecting a set of efficient seed points for a random walk for the rho method.

Original language	English
Title of host publication	34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781728132716
DOIs	https://doi.org/10.1109/ITC-CSCC.2019.8793449
Publication status	Published - Jun 2019
Event	34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019 - JeJu, Korea, Republic of Duration: Jun 23 2019 → Jun 26 2019

Publication series

Name	34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019

Conference

Conference	34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019
Country/Territory	Korea, Republic of
City	JeJu
Period	6/23/19 → 6/26/19

Keywords

Barreto-Naehrig curve
ECDLP
Pollard's rho method
fruitless cycle

ASJC Scopus subject areas

Information Systems
Electrical and Electronic Engineering
Artificial Intelligence
Computer Networks and Communications
Hardware and Architecture

Access to Document

10.1109/ITC-CSCC.2019.8793449

Cite this

Miura, H., Ikuta, K., Joichi, S., Kusaka, T., & Nogami, Y. (2019). Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves. In 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019 Article 8793449 (34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITC-CSCC.2019.8793449

Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves. / Miura, Hiromasa; Ikuta, Ken; Joichi, Sho et al.
34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. 8793449 (34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Miura, H, Ikuta, K, Joichi, S, Kusaka, T & Nogami, Y 2019, Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves. in 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019., 8793449, 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019, Institute of Electrical and Electronics Engineers Inc., 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019, JeJu, Korea, Republic of, 6/23/19. https://doi.org/10.1109/ITC-CSCC.2019.8793449

Miura H, Ikuta K, Joichi S, Kusaka T , Nogami Y. Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves. In 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. 8793449. (34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019). doi: 10.1109/ITC-CSCC.2019.8793449

Miura, Hiromasa ; Ikuta, Ken ; Joichi, Sho et al. / Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves. 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. (34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019).

@inproceedings{9de9a010a11b49bab6f756ce373559e7,

title = "Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves",

abstract = "This paper focuses on the computational security of elliptic curve discrete logarithm (ECDLP), which can evaluate by an actual attack. The authors apply Pollard's rho method to a Barreto-Naehrig curve with minimum parameters for solving an ECDLP. An analysis of the structure for all combinations of a select of seed and starting points are given. Then, we propose the method for selecting a set of efficient seed points for a random walk for the rho method.",

keywords = "Barreto-Naehrig curve, ECDLP, Pollard's rho method, fruitless cycle",

author = "Hiromasa Miura and Ken Ikuta and Sho Joichi and Takuya Kusaka and Yasuyuki Nogami",

year = "2019",

month = jun,

doi = "10.1109/ITC-CSCC.2019.8793449",

language = "English",

series = "34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019",

note = "34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

}

TY - GEN

T1 - Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves

AU - Miura, Hiromasa

AU - Ikuta, Ken

AU - Joichi, Sho

AU - Kusaka, Takuya

AU - Nogami, Yasuyuki

PY - 2019/6

Y1 - 2019/6

N2 - This paper focuses on the computational security of elliptic curve discrete logarithm (ECDLP), which can evaluate by an actual attack. The authors apply Pollard's rho method to a Barreto-Naehrig curve with minimum parameters for solving an ECDLP. An analysis of the structure for all combinations of a select of seed and starting points are given. Then, we propose the method for selecting a set of efficient seed points for a random walk for the rho method.

AB - This paper focuses on the computational security of elliptic curve discrete logarithm (ECDLP), which can evaluate by an actual attack. The authors apply Pollard's rho method to a Barreto-Naehrig curve with minimum parameters for solving an ECDLP. An analysis of the structure for all combinations of a select of seed and starting points are given. Then, we propose the method for selecting a set of efficient seed points for a random walk for the rho method.

KW - Barreto-Naehrig curve

KW - ECDLP

KW - Pollard's rho method

KW - fruitless cycle

UR - http://www.scopus.com/inward/record.url?scp=85071473290&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071473290&partnerID=8YFLogxK

U2 - 10.1109/ITC-CSCC.2019.8793449

DO - 10.1109/ITC-CSCC.2019.8793449

M3 - Conference contribution

AN - SCOPUS:85071473290

T3 - 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019

BT - 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 34th International Technical Conference on Circuits/Systems, Computers and Communications, ITC-CSCC 2019

Y2 - 23 June 2019 through 26 June 2019

ER -

Analysis of the fruitless cycle of Pollard's rho method based attack for solving ECDLP over Barreto-Naehrig curves

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this