Some New Optimal Pairings

The Ate pairing can be computed efficiently on ordinary elliptic curves with small value of the trace of Frobenius t. The Ate pairing generalizes the Ate pairing, and can possibly shorten the Miller loop to be as small as r 1/φ(k) on some special pairing-friendly curves with large value of Frobenius t. However, not all pairing-friendly curves have this property. In this paper, we generalize the Ate_i pairing further. By our method, we can shorten the the Miller loop to be nearly r 1/φ(k) on some pairing-friendly curves, while the Ate pairing can not reach.

I. Introduction

In 2000, Sakai et al.[1] proposed an ID-based key agreement protocol using a bilinear pairing, and pairing-based cryptosystems are becoming one of the most attractive research areas in elliptic curve cryptography. Famous examples are Identity Based Encryption [2] and Short Signature [3]. These protocols require so-called pairing-friendly elliptic curves. These curves have special properties which most randomly generated curves will not have. In recent years, The interest is to explore various methods of constructing pairing-friendly elliptic curves with prescribed embedding degrees. And ideally the method are made to be more efficient and more secure.