Advanced Search
Article Contents
Article Contents

Heuristics of the Cocks-Pinch method

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 14H52, 11T71; Secondary: 11G20.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    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.


    D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, SIAM J. Comput., 32 (2003), 586-615.doi: 10.1137/S0097539701398521.


    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.


    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.


    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.


    J. Boxall, Heuristics on pairing-friendly elliptic curves, J. Math. Cryptol., 6 (2012), 81-104.


    C. Cocks and R. G. E. Pinch, Identity-based cryptosystems based on the Weil pairing, manuscript, 2001.


    J. Esmonde and M. R. Murty, Problems in Algebraic Number Theory, Springer-Verlag, 2004.doi: 10.1007/978-3-642-87939-5.


    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.


    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.


    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.


    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.


    G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, Oxford, 1979.


    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.


    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.


    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.


    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.


    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.


    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.


    V. Miller, The Weil pairing, and its efficient calculation, J. Cryptology, 17 (2004) 235-261.doi: 10.1007/s00145-004-0315-8.


    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.


    W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag, 2004.


    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.


    R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing, in Symp. Crypt. Inf. Secur. 2000, Okinawa, Japan, 2000.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(107) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint