Pairing-Friendly Curves with Minimal Security Loss by Cheon's Algorithm

ETRI Journal

关键词: pairing-friendly elliptic curve;    cyclotomic polynomial;    Cheon's algorithm;   

Others  :  1186096
DOI  :  10.4218/etrij.11.0210.0338

【 摘 要 】

In ICISC 2007, Comuta and others showed that among the methods for constructing pairing-friendly curves, those using cyclotomic polynomials, that is, the Brezing-Weng method and the Freeman-Scott-Teske method, are affected by Cheon's algorithm. This paper proposes a method for searching parameters of pairing-friendly elliptic curves that induces minimal security loss by Cheon's algorithm. We also provide a sample set of parameters of BN-curves, FST-curves, and KSS-curves for pairing-based cryptography.

   

【 参考文献 】

• [1]J.H. Cheon, "Discrete Logarithm Problems with Auxiliary Inputs," J. Cryptology, vol. 23, no. 3, 2010, pp. 457-476.
• [2]D. Sun, Elliptic Curves with the Minimized Security Loss of the Strong Diffie-Hellman Problem, Doctoral Dissertation, Seoul National University, 2007.
• [3]A. Miyaji, M. Nakabayashi, and S. Takano, "New Explicit Conditions of Elliptic Curve Traces for FR-Reduction," IEICE Trans. Fundamentals, E84-A(5), 2001, pp.1234-1243.
• [4]P.S.L.M. Barreto, B. Lynn, and M. Scott, "Constructing Elliptic Curves with Prescribed Embedding Degrees," Proc. SCN, LNCS, vol. 2576, 2002, pp. 263-273.
• [5]F. Brezing, and A. Weng. "Elliptic Curves Suitable for Pairing Based Cryptography," Designs, Codes, Cryptography, vol. 37, no. 1, 2005, pp. 133-141.
• [6]A. Comuta, M. Kawazoe, and T. Takahashi, "Pairing-Friendly Elliptic Curves with Small Security Loss by Cheon’s Algorithm," Proc. ICISC, LNCS, vol. 4817, 2007, pp. 297-308.
• [7]D. Freeman, "Constructing Pairing-Friendly Elliptic Curves with Embedding Degree 10," Proc. ANTS-VII, LNCS, vol. 4076, 2006, pp. 452-465.
• [8]D. Freeman, M. Scott, and E. Teske, "A Taxonomy of Pairing-Friendly Elliptic Curves," J. Cryptology, vol. 23, no. 2, 2010, pp. 224-280.
• [9]H.W. Lenstra Jr., "Factoring Integers with Elliptic Curves," Annals of Mathematics, vol. 126, no. 3, 1987, pp. 649-673.
• [10]A.O.L. Atkin and F. Morain, "Elliptic Curves and Primality Proving," Mathematics of Computation, vol. 61, 1993, pp. 29-68.
• [11]P.S.L.M. Barreto and M. Naehrig, "Pairing-Friendly Elliptic Curves of Prime Order," Proc. SAC, LNCS, vol. 3897, 2005, pp. 319-331.
• [12]E. Kachisa, E. Schaefer, and M. Scott, "Constructing Brezing-Weng Pairing Friendly Elliptic Curves Using Elements in the Cyclotomic Field," Proc. Pairing, LNCS, vol. 5209, 2008, pp. 126-135.