Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> I am looking into doing karatsuba multiplication at evaluation points 0,
> +1, and infinity.  We usually evaluate in -1 instead of +1.

It will be very interesting to see what thresholds we get with that.

> The main advantage of evaluating in +1 is that it makes it more straight-
> forward to avoid side channel leakage.  (Currently, we completely avoid
> all o(n^2) multiplication algorithms in side channel sensitive contexts.)

I don't think we should rule out using -1. It needs side-channel silent
conditional negation, but that's not so hard. sec_invert.c implements
mpn_cnd_neg in in terms of mpn_lshift and mpn_cnd_sub_n, one could also
do it as a single pass xor:ing a mask + propagating carry.

What's most efficient is not at all clear to me: negation costs O(n),
but so does handling of the extra top bits one get with evaluation in
+1.

> My first project is to write some mpn_addmul_2 assembly functions for
> machines with slow 64b x 64b -> 128b hardware.  E.g., all ARM designed
> Arm64 cores have a throughput of 1/7 per cycle for that operation, while
> plain operations has a throughput of 2 to 3 per cycle.  If things pan out,
> we might be able to reach a addmul accumulation performance of 5.25 cycles
> per limb.  Very far from great, but less awful than 7.

I did a sketch for x86 a while ago, but didn't complete it. See
https://gmplib.org/list-archives/gmp-devel/2017-June/004651.html. This
appears to use evaluation in -1.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.