Side channel silent karatsuba / mpn_addmul_2 karatsuba

[Marco Bodrato]

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>