Good evening,

I've been doing some more performance measurements. This time I replaced
the shamir.share and shamir.recombine functions with fake versions (see
revision f7d1f7cd3dda). The replacements do a zero-degree sharing:

[(1, 17), (2, 17), (3, 17)]

17

They skip the normal machinery and do:

  share     = lambda s, t, n: [(s.field(i+1), s) for i in range(n)]
  recombine = lambda s, x=0: s[0][1]

Enabling both fakes gives these timing results when doing 10000
multiplications on camel{10..12} on DAIMI (thyra02 is down so I used the
slightly slower camel machines):

    +-------------------+----------+----------+------+
    | Field size (bits) | Real (s) | Fake (s) | Diff |
    +-------------------+----------+----------+------+
    |         50        |   14.3   |   11.5   | 20%  |
    +-------------------+----------+----------+------+
    |        100        |   14.4   |   11.4   | 21%  |
    +-------------------+----------+----------+------+
    |        200        |   14.6   |   11.7   | 20%  |
    +-------------------+----------+----------+------+
    |        400        |   15.0   |   11.9   | 21%  |
    +-------------------+----------+----------+------+
    |        800        |   15.8   |   12.3   | 22%  |
    +-------------------+----------+----------+------+
    |       1600        |   18.4   |   14.0   | 24%  |
    +-------------------+----------+----------+------+

I think that is quite a saving!

Feel free to suggest other functions that I should replace with a fake
version. Ah, the PRSS functions would of course be an easy target... I
guess I'll take a look at them tomorrow.

Yes, that is a good idea -- I'll try to rip out the Shamir sharing and
recombination next. Then we can gradually strip things down to the bare
"machinery" behind it all.

Hi folks,

Very interesting! I think Martin is right that there is something lost  
in general machinery, but I don't think this means that none of this  
machinery can be removed.
There are bigger lumps of computation that could be done with one call  
to a faster module. Examples:

1) Lagrange interpolation, i.e., reconstructing secret from a set of shares
2) the linear recombination that is done at the end of a multiplication.
3) Secret sharing, i.e., given secret, choose random polynomial and  
evaluate in given points
4) PRSS, which also involves some symmetric crypto.

I guess it would be easy to simply skip 2) in the current code,  
simulating that we have a superfast for linear combination, and see  
what difference that makes..

regards, Ivan

Quoting Martin Geisler <mg@daimi.au.dk>:

> Hi everybody,
>
> I've done some tests where I replaced the normal FieldElement class
> with a new class named FakeFieldElement (rev 464008ada9c2). This class
> fakes all computations by always returning 1.
>
> Timing 10000 multiplications using the real and the fake field
> elements give these results between three machines on the DAIMI LAN:
>
>   +-------------------+----------+----------+------+
>   | Field size (bits) | Real (s) | Fake (s) | Diff |
>   +-------------------+----------+----------+------+
>   |         50        |   14.1   |   13.5   |  4%  |
>   +-------------------+----------+----------+------+
>   |        100        |   14.3   |   13.2   |  8%  |
>   +-------------------+----------+----------+------+
>   |        200        |   14.5   |   13.3   |  8%  |
>   +-------------------+----------+----------+------+
>   |        400        |   15.0   |   13.1   | 13%  |
>   +-------------------+----------+----------+------+
>   |        800        |   16.2   |   13.3   | 18%  |
>   +-------------------+----------+----------+------+
>   |       1600        |   21.4   |   13.5   | 37%  |
>   +-------------------+----------+----------+------+
>
> The results show that there is something to improve for large numbers,
> but for field of size 50-100 bit the difference is quite small. It
> would be interesting to see how the numbers compare when Sigurd
> finishes the patch for using GMPY:
>
>   http://tracker.viff.dk/issue10
>
> It is currently waiting for a reply on my review comments.
>
> These results are from a gigabit LAN, so the time spend on network
> communication is as low as it can possible get. I guess that means
> that the rest of the time is lost in the overall machinery :-(
>
> --
> Martin Geisler
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel@viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>

Hi everybody,

I've done some tests where I replaced the normal FieldElement class
with a new class named FakeFieldElement (rev 464008ada9c2). This class
fakes all computations by always returning 1.

Timing 10000 multiplications using the real and the fake field
elements give these results between three machines on the DAIMI LAN:

  +-------------------+----------+----------+------+
  | Field size (bits) | Real (s) | Fake (s) | Diff |
  +-------------------+----------+----------+------+
  |         50        |   14.1   |   13.5   |  4%  |
  +-------------------+----------+----------+------+
  |        100        |   14.3   |   13.2   |  8%  |
  +-------------------+----------+----------+------+
  |        200        |   14.5   |   13.3   |  8%  |
  +-------------------+----------+----------+------+
  |        400        |   15.0   |   13.1   | 13%  |
  +-------------------+----------+----------+------+
  |        800        |   16.2   |   13.3   | 18%  |
  +-------------------+----------+----------+------+
  |       1600        |   21.4   |   13.5   | 37%  |
  +-------------------+----------+----------+------+

The results show that there is something to improve for large numbers,
but for field of size 50-100 bit the difference is quite small. It
would be interesting to see how the numbers compare when Sigurd
finishes the patch for using GMPY:

  http://tracker.viff.dk/issue10

It is currently waiting for a reply on my review comments.

These results are from a gigabit LAN, so the time spend on network
communication is as low as it can possible get. I guess that means
that the rest of the time is lost in the overall machinery :-(

We want to do tests where all local computations are replaced by dummy
implementations. An example would be the multiplications of field
elements done in viff.field.

Having timing results from such a dummy implementation would give us a
baseline. Comparing this to the normal timings should tell us how much
we can hope to save by using faster routines from the NaCl library.