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

perf(bls24-315): faster G2 membership test #123

Merged
merged 3 commits into from
Jan 6, 2022

Conversation

yelhousni
Copy link
Collaborator

@yelhousni yelhousni marked this pull request as draft January 3, 2022 09:10
@yelhousni yelhousni marked this pull request as ready for review January 3, 2022 09:19
@ThomasPiellard
Copy link
Contributor

ThomasPiellard commented Jan 4, 2022

@yelhousni Can you add a specific test for IsInSubGroup ?

Also there is something that bothers me in https://eprint.iacr.org/2021/1130.pdf... The reasoning that I understood from the paper is "psi acts as the multiplication by u on the r torsion of E' (=the twist), so let's just check that psi(Q)=[u]Q".

However, nothing says that there is no other torsion subgroup on which psi acts like this. For example, if we find a such that a | h2, (so E'[Fp^2] contains at least a subgroup of E'[r]) and u is a root of X^2-tX+p [a], then psi acts by multiplication by u on (at least a subgroup of) the a torsion of E'[Fp^2]. So the test might work in some other very specific subgroups (those a torsion subgroups). From the equations, it's not clear that such a situation does not happen. It seems really unlikely because of the second condition (that u has to be a root of X^2-tX+p [a]), but unless proceeding case by case (I checked it does not happen for bls12381 for instance) there is no guarantee of that.

So I am in favour of keeping the solution before the very end of sect 4 for a general implem (that is checking if psi(uQ)+psi(Q)+..=uQ), or keep this implem but we must check for each curves that the situation does not happen.

The delta between the 2 implems is

benchmark                         old ns/op     new ns/op     delta
BenchmarkG2JacIsInSubGroup-12     122793        126198        +2.77%

@yelhousni
Copy link
Collaborator Author

@yelhousni Can you add a specific test for IsInSubGroup ?

added

Also there is something that bothers me in https://eprint.iacr.org/2021/1130.pdf... The reasoning that I understood from the paper is "psi acts as the multiplication by u on the r torsion of E' (=the twist), so let's just check that psi(Q)=[u]Q".

However, nothing says that there is no other torsion subgroup on which psi acts like this. For example, if we find a such that a | h2, (so E'[Fp^2] contains at least a subgroup of E'[r]) and u is a root of X^2-tX+p [a], then psi acts by multiplication by u on (at least a subgroup of) the a torsion of E'[Fp^2]. So the test might work in some other very specific subgroups (those a torsion subgroups). From the equations, it's not clear that such a situation does not happen. It seems really unlikely because of the second condition (that u has to be a root of X^2-tX+p [a]), but unless proceeding case by case (I checked it does not happen for bls12381 for instance) there is no guarantee of that.

So I am in favour of keeping the solution before the very end of sect 4 for a general implem (that is checking if psi(uQ)+psi(Q)+..=uQ), or keep this implem but we must check for each curves that the situation does not happen.

The delta between the 2 implems is

benchmark                         old ns/op     new ns/op     delta
BenchmarkG2JacIsInSubGroup-12     122793        126198        +2.77%

As discussed, I checked that the criterion for this to be valid works for all BLS12 and BLS24 curves (although I agree on the discrepancy of the proof in the eprint). I think we can keep this one.

@yelhousni yelhousni merged commit 22a9546 into develop Jan 6, 2022
@yelhousni yelhousni deleted the perf/BLS24-G2-IsInSubGroup branch January 6, 2022 09:25
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants