Heuristics of the Cocks-Pinch method

Min Sha

doi:10.3934/amc.2014.8.103

Article Contents

2014, Volume 8, Issue 1: 103-118. Doi: 10.3934/amc.2014.8.103

This issue Previous Article Sets of zero-difference balanced functions and their applications Next Article

Heuristics of the Cocks-Pinch method

Min Sha^1,

1.
Institut de Mathématiques de Bordeaux, Université Bordeaux 1, 351, Cours de la Libération, 33405 Talence Cedex

Received: March 31, 2013

Revised: November 30, 2013

Published: January 2014

Abstract Related Papers Cited by

Abstract

We heuristically analyze the Cocks-Pinch method by using the Bateman-Horn conjecture. Especially, we present the first known heuristic which suggests that any efficient construction of pairing-friendly elliptic curves can efficiently generate such curves over pairing-friendly fields, naturally including the Cocks-Pinch method. Finally, some numerical evidence is given.

Keywords:

Mathematics Subject Classification: Primary: 14H52, 11T71; Secondary: 11G20.

Citation:

Related Papers

Cited by

References

[1]	R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography, CRC Press, 2005.
[2]	P. S. L. M. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order, in Selected Areas in Cryptography 2005, Springer-Verlag, 2006, 319-331.doi: 10.1007/11693383_22.
[3]	P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp., 16 (1962), 363-367.doi: 10.1090/S0025-5718-1962-0148632-7.
[4]	D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, SIAM J. Comput., 32 (2003), 586-615.doi: 10.1137/S0097539701398521.
[5]	D. Boneh, E.-J. Goh and K. Nissim, Evaluating 2-DNF formulas on ciphertexts, in Proc. TCC 2005, Springer-Verlag, 2005, 325-341.doi: 10.1007/978-3-540-30576-7_18.
[6]	D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing, J. Cryptology, 17 (2004), 297-319.doi: 10.1007/s00145-004-0314-9.
[7]	D. Boneh, K. Rubin and A. Silverberg, Finding composite order ordinary elliptic curves using the Cocks-Pinch method, J. Number Theory, 131 (2011), 832-841.doi: 10.1016/j.jnt.2010.05.001.
[8]	J. Boxall, Heuristics on pairing-friendly elliptic curves, J. Math. Cryptol., 6 (2012), 81-104.
[9]	C. Cocks and R. G. E. Pinch, Identity-based cryptosystems based on the Weil pairing, manuscript, 2001.
[10]	J. Esmonde and M. R. Murty, Problems in Algebraic Number Theory, Springer-Verlag, 2004.doi: 10.1007/978-3-642-87939-5.
[11]	S. Finch, G. Martin and P. Sebah, Roots of unity and nullity modulo $n$, Proc. Amer. Math. Soc., 138 (2010), 2729-2743.doi: 10.1090/S0002-9939-10-10341-4.
[12]	D. Freeman, M. Scott and E. Teske, A taxonomy of pairing-friendly elliptic curves, J. Cryptology, 23 (2010), 224-280.doi: 10.1007/s00145-009-9048-z.
[13]	G. Frey and H. Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp., 62 (1994), 865-874.doi: 10.2307/2153546.
[14]	S. Galbraith, Pairings, in Advances in Elliptic Curve Cryptography (eds. I. Blake, G. Seroussi and N. Smart), Cambridge University Press, 2005, 183-213.doi: 10.1017/CBO9780511546570.011.
[15]	G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, Oxford, 1979.
[16]	T. Hayashi, T. Shimoyama, N. Shinohara and T. Takagi, Breaking pairing-based cryptosystems using $\eta_T$ pairing over $GF(3^{97})$, in Asiacrypt 2012, Springer-Verlag, 2012, 43-60.
[17]	A. Joux, A one round protocol for tripartite Diffie-Hellman, in Algorithmic Number Theory Symposium 2000, Springer-Verlag, 2000, 385-393.doi: 10.1007/10722028_23.
[18]	N. Koblitz and A. J. Menezes, Pairing-based cryptography at high security levels, in Cryptography and Coding, Springer-Verlag, 2005, 13-36.doi: 10.1007/11586821_2.
[19]	J. Korevaar and H. Te Riele, Average prime-pair counting formula, Math. Comp., 79 (2010), 1209-1229.doi: 10.1090/S0025-5718-09-02312-6.
[20]	F. Luca and I. E. Shparlinski, Elliptic curves with low embedding degree, J. Cryptology, 19 (2006), 553-562.doi: 10.1007/s00145-006-0544-0.
[21]	A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. Inform. Theory, 39 (1993), 1639-1646.doi: 10.1109/18.259647.
[22]	V. Miller, The Weil pairing, and its efficient calculation, J. Cryptology, 17 (2004) 235-261.doi: 10.1007/s00145-004-0315-8.
[23]	A. Miyaji, M. Nakabayashi and S. Takano, New explicit conditions of elliptic curve traces for FR-reduction, IEICE Trans. Fundam., E84-A (2001), 1234-1243.
[24]	W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, 2004.
[25]	PARI/GP, version 2.5.3,, Bordeaux, (2012).
[26]	K. Paterson, Cryptography from pairings, in Advances in Elliptic Curve Cryptography (eds. I. Blake, G. Seroussi and N. Smart), Cambridge University Press, 2005, 215-251.doi: 10.1017/CBO9780511546570.012.
[27]	R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing, in Symp. Crypt. Inf. Secur. 2000, Okinawa, Japan, 2000.
[28]	A. V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem, Math. Comp., 80 (2011), 501-538.doi: 10.1090/S0025-5718-2010-02373-7.
[29]	J. J. Urroz, F. Luca and I. E. Shparlinski, On the number of isogeny classes and pairing-friendly elliptic curves and statistics for MNT curves, Math. Comp., 81 (2012), 1093-1110.doi: 10.1090/S0025-5718-2011-02543-3.
[30]	E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems, J. Cryptology, 17 (2004), 277-296.doi: 10.1007/s00145-004-0313-x.