\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Heuristics of the Cocks-Pinch method

Abstract / Introduction 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.

    Citation:

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

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

  • 加载中
SHARE

Article Metrics

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

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return