Heuristics of the Cocks-Pinch method

Previous Article
Sets of zero-difference balanced functions and their applications
AMC Home
This Issue
Next Article

February 2014, 8(1): 103-118. doi: 10.3934/amc.2014.8.103

Heuristics of the Cocks-Pinch method

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

Received April 2013 Revised December 2013 Published January 2014

Abstract
Related Papers

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: Bateman-Horn conjecture, Cocks-Pinch method, Pairing-friendly elliptic curve, pairing-friendly field..

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

Citation: Min Sha. Heuristics of the Cocks-Pinch method. Advances in Mathematics of Communications, 2014, 8 (1) : 103-118. doi: 10.3934/amc.2014.8.103

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). Google Scholar
[2]	P. S. L. M. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in Selected Areas in Cryptography 2005, (2005), 319. doi: 10.1007/11693383_22. Google Scholar
[3]	P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers,, Math. Comp., 16 (1962), 363. doi: 10.1090/S0025-5718-1962-0148632-7. Google Scholar
[4]	D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing,, SIAM J. Comput., 32 (2003), 586. doi: 10.1137/S0097539701398521. Google Scholar
[5]	D. Boneh, E.-J. Goh and K. Nissim, Evaluating 2-DNF formulas on ciphertexts,, in Proc. TCC 2005, (2005), 325. doi: 10.1007/978-3-540-30576-7_18. Google Scholar
[6]	D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar
[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. doi: 10.1016/j.jnt.2010.05.001. Google Scholar
[8]	J. Boxall, Heuristics on pairing-friendly elliptic curves,, J. Math. Cryptol., 6 (2012), 81. Google Scholar
[9]	C. Cocks and R. G. E. Pinch, Identity-based cryptosystems based on the Weil pairing,, manuscript, (2001). Google Scholar
[10]	J. Esmonde and M. R. Murty, Problems in Algebraic Number Theory,, Springer-Verlag, (2004). doi: 10.1007/978-3-642-87939-5. Google Scholar
[11]	S. Finch, G. Martin and P. Sebah, Roots of unity and nullity modulo $n$,, Proc. Amer. Math. Soc., 138 (2010), 2729. doi: 10.1090/S0002-9939-10-10341-4. Google Scholar
[12]	D. Freeman, M. Scott and E. Teske, A taxonomy of pairing-friendly elliptic curves,, J. Cryptology, 23 (2010), 224. doi: 10.1007/s00145-009-9048-z. Google Scholar
[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. doi: 10.2307/2153546. Google Scholar
[14]	S. Galbraith, Pairings,, in Advances in Elliptic Curve Cryptography* (eds. I. Blake*, (2005), 183. doi: 10.1017/CBO9780511546570.011. Google Scholar
[15]	G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers,, Oxford University Press, (1979). Google Scholar
[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, (2012), 43. Google Scholar
[17]	A. Joux, A one round protocol for tripartite Diffie-Hellman,, in Algorithmic Number Theory Symposium 2000, (2000), 385. doi: 10.1007/10722028_23. Google Scholar
[18]	N. Koblitz and A. J. Menezes, Pairing-based cryptography at high security levels,, in Cryptography and Coding, (2005), 13. doi: 10.1007/11586821_2. Google Scholar
[19]	J. Korevaar and H. Te Riele, Average prime-pair counting formula,, Math. Comp., 79 (2010), 1209. doi: 10.1090/S0025-5718-09-02312-6. Google Scholar
[20]	F. Luca and I. E. Shparlinski, Elliptic curves with low embedding degree,, J. Cryptology, 19 (2006), 553. doi: 10.1007/s00145-006-0544-0. Google Scholar
[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. doi: 10.1109/18.259647. Google Scholar
[22]	V. Miller, The Weil pairing, and its efficient calculation,, J. Cryptology, 17 (2004), 235. doi: 10.1007/s00145-004-0315-8. Google Scholar
[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. Google Scholar
[24]	W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers,, Springer-Verlag, (2004). Google Scholar
[25]	, PARI/GP, version 2.5.3,, Bordeaux, (2012). Google Scholar
[26]	K. Paterson, Cryptography from pairings,, in Advances in Elliptic Curve Cryptography* (eds. I. Blake*, (2005), 215. doi: 10.1017/CBO9780511546570.012. Google Scholar
[27]	R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing,, in Symp. Crypt. Inf. Secur. 2000, (2000). Google Scholar
[28]	A. V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem,, Math. Comp., 80 (2011), 501. doi: 10.1090/S0025-5718-2010-02373-7. Google Scholar
[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. doi: 10.1090/S0025-5718-2011-02543-3. Google Scholar
[30]	E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems,, J. Cryptology, 17 (2004), 277. doi: 10.1007/s00145-004-0313-x. Google Scholar

show all references

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). Google Scholar
[2]	P. S. L. M. Barreto and M. Naehrig, Pairing-friendly elliptic curves of prime order,, in Selected Areas in Cryptography 2005, (2005), 319. doi: 10.1007/11693383_22. Google Scholar
[3]	P. T. Bateman and R. A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers,, Math. Comp., 16 (1962), 363. doi: 10.1090/S0025-5718-1962-0148632-7. Google Scholar
[4]	D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing,, SIAM J. Comput., 32 (2003), 586. doi: 10.1137/S0097539701398521. Google Scholar
[5]	D. Boneh, E.-J. Goh and K. Nissim, Evaluating 2-DNF formulas on ciphertexts,, in Proc. TCC 2005, (2005), 325. doi: 10.1007/978-3-540-30576-7_18. Google Scholar
[6]	D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing,, J. Cryptology, 17 (2004), 297. doi: 10.1007/s00145-004-0314-9. Google Scholar
[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. doi: 10.1016/j.jnt.2010.05.001. Google Scholar
[8]	J. Boxall, Heuristics on pairing-friendly elliptic curves,, J. Math. Cryptol., 6 (2012), 81. Google Scholar
[9]	C. Cocks and R. G. E. Pinch, Identity-based cryptosystems based on the Weil pairing,, manuscript, (2001). Google Scholar
[10]	J. Esmonde and M. R. Murty, Problems in Algebraic Number Theory,, Springer-Verlag, (2004). doi: 10.1007/978-3-642-87939-5. Google Scholar
[11]	S. Finch, G. Martin and P. Sebah, Roots of unity and nullity modulo $n$,, Proc. Amer. Math. Soc., 138 (2010), 2729. doi: 10.1090/S0002-9939-10-10341-4. Google Scholar
[12]	D. Freeman, M. Scott and E. Teske, A taxonomy of pairing-friendly elliptic curves,, J. Cryptology, 23 (2010), 224. doi: 10.1007/s00145-009-9048-z. Google Scholar
[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. doi: 10.2307/2153546. Google Scholar
[14]	S. Galbraith, Pairings,, in Advances in Elliptic Curve Cryptography* (eds. I. Blake*, (2005), 183. doi: 10.1017/CBO9780511546570.011. Google Scholar
[15]	G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers,, Oxford University Press, (1979). Google Scholar
[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, (2012), 43. Google Scholar
[17]	A. Joux, A one round protocol for tripartite Diffie-Hellman,, in Algorithmic Number Theory Symposium 2000, (2000), 385. doi: 10.1007/10722028_23. Google Scholar
[18]	N. Koblitz and A. J. Menezes, Pairing-based cryptography at high security levels,, in Cryptography and Coding, (2005), 13. doi: 10.1007/11586821_2. Google Scholar
[19]	J. Korevaar and H. Te Riele, Average prime-pair counting formula,, Math. Comp., 79 (2010), 1209. doi: 10.1090/S0025-5718-09-02312-6. Google Scholar
[20]	F. Luca and I. E. Shparlinski, Elliptic curves with low embedding degree,, J. Cryptology, 19 (2006), 553. doi: 10.1007/s00145-006-0544-0. Google Scholar
[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. doi: 10.1109/18.259647. Google Scholar
[22]	V. Miller, The Weil pairing, and its efficient calculation,, J. Cryptology, 17 (2004), 235. doi: 10.1007/s00145-004-0315-8. Google Scholar
[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. Google Scholar
[24]	W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers,, Springer-Verlag, (2004). Google Scholar
[25]	, PARI/GP, version 2.5.3,, Bordeaux, (2012). Google Scholar
[26]	K. Paterson, Cryptography from pairings,, in Advances in Elliptic Curve Cryptography* (eds. I. Blake*, (2005), 215. doi: 10.1017/CBO9780511546570.012. Google Scholar
[27]	R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing,, in Symp. Crypt. Inf. Secur. 2000, (2000). Google Scholar
[28]	A. V. Sutherland, Computing Hilbert class polynomials with the Chinese remainder theorem,, Math. Comp., 80 (2011), 501. doi: 10.1090/S0025-5718-2010-02373-7. Google Scholar
[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. doi: 10.1090/S0025-5718-2011-02543-3. Google Scholar
[30]	E. Verheul, Evidence that XTR is more secure than supersingular elliptic curve cryptosystems,, J. Cryptology, 17 (2004), 277. doi: 10.1007/s00145-004-0313-x. Google Scholar

[1]	Indranil Biswas, Georg Schumacher, Lin Weng. Deligne pairing and determinant bundle. Electronic Research Announcements, 2011, 18: 91-96. doi: 10.3934/era.2011.18.91
[2]	Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[3]	Feng Yang, Kok Lay Teo, Ryan Loxton, Volker Rehbock, Bin Li, Changjun Yu, Leslie Jennings. VISUAL MISER: An efficient user-friendly visual program for solving optimal control problems. Journal of Industrial & Management Optimization, 2016, 12 (2) : 781-810. doi: 10.3934/jimo.2016.12.781
[4]	Huaiyu Jian, Hongjie Ju, Wei Sun. Traveling fronts of curve flow with external force field. Communications on Pure & Applied Analysis, 2010, 9 (4) : 975-986. doi: 10.3934/cpaa.2010.9.975
[5]	Koray Karabina, Berkant Ustaoglu. Invalid-curve attacks on (hyper)elliptic curve cryptosystems. Advances in Mathematics of Communications, 2010, 4 (3) : 307-321. doi: 10.3934/amc.2010.4.307
[6]	Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169
[7]	Roberto Avanzi, Nicolas Thériault. A filtering method for the hyperelliptic curve index calculus and its analysis. Advances in Mathematics of Communications, 2010, 4 (2) : 189-213. doi: 10.3934/amc.2010.4.189
[8]	Steven D. Galbraith, Ping Wang, Fangguo Zhang. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. Advances in Mathematics of Communications, 2017, 11 (3) : 453-469. doi: 10.3934/amc.2017038
[9]	Lisa Hollman, P. J. McKenna. A conjecture on multiple solutions of a nonlinear elliptic boundary value problem: some numerical evidence. Communications on Pure & Applied Analysis, 2011, 10 (2) : 785-802. doi: 10.3934/cpaa.2011.10.785
[10]	Jingzhi Li, Jun Zou. A direct sampling method for inverse scattering using far-field data. Inverse Problems & Imaging, 2013, 7 (3) : 757-775. doi: 10.3934/ipi.2013.7.757
[11]	Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028
[12]	Robert L. Devaney, Daniel M. Look. Buried Sierpinski curve Julia sets. Discrete & Continuous Dynamical Systems - A, 2005, 13 (4) : 1035-1046. doi: 10.3934/dcds.2005.13.1035
[13]	Claudianor O. Alves, Giovany M. Figueiredo, Marcelo F. Furtado. Multiplicity of solutions for elliptic systems via local Mountain Pass method. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1745-1758. doi: 10.3934/cpaa.2009.8.1745
[14]	Bastian Gebauer, Nuutti Hyvönen. Factorization method and inclusions of mixed type in an inverse elliptic boundary value problem. Inverse Problems & Imaging, 2008, 2 (3) : 355-372. doi: 10.3934/ipi.2008.2.355
[15]	Luis J. Roman, Marcus Sarkis. Stochastic Galerkin method for elliptic spdes: A white noise approach. Discrete & Continuous Dynamical Systems - B, 2006, 6 (4) : 941-955. doi: 10.3934/dcdsb.2006.6.941
[16]	Eric Chung, Yalchin Efendiev, Ke Shi, Shuai Ye. A multiscale model reduction method for nonlinear monotone elliptic equations in heterogeneous media. Networks & Heterogeneous Media, 2017, 12 (4) : 619-642. doi: 10.3934/nhm.2017025
[17]	Yanqin Fang, De Tang. Method of sub-super solutions for fractional elliptic equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3153-3165. doi: 10.3934/dcdsb.2017212
[18]	Tina Hartley, Thomas Wanner. A semi-implicit spectral method for stochastic nonlocal phase-field models. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 399-429. doi: 10.3934/dcds.2009.25.399
[19]	Jie Wang, Xiaoqiang Wang. New asymptotic analysis method for phase field models in moving boundary problem with surface tension. Discrete & Continuous Dynamical Systems - B, 2015, 20 (9) : 3185-3213. doi: 10.3934/dcdsb.2015.20.3185
[20]	Yi Shi, Kai Bao, Xiao-Ping Wang. 3D adaptive finite element method for a phase field model for the moving contact line problems. Inverse Problems & Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences