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

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.

Authors:

• Pu Duan
• Shi Cui
• Choong Wah Chan

Keywords:

• Family of group order
• kth root of unity
• non-supersingular elliptic curves polynomial field.

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.