Co-factor clearing and subgroup membership testing on pairing-friendly curves

Youssef El Housni; Aurore Guillevic; Thomas Piellard

Paper 2022/352

Co-factor clearing and subgroup membership testing on pairing-friendly curves

Youssef El Housni

, ConsensSys, gnark, LIX, CNRS, École Polytechnique, Institut Polytechnique de Paris, French Institute for Research in Computer Science and Automation

Aurore Guillevic

, Inria Nancy - Grand-Est research centre, Aarhus University

Thomas Piellard, ConsenSys, gnark

Abstract

An important cryptographic operation on elliptic curves is hashing to a point on the curve. When the curve is not of prime order, the point is multiplied by the cofactor so that the result has a prime order. This is important to avoid small subgroup attacks for example. A second important operation, in the composite-order case, is testing whether a point belongs to the subgroup of prime order. A pairing is a bilinear map e : G1 × G2 → GT where G1 and G2 are distinct subgroups of prime order r of an elliptic curve, and GT is a multiplicative subgroup of the same prime order r of a finite field extension. Pairing-friendly curves are rarely of prime order. We investigate cofactor clearing and subgroup membership testing on these composite-order curves. First, we generalize a result on faster cofactor clearing for BLS curves to other pairing-friendly families of a polynomial form from the taxonomy of Freeman, Scott and Teske. Second, we investigate subgroup membership testing for G1 and G2. We fix a proof argument for the G2 case that appeared in a preprint by Scott in late 2021 and has recently been implemented in different cryptographic libraries. We then generalize the result to both G1 and G2 and apply it to different pairing-friendly families of curves. This gives a simple and shared framework to prove membership tests for both cryptographic subgroups.

Note: https://hal.inria.fr/hal-03608264

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. AFRICACRYPT 2022
DOI: 10.1007/978-3-031-17433-9_22
Keywords: elliptic curves subgroup membership cofactor clearing
Contact author(s): youssef elhousni @ consensys net
aurore guillevic @ inria fr
thomas piellard @ consensys net
History: 2023-01-27: last of 3 revisions; 2022-03-18: received; See all versions
Short URL: https://ia.cr/2022/352
License: CC BY

BibTeX

@misc{cryptoeprint:2022/352,
      author = {Youssef El Housni and Aurore Guillevic and Thomas Piellard},
      title = {Co-factor clearing and subgroup membership testing on pairing-friendly curves},
      howpublished = {Cryptology ePrint Archive, Paper 2022/352},
      year = {2022},
      doi = {10.1007/978-3-031-17433-9_22},
      note = {\url{https://eprint.iacr.org/2022/352}},
      url = {https://eprint.iacr.org/2022/352}
}