Pairing-friendly elliptic curves with small security loss by Cheon's algorithm

Aya Comuta; Mitsuru Kawazoe; Tetsuya Takahashi

Paper 2006/427

Pairing-friendly elliptic curves with small security loss by Cheon's algorithm

Aya Comuta, Mitsuru Kawazoe, and Tetsuya Takahashi

Abstract

Pairing based cryptography is a new public key cryptographic scheme. An elliptic curve suitable for pairing based cryptography is called a ``pairing-friendly'' elliptic curve. After Mitsunari, Sakai and Kasahara's traitor tracing scheme and Boneh and Boyen's short signature scheme, many protocols based on pairing-related problems such as the $q$-weak Diffie-Hellman problem have been proposed. In Eurocrypt 2006, Cheon proposed a new efficient algorithm to solve pairing-related problems and recently the complexity of Cheon's algorithm has been improved by Kozaki, Kutsuma and Matsuo. Due to these two works, an influence of Cheon's algorithm should be considered when we construct a suitable curves for the use of a protocol based on a pairing-related problem. Among known methods for constructing pairing-friendly elliptic curves, ones using cyclotomic polynomials such as the Brezing-Weng method and the Freeman-Scott-Teske method are affected by Cheon's algorithm. In this paper, we study how to reduce a security loss of a cyclotomic family by Cheon's algorithm. The proposed method constructs many pairing-friendly elliptic curves with small security loss by Cheon's algorithm suitable for protocols based on pairing-related problems.

Note: A new section about how to avoid an attack based on Cheon's algorithm was added (1 May 2007). Title has been changed. Many part of the article have been rewritten. (1 July 2007)

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: elliptic curve pairing based cryptography
Contact author(s): kawazoe @ las osakafu-u ac jp
History: 2007-07-01: last of 6 revisions; 2006-11-19: received; See all versions
Short URL: https://ia.cr/2006/427
License: CC BY

BibTeX

@misc{cryptoeprint:2006/427,
      author = {Aya Comuta and Mitsuru Kawazoe and Tetsuya Takahashi},
      title = {Pairing-friendly elliptic curves with small security loss by Cheon's algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/427},
      year = {2006},
      url = {https://eprint.iacr.org/2006/427}
}