IEICE TRANSACTIONS on Fundamentals
Efficient Construction of CGL Hash Function Using Legendre Curves
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.9 pp.1131-1140
- Publication Date
- 2023/09/01
- Publicized
- 2023/02/07
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2022DMP0003
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Cryptography and Information Security
Authors
Yuji HASHIMOTO
Tokyo Denki University,National Institute of Advanced Industrial Science and Technology
Koji NUIDA
National Institute of Advanced Industrial Science and Technology,Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuji HASHIMOTO, Koji NUIDA, "Efficient Construction of CGL Hash Function Using Legendre Curves" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 9, pp. 1131-1140, September 2023, doi: 10.1587/transfun.2022DMP0003.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022DMP0003/_p
Copy
@ARTICLE{e106-a_9_1131,
author={Yuji HASHIMOTO, Koji NUIDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Efficient Construction of CGL Hash Function Using Legendre Curves},
year={2023},
volume={E106-A},
number={9},
pages={1131-1140},
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.},
keywords={},
doi={10.1587/transfun.2022DMP0003},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Efficient Construction of CGL Hash Function Using Legendre Curves
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1131
EP - 1140
AU - Yuji HASHIMOTO
AU - Koji NUIDA
PY - 2023
DO - 10.1587/transfun.2022DMP0003
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2023
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.
ER -
English
