YOU Lin, YANG Yilin, GAO Shuhong. Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves[J]. Chinese Journal of Electronics, 2020, 29(1): 97-105. doi: 10.1049/cje.2019.10.005
Citation: YOU Lin, YANG Yilin, GAO Shuhong. Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves[J]. Chinese Journal of Electronics, 2020, 29(1): 97-105. doi: 10.1049/cje.2019.10.005

Divisor Class Halving Algorithms for Genus Three Hyperelliptic Curves

doi: 10.1049/cje.2019.10.005
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
  • 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.
  • loading
  • 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 (2m) 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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (131) PDF downloads(511) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return