Efficient Pairing Computation on Huff Curves

Abstract

Pairings on elliptic curves are currently of great interest due to their applications in a number of cryptographic protocols such as identity-based encryption, group signatures, short signatures, and the tripartite Diffie-Hellman. Miller's algorithm is the most commonly used method of computing Tate pairing. Denominator elimination can improve Miller's algorithm when the embedding degree has the form 2ⁱ3^j. However, if the embedding degree does not have the above form, how can the speed of Miller's algorithm be increased? In this article, the authors modified Miller's algorithm over Huff curves. It is about 20.38% faster than the original algorithm.

Keywords:

• elliptic curves
• Huff curves
• pairing

Acknowledgments

We thank the anonymous reviewers for their careful reading of our manuscript and their valuable comments.

Additional information

Notes on contributors

Haihua Gu

Haihua Gu is a research staff member in the Lab of Cryptology and Computer Security at Shanghai Jiao Tong University and is also a senior engineer in Shanghai Huahong Integrated Circuit Co., Ltd. His research interests include public key cryptography and computational number theory.

Dawu Gu

Dawu Gu is a full professor and a faculty member at Shanghai Jiao Tong University in the Computer Science and Engineering Department. He was awarded a B.S. degree in applied mathematics in 1992 and a Ph.D. degree in cryptography in 1998, both from Xidian University. He is a senior member of China Computer Federation and is also a member of both IACR and ACM. He even won the honor of New Century Excellent Talent from the Ministry of Education of China in 2005. He was a visiting scholar in Tokyo University in 2002 and a senior research fellow in Katholieke Universiteit Leuven (KUL) in 2008. His main research interests focus on applied cryptography and computer security. He has over 90 scientific papers that have appeared in academic journals and conferences.

Wenlu Xie

Wenlu Xie received the Ph.D. degree from Xidian University. He is currently a deputy general manager in Shanghai Huahong Integrated Circuit Co., Ltd.. He is an expert in information security.

Ray C. C. Cheung

Ray C. C. Cheung received the B.Eng.(Hons) and M.Phil. degrees in computer engineering and computer science & engineering from The Chinese University of Hong Kong (CUHK) in 1999 and 2001 respectively, and the DIC and Ph.D. degree in computing from Imperial College London (IC) in 2007. He is currently an Assistant Professor in the Department of Electronic Engineering at City University of Hong Kong, and with Digital Systems Lab. His current research interests include cryptographic hardware designs and design exploration of System-on-Chip (SoC) designs and embedded system designs.