Cryptology ePrint Archive: Report 2015/247

Subgroup security in pairing-based cryptography

Paulo S. L. M. Barreto and Craig Costello and Rafael Misoczki and Michael Naehrig and Geovandro C. C. F. Pereira and Gustavo Zanon

Abstract: Pairings are typically implemented using ordinary pairing-friendly elliptic curves. The two input groups of the pairing function are groups of elliptic curve points, while the target group lies in the multiplicative group of a large finite field. At moderate levels of security, at least two of the three pairing groups are necessarily proper subgroups of a much larger composite-order group, which makes pairing implementations potentially susceptible to small-subgroup attacks.

To minimize the chances of such attacks, or the effort required to thwart them, we put forward a property for ordinary pairing-friendly curves called subgroup security. We point out that existing curves in the literature and in publicly available pairing libraries fail to achieve this notion, and propose a list of replacement curves that do offer subgroup security. These curves were chosen to drop into existing libraries with minimal code change, and to sustain state-of-the-art performance numbers. In fact, there are scenarios in which the replacement curves could facilitate faster implementations of protocols because they can remove the need for expensive group exponentiations that test subgroup membership.

Category / Keywords: Pairing-based cryptography, elliptic-curve cryptography, pairing-friendly curves, subgroup membership, small-subgroup attacks

Original Publication (with minor differences): LATINCRYPT2015

Date: received 16 Mar 2015, last revised 1 Jun 2015

Contact author: craigco at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20150601:175919 (All versions of this report)

Short URL: ia.cr/2015/247

Discussion forum: Show discussion | Start new discussion