Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Subgroup checks #28

Open
JanBobolz opened this issue Aug 12, 2021 · 9 comments · May be fixed by #29
Open

Subgroup checks #28

JanBobolz opened this issue Aug 12, 2021 · 9 comments · May be fixed by #29
Assignees
Labels
bug Something isn't working

Comments

@JanBobolz
Copy link
Member

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
Copy link
Member

rheitjoh commented Aug 13, 2021

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
Copy link
Member

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
Copy link
Member

rheitjoh commented Aug 13, 2021

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
Copy link
Member Author

JanBobolz commented Aug 16, 2021

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
Copy link
Member

rheitjoh commented Aug 18, 2021

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
Copy link
Member Author

Good plan.

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

@rheitjoh
Copy link
Member

rheitjoh commented Aug 18, 2021

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 rheitjoh linked a pull request Aug 18, 2021 that will close this issue
@rheitjoh
Copy link
Member

There is now a pull request for the mcl addition here herumi/mcl#126.

@rheitjoh rheitjoh linked a pull request Aug 18, 2021 that will close this issue
@JanBobolz
Copy link
Member Author

JanBobolz commented Aug 19, 2021

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.)

@JanBobolz JanBobolz assigned JanBobolz and rheitjoh and unassigned rheitjoh Aug 19, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants