Faster halvings in genus 2. (English) Zbl 1256.94044
Avanzi, Roberto Maria (ed.) et al., Selected areas in cryptography. 15th international workshop, SAC 2008, Sackville, New Brunswick, Canada, August 14–15. Revised selected papers. Berlin: Springer (ISBN 978-3-642-04158-7/pbk). Lecture Notes in Computer Science 5381, 1-17 (2009).
Summary: We study divisor class halving for hyperelliptic curves of genus 2 over binary fields. We present explicit halving formulas for the most interesting curves (from a cryptographic perspective), as well as all other curves whose group order is not divisible by 4. Each type of curve is characterized by the degree and factorization form of the polynomial \(h(x)\) in the curve equation. For each of these curves, we provide explicit halving formulæ for all possible divisor classes, and not only the most frequent case where the degree of the first polynomial in the Mumford representation is 2. In the optimal performance case, where \(h(x) = x\), we also improve on the state-of-the-art and when \(h(x)\) is irreducible of degree 2, we achieve significant savings over both the doubling as well as the previously fastest halving formulas.
For the entire collection see [Zbl 1173.94003].
For the entire collection see [Zbl 1173.94003].
MSC:
| 94A60 | Cryptography |
| 11G20 | Curves over finite and local fields |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
References:
| [1] | Avanzi, R.M., Cohen, H., Doche, C., Frey, G., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, Boca Raton (2006) · Zbl 1082.94001 |
| [2] | Avanzi, R.M.: A Note on Square Roots in Binary Fields (preprint) |
| [3] | Birkner, P.: Efficient Divisor Class Halving on Genus Two Curves. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 317–326. Springer, Heidelberg (2007) · Zbl 1161.94386 · doi:10.1007/978-3-540-74462-7_22 |
| [4] | Fong, K., Hankerson, D., López, J., Menezes, A.: Field Inversion and Point Halving Revisited. IEE Trans. Computers 53(8), 1047–1059 (2004) · doi:10.1109/TC.2004.43 |
| [5] | Gaudry, P.: Index calculus for abelian varieties and the elliptic curve discrete logarithm problem (2004) (preprint), http://eprint.iacr.org/2004/073/ · Zbl 1177.94148 |
| [6] | Gaudry, P., Hess, F., Smart, N.P.: Constructive and destructive facets of Weil descent on elliptic curves. Journal of Cryptology 15(1), 19–46 (2002) · Zbl 0996.94036 · doi:10.1007/s00145-001-0011-x |
| [7] | Kitamura, I., Katagi, M., Takagi, T.: A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two (preprint) (2005), http://eprint.iacr.org/2005/255/ · Zbl 1127.94347 |
| [8] | Kitamura, I., Katagi, M., Takagi, T.: A complete divisor class halving algorithm for hyperelliptic curve cryptosystems of genus two. In: Boyd, C., González Nieto, J.M. (eds.) ACISP 2005. LNCS, vol. 3574, pp. 146–157. Springer, Heidelberg (2005) · Zbl 1127.94347 · doi:10.1007/11506157_13 |
| [9] | Knudsen, E.W.: Elliptic scalar multiplication using point halving. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 135–149. Springer, Heidelberg (1999) · Zbl 0977.94035 · doi:10.1007/978-3-540-48000-6_12 |
| [10] | Lange, T.: Formulae for Arithmetic on Genus 2 Hyperelliptic Curves. Applicable Algebra in Engineering. Communication and Computing 15(5), 295–328 (2005) · Zbl 1068.14065 |
| [11] | Lange, T., Stevens, M.: Efficient doubling on genus two curves over binary fields. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 170–181. Springer, Heidelberg (2004) · Zbl 1117.94011 · doi:10.1007/978-3-540-30564-4_12 |
| [12] | Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Cambridge University Press, Cambridge (1997) · Zbl 1139.11053 |
| [13] | Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF( p) and its cryptographic significance. IEEE Trans. Inform. Theory IT-24, 106–110 (1978) · Zbl 0375.68023 · doi:10.1109/TIT.1978.1055817 |
| [14] | Schroeppel, R.: Elliptic curves: Twice as fast! In: Crypto 2000 Rump Session (2000) |
| [15] | Thériault, N.: Weil Descent for Artin-Schreier Curves (preprint) (2003), http://homepage.mac.com/ntheriau · Zbl 1081.14037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
