Subgroup checks

[JanBobolz]

When instantiating a GroupElementImpl (say, from Representation), I'm unclear whether our current implementation (1) checks if the given coordinates are on curve, and (2) if it's in the right subgroup.

Do we know? Can we find out?

[rheitjoh]

Edit: Missed the fact that this was written for Mclwrap. I am referring to Math in my comments.

Taking a look at PairingSourceGroupImpl, the method restoreElement is used to restore elliptic curve group elements. That method just recovers the coordinates via the Field and then calls getElement. getElement pretty much just uses the constructor. So no curve check or subgroup check there. PairingSourceGroupImpl already provides a isMember method that checks for subgroup membership, but that is unused according to IntelliJ. Also a isOnCurve method but that is only used in the isMember method. The Secp256k1 implementation also has no checks.

[rheitjoh]

The easiest way to insert a check seems to be in the constructor of PairingSourceGroupElement since all the other G1 and G2 group element constructors refer to that constructor.

Secp256k1 has cofactor one so a curve check should be enough. We could think about integrating the curve check into WeierstrassCurve instead of PairingSourceGroupImpl (then Secp256k1 can use it too). Subgroup membership check probably cannot (and should not) be integrated into WeierstrassCurve since the latter is missing the cofactor.

[rheitjoh]

Regarding mcl: This page says that we can enable subgroup checks via that method. Furthermore, it affects setStr() for G1/G2, which I interpret as meaning that once verification is enabled, setStr automatically does that verification. And setStr is pretty much the only way we instantiate elements.

I don't see that method in the Java FFI though, so we might need to call isValidOrder ourselves.

[JanBobolz]

Configuring setStr() to check curve equation and order would work.

Any idea how to do that?

(isValidOrder doesn't seem to be available for G2 or GT, but, uselessly, is there for G1?!)

[rheitjoh]

My first idea would be to port verifyOrderG1 and verifyOrderG2 to the FFI and then test whether they actually do the verification stuff as we think. The G1 thing is interesting indeed since, according to Naehrig's dissertation, G1 is just the whole curve so no subgroup check should be necessary.

[JanBobolz]

Good plan.

Maybe the existence of verifyOrderG1 is a good sign that the verifyOrderX methods also check the on-curve property.

[rheitjoh]

Even without verifyOrderG2, setStr rejects points not on the curve. As far as I can tell enabling verifyOrderG2 just means it will additionally also check the subgroup membership. Thats what the load method here indicates to me. So that should suffice for G1 and G2.

[rheitjoh]

There is now a pull request for the mcl addition here https://github.com/herumi/mcl/pull/126.

[JanBobolz]

Todo: also need subgroup check for GT. @JanBobolz . Maybe just use their pow() to check. Try whether a random element in the large group has the pow(order) = 1 property (then pow() optimizes and we can't go that route.)