American Institute of Mathematical Sciences

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

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, France

Received  April 2013 Revised  December 2013 Published  January 2014

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.

[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.

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.

[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.

[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 and 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 and 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]

Xiaojun Zheng, Zhongdan Huan, Jun Liu. On the solvability of a semilinear higher-order elliptic problem for the vector field method in image registration. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022068
[8]

Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong. Speeding up regular elliptic curve scalar multiplication without precomputation. Advances in Mathematics of Communications, 2020, 14 (4) : 703-726. doi: 10.3934/amc.2020090
[9]

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
[10]

Yuxia Guo, Ting Liu. Lazer-McKenna conjecture for higher order elliptic problem with critical growth. Discrete and Continuous Dynamical Systems, 2020, 40 (2) : 1159-1189. doi: 10.3934/dcds.2020074
[11]

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
[12]

Lucio Boccardo, Luigi Orsina. The duality method for mean field games systems. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1343-1360. doi: 10.3934/cpaa.2022021
[13]

Yibin Zhang. The Lazer-McKenna conjecture for an anisotropic planar elliptic problem with exponential Neumann data. Communications on Pure and Applied Analysis, 2020, 19 (7) : 3445-3476. doi: 10.3934/cpaa.2020151
[14]

Lisa Hollman, P. J. McKenna. A conjecture on multiple solutions of a nonlinear elliptic boundary value problem: some numerical evidence. Communications on Pure and Applied Analysis, 2011, 10 (2) : 785-802. doi: 10.3934/cpaa.2011.10.785
[15]

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
[16]

Jingzhi Li, Jun Zou. A direct sampling method for inverse scattering using far-field data. Inverse Problems and Imaging, 2013, 7 (3) : 757-775. doi: 10.3934/ipi.2013.7.757
[17]

Frank Trujillo. Uniqueness properties of the KAM curve. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5165-5182. doi: 10.3934/dcds.2021072
[18]

Alex Eskin, Gregory Margulis and Shahar Mozes. On a quantitative version of the Oppenheim conjecture. Electronic Research Announcements, 1995, 1: 124-130.

[19]

Uri Shapira. On a generalization of Littlewood's conjecture. Journal of Modern Dynamics, 2009, 3 (3) : 457-477. doi: 10.3934/jmd.2009.3.457
[20]

Vitali Kapovitch, Anton Petrunin, Wilderich Tuschmann. On the torsion in the center conjecture. Electronic Research Announcements, 2018, 25: 27-35. doi: 10.3934/era.2018.25.004

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (91)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy