Albin Ahlbäck <albin.ahlb...@gmail.com> writes:
> Have you looked at https://eprint.iacr.org/2020/972.pdf, where the
> author seems to suggests an even faster algorithm? Or at least it was
> faster under heavy optimization under the assumption of what inputs
> the algorithm recieved.
No, I wasn't ware of that. I've now had a quick look (algorithm 2, page
6, seems to be the main part).
It's pretty close to standard extended binary, and like gmp's
mpn_sec_invert, a single innerloop iteration is one conditional
subtraction of the smaller number from the larger and right shift of a
single bit.
The trick (which is new to me) is to reduce k-1 bits by taking the least
significant k-1 bits *and* most significant approx k+1 bits of both
numbers, and then the innerloop operates only on these smaller nubmers,
ignoring the middle bits. The iteration steps are collected into a
transformation matrix.
And then have an outerloop applying that transformation matrix to the
complete numbers and the cofactors.
I haven't read the correctness argument, but there seems to be some
subtle issues: At line 3,
n = max(len(a), len(b), 2k)
makes n data dependant, which in turn makes side-channel silent
extraction of top bits, floor (a / 2^{n-k-1}) a bit tricky, since the
way these bits straddles a boundaries becomes data dependent.
And the need for the conditional negations (lines 18 -- 21) seems
related to rounding errors from ignored middle bits.
Regards,
/Niels
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
