Abstract
We generalize Boneh-Rubin-Silverberg method [3] to construct ordinary elliptic curves with embedding degree one, which provides composite order groups for cryptographic protocols based on such bilinear groups. Our construction is more efficient and almost optimal for parameter setting. In addition, we analyze the non-degeneracy of symmetric pairing derived from the reduced Tate pairing on such curves, and prove that its non-degeneracy only relies on the existence of distortion maps. Based on this observation, we propose a new method for computing the reduced Tate pairing on ordinary curves with embedding degree one. Compared with previous methods, our formulae provide faster computation of the reduced Tate pairing on such curves, which also implies that the reduced Tate pairing may be preferred to use as symmetric pairing instead of the modified Weil pairing in certain cases.
Chapter PDF
Similar content being viewed by others
References
Atkin, A.O.L., Morain, F.: Elliptic Curves and Primality Proving. Math. Comput. 61, 29–68 (1993)
Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF Formulas on Ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005)
Boneh, D., Rubin, K., Silverberg, A.: Finding Composite Order Ordinary Elliptic Curves Using the Cocks-Pinch Method. J. Number Theor. 131(5), 832–841 (2011)
Boneh, D., Sahai, A., Waters, B.: Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 573–592. Springer, Heidelberg (2006)
Boyen, X., Waters, B.: Compact Group Signatures without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427–444. Springer, Heidelberg (2006)
Charles, D.: On the Existence of Distortion Maps on Ordinary Elliptic Curves. Cryptology ePrint Archive Report 2006/128, http://eprint.iacr.org/2006/128/
Frey, G., Rück, H.: A Remark Concerning m-divisibility and The Discrete Logarithm in The Divisor Class Group of Curves. Math. Comp. 62, 865–874 (1994)
Freeman, D., Scott, M., Teske, E.: A Taxonomy of Pairing-friendly Elliptic Curves. J. Cryptol. 23, 224–280 (2010)
Galbraith, S.D.: Pairings-Advanced in Elliptic Curve Cryptography. In: Blake, I.F., Seroussi, G., Smart, N.P. (eds.) Cambridge Univ. Press, Cambridge (2005)
Groth, J., Sahai, A.: Efficient Non-interactive Proof Systems for Bilinear Groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)
Hu, Z., Xu, M., Zhou, Z.H.: A Generalization of Verheul’s Theorem for Some Ordinary Curves. In: Lai, X., Yung, M., Lin, D. (eds.) Inscrypt 2010. LNCS, vol. 6584, pp. 105–114. Springer, Heidelberg (2011)
Ionica, S., Joux, A.: Another Approach to Pairing Computation in Edwards Coordinates. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 400–413. Springer, Heidelberg (2008)
Ionica, S.: Algorithmique des couplages et cryptographie. PhD thesis of the Versailles Saint-Quentin-en-Yvelines University (2010)
Keller, S.: The RSA Validation System (November 9, 2004)
Koblitz, N., Menezes, A.J.: Pairing-based Cryptography at High Security Levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005)
Koblitz N.: A Security Weakness in Composite Order Pairing Based Protocols with Embedding Degree k > 2. Cryptology ePrint Archive Report 2010/227, http://eprint.iacr.org/2010/227/
Lewko, A.: Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 318–335. Springer, Heidelberg (2012)
Menezes, A.J., Okamoto, T., Vanstone, S.A.: Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field. IEEE Trans. Inf. Theory. 39(5), 1639–1646 (1993)
Miller, V.S.: The Weil Pairing, and Its Efficient Calculation. J. Cryptol. 17, 235–261 (2004)
Moody, D.: The Diffie-Hellman Problem and Generalization of Verheuls Theorem. Des. Codes Cryptogr. 52, 381–390 (2009)
The RSA Challenge Numbers, http://www.rsa.com/rsalabs/node.asp?id=2093
Seo, J.H.: On the (Im)possibility of Projecting Property in Prime-Order Setting. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 61–79. Springer, Heidelberg (2012)
Shacham, H., Waters, B.: Efficient Ring Signatures without Random Oracles. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 166–180. Springer, Heidelberg (2007)
Silverman, J.: The Arithmetic of Elliptic Curves. Springer, New York (1986)
Stark, H.M.: Class Numbers of Complex Quadratic Fields. In: Kuyk, W. (ed.) Modular Functions of One Variable I. Lecture Notes in Math., vol. 320, pp. 153–174. Springer, New York (1973)
Sutherland, A.: Computing Hilbert class polynomials with the Chinese Remainder Theorem. Math. Comput. 80(273), 501–538 (2011)
Vélu, J.: Isogénies entre courbes elliptiques. C.R. Acad. Sc. Paris, Série A 273, 238–241 (1971)
Verheul, R.: Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems. J. Cryptol. 17, 277–296 (2004)
Wu, H., Feng, R.: Efficient Self-pairing on Ordinary Elliptic Curves. In: Chan, T.-H.H., Lau, L.C., Trevisan, L. (eds.) TAMC 2013. LNCS, vol. 7876, pp. 282–293. Springer, Heidelberg (2013)
Zhang, X.S., Lin, D.D.: Efficient Pairing Computation on Ordinary Elliptic Curves of Embedding Degree 1 and 2. In: Chen, L. (ed.) IMACC 2011. LNCS, vol. 7089, pp. 309–326. Springer, Heidelberg (2011)
Zhao, C.A., Zhang, F.G., Xie, D.Q.: Fast Computation of Self-pairings. IEEE Trans. Inf. Theory 58(5), 3266–3272 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Hu, Z., Wang, L., Xu, M., Zhang, G. (2013). Generation and Tate Pairing Computation of Ordinary Elliptic Curves with Embedding Degree One. In: Qing, S., Zhou, J., Liu, D. (eds) Information and Communications Security. ICICS 2013. Lecture Notes in Computer Science, vol 8233. Springer, Cham. https://doi.org/10.1007/978-3-319-02726-5_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-02726-5_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02725-8
Online ISBN: 978-3-319-02726-5
eBook Packages: Computer ScienceComputer Science (R0)