Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves

YOU Lin; YANG Yilin; GAO Shuhong

doi:10.1049/cje.2019.10.005

Volume 29 Issue 1

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2020 > 29(1): 97-105

YOU Lin, YANG Yilin, GAO Shuhong, “Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves,” Chinese Journal of Electronics, vol. 29, no. 1, pp. 97-105, 2020, doi: 10.1049/cje.2019.10.005

Citation:

YOU Lin, YANG Yilin, GAO Shuhong, “Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves,” Chinese Journal of Electronics, vol. 29, no. 1, pp. 97-105, 2020, doi: 10.1049/cje.2019.10.005

Citation:

PDF( 602 KB)

Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves

doi: 10.1049/cje.2019.10.005

1.
School of Cyberspace Security, Hangzhou Dianzi University, Hangzhou 310013, China;
2.
School of Mathematical and Statistical Sciences, Clemson University, Clemson SC 29634-0975, USA

Funds: This work is supported by the Key Program of the Nature Science Foundation of Zhejiang Province of China (No.LZ17F020002) and the National Natural Science Foundation of China (No.61772166).

Received Date: 2016-05-10
Rev Recd Date: 2019-03-13
Publish Date: 2020-01-10

Abstract

Abstract

In an (hyper)elliptic curve cryptosystem, the most important operation or the most time-consuming operation is the divisor scalar multiplication which consists of a sequence of doubling (of divisor) and addition (of two divisors). Point halving algorithms for elliptic curve cryptosystem and divisor halving algorithms for genus-2 hyperelliptic curve cryptosystem had been successively put forward to take the place of doubling algorithms for speeding up (hyper)elliptic curve cryptosystem. We present an outline for an algorithm for divisor halving on genus-3 hyperelliptic curves over the binary field and give some explicit formulae for a class of genus-3 curves. Our algorithm improves previously known best doubling algorithms in most cases. A halve-and-add binary method for divisor scalar multiplications is presented.
- Genus-3 hyperelliptic curve cryptosystem,
- Divisor scalar multiplication,
- Divisor doubling,
- Divisor halving

FullText(HTML)

References(19)

References

L. You, M. Z. Xu, J. Z. Zhao and Z. M. Zheng, "Speeding up scalar multiplications on hyperelliptic curves by making use of Frobenius endomorphism", Chinese Journal of Electroincs, Vol.15, No.1, pp.123-128, 2006.

P. G. Shah, X. Huang and D. Sharma, "Sliding window method with flexible window size for scalar multiplication on wireless sensor network nodes", Proc. of the 2010 International Conference on Wireless Communication and Sensor Computing, Chennai, India, pp.1-6, 2010.

W. Yu, K. Wang, B. Li and S. Tian, "Montgomery algorithm over a prime field", Chinese Journal of Electronics, Vol.28, No.1, pp.39-44, 2019.

E.W. Knudsen, "Elliptic scalar multiplication using point halving", Advances in Cryptology-ASIACRYPT'99, in LNCS, Springer, Vol.1716, pp.135-149, 1999.

R. Schroeppel, "Elliptic curve point halving wins big", Proc. of the 2nd Midwest Arithmetic Geometry in Cryptography Workshop, Urbana, IL, USA, Nov 17-19, 2000.

I. Kitamura, M. Katagi and T. Takagi, "A complete divisor class halving algorithm for hyperelliptic curve cryptosystems of genus two", ACISP' 2005:Information Security and Privacy, in LNCS, Springer Berlin Heidelberg, Vol.3574, pp.146-157, 2005.

P. Birkner, "Efficient divisor class halving on genus two curves", SAC 2006:Selected Areas in Cryptography, in LNCS, Springer, Vol.4356, pp.317-326, 2007.

P. Birkner and N. Th é riault, "Faster halvings in genus 2", SAC 2008:Selected Areas in Cryptography, in LNCS, Springer, Vol.5381, pp.1-17, 2009.

A.J. Menezes, Y. Wu and R.J. Zuccherato, "An elementary introduction to hyperelliptic curves", Technical Report CORR, Dept of Combinatorics and Optimization, University of Waterloo, Ontario, Canada, 1996.

C. Guyot, K. Kaveh and V.M. Patankar,"Explicit algorithm for the arithmetic on the hyperelliptic Jacobians of genus 3", Journal of Ramanujan Mathematical Society, Vol.19, No.2, pp.75-115, 2004.

X. Fan, T. Wollinger and Y. Wang, "Efficient doubling on genus 3 curves over binary fields", Topics in Cryptology -CTRSA'2006, in LNCS, Vol.3860, pp.64-81, Springer, 2006.

J. Pelzl, T. Wollinger and J. Guajardo, et al., "Hyperelliptic curve cryptosystems:Closing the performance gap to elliptic curves", Cryptographic Hardware and Embedded SystemsCHES' 2003, in LNCS, Springer Berlin Heidelberg, Vol.2779, pp.351-365, 2003.

K. Fong, D. Hankerson, J. L ó pez and A. Menezes, "Field inversion and point halving revisited", IEEE Transactions on Computers, Vol.53, Vol.8, pp.1047-1059, 2004.

T. Itoh and S. Tsujii, "A fast algorithm for computing multiplicative inverses in GF (2m) using normal bases", Information and Computation, Vol.78, pp.171-177, 1988.

J. Hu, W. Guo, J. Wei, and R. C. Cheung, "Fast and generic inversion architectures over GF (2m) using modified Itoh-Tsujii algorithms", IEEE Transations on Circuits Systems II-Express Briefs, Vol.62, No.4, pp.367-371, 2015.

R. Azarderakhsh, K. J'arvinen and V. Dimitrov, "Fast inversion in GF (2^m) with normal basis using hybrid-double multipliers", IEEE Transsactions on Computers, Vol.63, No.4, pp.1041-1047, 2014.

M. Ciet, M. Joye, K. Lauter and P. L. Montgomery, "Trading Inversions for Multiplications in Elliptic Curve Cryptography", Designs, Codes and Cryptography, Vol.39, No.2, pp.189-206, 2006.

L. Li and S. Li, "Fast inversion in GF (2m) with polynomial basis using optimal addition chains", Proc. of the 2017 IEEE Int. Symp. on Circuits & Systems, pp.1-4, 2017.

R. M. Avanzi, " Another Look at Square Roots in Fields of Even Characteristic", SAC 2007:Selected Areas in Cryptography, in LNCS, Vol.4876, pp.138-154, 2007.

Relative Articles

Supplements(0)

Cited By

Proportional views