http://blog.gmane.org/gmane.comp.cryptography.viff.devel hourly 1 1901-01-01T00:00+00:00 http://gmane.org/img/gmane-25t.png http://gmane.org http://comments.gmane.org/gmane.comp.cryptography.viff.devel/522 Martin Geisler 2008-11-30T17:30:47 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/518 As requested, here is the command to install the dependencies on Gentoo: $ emerge -av twisted gmpy Make sure to have the crypt use flag enabled, otherwise SSL might not be available. Marcel Keller 2008-11-17T12:54:55 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/517 Hi everybody, I have been looking at writing a specification of "VIFF as a VM". The idea is to consider the API offered by VIFF as a target for a compiler (not yet written). This is done for the CACE project[1] where there will be a meeting on December 3rd. So far I've made a rough sketch of such a specification, and I would like your comments. I've attached a PDF with the latest version (I'm sorry that this file got so big, but someone managed to make a 1.4 MiB file with the CACE logo, and this is included in the PDF.). Currently I have written a bit about this and that, but the document need some heavy editing. You can find my work here: http://www.bitbucket.org/mg/viff-spec/overview/ http://www.bitbucket.org/mg/viff-spec/get/tip.zip and you are very welcome to send me any corrections. [1]: CACE homepage: http://www.cace-project.eu/ Martin Geisler 2008-11-17T10:22:25 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/507 Hi everybody, I would just like to draw attention to a recent ePrint report on VIFF: http://eprint.iacr.org/2008/415 It gives a formal description of the asynchronous protocol used against active adversaries in VIFF and some benchmark results. Martin Geisler 2008-10-27T08:43:41 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/506 Hi everybody, We have something to celebrate -- we've got 1001 changesets in the main VIFF repository: http://hg.viff.dk/viff/ If we take a look at the number of lines changed per month we can see how the intensity has gone up and down over the last year and a half: % hg churn -f '%Y-%m' -s 2007-06 4802 ************************************ 2007-07 2409 ****************** 2007-08 2806 ********************* 2007-09 2407 ****************** 2007-10 7341 ******************************************************** 2007-11 1390 ********** 2007-12 4292 ******************************** 2008-01 126 2008-02 2322 ***************** 2008-03 5579 ****************************************** 2008-04 5340 **************************************** 2008-05 1425 ********** 2008-06 56 2008-07 1425 ********** 2008-08 606 **** 2008-09 2351 ***************** 2008-10 3292 ************************* Here I would say that the drop in January corresponds to me writing my progress report, and the drop in June is me going to Switzerland. We can also look at the activity per hour: % hg churn -f '%H' -s 00 1294 ******* 01 245 * 02 0 03 0 04 0 05 0 06 2 07 40 08 981 ***** 09 7447 ********************************************* 10 2568 *************** 11 4034 ************************ 12 889 ***** 13 1865 *********** 14 2182 ************* 15 3396 ******************** 16 3263 ******************* 17 1071 ****** 18 280 * 19 842 ***** 20 1326 ******** 21 10067 ************************************************************* 22 3476 ********************* 23 2701 **************** We somehow managed to change two lines at six o'clock in the morning! Or at least before seven... wow :-) Martin Geisler 2008-10-15T07:12:46 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/501 Hello everybody, It's my great pleasure to announce the immediate release of the latest and greatest version of VIFF: 0.7.1. Let the release party begin! When you're done partying, then please download it here: Tar/GZ: http://viff.dk/release/viff-0.7.1.tar.gz Tar/BZ2: http://viff.dk/release/viff-0.7.1.tar.bz2 Zip: http://viff.dk/release/viff-0.7.1.zip Exe: http://viff.dk/release/viff-0.7.1.win32.exe This is bugfix release -- thanks to Sebastiaan and Tomas for finding a nasty bug in the passive multiplication protocol. The NEWS file says: Version 0.7.1, released on 2008-10-09 ------------------------------------- A major bug was fixed in the passive multiplication protocol in the case where 2t + 1 != n. Unit tests were updated for Python 2.6. * Players would do inconsistent recombination of shares in the passive multiplication protocol (Runtime.mul). This resulted in wrong answers being computed when 2t + 1 != n. * Fixed unit tests on Python 2.6. The Bracha broadcast let the players send data to themselves by mistake, and for some reason this was not detected in earlier Python versions. * Profiling information (from a run with --profile) is dumped in player-X.pstats and player-X.prof files for later analysis. * Issue 57: Get rid of Runtime._shamir_share. The method was folded into Runtime.mul. * Issue 69: The installation was simplified by including the ConfigObj library in the VIFF source. A system-wide installation of ConfigObj (if any) will be ignored. Martin Geisler 2008-10-09T11:33:01 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/500 Martin Geisler 2008-10-08T21:11:57 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/480 Martin Geisler 2008-10-02T21:55:06 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/479 Hi, I figured that I would try to profile something more complicated than multiplications, so here is a plot for 10 Toft07 comparisons. The operations are sorted by their start time along the y-axis, and the x-axis shows their duration, as normal. You can see data for addition, multiplication, preprocessing and online time. Martin Geisler 2008-10-01T12:35:01 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/473 Hoogh, S.J.A. de 2008-10-01T07:19:55 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/471 Hi again, I just found an old fun graph I once made. It shows the flow of values in a single multiplication in VIFF. I have never used it for anything, but I think it is a nice way to show which parts of the protocol that can be run in parallel. digraph G { graph [rankdir=LR]; subgraph cluster_P1 { a; share_a[label="share"]; a1; b1; subgraph cluster_mul1 { "*1"[label="*"]; share1[label="share"]; recombine1[label="recombine"]; } output1; } subgraph cluster_P2 { b; share_b[label="share"]; a2; b2; subgraph cluster_mul2 { "*2"[label="*"]; share2[label="share"]; recombine2[label="recombine"]; } output2; } subgraph cluster_P3 { a3; b3; subgraph cluster_mul3 { "*3"[label="*"]; share3[label="share"]; recombine3[label="recombine"]; } output3; } a -> share_a; share_a -> a1; share_a -> a2; share_a -> a3; b -> share_b; share_b -> b1; share_b -> b2; share_b -> b3; a1 -> "*1"; b1 -> "*1"; a2 -> "*2"; b2 -> "*2"; a3 -> "*3"; b3 -> "*3"; "*1" -> share1; "*2" -> share2; "*3" -> share3; share1 -> recombine1; share1 -> recombine2; share1 -> recombine3; share2 -> recombine1; share2 -> recombine2; share2 -> recombine3; share3 -> recombine1; share3 -> recombine2; share3 -> recombine3; recombine1 -> output1; recombine2 -> output2; recombine3 -> output3; } Martin Geisler 2008-09-26T20:39:02 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/470 Hi guys, I found a new tool today which can generate nice call graphs: http://code.google.com/p/jrfonseca/wiki/Gprof2Dot Using that I made a graph for 5000 multiplications which show that a total of 130033 field elements were created in the execution. __mul__ created 45011, __add__ created 40002, and shamir.share created 25002. I don't know who created the missing 20000 elements. I guess such graphs can help us look for stupid call chains that we can shorten, but for now I just wanted to put it out here. Martin Geisler 2008-09-26T20:20:16 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/467 Martin Geisler 2008-09-25T22:27:27 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/449 Hi everybody, I have done some testing and come up with some strange numbers. I measured the time each individual multiplication takes by storing a timestamp when the multiplication is scheduled, and another when it finishes. I've attached two plots, one for 1000 multiplications and one for 4000. Each plot has the multiplication-number on the x-axis and the time for that multiplication on the y-axis. In both plots we see that the first multiplication takes very long, it is sort of waiting on the other multiplications. I think this is because we're not yielding to the reactor when we start all the multiplications. This also means that no network communication is started for the first multiplication until after all multiplications have been scheduled -- this is actually not what we want... Here are the plots, please let me know what you think of this. This is the change I made, in case someone wants to play around with this: diff --git a/viff/runtime.py b/viff/runtime.py --- a/viff/runtime.py +++ b/viff/runtime.py < at >< at > -49,6 +49,18 < at >< at > from twisted.internet.defer import maybeDeferred from twisted.internet.protocol import ReconnectingClientFactory, ServerFactory from twisted.protocols.basic import Int16StringReceiver + +PHASES = {} + +def begin(result, phase): + PHASES[phase] = time.time() + return result + +def end(result, phase): + stop = time.time() + start = PHASES.pop(phase, 0) + print "Finished %s in %f sec" % (phase, stop - start) + return result class Share(Deferred): < at >< at > -797,6 +809,9 < at >< at > result.addCallback(lambda a: a * share_b) return result + phase = "mul-%d" % self.program_counter[0] + begin(None, phase) + # At this point both share_a and share_b must be Share # objects. So we wait on them, multiply and reshare. result = gather_shares([share_a, share_b]) < at >< at > -804,6 +819,7 < at >< at > self.schedule_callback(result, self._shamir_share) self.schedule_callback(result, self._recombine, threshold=2*self.threshold) + result.addCallback(end, phase) return result < at >increment_pc Martin Geisler 2008-09-24T11:00:37 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/438 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 2008-09-22T11:10:46 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/433 Martin Geisler 2008-09-21T11:41:32 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/427 Hi, I have made some tests of ElGamal encryption in Python (with some nontrivial amount of help from Martin thanks) First test was in bare Python, here an encryption took time for 1 enc time for 4*10^6 enc Python : 0,002980 sec : approx. 3 hours and 20 min GMPY : 0,000535 sec : 35 min and 40 sec All the timing is made on my elderly office machine. Another possiblity I have not tested yet is to use the Dan Bernstein implementation of encryption based on elliptic curves. I guess that we can get some more speed from there. However I think that 35 min is worth waiting for and that we can get further speed up using a better implementation, and using state-of the art machines. -- Janus Janus Dam Nielsen 2008-09-19T09:08:30 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/424 Hi guys, I would like to cut a release this weekend since I'm writing a paper with Ivan, Mikkel, and Jesper in which it would be nice to refer to a stable released version of VIFF. But we have also made lots of improvements to the robustness of VIFF and support for Windows, so a release would make sense anyway. It has also been way too long since the last release (about 4 months). You can find a list of the so-called simple bugs here: http://ln-s.net/2E+7 Please send any stuff you want to be part of VIFF 0.7 to viff-patches before Sunday -- this includes documentation and tests for new stuff. Martin Geisler 2008-09-17T09:49:24 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/423 Hi guys, Sigurd just sent a bunch of patches to the viff-patches list -- they implement an equality operator with secret shared result: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/26 Sigurd: I think it is best to announce new and exciting patches here too. Then we can do the detailed code-discussion on viff-patches and the general feature-discussion here, or something like that. Martin Geisler 2008-09-17T07:09:18 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/416 Hi Martin, Say, if a and b are two floating point numbers that are secret-shared between members (e.g. additively), then we want to compute: c = a # b where # is one of { *, / , + , - } c should be computed to a desired degree of accuracy such that c is secret-shared between the members at the end of the protocol. its possible that one of {a, b} may be public but not always. It would be nice if this can be done locally without interaction. Current approaches based on integers arithmetic to do floating point operations suffer from the problem of "bit-size expansion during intermediate computations" and I see problems in scaling up. I'd like some references that deal with this problem ('efficient MPC with rationals'). I found one related paper called "Cryptocomputing with rationals" published a while ago. I've not surveyed the very recent works yet. Thanks in advance. Amitabh Amitabh Saxena 2008-09-15T15:13:30 http://comments.gmane.org/gmane.comp.cryptography.viff.devel/409 Hi all, The VIFF issue tracker at http://tracker.viff.dk has now been modified to better reflect our current workflow. This means that issues can now only be created as 'bug' or 'wish'. Further, each issue has a new field called 'importance'. The 'importance' is a number between 0 and 100 that should reflect the importance of the issue relative to the other issues. The higher importance number, the more important. For instance, an issue that would previously have been labeled as 'critical' should now probably be labeled as a 'bug' with an importance level close to 100. Note that you may want to update some of your saved custom searches to include the importance level. Comments and suggestions on this are welcome :-) Regards, Thomas Thomas Jakobsen 2008-09-08T19:57:47 Search the mailing list at Gmane query http://search.gmane.org/?group=$group=gmane.comp.cryptography.viff.devel