*_is_valid() functions produce false negative for not normalized points

[laurent-girod]

While working on Petrelic, I noticed that some tests were no longer passing after updating Relic. We identified two likely bugs, one related to the *_is_valid() functions, and one related to the g2_map() function.

This issue is the bug related to the *_is_valid() functions.

After some checks, I noticed that some checks like these one

g1_get_gen(a);
g1_get_gen(b);

g1_neg(b);
g1_add(c, a, b);

res = g1_is_valid(c); // res = 0

indicated that c was an invalid point.

Wouter got the idea to normalize the point with g1_norm(c) before checking its validity, upon which g1_is_valid(c) returned that c was valid.

[dfaranha]

Thanks! Scalar multiplication algorithms expect points in affine coordinates, and are the likely culprit. They should normalize them as well.

I plan to soon refactor the *_is_valid() code with just binary multiplication, as the current approach makes me nervous, so there will be an opportunity to fix this.

[dfaranha]

There is a semantic mismatch between the PC interface and the underlying modules. Functions g*_is_valid() are supposed to check if elements have the right order (and thus reject any elements of small order), while ep_is_valid() basically only checks if the point lies in the curve. That is something that also needs fixing.

[dfaranha]

Hi again,

I have recently updated the implementation, and I think it is more consistent now. Now g*_is_valid check that elements have a prime order r = |G1| = |G2| = |GT|, so identity elements are rejected (as this is commonly the case with cryptographic protocols).

The underlying modules now uses _on_curve() for checking point validity. Sometimes one coincides with the other (BN curves with prime order), but it is not necessarily the case.

Please let me know if this abstraction makes more sense for what you are doing. :)

[laurent-girod]

Hello Diego,

Sorry for the late reply!
Thank you for your work! That new interface makes sense.

Regards,
Laurent