search

scipr-lab / ecfactory

SageMath library for constructing elliptic curves
Other
63 stars 17 forks source link

Subgroup security of the BN curve searching #3

Open weikengchen opened 3 years ago

weikengchen commented 3 years ago

The current implementation in ecfactory to search BN curves did not evaluate the subgroup security, as discussed in https://eprint.iacr.org/2015/247.pdf.

Mainly, pairing might be subject to subgroup attacks. To prevent such attacks, this paper adds additional criteria on selecting good curves, by also requiring the h of the G_2 and G_T to have a large prime factor. This new requirement places a lot of constraints on the choices of parameters.

Note that the parameters of BN254 (which indeed has a historical meaning) in arkworks do not have such properties, since those parameters are sampled before this paper.

Therefore, it is left as a TODO to add BN curve searching algorithms that have subgroup security guarantees.

weikengchen commented 3 years ago

I assign this to myself since one of my ongoing projects needs this.

weikengchen commented 3 years ago

Note that the need for subgroup security depends on the specific application. For example, if one is using the BN curve, and only $G_1$ is being transmitted between malicious parties, then subgroup security for $G_2$ and $G_T$ may be unnecessary.

weikengchen commented 3 years ago

And also, prevention against subgroup attacks can be done via a full membership check (which checks if the element is, not just a point on the curve, but in the subgroup that the pairing is defined over). This could be expensive though.