Hyperelliptic curves for the vector decomposition problem over fields of even characteristic. (English) Zbl 1352.14016

S. D. Galbraith and E. R. Verheul [Lect. Notes Comput. Sci. 4939, 308–327 (2008; Zbl 1162.94359)] showed that the Vector Decomposition Problem (VDP) on a two-dimensional vector space is as difficult as the computational one-dimensional Diffie-Hellman problem if we choose a distortion eigenvector base for the two-dimensional space. The paper under review concerns a cryptosystem that uses the VDP of hyperelliptic curves of genus two that are the product of two elliptic curves. Yoshida suggested to use the one-dimensional VDP of a family of elliptic curves, which turns out to be not secure enough, and I. Duursma and N. Kiyavash [J. Ramanujan Math. Soc. 20, No. 1, 59–76 (2005; Zbl 1110.14021)] introduced a family of hyperelliptic curves of genus two over odd characteristic to improve the security. N. P. Smart [Lect. Notes Comput. Sci. 1592, 165–175 (1999; Zbl 0938.94010)] showed that the group operation algorithm on the Jacobian of Duursma and Kiyavash’s is twice as slow as that over a field of even characteristic.
The author of the paper under review considers the following family of hyperelliptic curves of genus two over a finite field \(K\) of even characteristic: \[ C : y^2 + y = \frac a {x^3 + 1} \] where \(a = \alpha^2 + \alpha\) for some \(\alpha\in K\), and shows how to generate a distortion eigenvector base consisting of two vectors in the Jacobian variety of \(C\) over some finite field of characteristic \(2\).


14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography
Full Text: DOI


[1] Yoshida, M.; Mitsunari, S.; Fujiwara, T., Vector decomposition problem and the trapdoor inseparable multiplex transmission scheme based problem, Proceedings of the Symposium on Cryptography and Information Security (SCIS ’03)
[2] Galbraith, S. D.; Verheul, E. R., An analysis of the vector decomposition problem, Public Key Cryptography—PKC 2008. Public Key Cryptography—PKC 2008, Lecture Notes in Computer Science, 4939, 308-327, (2008), Berlin, Germany: Springer, Berlin, Germany · Zbl 1162.94359
[3] Yoshida, M.; Fujiwara, T., Toward digital watermarking for cryptographic data, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E94-A, 1, 270-272, (2011)
[4] Yoshida, M.; Fujiwara, T., Watermarking cryptographic data, Proceedings of the 5th International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IH-MSP ’09)
[5] Yoshida, M., Inseparable multiplex transmission using the pairing on elliptic curves and its application to watermarking, Proceedings of 5th Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography, Graduate School of Mathematical Sciences, University of Tokyo
[6] Duursma, I.; Kiyavash, N., The vector decomposition problem for elliptic and hyperelliptic curves, Journal of the Ramanujan Mathematical Society, 20, 1, 59-76, (2005) · Zbl 1110.14021
[7] Smart, N. P., On the performance of hyperelliptic cryptosystems, Advances in Cryptology—EUROCRYPT ’99. Advances in Cryptology—EUROCRYPT ’99, Lecture Notes in Computer Science, 1592, 165-175, (1999), Berlin, Germany: Springer, Berlin, Germany · Zbl 0938.94010
[8] Kwon, S.; Lee, H.-S., Analysis of the strong instance for the vector decomposition problem, Bulletin of the Korean Mathematical Society, 46, 2, 245-253, (2009) · Zbl 1167.42011
[9] Kani, E.; Rosen, M., Idempotent relations and factors of Jacobians, Mathematische Annalen, 284, 2, 307-327, (1989) · Zbl 0652.14011
[10] Lercier, R., Computing isogenies in \(F_{2^n}\), Algorithmic Number Theory. Algorithmic Number Theory, Lecture Notes in Computer Science, 1122, 197-212, (1996), Berlin, Germany: Springer, Berlin, Germany · Zbl 0911.11029
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.