Efficient Construction of CGL Hash Function Using Legendre Curves

Yuji Hashimoto; Koji Nuida

doi:10.1587/transfun.2022DMP0003

Efficient Construction of CGL Hash Function Using Legendre Curves

Yuji Hashimoto, Koji Nuida

Laboratory of Mathematical Design for Advanced Cryptography

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2^e-th roots in quadratic extension fields.

Original language	English
Pages (from-to)	1131-1140
Number of pages	10
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E106.A
Issue number	9
DOIs	https://doi.org/10.1587/transfun.2022DMP0003
Publication status	Published - Sept 1 2023

All Science Journal Classification (ASJC) codes

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Access to Document

10.1587/transfun.2022DMP0003

Cite this

@article{95e10c25727445f78a1ed694b68fe975,

title = "Efficient Construction of CGL Hash Function Using Legendre Curves",

abstract = "The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2e-th roots in quadratic extension fields.",

author = "Yuji Hashimoto and Koji Nuida",

note = "Publisher Copyright: Copyright {\textcopyright} 2023 The Institute of Electronics, Information and Communication Engineers.",

year = "2023",

month = sep,

day = "1",

doi = "10.1587/transfun.2022DMP0003",

language = "English",

volume = "E106.A",

pages = "1131--1140",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "9",

}

TY - JOUR

T1 - Efficient Construction of CGL Hash Function Using Legendre Curves

AU - Hashimoto, Yuji

AU - Nuida, Koji

PY - 2023/9/1

Y1 - 2023/9/1

N2 - The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2e-th roots in quadratic extension fields.

AB - The CGL hash function is a provably secure hash function using walks on isogeny graphs of supersingular elliptic curves. A dominant cost of its computation comes from iterative computations of power roots over quadratic extension fields. In this paper, we reduce the necessary number of power root computations by almost half, by applying and also extending an existing method of efficient isogeny sequence computation on Legendre curves (Hashimoto and Nuida, CASC 2021). We also point out some relationship between 2-isogenies for Legendre curves and those for Edwards curves, which is of independent interests, and develop a method of efficient computation for 2e-th roots in quadratic extension fields.

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

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

U2 - 10.1587/transfun.2022DMP0003

DO - 10.1587/transfun.2022DMP0003

M3 - Article

AN - SCOPUS:85170572324

SN - 0916-8508

VL - E106.A

SP - 1131

EP - 1140

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 9

ER -

Efficient Construction of CGL Hash Function Using Legendre Curves

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this