search

cfrg / draft-irtf-cfrg-hash-to-curve

Hashing to Elliptic Curves
Other
79 stars 27 forks source link

revisiting sqrt_ratio: optimized routines, code/testing fixes, and small remaining comments #317

Closed kwantam closed 3 years ago

kwantam commented 3 years ago

(cc @chris-wood @daira @armfazh)

This PR does the following:

The generic sqrt_ratio routine has a constant S that was previously defined as a primitive element of the field. This certainly works, but there are two issues with it:

  1. (minor) S != Z needs an extra "cleanup" multiplication and a corresponding constant in the sswu routine
  2. (major) identifying a primitive element of a field is computationally expensive: Sage does it by factoring q - 1, and I'm not aware of another method. This is infeasible for BLS12-381 G2, for example.

Fortunately, we don't actually need S to be a primitive element of F. Defining q - 1 = 2^l * o with o odd, what we actually need is that S^o generates the multiplicative subgroup of order 2^l. This is satisfied by any non-square in F: if S is non-square, then S^o is also non-square (because o is odd), and is also an element of the order-2^l subgroup by construction. Moreover, any element of this subgroup that is a non-square in F must generate the subgroup, and likewise any generator must be non-square in F. Since we require the constant Z to be non-square already, and since the generic sqrt_ratio routine already computes S^o, setting S = Z appears to suffice.

But @daira I'd appreciate if you'd double check me on the above!

kwantam commented 3 years ago

I did a bit more pseudocode cleanup, both for sqrt_ratio and for the constant-time Tonelli-Shanks impl in a different appendix (and I back-ported the changed code to the codebase, and tested it).

The goal was to remove expressions from CMOVs, just to emphasize that every expression needs to be evaluated in a straight-line impl.

daira commented 3 years ago

The argument for why it's sufficient to choose S = Z looks correct.