[viff-devel] Optimizing preprocessing

[Janus Dam Nielsen]

Hi Marcel,

I am not opposed to your suggestion. However I would like to point out  
that in VIFF you compute on shares and not field elements!. Computing  
directly on the field elements is hacking the abstractions of VIFF.
Computation on field elements or rather the representation of a Share  
can be useful as an optimization, however this optimization should be  
confined within applications or runtimes, and should not progress over  
interface boundaries as I fear you are suggesting.


On 08/10/2009, at 20.11, Marcel Keller wrote:

> Dear friends of VIFF,
>
> I have a proprosal to optimize preprocessing in VIFF, which I would  
> like to put up for discussion.
>
> Notation:
> - D(x): a Deferred object whose callback function will be called  
> with x
> - S(x): same for a Share object
> - F: a FieldElement object
> - [x, ...]: a Python list
> - (x, ...): a Python tuple
>
> Current situation:
> The two generate_triples() functions in the active runtimes return
> n, D([(S(F), S(F), S(F)), ...]),
> where n denotes the length of the list. Runtime.preprocess() puts  
> one D(S(F), S(F), S(F)) per program counter in the preprocessing  
> pool and uses util.deep_wait() to return a Deferred whose callback  
> is called when all field elements are available.
>
> The get_triple() functions return
> D(S(F), S(F), S(F)),
> either taken from the preprocessing pool, or by calling  
> generate_triples() and adding an extra callback to extract the first  
> triple.
>
> My proposal:
> The generate_triples() functions return
> [D([F, F, F]), ...],
> and Runtime.preprocess() puts one [F, F, F] per program counter in  
> the preprocessing pool. There is no need for deep_wait, we can just  
> use gatherResults on the Deferreds return by the generator  
> functions. The generator functions can use gatherResults to get  
> D([F, F, F]) from [S(F), S(F), S(F)].
>
> The get_triple() functions return
> [F, F, F], True              if there is a triple in the pool, and
> [S(F), S(F), S(F)], False    otherwise.
> For the multiplication in BasicActiveRuntime it doesn't make a  
> difference whether FieldElements or Shares are returned. Future  
> applications which require Shares can wrap the FieldElements in  
> Shares if the Boolean is True.
>
> Benchmarks:
> - 10000 multiplications in parallel with active security using PRSS
>  - 4% faster preprocessing
>  - 5% faster online operation
>  - 50 MB less memory used
> - 10 AES blocks in parallel using masked exponentiation with active  
> security using PRSS
>  - 10% faster preprocessing
>  - 10% faster online operation
>  - 140 MB less memory used
>
> Further considerations:
> - I don't see any problem for replacing FieldElement with anything  
> that does not contain Deferreds in any form.
> - Probably, it would also be possible to leave the generator  
> functions as they are and use something similar to deep_wait().  
> However, I consider it as an overhead.
> - One could also always wrap the FieldElements in Shares, but this  
> would again be an overhead.
>
> Best regards,
> Marcel
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

____________________________________________________

Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD.

T +45 42 22 93 56
E janus.nielsen at alexandra.dk
W alexandra.dk
____________________________________________________

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20091009/aed58ff5/attachment-0001.htm>