Re: [viff-devel] Speed of ElGamal encryption
160 bit -- Janus Den 21/09/2008 kl. 17.02 skrev Claudio Orlandi: Could everyone specify the size of the field and the size of the secret keys used? Otherwise it's quite hard to understand the performance reported. Regards, Claudio On Sun, Sep 21, 2008 at 4:59 PM, Adam Langley <[EMAIL PROTECTED]> wrote: On Sun, Sep 21, 2008 at 3:23 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: Calling a ElGamal function in NaCl would be very cool and probably a bit faster since you wont have to do all the tuple packing and unpacking that you do in the Python version. NaCl has support for a primitive called a 'box'. The boxing function takes these inputs: * The message * An nonce * The recipient's public key * The sender's private key Note that requiring the sender's private key makes this different from most public key encryption functions. The unboxing function, symmetrically, requires the sender's public key. (This boxing function may be viewed as a encrypt+sign operation.) If this fits your model, then NaCl already contains everything you need. In this case, the underlying primitive is not ElGamel, but Diffie-Hellman. The two keys are combined with ECDH and the nonce (which both sides must know, but need not be secret) diversifies the long-term shared key into a per-message key. Based on timings for the x86-64 ECDH implementation, which I wrote, 4*10^6 operations should take about 880 seconds for a short message. AGL -- Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk -- Claudio Orlandi PhD student, Department of Computer Science, Turing-223 Aarhus Universitet, Denmark http://www.daimi.au.dk/~orlandi ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] What to benchmark
Hi everybody, I have just talked with Thomas about how to benchmark VIFF and what we should try measuring. We found it difficult to come up with good answers, so now we ask here. We talked about the goals of benchmarking: * Determine bottle-necks. It wont do us any good if the carefull optimizations done by the CACE project cannot be seen because the time is spent in other parts of the code. So this suggests that we need to determine: - Amount of time spent on local computations: how much of the time is spent on book-keeping and how much on actual computations? - Amount of time spent waiting on the network. Since we have everything centralized in the Twisted event loop, we might be able to simply hook into that and make it measure its idle time. * Track performance over time in order to find performance regressions. For this we talked about making a system which does a nightly benchmark run (if there has been a new commit) and then stores the result in a database. From that we can then generate nice HTML pages with graphs and numbers. I have already made a script which uses SSH to start any number of playes here on DAIMI, and I've used it to test up to 25 players (it took 15 ms on average for a 32-bit passively secure multiplication, and 19 ms for an actively secure one). It should be fairly easy to extend this to run nightly and make graphs from the results. Please come with your other good ideas -- or let us know why the above are bad ideas! :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Citat Martin Geisler <[EMAIL PROTECTED]>: > I have already made a script which uses SSH to start any number of > playes here on DAIMI, and I've used it to test up to 25 players (it > took 15 ms on average for a 32-bit passively secure multiplication, > and 19 ms for an actively secure one). It should be fairly easy to > extend this to run nightly and make graphs from the results. > > Please come with your other good ideas -- or let us know why the above > are bad ideas! :-) Well I can't say there's anything wrong with the ideas about benchmarking, although I don't know the best way to separate the bookkeeping and the actual computations. With regards to the quoted bit above, if we're going to do such a thing, we should ask definitely ask the staff here at DAIMI for permission. Not only could they put a quick stop to it if they got annoyed, but it also seems likely that something's going to happen to some of the machines involved which will mess with our results. We should really have a (perhaps smaller) set of stable and otherwise unused machines for this sort of testing. Can we do this entirely outside DAIMI? ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Hi Martin, I think that looking at the two bottlenecks as suggested is a very good idea and should have the highest priority. We don't know nearly enough about how much time Python in general and Twisted in particular is stealing from us. In principle, we could be in a situation where it is hopeless to get the performance we should be able to get unless we ditch Python and implement Twisted ourselves in C++. Note that I am not saying we are in that situation, in fact I don't think so - but I am saying that it is important to find out ASAP! regards, Ivan Quoting Martin Geisler <[EMAIL PROTECTED]>: > Hi everybody, > > I have just talked with Thomas about how to benchmark VIFF and what we > should try measuring. We found it difficult to come up with good > answers, so now we ask here. > > We talked about the goals of benchmarking: > > * Determine bottle-necks. It wont do us any good if the carefull > optimizations done by the CACE project cannot be seen because the > time is spent in other parts of the code. So this suggests that we > need to determine: > > - Amount of time spent on local computations: how much of the time > is spent on book-keeping and how much on actual computations? > > - Amount of time spent waiting on the network. Since we have > everything centralized in the Twisted event loop, we might be able > to simply hook into that and make it measure its idle time. > > * Track performance over time in order to find performance > regressions. > > For this we talked about making a system which does a nightly > benchmark run (if there has been a new commit) and then stores the > result in a database. From that we can then generate nice HTML pages > with graphs and numbers. > > I have already made a script which uses SSH to start any number of > playes here on DAIMI, and I've used it to test up to 25 players (it > took 15 ms on average for a 32-bit passively secure multiplication, > and 19 ms for an actively secure one). It should be fairly easy to > extend this to run nightly and make graphs from the results. > > Please come with your other good ideas -- or let us know why the above > are bad ideas! :-) > > -- > Martin Geisler > > VIFF (Virtual Ideal Functionality Framework) brings easy and efficient > SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. > ___ > viff-devel mailing list (http://viff.dk/) > viff-devel@viff.dk > http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk > ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Martin Geisler <[EMAIL PROTECTED]> writes: > Hi everybody, > > I have just talked with Thomas about how to benchmark VIFF and what we > should try measuring. We found it difficult to come up with good > answers, so now we ask here. > > We talked about the goals of benchmarking: > > * Determine bottle-necks. It wont do us any good if the carefull > optimizations done by the CACE project cannot be seen because the > time is spent in other parts of the code. So this suggests that we > need to determine: > > - Amount of time spent on local computations: how much of the time > is spent on book-keeping and how much on actual computations? > > - Amount of time spent waiting on the network. Since we have > everything centralized in the Twisted event loop, we might be able > to simply hook into that and make it measure its idle time. Another bottle-neck to examine: - Memory usage. It would be very nice(tm) if VIFF could be told to limit its memory usage to, say, 16 MiB. This should make it automatically delay creating new Deferreds until the memory usage drops. I don't know yet if this is feasible without us constantly shooting ourselves in the feet because of the danger of deadlocks... A more safe way to do this is to simply structure the programs in such a way that they only have a limited number of outstanding Deferreds. Tomas and I have already talked a bit about this: http://article.gmane.org/gmane.comp.cryptography.viff.devel/256 -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Actually upon reading my own email I realized that I forgot to mention the added bonus of having real internet communication going on if we have machines outside DAIMI involved in the testing. Martin, could you buy a dozen computers and set them up in various locations around the world? :) ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Mikkel Krøigård <[EMAIL PROTECTED]> writes: > Actually upon reading my own email I realized that I forgot to > mention the added bonus of having real internet communication going > on if we have machines outside DAIMI involved in the testing. > > Martin, could you buy a dozen computers and set them up in various > locations around the world? :) Sure, why not... No, wait a minute -- you didn't say "please"! Sorry, no computer for you today! -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Mikkel Krøigård <[EMAIL PROTECTED]> writes: > Citat Martin Geisler <[EMAIL PROTECTED]>: > >> I have already made a script which uses SSH to start any number >> of playes here on DAIMI, and I've used it to test up to 25 >> players (it took 15 ms on average for a 32-bit passively secure >> multiplication, and 19 ms for an actively secure one). It should >> be fairly easy to extend this to run nightly and make graphs from >> the results. >> >> Please come with your other good ideas -- or let us know why the >> above are bad ideas! :-) > > Well I can't say there's anything wrong with the ideas about > benchmarking, although I don't know the best way to separate the > bookkeeping and the actual computations. > > With regards to the quoted bit above, if we're going to do such a > thing, we should ask definitely ask the staff here at DAIMI for > permission. Not only could they put a quick stop to it if they got > annoyed, but it also seems likely that something's going to happen > to some of the machines involved which will mess with our results. Very good point! And I just forgot to write that I have asked them and am waiting for a reply. I suggested that we do our runs at night on the shared machines, there are 25-27 of them that we can use if we get permission. > We should really have a (perhaps smaller) set of stable and > otherwise unused machines for this sort of testing. Can we do this > entirely outside DAIMI? It would be nicer if we could have our own machines -- for if we want to do the network emulation stuff talked about in Issue66[1] then we need root access. I think having 10 old-ish machines would be perfect for us. [1]: http://tracker.viff.dk/issue66 -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk