Finding More Non-Supersingular Elliptic Curves for Pairing-Based Cryptosystems

Authors: Pu Duan, Shi Cui, Choong Wah Chan

Abstract:

Finding suitable non-supersingular elliptic curves for pairing-based cryptosystems becomes an important issue for the modern public-key cryptography after the proposition of id-based encryption scheme and short signature scheme. In previous work different algorithms have been proposed for finding such elliptic curves when embedding degree k ∈ {3, 4, 6} and cofactor h ∈ {1, 2, 3, 4, 5}. In this paper a new method is presented to find more non-supersingular elliptic curves for pairing-based cryptosystems with general embedding degree k and large values of cofactor h. In addition, some effective parameters of these non-supersingular elliptic curves are provided in this paper.

Keywords: Family of group order, kth root of unity, non-supersingular elliptic curves polynomial field.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335422

References:

[1] D. Boneh and M. Franklin, "Identity based encryption from the Weil pairing," SIAM J. of Computing, vol. 32, no.3, pp. 586-615, 2003.
[2] D. Boneh, B. Lynn and H. Shacham, "Short signatures from the Weil pairing," Advances in Cryptology - Asiacrypt-2001, volume 2248 of Lecture Notes in Computer Science, page 514-532, Springer-Verlag, 2002.
[3] M. Scott and P. S. L. M. Barreto, "Generating more MNT elliptic curves," Cryptology ePrint Archive, Report 2004/058, 2004.
[4] A. Miyaji, M. Nakabayashi, and S. Takano, "New explicit conditions of elliptic curve traces for FR-reduction," IEICE Transactions on Fundamentals, E84-A(5):1234-1243, 2001.
[5] F. Brezing and A. Weng, "Elliptic curves suitable for pairing based cryptography," Cryptology ePrint Archive, Report 2003/143, 2003.
[6] D. Page, N. P. Smart and F. Vercauteren, "A comparison of MNT curves and supersingular curves," Cryptology ePrint Archive, Report 2004/165, 2004.
[7] Steven D. Galbraith, J. Mckee and P. Valenca, "Ordinary abelian varieties having small embedding degree," Cryptology ePrint Archive, Report 2004/365, 2004.
[8] I. F. Blake, G. Seroussi and N. P. Smart, Elliptic Curves in Cryptography,Volume 265 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1999.
[9] N. P. Smart., The Algorithmic Resolution of Diophantine Equations, Landon Mathematical Society Student Text 41, Cambridge University Press, 1998.
[10] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publisher, 1993
[11] IEEE Computer Society, New York, USA, IEEE Standard Specifications for Public Key Cryptography- IEEE Std 1363-2000, 2000.
[12] A. Menezes, T. Okamoto, and S. Vanstone, "Reducing elliptic curve logarithms to logarithms in a finite field," Proc.22nd Annual ACM Symposium on the Theory of Computing, pp. 80-89, 1991.
[13] A. M. Odlyzko, Discrete logarithms: the past and the future. Design, Codes and Cryptography, 19:129-145, 2000.
[14] R. Balasubramanian and N. Koblitz, "The improbability that an elliptic curve has subexponential discrete log problem under the Menezes-Okamoto-Vanstone algorithm", Journal of Cryptology, vol. 11, pp. 141- 145, 1998.