Side channel silent karatsuba / mpn_addmul_2 karatsuba
Marco Bodrato
bodrato at mail.dm.unipi.it
Tue Dec 8 17:21:11 UTC 2020
Ciao,
since someone is asking about secure powm... I reply to an old message
:-)
Il 2018-12-13 07:05 nisse at lysator.liu.se ha scritto:
> 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.
At a first glance, I'd say around a dozen limbs higher than the non-sec
thresholds.
You can try, by replacing the two files mpn/generic/toom2{2_mul,_sqr}.c
with the attached ones. Then make check and make tune, to see what
happens.
Of course the two functions should not replace the current ones, but
that was the easiest way to test the new files :-)
>> 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
The attached code for squaring, uses -1.
I.e. it is strictly equivalent to the non-sec version. I only replaced
the strategy to obtain the absolute value of the difference, and carry
propagation. It also has exactly the same memory usage.
> mpn_cnd_neg in in terms of mpn_lshift and mpn_cnd_sub_n, one could also
I'm recycling your code here, in mpn_sec_absub.
> 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.
That's true only for the last recursion level, when you fall into
_basecase...
I know that toom2_sqr enters the game later wrt toom22_mul. But in the
_sec_ area, to compute the square of a number we use sqr_basecase if the
number is small enough, and mul_basecase for larger integers... so that
a Karatsuba function may be more important for squaring than for the
product...
Ĝis,
m
-------------- next part --------------
A non-text attachment was scrubbed...
Name: toom2_sqr.c
Type: text/x-c
Size: 4088 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20201208/1968ed6b/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: toom22_mul.c
Type: text/x-c
Size: 3831 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20201208/1968ed6b/attachment-0001.bin>
More information about the gmp-devel
mailing list