Re: [viff-devel] Securely running the same VIFF program multiple times
Thomas P Jakobsen thomas@gmail.com writes: Hi all, As you may or may not know, running the same VIFF program more than once using the same set of player configuration files is insecure when the runtime relies on pseudo-random secret sharing. This is the case for e.g. the PassiveRuntime. This is not a bug, but rather a consequence of the way in which we use pseudo-random secret sharing. In order to maintain security, a new set of player configuration files has to be generated for each run. In some practical settings this turns out to be inconvenient. So we recently added a changeset (1538:9d4f9551644c) that fixes this. It means that one no longer has to use fresh configuration files for each run. Instead, there's now a command line option called computation-id, e.g. python my_viff_program.py --computation-id=42 player-1.ini When using runtimes based on pseudo-random secret sharing, like PassiveRuntime, one can then safely reuse the configuration files as long as the computation ids are unique. That is, for each run with a given set of configuration files, the players should agree on a computation id that has not been used before for that set of configuration files. Would it not be fairly easy to let each of the players secret share a random integer, add all the shared numbers, open the result, and use that as the computation ID? That is, automate this so that you don't have to agree on a certain computation ID in advance. -- Martin Geisler aragost Trifork Professional Mercurial support http://aragost.com/mercurial/ ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] IRC channel
Hi guys, I just want to let you know what I had a nice conversation today in the IRC channel for VIFF where there were 6 guys present (and one bot). They came from a organization that lobbies the EU for more openness: http://interfax.werebuild.eu/2010/05/31/werebuild-and-telecomix-cv/ It happens from time to time that people stop by and ask a question and I normally refer them to the mailinglist. But it would be great if a (current) VIFF develop would hang out in the channel from time to time. Don't worry about it being distracting -- most of the time the channel is very quiet. -- Martin Geisler aragost Trifork Professional Mercurial support http://aragost.com/mercurial/ ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] New project lead
Hello everybody, When I was visiting Denmark last week, I asked Marcel if he would step up and be the project leader for VIFF. I'm very happy he accepted :-) I have given Marcel admin access to viff.dk and the mailinglists as well as the SSH accounts we use in VIFF. In other words, he should now be able to manage everything. I will of course stick around if you guys need anything... -- Martin Geisler Fast and powerful revision control: http://mercurial.selenic.com/ pgpnvTpH1piWk.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] VIFF reactor
Joel Pettersson joel...@kth.se writes: Hi everybody, Is it still necessary to run `viff.reactor.install()` as described in http://www.mail-archive.com/viff-devel@viff.dk/msg00657.html in order to utilize the VIFF reactor? - If so, would it be possible to fix that? - If not, then the example apps would need to be updated accordingly. I see Marcel answered this with lightning speed, cool! :-) I will, by the way, be available in #viff @ Freenode most of my time the next couple of days. I'll like to add that it's very easy to get online: http://webchat.freenode.net/ -- Martin Geisler aragost Trifork Professional Mercurial support http://aragost.com/mercurial/ ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] My dissertation
s.sriniva...@surrey.ac.uk writes: Hi Sriram, I'll CC this message to the VIFF mailinglist as well -- there are many people there who can help you if I cannot. Please keep the list as CC on your replies. Hi Martin I hope you have settled into your new workplace and enjoying yourself. Thanks, it's going well in my new job. I had a few quick queries if you don't mind. I have been trying to get a grasp on MPC ideas over the past few days. I was wondering if you could point me a recent comprehensive, but not too heavy survey on MPC. If I could get an idea of how the field has progressed and various approaches to achieving MPC without getting bogged down in too much detail, it may be helpful for me at this stage. I don't know of such a survey off the top of my head. As I understand, VIFF implements the underlying functionality using Shamir Secret Sharing. It seems there are other approaches possible as well and one of my colleagues wanted to know if VIFF also implements the ideas from the paper Multiparty Computation from Threshold Homomorphic Encryption by Ronald Cramer and Ivan Damgard and Jesper Buus Nielsen? My guess is No, but I am not not sure. Right, we have not implemented the protocols from that paper. There are some papers that refer to this latter work, for example Efficient Binary Conversion for Paillier Encrypted Values by Berry Schoenmakers and Pim Tuyls. I was wondering if the application in this paper can be coded with the functionality provided by VIFF in principle, or there are some details which may prevent it from being so. I'm sorry, but I'm not familiar with that paper. But you should think of VIFF as having a number of layers: 1. basic player administration 2. network setup 3. secret sharing and reconstruction (Shamir-based) 4. secure addition and multiplication 5. more complex protocols So depending on how the primitive above fits into the stack, you may be able to reuse more or less code. Sorry if my queries don't make sense. I can admit I don't have much knowledge of the details and I am trying pick up stuff as I go along. Thanks in advance. Best Wishes Sriram -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] My dissertation
Hi guys, I have put my dissertation online, please find it here: http://bitbucket.org/mg/dissertation/downloads/ I'll add a link to the VIFF documentation next. -- Martin Geisler Fast and powerful revision control: http://mercurial.selenic.com/ pgpBCfDCX2qNl.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] VIFF 1.0 released
Hi everybody! On behalf of the VIFF Development Team, it is my pleasure to declare that we have reached VIFF version 1.0. The current code is useful, flexible and unlikely to change radically. Please download it here: Tar/GZ: http://viff.dk/release/viff-1.0.tar.gz Tar/BZ2: http://viff.dk/release/viff-1.0.tar.bz2 Zip: http://viff.dk/release/viff-1.0.zip Exe: http://viff.dk/release/viff-1.0.win32.exe Thanks to all contributors who have helped create this release! The largest changes since 0.7.1 are summarized below: Version 1.0, released on 2009-12-14 --- The central class named Runtime was renamed to PassiveRuntime. All runtime classes now uses the common method names input and output for providing data to and retrieving data from the computation. A multiparty version of AES was added: it allows parties to encrypt a Shamir secret shared message under a secret shared AES key to obtain a secret shared ciphertext. * Moved the crypto-related code from the viff.runtime.Runtime class to a new class called viff.passive.PassiveRuntime. This is a backwards incompatible change. Please update your import statements to import PassiveRuntime instead of Runtime. * Introduced input method in PassiveRuntime and PaillierRuntime. This method should be used instead of shamir_share and share unless there is a particular reason to select a secret sharing strategy. * Introduced output method in Runtime classes. This method should be used instead of the open method, which will go away in a future release. * Renamed random seed environment variable from SEED to VIFF_SEED. * Made viff.prss.PRF produce consistent output on both 32-bit and 64-bit systems. * Exponentiation of shares by square-and-multiply for public exponents. This means that if x is a Share, x**7 now works. * Added multiparty AES encryption. A highly optimized version of AES has been added to viff.aes. It allows multiparty encryption of a secret shared message using a secret shared AES key. * Introduced our own Twisted reactor. This increases throughput by sending data sooner, rather than later. * Added new full-threshold actively secure runtime in viff.orlandi. It currently relies on a third-party proprietary library for computing commitments over elliptic curves, so it cannot be use with a plain VIFF installation. * Issue 4: Replace the marshal module. The marshal module is not safe to use for malicious data, so we now use the struct module to parse a fixed length format instead. * Issue 62: Proper error message when no SSL certificate present. * Issue 75: Test without local computations. The new FakeFieldElement class has the interface of a FieldElement but does no computations. A new --fake flag for benchmark.py enables these elements. -- Martin Geisler pgpaGrlvAgi23.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] VIFF 1.0 this weekend
Hi everybody, I would like to release what we currently have in VIFF as version 1.0 this weekend. The code has not evolved very much the last year, and releasing version 1.0 now will fit nicely with the reports we're writing for CACE and with my own dissertation :-) As preparation for that, I've made a small document about the applications where VIFF has been used: http://viff.dk/doc/applications.html Atle and Håvard: do you have your thesis' online somewhere? I would like to include links to them. I have your thesis' in PDF format already, so I would also be happy to host them on viff.dk if you prefer that? Everybody: if someone wants to describe the Nordic Sugar auction then that would be super, otherwise I'll do it. Marcel has promissed to write something about the distributed RSA. Finally, if you have been sitting on a bugfix (small or large), then please put it in now :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Next problem
Nigel Smart ni...@compsci.bristol.ac.uk writes: If you can give me SSH access to the machine, then I can take a closer look. I've yet to meet a machine where I couldn't get VIFF running :-) I've put my SSH public key here: Alas we cant do that due to our security policies. /me mutters something about security can be in the real-world... Well, my advice to you is to make sure you have everything laid out nicely in the PYTHONPATH. Then try importing VIFF code in an interactive Python session -- you can see which code to import from the benchmark.py script, for example. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Next problem
Nigel Smart ni...@compsci.bristol.ac.uk writes: Whats you complete PYTHONPATH? Maybe I am not picking up something It's just the one ~/opt/lib/python directory. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpkasjyrqXmu.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Next problem
Nigel Smart ni...@compsci.bristol.ac.uk writes: set is a built-in set data type in Python 2.4 and later. Twisted has a compatibility module for older versions of Python. On my system, the twisted/python/compat.py file (from which the code tries to import set) has try: set = set except NameError: from sets import Set as set which simply tests to see if set is defined, otherwise it imports it From the sets module, which defines a Set class in old Python versions. Have now added this line, and I get the error Uh, it was supposed to be a solution for you to add :-( It was an explanation that you have a broken installation of Twisted. First of all, Python works no unlike Java with regard to it's PYTHONPATH environment variable. On my system I have installed Twisted into ~/opt/lib/python/ and have set PYTHONPATH to that same value. Inside of ~/opt/lib/python/ I have -rwxr-xr-x 1 mgeisler users 230K May 16 2007 gmpy.so drwxr-xr-x 24 mgeisler users 4.0K Sep 16 2008 twisted drwxr-xr-x 3 mgeisler users 4.0K Sep 16 2008 zope among other files. You can check that things are installed nicely by switching to some other directory and starting the interactive python interpreter: % python Python 2.4.3 (#1, Jun 11 2009, 14:09:58) [GCC 4.1.2 20080704 (Red Hat 4.1.2-44)] on linux2 Type help, copyright, credits or license for more information. from twisted import version version Version('twisted', 2, 5, 0) Likewise for GMPY: import gmpy x = gmpy.mpz(1234567891234567891234567) len(str(x**12345)) 297410 Which Python version are you using (python -V)? Which distribution is this? Twisted is a standard component which is surely packaged for the distribution -- there should be no need to installing it yourself. Python 2.4.3 (#1, Sep 3 2009, 15:37:37) That is fine, we have an old Redhat here with the same Python version. We have Centos as the OS, it is a managed distributed system. - i.e. the filestore is shared and used by 150 odd machines. So I cant just add packages etc. If I want something installed which my path does not pick up I either have to a) Search around to find it on the system or b) Install it myself in my own space Clearly b usually takes less time ;-) Heh, yeah. Also no-one in the dept seems to use python for anything, so I doubt python related stuff is instaleld. Which means option a is unlikely to work. It's not like it will mess things up to install Python, Twisted, and GMPY globally. The packages will just sit nicely in the corner and nobody will notice :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Next problem
Nigel Smart ni...@compsci.bristol.ac.uk writes: Uh, it was supposed to be a solution for you to add :-( It was an explanation that you have a broken installation of Twisted. I have actually installed a whole new version of twisted, Zope, gmpy from scratch this week. Hmm, okay. You can check that things are installed nicely by switching to some other directory and starting the interactive python interpreter: % python Python 2.4.3 (#1, Jun 11 2009, 14:09:58) [GCC 4.1.2 20080704 (Red Hat 4.1.2-44)] on linux2 Type help, copyright, credits or license for more information. from twisted import version version Version('twisted', 2, 5, 0) Likewise for GMPY: import gmpy x = gmpy.mpz(1234567891234567891234567) len(str(x**12345)) 297410 So I get ~% python Python 2.4.3 (#1, Sep 3 2009, 15:37:37) [GCC 4.1.2 20080704 (Red Hat 4.1.2-46)] on linux2 Type help, copyright, credits or license for more information. from twisted import version version Version('twisted', 9, 0, 0) import gmpy x = gmpy.mpz(1234567891234567891234567) len(str(x**12345)) 297410 Okay, so some things are working... I'm afraid I don't know why you get the import errors you reported in the other mails. If you can give me SSH access to the machine, then I can take a closer look. I've yet to meet a machine where I couldn't get VIFF running :-) I've put my SSH public key here: http://cs.au.dk/~mg/tmp/mg.pub Which implies your Twisted is ancient, as my version is 9.0.0 No, it's not as bad as it sounds -- they switched from version 2.x to version x.something where x is used in year 200x :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpqppgcsYeBf.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [Fwd: viff-devel Digest, Vol 25, Issue 4]
Nigel Smart ni...@compsci.bristol.ac.uk writes: Hi Thanks for this. No problem! I'm sending this to the list too, please use reply-all or similar to send your replies there as well :-) So having installed gmpy, how do I get python to see it - I have not used python before The install of gmpy seemed to just do the following copy only... copying build/lib.linux-x86_64-2.4/gmpy.so - /home/projects/crypto/Linux/lib64/python Try adding /home/projects/crypto/Linux/lib64/python to your PYTHONPATH environment variable. Python works similarly to Java in that it has a concept of a PYTHONPATH on which it finds it's modules -- Java has the class path where it finds it's jars. How it managed to find our gmp installation I have no idea, as I did not tell it where that was. - Assuming it did that is It must have searched in the standard library paths such as /usr/lib. That's where I find a lot of libgmp.* files. Nigel -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] benchmark
Hi Janus, I like it very much that the benchmark can figure out by itself which program counters are needed for preprocessing. Can you change it so that it will only run the benchmark once if it sees that no preprocessing is needed? -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] MPC implementation news
Dan Bogdanov d...@math.ut.ee writes: Hi Dan, I've added your address to the whitelist for this mailinglist, so you wont be bothered by the moderation again. I just wanted to let you know that we have completed the next version of Sharemind and we thought we'll let you know. Cool, congratulations on the release! Sharemind 1.9 has these major improvements 1) The first version of the SecreC language compiler. SecreC is a high-level language that separates public and private data and processes them separately. Private data is processed using MPC whereas public data is processed normally. 2) Improved Sharemind assembly language interpreter to allow SecreC to work. 3) A new protocol suite that is faster than the previous Du-Atallah-based one. 4) Support for multiple client applications. 5) Lots of demo applications that show how to use the framework, including SecreC implementations of Apriori and Eclat. Sounds very impressive :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] AES slides from SPEED-CC
Marcel Keller mkel...@cs.au.dk writes: Hi, There are two talks about how to implement AES efficiently, this one http://www.hyperelliptic.org/SPEED/slides09/kasper-aes_speedcc09_slides.pdf describes on slide 9 how one will typically combine SubBytes, ShiftRows, and MixColumns into one operation operating on diagonals. I don't know if that will matter for us? I don't think so because lookup tables are not efficient in MPC. Ah, of course! I had not thought of that. By the way, everybody should take a look at the Stick Figure Guide to the Advanced Encryption Standard (AES): http://www.moserware.com/ -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpP6kYVErL01.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] AES slides from SPEED-CC
Hi everybody, The slides from SPEED-CC are up: http://www.hyperelliptic.org/SPEED/ http://www.hyperelliptic.org/SPEED/timetable.html There are two talks about how to implement AES efficiently, this one http://www.hyperelliptic.org/SPEED/slides09/kasper-aes_speedcc09_slides.pdf describes on slide 9 how one will typically combine SubBytes, ShiftRows, and MixColumns into one operation operating on diagonals. I don't know if that will matter for us? -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpa7V1g2pMT1.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Broken build!
Hi everybody, The build is broken: http://buildbot.viff.dk/waterfall Janus, you added this code to benchmark.py: def update_args(runtime, options): args = {} if options.args != : for arg in options.args.split(','): id, value = arg.split('=') args[id] = long(value) runtime.setArgs(args) return runtime What is that supposed to do? We don't have a setArgs method anywhere, and we don't use the Java-like CamelCase coding style anyway. You're not trying to parse the command line, right? (we have optparse for that) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] [PATCH 00 of 12] Partial implementation of the Orlandi runtime.
Janus Dam Nielsen janus.niel...@alexandra.dk writes: Maybe you should publish the patches as a tree on hg.viff.dk like Marcel has done -- and then let me know when you're happy with it and want me to pull it into the main tree. How do I get such a nice tree? You already have SSH access right? Then just create a repository under ~/repos and it will automatically show up in the web interface. Add metadata in .hg/hgrc like for the other repositories. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgp2onnPWLd7a.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [PATCH 02 of 12] Implemented secret sharing command
Janus Dam Nielsen janus.niel...@alexandra.dk writes: +s1, xi = ls[0] +s2, rhoi1 = ls[1] +s3, rhoi2 = ls[2] +s4, Cx = ls[3] +if not (s1 and s2 and s3 and s4): +raise OrlandiException(Cannot share number, trying to create share, + \ +but a component did arrive properly.) Same problem as above with the backslashes. Also, I think we talked about this, but it looks like gather_shares would be better than ShareList since you must have all four shares anyway. I don't agree with this entirely. gather_shares ignores errors. Yeah, sort of. It will still pass on the list of results in case of an error, but some of them will be None or a Failure instance. But so ShareList is fine. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgphQleYB548n.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [PATCH 03 of 12] Implementation of the open command
Janus Dam Nielsen janus.niel...@alexandra.dk writes: +@increment_pc +def open(self, share, receivers=None, threshold=None): +Share reconstruction. + +Every parti broadcasts a share pair (x_{i}^{'}, rho_{x,i}^{'}). Typo: parti - party. Also, the prime (') should not be put as a superscript in LaTeX. + +The parties compute the sums x^{'}, rho_{x}^{'} and +check Com_{ck}(x^{'},rho_{x}^{'} = C_{x}. + +If yes, output x = x^{'}, else output x = _|_. Heh, I though it was only in Haskell that they write the bottom symbol like that... :-) You really mean else return :const:`None`, right? + +assert isinstance(share, Share) +# all players receive result by default +if receivers is None: +receivers = self.players.keys() +assert threshold is None +threshold = self.num_players - 1 + +def recombine_value(shares, Cx): +x = share.field(0) +rho1 = share.field(0) +rho2 = share.field(0) Due to automagic coercion you can actually initialize the values to 0. +for xi, (rhoi1, rhoi2), c in shares: +x += xi +rho1 += rhoi1 +rho2 += rhoi2 +assert c is None, A commitment is found. +return self.check_commitment(x, (rho1, rho2), Cx) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpP8XozoAFcu.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [PATCH 10 of 12] Added a variant of the encryption method which takes a random value as argument
Janus Dam Nielsen janus.niel...@alexandra.dk writes: # HG changeset patch # User Janus Dam Nielsen janus.niel...@alexandra.dk # Date 1245395100 -7200 # Node ID ad19cc189a5bf04ba37c0a9e25600040585cc1e9 # Parent cd787f04de1f3be2e7c969e963ed7bcd94f81305 Added a variant of the encryption method which takes a random value as argument. Thanks, pushed as revision c1259ceebc55! -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpmv8UmRd5yi.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [PATCH 00 of 12] Partial implementation of the Orlandi runtime.
Janus Dam Nielsen janus.niel...@alexandra.dk writes: This patchbomb contains partial implementation of the Orlandi runtime. Wow, cool! I've just looked through the first couple of patches and even though I had some style-complaints, I think this is great! If I've understood things correctly, then this gives us an actively secure protocol for full threshold scenarios, right? The patches implements the basic and advanced commands along with the triple_gen and triple_test commands. The patches are partial implementations in the sense that the commitments are not implemented correctly, pending an implementation of Elliptic Curves. Maybe you should publish the patches as a tree on hg.viff.dk like Marcel has done -- and then let me know when you're happy with it and want me to pull it into the main tree. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpzxNWt1MBsU.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [Marc Makkes] Homomorphic encryption
Hi Janus and hi everybody, I got this mail from Marc about fast Paillier: ---BeginMessage--- Hi Martin, My name is Marc X. Makkes and i'm the student who is implementing the homomorphic encryption scheme for for NaCL project. Tanja urged me to contact you for some detail regarding the implementation and if i understand correctly your the one that is going to use this scheme for certain applications. Can you tell me a little bit the applications? In addition i've received the whish list. But it seems to me that there is missing a key setup/generation function. Can you maybe comment on that? Currently i've have made a ''basic'' c implementation, which is equivalent to your and my own python implementation. In the next few day's i hope to implement the subgroup variant as well as doing the CRT speedup for decryption. Regards, -Marc -- If this email is PGP signed, the fingerprint is: C6D2 B5D7 390E 0D4E DE02 460E DC7F 651E A9CB 1B34 signed with a 521-bit ECC key pgpAFMM2arQud.pgp Description: PGP signature ---End Message--- -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Say hello to viff.reactor
Marcel Keller mkel...@cs.au.dk writes: Hi friends of VIFF, I've now implemented a special reactor for VIFF, based on the standard SelectReactor. The new reactor should make non-trivial programs considerably faster, e.g. computation of 10 AES-blocks in parallel from over 6 seconds to 2.3 seconds per block (3 players, passive security). The code is in my repository: http://hg.viff.dk/mkeller To use the new reactor, simply install it before importing the reactor: import viff.reactor viff.reactor.install() from twisted.internet import reactor If you use other reactors such as Gtk2Reactor or WxReactor, VIFF still will work but without any speed improvements. Very cool! Thank you very much for sticking with your idea and refining it like this. I'm pushing it now... -- Martin Geisler pgpFYzQcGfdEV.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Accessing functions in Protocol from outside
Håvard Vegge hava...@stud.ntnu.no writes: Awesome! Now it works, why didn't I think of Twisted's XML-RPC server before... Yeah, always look there first -- they have a quite large tool box... :-) Well, I'll probably post the URL of the (simple) web application on this mailing list some time, but not yet. It needs some minor adjustments;-) Well, back to the report writing. Thanks again! Sounds great, I'll look forward to seeing more. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpGZ7FIv9PTq.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Distributed RSA
Hi Atle and hi list, You might have looked at this paper already, but I was talking with Gert Mikkelsen today about RSA, and he pointed me to a paper with a protocol for distributed generation of RSA keys: Dan Boneh, Matthew K. Franklin: Efficient Generation of Shared RSA Keys (Extended Abstract). CRYPTO 1997: 425-439 It might be possible to implement this protocol directly in VIFF, instead of building things from scratch. The paper can be found here: http://www.springerlink.com/content/bq1jxkcuygj287cy/ -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Error when coding with callbacks and reveals
Tord Ingolf Reistad to...@stud.ntnu.no writes: Hi Tord, Please use the list-reply function in your mail program (it might be called reply to all or something like that). I'm sending this reply back on the list. Thank you for the help, with the coding problem. No problem! I am also trying to understand was the use of deferred objects. So I understand that a share is a deferred object, but can I also compute with field elements as deferred objects? You should think of Share objects as deferred field elements. The Share class is a subclass of Deferred, so every Share is a Deferred. Share objects promise to call their callbacks with a field element as argument. So if we do this: from pprint import pprint from viff.runtime import Share from viff.field import GF Zp = GF(17) s = Share(None, Zp) then s is a Share object which promisses to eventually contain a field element from the Zp field. We can now add callbacks: s.addCallback(lambda x: x + 3) Share at 0xabc596c s.addCallback(pprint) Share at 0xabc596c s.callback(Zp(10)) {13} The reason why we have this specialized Deferred class is that it overloads the arithmetic operators. So s + 3 will result in something very similar to s.addCallback(lambda x: x + 3) Here the x in the lambda expression is a field element, which itself overload the aritmetic operators to do the right thing. The end result is that we can use normal infix notation to do arithmetic on (future) field elements in shares. I would also have liked to contain the callbacks in test = self.test_not_all_zero(r_as_bits, mask) such that the protocol was oblivious to if there was a callback in the code test_not_all_zero and I just got the boolean value back, but that is probably not possible? Here's the code: def protocol_part_1(self, r_as_bits, r, mask, x): test = self.test_not_all_zero(r_as_bits, mask) self.r = r self.x = x return test.addCallback(self.protocol_part_2) def protocol_part_2(self, test): if test: c = self.r + self.x c_open = self.runtime.open(c) result = gather_shares([c_open]) callback_result = result.addCallback(self.print_answer) return callback_result else: print No value, False return False Since you really need to branch on the boolean result, you cannot avoid adding an explicit callback. The reason is that you cannot wait on a value in VIFF, you always have to tell VIFF what it should do when the value arrives at some point in the future. My goal is to keep most of the code oblivious as to if it is computing with shares or field elements. This greatly simplifies the testing and readability of the code. I see, that is indeed a nice property. And it can work some of the way, as you've seen, but only for simple functions which only do arithmetic on the shares. Tord -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpEF8LaONDNQ.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Error when coding with callbacks and reveals
Tord Ingolf Reistad to...@stud.ntnu.no writes: I just took a closer look at your code -- some comments below :-) #!/usr/bin/python # Copyright 2007, 2008 VIFF Development Team. The year should be 2009 since this is the first year in which this code is released. class Protocol: def __init__(self, runtime): # Save the Runtime for later use self.runtime = runtime own_id = self.runtime.id Zp = GF(43) test_vector = [0, 1, 6, 0] self.value = test_vector[own_id - 1] m1, m2, m3 = runtime.shamir_share([1, 2, 3], Zp, self.value) shares = [m1, m2, m3] r_as_bits = [m1, m2, m1] r = m3 mask = m3 x = m3 result = self.protocol_part_1(r_as_bits, r, mask, x) callback_result = result.addCallback(self.print_answer) The addCallback method returns self -- so after that assignment we have callback_result == result So normally you wont save the result of addCallback. #results.addCallback(lambda _: runtime.synchronize()) m1.addCallback(lambda _: runtime.shutdown()) #Create_random_bits #Convert_to_test_values #Test_values if useable use random bits otherwise find new bits #c = r + x #Compare (c,r) def protocol_part_1(self, r_as_bits, r, mask, x): test = self.test_not_all_zero(r_as_bits, mask) self.r = r self.x = x return test.addCallback(self.protocol_part_2) def protocol_part_2(self, test): if test: c = self.r + self.x c_open = self.runtime.open(c) result = gather_shares([c_open]) The gather_shares function may have an unfortunate name... it is not used to collect the shares from a single number. Instead it is used to collect a list of several shares. So if you need to wait on a and b you do: x = gather_shares([a, b]) Now x is a Share which will call its callbacks with a list of *two* field elements. This means that we can do this: x.addCallback(lambda results: result[0] + result[1]) You have now made a Share which represents the future sum of a and b! So in your case I would do c_open = self.runtime.open(c) c_open.addCallback(self.print_answer) return c_open def test_not_all_zero(self, r_as_bits, mask): #reveal (sum(bits))*mask temp = sum(r_as_bits[:]) * mask temp_open = self.runtime.open(temp) def check_result(check): print Comparing , check, to 0 if check[0].value == 0: Here you see how check_result is called with a 1-item list because you use gather_shares below. If you simply add check_result as a callback to temp_open, then things become simpler. And you can just compare a field element with an integer, so if check == 0 should work just fine. return False return True results = gather_shares([temp_open]) test_results = results.addCallback(check_result) return test_results Like above you can just add the check_result callback to temp_open and return temp_open. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpkP14OfTr9I.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller mkel...@cs.au.dk writes: You're talking about this two-threaded solution as if it is something that exists and will solve all our problems... No, for now, it's just an imagination in my mind, a proposal for the next meeting, and a strong feeling that it's the right way to do it. Yeah, I think it would help too. But I still haven't seen it, and I would like to see how you can cleanly seperate the work of the two threads. I'm afraid that the threads will be alternating between working and waiting on the other thread in such a way that we could just as well use one thread. My idea is that the Twisted main loop runs in one thread and most of the VIFF code in the other. The Twisted thread only waits for I/O and the VIFF thread only waits if there is no work to be done. It's funny -- then we'll have sort of two event loops. If the group decides to give this idea a try, I would be happy to implement it. I would claim that it can be done in one or two weeks. So you'll have something when I get back from PKC? :) Seriously, I think you're right, the code is fairly well partitioned already, so we should be able to make this change without too much trouble. Also, threading in Python is unfortunately not optimal :-( The Python VM will use a single thread to execute the bytecode, even when using multiple thread in Python. It is only if the threads do things blocking for I/O that you will see a performance increase by using multiple threads. I'm aware that Python only runs on one CPU, a friend pointed that out to me today. However, the Twisted thread mentioned above would block on I/O. Right, that should help us! Janus has been looking more into Python threads, so be sure to discuss it with him too. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpNe3r9JiJcA.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Mystery of the quadratic running time solved?
Marcel Keller mkel...@cs.au.dk writes: Indeed we did not know (well I didn't) back then that the data was not sent immediately by Twisted, and I was starting to think yesterday whether the hack would make a difference. Lucky for us, it apparently does :) That is not the only problem. To free the memory of the shares and to send out further shares, also the incoming shares must be processed as soon as possible. This is even trickier because incoming shares might trigger code that calls functions sending out data, which activates the Twisted reactor again and therefore leads to a possibly too deep recursion. I think I have a solution for that, it just wasn't necessary to implement it for now because the hack worked anyway. I guess we could simply not recurse if the recursion depth is too big? At some point we have to let the recursive calls finish in order to let the local variables and stack frames be garbage collected. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpp6C0lL7dUL.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Multiparty AES in less than 3 seconds per block thanks to Twisted hack
Martin Geisler m...@daimi.au.dk writes: I'll try and write a mail to them to explain our problem in more detail. Maybe your short patch didn't provide enough information when taken out of context. I've included a larger answer from Jean-Paul Calderone below -- you can read in context here: http://thread.gmane.org/gmane.comp.python.twisted/18029/focus=18089 Jean-Paul Calderone exar...@divmod.com writes: On Sat, 07 Mar 2009 19:38:46 +0100, Martin Geisler m...@daimi.au.dk wrote: Jean-Paul Calderone exar...@divmod.com writes: Hi, Thanks for the answer. I'm also with the VIFF project and I would like to explain a bit more about the background for the hack by Marcel. [snip] So you're doing a ton of work all at once now and you want to split up that ton of work into smaller pieces and do it a little at a time? Sort of. We have overloaded the arithmetic operators in our library, so people will expect to be able to write # xs and ys are big lists of our objects dot_product for (x, y) in zip(xs, ys): dot_product += x * y Here the multiplications involves network traffic and return Deferreds. We would like the network traffic for the first multiplication to begin immediately, *before* the remaining multiplications are done. Doing all the multiplications up front makes the code block the reactor and uses an awful lot of RAM. If we let each multiplication trigger the sending of its data immediately, and if we process incoming messages along the way, memory can be reclaimed for the earlier multiplications and the above calculation should run in constant memory. Hm. I would bet the constant would be pretty high, though. Things will only balance out once the network is keeping up with the local for loop. Actually, I'm not sure why it would be constant at all. Won't the local for loop always run much faster than any network operations can happen? In this case, memory usage will go towards K(local) * set size - K(remote) * set size, or just O(set size); that is to say, linear. Sending and processing data in a more even flow makes our benchmark results better and more consistent from one run to the next. It seems like what you'll really benefit from most is pipelining with a maximum pipeline depth that's not too big (so as to conserve memory) but not too small (so as to avoid wasting time on network round trip time). If that's the case, then you don't need to modify the reactor, you just need to split up the work your code is going. There are a lot of techniques for doing this. coiterate and inlineCallbacks are two solutions which are closest to cookie cutter (ie, you have the least flexibility in deciding how to use them). Right -- we might be able to use these techniques. I haven't looked at coiterate yet. With inlineCallbacks I guess the code would look something like this: # xs and ys are big lists of our objects dot_product for (x, y) in zip(xs, ys): dot_product += (yield x * y) which is not so bad, expect that it destroys the nice illusion that x and y behave like normal integers even though the multiplication involves network traffic. Perhaps with coiterate this might look something like... def op(xs, ys): dot_product = 0 for (x, y) in zip(xs, ys): dot_product += x * y yield yield dot_product d = coiterate(op(xs, ys)) This is flawed, but maybe it can be fixed. What's good about it is that it doesn't try to drive the reactor re-entrantly. :) It also avoids the yield in the += and * operations, which somewhat preserves your illusion of normalcy (I'm not saying I like that illusion, but I'll leave that aside for now). What's bad about it is that it still lets the local loop run arbitrarily far ahead of the results from the network, giving you unbounded memory usage. To fix that, it should yield a Deferred every once in a while. The reason I leave it flawed here is that it's a little tricky to figure out which Deferred to yield. What would be great would be to yield the Deferred for an operation which preceeds the most recently executed operation by some number of operations. The number of operations by which it preceeds the most recent will be your pipeline depth (roughly). The effect this has on coiterate is to cause your local loop to cease to execute until that Deferred has fired. By making it a Deferred for an operation some time /before/ the most recent operation, you keep the network busy and avoid wasting time on round trip times. Once the Deferred fires, your loop gets run a few more times which has the effect of putting more work into the pipeline - until you've got enough extra work to keep things from stalling again, and then coiterate puts you to sleep for a while again. You have a very long, steep, uphill battle to convince me that adding support for re-entrant iteration is a good idea. One problem I can think
Re: [viff-devel] GUI programming for Python/VIFF
Håvard Vegge hava...@stud.ntnu.no writes: I don't know what you mean with the issue synchronization of program counters, but as far as my simple GUI application goes, it just works. At least for now... Great! Tomas is currently lying at the beach in Barbados[1]..., but when he get's back I hope he will share his experiences with GUI programs. [1]: http://fc09.ifca.ai/ Another question related to GUI; say we have n players which all have some secret input. Is it possible to make a progress bar of how many inputs that is currently submitted? Or is this information unavailable? When you do a, b, c = runtime.shamir_share(range(1, n+1), Zp, my_input) you can attach callbacks to the three shares. If self.pbar is a gtk.ProgressBar something like this should do the trick: self.shares = 0 def step(value): self.shares += 1 self.pbar.set_fraction(self.shares / float(n)) return value a.addCallback(step) b.addCallback(step) c.addCallback(step) The idea is to make the callback update the progress bar, but otherwise pass the value through unharmed. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpsjvv9AOgGF.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] VIFF benchmarks
Thomas Jakobsen thomas@gmail.com writes: Hi Thomas I've written a VIFF application that should make it easy to create, run and visualize benchmarks for VIFF protocols. I've put some changes to it here -- it's only style changes in order to make it more pythonic :-) Please pull from this repository: http://bitbucket.org/mg/viffbench-mg/ I have not really tested the changes, expect by running pyflakes on the source. By the way, pyflakes informs me that: viffbench/examples/ComparisonToft05.py:68: undefined name 'start_time' viffbench/lib/enum.py:193: undefined name 'EnumValueCompareError' viffbench/test/test.py:52: undefined name 'Suite' in addition to some warnings. I hope you like the changes, and that they mostly work! :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgps7KXCgLzkV.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] How to convert field elements to integers?
Tord Ingolf Reistad to...@stud.ntnu.no writes: Hi Tord I have a simple question: After completing a VIFF program I have opened the shares and gotten the results, but the results are field elements (probably elements of class GFElement), how do I turn them back into integers? You just access the value attribute of your GFElement: x.value. If you update to the very latest version of VIFF you can now also use int(x) to do the same. The documentation says nothing about how to turn them back into integers, which should be essencial if I am going to use these shares in other applications. There seems to be some code __repr__ in GFElements, but I cannot see how I can use it. That method is called when x is a field element and you do foo %r bar % x or repr(x) It just produces a string with the value. As an additional problem, the integers should not be integers in the set form 0 to p-1, but integers from -(p-1)/2 to +(p-1)/2. How should one do that efficiently? That should be as simple as x.value - (x.modulus - 1) // 2 -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Problems installing pyOpenSSL with Python version 2.6.1
Håvard Vegge hava...@stud.ntnu.no writes: Hi Håvard I'm probably going to use VIFF as a part of my master thesis, but a problem have occurred when following the installation guide. Did you manage to get VIFF installed? Please report back with your experience so that Google and others can benifit from it :-) -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgp3U0b5PwhTH.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Time for a new release
Martin Geisler m...@daimi.au.dk writes: Hi I suggest that we aim for a release after the weekend, on the 22nd. Does people think this is a good idea? It's been a week since I asked and nobody has replied, neither positively or negatively. So the release is put on hold for now. To those who celebrate Christimas: enjoy your holidays! -- Martin Geisler pgpzHUDUR1Vd3.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Time for a new release
Hi everybody, It's that time again -- I think we should make a new release of VIFF. That would be a nice Christmas present for all the VIFFaholics around the world! :-) I suggest that we aim for a release after the weekend, on the 22nd. Does people think this is a good idea? We still have some outstanding patches: * I wrote a patch which makes the normal passive multiplication protocol divide the work between the players so that only a random subset of 2t+1 players do any work. The patch is not yet in VIFF since it slows down the performance for the (n, t) = (3, 1) case: http://article.gmane.org/gmane.comp.cryptography.viff.devel/495 http://thread.gmane.org/gmane.comp.cryptography.viff.patches/49 I guess it needs more testing and thinking before it can go in. * Mikkel wrote code to replace the insecure marshal module, but that turned into a grammar fight :-) and I'm waiting on it to be updated based on my review: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/54 This one should be almost ready to go in -- Mikkel you can push it yourself if you want. But please add the comments I ask for in the above review. * Sigurd wrote a faster equality test based on Fermat. I reviewed it but haven't seen an updated patch: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/50 This one is also almost good to go! * I wrote a patch which speeds up and streamlines the handling of incoming network data. Unfortunately it breaks the test setup so I haven't include it in VIFF. It's six weeks old, but comments are still very much appreciated: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/66 This one is not ready yet unless someone can untangle the test setup and make it pass with the patch. Apart from the patches my checklist says that we need to: * update the code to use the new input/output methods instead of shamir_share and open. We'll keep the old method names as depreceated aliases (right now it is the other way around). * update the NEWS file to reflect all the changes since 0.7.1. This is mostly done, but someone needs to look over the Mercurial changelog and update NEWS as needed. It would also be nice if someone else than me would read through the file *before* release so that we can avoid any silly typos :-) * Test the example applications. I've just tested these: - int-bit-conversion.py - millionaires.py - two-fields.py Pick a couple of programs and test them on your platforms. You are *very* welcome to write more test programs and to *comment* the ones already there. The millionaires.py program is probably the best program to use as a template. It you can improve the programs so that they test themselves then please do! What I mean is that some of the programs automatically figure out if the answer is correct, whereas some require you to compare the three outputs and figure this out for yourself. Let me know what you think -- if nobody thinks anything, then we'll just delay the release. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Yet another SFDL parser
Mikkel Krøigård m...@cs.au.dk writes: In Amsterdam we were asked about how long it would take, and I didn't have a good answer. Can you try to give a time estimate that we can tell the FairPlay guys? It's kind of hard to tell how long it will take, but I have a gut feeling that says that the basic functionality could be implemented very quickly (a matter of a few days concentrated effort at most), of course excluding the obligatory polishing phase which always takes forever. I can and will do this on the condition that we agree 100% that we don't do things in parallel :) Definitely a good idea :-) However, we talked about this loss of momentum earlier. Up until Christmas, I am still teaching 2 classes and I think it would be a mistake for me to promise anything until January. That sounds very good to me! Since ANTLR doesn't make it easy for us to to handle these int size things, let's just use the parser you made. Okay, good. It also comes with a fairly large set of unit tests, which I found usefull while working with it. I have it as a patch queue here on DAIMI -- you can clone that or convert it to a normal repository and clone that instead. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Benchmarks on a mac
Sigurd Torkel Meldgaard s...@daimi.au.dk writes: Here is a transcript of my profiling run. Thank you for testing this. I disabled ssl, because I had some trouble with the keys, hope that does not matter too much. I guess not. sigurdmeldgaard$ python benchmark.py --profile --no-ssl -c 1 player-1.ini Seeding random generator with random seed 9520 Using field elements (65 bit modulus) I am player 1, will mul 1 numbers Using the base runtime: viff.passive.PassiveRuntime. Not using SSL Listening on port 9000 Will connect to Player 2: camel13:9001 Will connect to Player 3: camel14:9002 Starting reactor ### Starting reactor with profiling Need no preprocessing Runtime ready, generating shares Synchronizing test start. Starting test in 3 Starting test in 2 Starting test in 1 Starting test now Started parallel test Total time used: 21.186 sec Time per parallel test operation: 2 ms ** Synchronizing shutdown... done. Closing connections... done. Stopping reactor... done. Loading profiling statistics... done. 2176272 function calls (1852904 primitive calls) in 33.202 CPU seconds Ordered by: internal time, call count List reduced from 207 to 40 due to restriction 40 ncalls tottime percall cumtime percall filename:lineno(function) 366 20.9230.057 26.6800.073 selectreactor.py:93(doSelect) 173360/866802.5240.0009.8540.000 defer.py:314(_runCallbacks) Hmm... apart from spending much more time in doSelect than in my trace, then I don't see any big difference. Too bad, I thought I remembered seing a bunch of low-level calls like select and not just doSelect, which does a bit more than just calling select. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] ComparisonToft07Mixin
Tomas Toft tomas.t...@cwi.nl writes: ARGH! I replied to this earlier, but only to Ivan. Martin: You should be surprised that this goes wrong for me again, and by the principle of least surprise, you should therefore set reply to be to the list :-) Hmm -- what can I say, I'm not surpriced :-) Can you not just explain your mail client that this is a mailing list? Of course, if many replies wander off-list because of this, then we can change the setting. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] ComparisonToft07Mixin
Ivan Bjerre Damgård i...@cs.au.dk writes: Quoting Marcel Keller mkel...@cs.au.dk: Hi Does anyone know of a documentation explaining the code in the ComparisonToft07Mixin class in comparison.py? I've read the relevant part of Tomas' dissertation but it seems that the algorithm there is different. Indeed that's not the same algorithm as in Tomas' thesis. I think it is an algorithm from a paper he wrote with Tord Reistad, unfortunately I could not find the paper on-line anywhere, even though it was published in a conference called ICITS 2007 in Spain. Ah, I thought it was still unpublished. Of course, Tomas may be slightly better at answering this :-) Yeah, it would be nice to have this confirmed and then update the bibliography: http://viff.dk/doc/bibliography.html -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpQEeY0HHy26.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Yet another SFDL parser
Hi everybody, I've just sent 22 patches to the viff-patches list: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/104 They represent yet another attempt at making a SFDL parser. I say yet another since Mikkel and Sigurd has been working on one too, but unfortunately that seems to have lost some momentum. Or at least I haven't heard anything about it recently :-) At the WP4 meeting in Amsterdam we talked about comparing VIFF to FairPlay on the same inputs, so we should move forward with building the converter. I don't care which parser is used -- I just played around with it to learn more about Pyparsing. However, regardless of the choice, we should discuss who will commit to take the lead on it. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Yet another SFDL parser
Mikkel Krøigård [EMAIL PROTECTED] writes: Quoting Martin Geisler [EMAIL PROTECTED]: I've just sent 22 patches to the viff-patches list: http://thread.gmane.org/gmane.comp.cryptography.viff.patches/104 They represent yet another attempt at making a SFDL parser. I say yet another since Mikkel and Sigurd has been working on one too, but unfortunately that seems to have lost some momentum. Or at least I haven't heard anything about it recently :-) We haven't lost any momentum on the parser. In fact it has been done for quite a while. We have, however, lost momentum on the rest of the compiler. Right, that was sort of what I meant :-) I don't care which parser is used -- I just played around with it to learn more about Pyparsing. However, regardless of the choice, we should discuss who will commit to take the lead on it. We should have probably talked about that before we made 3 of them. I think we did agree on me, but somehow Sigurd and I ended up doing more or less the same thing concurrently. It would be great if you could go forward with the compiler! In Amsterdam we were asked about how long it would take, and I didn't have a good answer. Can you try to give a time estimate that we can tell the FairPlay guys? -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty 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] Repositories on hg.viff.dk
Good evening everybody, If you would like space for a Mercurial repository on hg.viff.dk, then it's easy -- all I need is your SSH public key. I've already added a repository for Marcel -- I got a first patch from him today! If anybody else would like a similar repository for outgoing changes, then let me know. Mikkel and Thomas: you already have access to viff.dk. You can easily create your own repositories by going to ~/repos on viff.dk and cloning an existing repository. Then edit the .hg/hgrc file to describe it, look in ~/repos/viff/.hg/hgrc for a starting point. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/. pgpA9V8KPoj59.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [issue75] Test without local computations
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 1 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
[viff-devel] [issue75] Test without local computations
New submission from Martin Geisler [EMAIL PROTECTED]: 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. -- assignedto: mg messages: 290 nosy: mg status: unread title: Test without local computations type: wish VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue75 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue77] Trottle creation of Deferreds based on memory pressure
New submission from Martin Geisler [EMAIL PROTECTED]: This is an idea which I think Thomas came up with first: it would be very nice if one could limit the memory usage to, say, 200 MiB. The program should run a normal, but when the memory usage grows above the limit, the remaining parts of the program should be delayed. When memory has been released, the program starts again. There are two problems with this: * Is it safe? * How should it work? The first question is a matter of avoiding deadlocks. The Deferreds used in VIFF can depend on other Deferreds, and we want to avoid cycles in the dependency graph. Locally I think it is okay since we always make the Deferreds wait on each other, and ultimately wait on incoming network traffic. So that should work. Globally is a different matter: can P1 be in a situation where it needs data from P2, and P2 needs data from P1? I don't hope so :-) As for how this could be implemented in an as seamless way as possible, then I just got an idea! It is too late to stop or delay the code at the time when it tries to create a new Deferred. I don't see any good way to suspend the rest of the program at that moment. But what we can do is to stop triggering already created Deferreds! If we have reached the memory limit, the code in stringReceived (which handles incoming network traffic) would simply store the data received and not yet trigger the waiting Deferred. That would mean that the program is starved for data -- it would appear to the program as if the data has simply not arrived yet. We should then periodically check the memory usage and when it has dropped we can start triggering some more Deferreds with the received data. This idea relies on an assumption on how much outstanding data there can be in transit at any given time. It also relies on the programs to be structured in such a way that they do not allocate Deferreds for the entire calculation up front, but instead allocate them during the computation. So it wont solve the program of doing large_result_list = [] for (x, y) in zip(very_large_list, another_large_list): z = x * y large_result_list.append(z) since that would still immediately allocate a Deferred for each product. -- messages: 293 nosy: mas, mg status: unread title: Trottle creation of Deferreds based on memory pressure type: wish VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue77 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue74] Test without network communication
New submission from Martin Geisler [EMAIL PROTECTED]: It should be possible to test a single player in isolation by replaying old network communication. That would allow us to measure the time spent on local computations and the overhead from the whole Twisted machinery. -- assignedto: mg messages: 289 nosy: mg status: unread title: Test without network communication type: wish VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue74 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] New passive multiplication protocol
Claudio Orlandi [EMAIL PROTECTED] writes: (I send your off-list reply back on track) Where is a description of the new protocol? Use the source, Luke! :-) It is just the normal passive multiplication protocol where I have cut away all the work that is not needed: we only need 2t+1 shares to recombine, so only 2t+1 players will even calculate and broadcast shares. The others simply wait on the 2t+1 shares. The good question is now how we can get the best of both worlds so that the case with (n, t) = (3, 1) remains fast. What about if n=3 then RunOldProtocol else RunNewProtocol? :) Wrong syntax: if n=3: RunOldProtocol() else: RunNewProtocol() :-) But apart from that then you're right -- maybe that is what we have to do if we can find a nice way to do it. -- 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] [issue71] Allow self-sending
New submission from Martin Geisler [EMAIL PROTECTED]: At some point it became illegal to send data to oneself, and so the code looks like this in several places (this is from open): if peer_id == self.id: d = Share(self, share.field, (share.field(peer_id), share)) else: d = self._expect_share(peer_id, share.field) I think the rationale for disallowing self-sending is that the players have no ShareExchanger for themselves, and so one cannot _expect_data or sendData to oneself. But it should still be possible to clean up the code by handling this in one central place. Maybe like it is done in _exchange_shares. -- keyword: design messages: 263 nosy: mg status: unread title: Allow self-sending type: wish VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue71 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
[EMAIL PROTECTED] writes: Hi all Today, Sebastiaan and I have been doing some serious thinking and looking into the VIFF code, and we feel convinced that we've found the bug. Great work, thanks to both of you for solving the mystery! I guess this bug is sufficiently grave that we should do a 0.7.1 release to fix it. So let me know if you've found other weird things... The problem lies entirely in the multiplication protocol. In Runtime.mul, products of shares are computed and shared. Then secure Lagrange interpolation runs to reconstruct the original sharing. With an odd number of players, $n$, and threshold $t = (n-1)/2$ a contribution is needed from all parties. But if the threshold is lower or there are more parties, then reconstruction doesn't require all shares. VIFF uses this to optimize the protocol, using only the first $2t+1$ shares received. This doesn't work for the multiplication protocol: Unless shares from the /same/ parties are used, there will be a mismatch. Say we have players 1,2,3,4 and a threshold of 1. Each $i$ shares their product with a polynomial $P_i(x)$. If one party uses shares from 1,2,3, then the polynomial is P_{1,2,3}(x) = P_1(x) + P_2(x) + P_3(x) Another could use 2,3,4, thus interpolating P_{2,3,4}(x) = P_2(x) + P_3(x) + P_4(x) Clearly this is not the same computation! Thus, the parties end up with inconsistent shares -- they have points on different polynomials. To solve the problem, the players must agree on which shares are used. A simple solution is to require all shares present. Alternatively (for the passive case) we could say that only the first $2t+1$ parties share the products of their shares. This basically eliminates any need for any of the other parties. That would be a good idea, also for performance. I suggest that we use a round-robin system where we determine the perticipating subset based on the current program counter. So far I have a failing unit test which clearly shows the bug, I'll try and fix it now. -- Martin Geisler pgpFQx5rzicnb.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Martin Geisler [EMAIL PROTECTED] writes: That would be a good idea, also for performance. I suggest that we use a round-robin system where we determine the perticipating subset based on the current program counter. Code for this would look like this: diff --git a/viff/runtime.py b/viff/runtime.py --- a/viff/runtime.py +++ b/viff/runtime.py @@ -39,7 +39,7 @@ from collections import deque from viff import shamir -from viff.prss import prss, prss_lsb, prss_zero +from viff.prss import prss, prss_lsb, prss_zero, generate_subsets from viff.field import GF256, FieldElement from viff.util import wrapper, rand @@ -703,6 +703,18 @@ def __init__(self, player, threshold, options=None): Initialize runtime. BasicRuntime.__init__(self, player, threshold, options) +self.subsets = {} + +def select_subset(self, threshold): +Select subset for *threshold* based on current program counter. +try: +subsets = self.subsets[threshold] +except KeyError: +players = frozenset(range(1, self.num_players+1)) +subsets = list(generate_subsets(players, 2*threshold + 1)) +self.subsets[threshold] = subsets +return subsets[hash(tuple(self.program_counter)) % len(subsets)] + @increment_pc def open(self, share, receivers=None, threshold=None): (perhaps with an @increment_pc decorator...) So far I have a failing unit test which clearly shows the bug, I'll try and fix it now. I've pushed the new unit tests as revision 4daa42544157, but I'm afraid I'm too tired to fix things tonight... feel free to jump in :-) -- Martin Geisler pgpO73AHmQUgo.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] FW: Bug in ViFF
Hoogh, S.J.A. de [EMAIL PROTECTED] writes: Hi Sebastiaan I've looked at your code, and I don't understand the final part, the one which is supposed to calculate the sorted order of the millionaires: # We can establish the correct order of Millionaires 2 and 3. comparison = [5] if m1_gt_m2 and m1_gt_m3 and m1_gt_m4 and m1_gt_m5: comparison = [1] elif not m1_gt_m2 and m2_gt_m3 and m2_gt_m4 and m2_gt_m5: comparison = [2] elif not m1_gt_m3 and not m2_gt_m3 and m3_gt_m4 and m3_gt_m5: comparison = [3] elif not m1_gt_m4 and not m2_gt_m4 and not m3_gt_m4 and m4_gt_m5: comparison = [4] The original code is here: http://hg.viff.dk/viff/file/153c24a4a6c5/apps/millionaires.py#l115 and it works by ordering the numbers 1, 2, 3 by hand in the comparison list: it first checks to see if 2 and 3 should be ordered [3, 2] or [2, 3] and it then puts the number 1 into this list in the right spot. The final output is thus something like this: I am Millionaire 1 and I am worth 193 millions. From poorest to richest: Millionaire 3 Millionaire 2 Millionaire 1 (193 millions) and I can understand why you don't get this output with your code. -- 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] Fwd: error while installing viff
Amitabh Saxena [EMAIL PROTECTED] writes: Hi Amitabh -- Forwarded message -- From: Amitabh Saxena [EMAIL PROTECTED] Date: Mon, Sep 15, 2008 at 2:08 PM Subject: Re: error while installing viff To: Martin Geisler [EMAIL PROTECTED] Thanks Martin, I will try the installation procedure again. Did you succeed with the installation of VIFF? -- 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] [issue68] Exceptions from tracker
New submission from Martin Geisler [EMAIL PROTECTED]: I'm getting errors like this from the Roundup tracker: Traceback (most recent call last): File /users/viff/opt/lib/python/roundup/cgi/client.py, line 303, in inner_main html = self.handle_action() File /users/viff/opt/lib/python/roundup/cgi/client.py, line 871, in handle_action return action_klass(self).execute() File /users/viff/opt/lib/python/roundup/cgi/actions.py, line 39, in execute return self.handle() File /users/viff/opt/lib/python/roundup/cgi/actions.py, line 1004, in handle for itemid in klass.filter(matches, filterspec, sort, group): File /users/viff/opt/lib/python/roundup/backends/back_sqlite.py, line 395, in filter filterspec, sort=sort, group=group)) File /users/viff/opt/lib/python/roundup/backends/rdbms_common.py, line 2129, in filter proptree = self._proptree(filterspec, sortattr) File /users/viff/opt/lib/python/roundup/hyperdb.py, line 1060, in _proptree p = p.append(k, sort_type = 2) File /users/viff/opt/lib/python/roundup/hyperdb.py, line 341, in append propclass = self.props[name] KeyError: 'priority' I guess that means that there is still some parts of the code that references the priority field. Thomas, could you look into this? -- messages: 237 nosy: mas, mg status: unread title: Exceptions from tracker type: bug VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue68 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue67] SFDL converter
New submission from Martin Geisler [EMAIL PROTECTED]: We've promised to make a converter which can read a SFDL program and turn it into an equivalent VIFF program. -- assignedto: mk importance: 70.0 messages: 229 nosy: mg, mk status: unread title: SFDL converter type: wish VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue67 ___ 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
[EMAIL PROTECTED] writes: Quoting Mikkel Krøigård [EMAIL PROTECTED]: Citat Martin Geisler [EMAIL PROTECTED]: I've looked at the GMPY code, and it is a fairly straightforward wrapper for the GMP library, as you describe. But I don't know if it makes it easier for us to benchmark just because it is split into its own C code... I never said it would. If you use this approach, it is easy to see how much is spent on the dangerous arithmetic, but I guess a profiler could tell you how much time Python spends on the functions implementing the operators anyway. If that's the case, then it doesn't make sense w.r.t. the profiling to use GMPY. I was assuming the profiler could not give you information that was so fine-grained. Some time ago I build in support for the normal Python profiler in all VIFF programs, so if you run the benchmark with --profile you get results like this for 4000 multiplications: 889364 function calls (762586 primitive calls) in 17.830 CPU seconds Ordered by: internal time, call count List reduced from 192 to 40 due to restriction 40 ncalls tottime percall cumtime percall filename:lineno(function) 447.3500.167 12.1770.277 selectreactor.py:82(doSelect) The line above says that the internal time spend on 44 calls to doSelect was 7.35 seconds. The cumtime includes time spend in functions called from doSelect, most importantly the actual select call done there. I interpret this to mean that the program slept for 5 seconds (12 - 7 = 5) out of the 18 seconds it ran. First one should note that this sleeping includes the 3 second countdown done by the benchmark and the time it takes for the programs connect to each other initially (the data is for Player 3/3 and this player waits for Player 1 and 2). Second, the profiling slows things down -- I'm not sure exactly how much, but maybe with a factor or 2. So it is the relative numbers which are important. 70684/413422.3300.0008.6690.000 defer.py:306(_runCallbacks) 0.6480.0001.7680.000 shamir.py:30(share) This player did a total of Shamir sharings: it was responsible for 8000/3 = 2666 of the initial 8000 Shamir sharings, and then it did 4000 resharings as part of the secure multiplications. 360070.6010.0000.7650.000 field.py:371(__mul__) This is the overloaded multiplication operator for field elements, the one in pure Python code. 85360/413600.5430.0005.0570.000 defer.py:168(addCallbacks) 1040210.4270.0000.4270.000 field.py:339(__init__) Total number of field elements created: 104021. This includes very short-lived objects created from an expression like x + y + z where x + y create a temporary field element which is then added to z. 133380.3640.0000.7980.000 runtime.py:627(_expect_share) 319980.3580.0000.4830.000 field.py:342(__add__) Additions in the field. The Shamir sharing and recombination does addition. 80040.3190.0001.6150.000 runtime.py:203(__init__) 40000.2750.0000.7080.000 shamir.py:95(recombine) This is the time it takes to recombine 4000 Shamir shares. 133400.2630.0004.4630.000 runtime.py:286(stringReceived) 80000.2510.0001.5380.000 runtime.py:1041(shamir_share) The time it took to do the initial Shamir sharing of 8000 numbers. 480.2490.0054.7120.098 basic.py:345(dataReceived) 28015/213420.2340.0004.2120.000 defer.py:283(_startRunCallbacks) 49350/213500.2260.0004.6130.000 defer.py:185(addCallback) 28015/213420.2160.0004.3810.000 defer.py:229(callback) 20002/120020.2120.0007.1260.001 runtime.py:372(inc_pc_wrapper) Program counter book-keeping. 280100.1960.0000.4030.000 runtime.py:80(__init__) 133380.1900.0000.3470.000 abstract.py:164(write) 32006/280040.1710.0001.4200.000 runtime.py:227(_callback_fired) 133380.1700.0000.1700.000 runtime.py:593(_expect_data) 120060.1590.0001.2380.000 runtime.py:611(_exchange_shares) 40000.1550.0002.6740.001 runtime.py:1025(_shamir_share) 93320.1410.0000.2700.000 random.py:148(randrange) 93320.1290.0000.1290.000 random.py:218(_randbelow) 133380.1200.0000.4670.000 basic.py:357(sendString) 133360.1180.0000.5850.000 runtime.py:325(sendData) 40000.1120.0005.4600.001 runtime.py:791(mul) 80000.1090.0004.3920.001 runtime.py:553(schedule_callback) 133380.0780.0000.1240.000 runtime.py:629(lambda) 133430.0780.0000.1570.000 tcp.py:260(startWriting) 10.0760.0761.9611.961
Re: [viff-devel] Some profiling results
Mikkel Krøigård [EMAIL PROTECTED] writes: Citat Martin Geisler [EMAIL PROTECTED]: Martin Geisler [EMAIL PROTECTED] writes: 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. Here is another plot which also shows when each multiplication is started and how long it takes. I guess the first multiplication is so slow because you're busy scheduling the rest. Notice that no multiplication actually finishes until they have all been started. This diagram makes sense in my mind at least. Yep, it makes good sense for me too! Now it would be interesting to see if we can obtain better timing results if we let the reactor process incoming data while still scheduling. I think I'll continue with this kind of inspection since it seems to be an easy way to obtain data about how the various pieces work together in VIFF. -- 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] Upgraded hg on viff.dk
Good evening everybody, I have upgraded the Mercurial installation on viff.dk, so we can now enjoy a new clear theme. It has a nifty graph which shows the changesets: http://hg.viff.dk/viff/graph/ I have also enabled syntax highlighting: http://hg.viff.dk/viff/file/tip/viff/shamir.py I hope you like it -- let me know if you find any problems! -- Martin Geisler pgpqn3aY71XOI.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Some profiling results
[EMAIL PROTECTED] writes: Hi Martin, I have a couple of stupid questions: Quoting Martin Geisler [EMAIL PROTECTED]: 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. If you have done 1000, resp. 4000 mult's, why do the x-axes start at 2000, reps. 8000? Ah, good question: the numbers are taken from the current program counter at the time when the multiplication is scheduled. And it turns out to start at about 2n since we start by doing 2n shamir secret sharings to get n pairs. And if you have measured time for individual multiplications, why are the numbers on the y-axis smaller in the 1000 multiplication case? Shouldn't they take about the same amount of time in both cases? Yes, that was what I expected too! I would at least expect the final multiplications to take about equally long, even if the first one are waiting longer when doing 4000 multiplications. -- 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] Some profiling results
Martin Geisler [EMAIL PROTECTED] writes: 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. Here is another plot which also shows when each multiplication is started and how long it takes. attachment: duration-4000.png -- 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
[EMAIL PROTECTED] writes: I think there was earlier some version where arithmetic was done by calling some external C code. From that I am guessing that it is feasible to make a version where all or most of the stuff in 1) is done by calling specific functions we can name and track rather than using the internal Python arithmetic, for instance. In such a version, it should be possible to find out how much time is spent on 1). If this gets much slower than the normal version, we are in trouble and then I don't know what to do. Sigurd is actually testing this at this very moment (we talked about it on IRC) and I hope he will give some benchmark results. This is about using GMPY for field arithmetic: http://tracker.viff.dk/issue10 2) I suppose can be measured by hooking into the event loop of Twisted That was what I described in the mail before -- I saw very few calls to the select() function, which is the one used in the event loop to sleep while waiting for data from a set of file descriptors. Exercise: if you can measure 1) and 2), how do you measure 3)? :-) Hehe :-) -- 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: I remember trying out how to implement Python modules in C, and you needed to define special functions that map to C functions. Presumably there is something of the same kind going on inside gmpy that we can measure separately from the rest of the Python code. I am not familiar with the profilers though, and I could be wrong. I've looked at the GMPY code, and it is a fairly straightforward wrapper for the GMP library, as you describe. But I don't know if it makes it easier for us to benchmark just because it is split into its own C code... -- 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] Roundup Importance Level
Thomas Jakobsen [EMAIL PROTECTED] writes: Hi Thomas I have just changed the name 'Priority' to 'Type' in the Roundup bugtracker. This makes more sense now, since we only have 'bugs' and 'wishes' - and because it is now the importance level that indicates the priorities of the issues. Thanks for doing this! Did you have to do it by hand, or did you find a better way? Also, would it make sense to let the default query sort by priority instead of by activity? -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgptHHFMWRRDW.pgp Description: PGP signature ___ 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
Re: [viff-devel] [issue66] Network emulator
Adam Langley [EMAIL PROTECTED] writes: On Fri, Sep 19, 2008 at 4:26 PM, Martin Geisler [EMAIL PROTECTED] wrote: I think it would be very interesting to setup a system using this so-called network emulator: http://wanem.sourceforge.net/ This is the common way to do such things: http://www.linuxfoundation.org/en/Net:Netem Excellent, thanks for the link! I had not found that in my search. So I think we should setup the three laptops from the Danisco auction (see http://tracker.viff.dk/issue64) with netem and configure each machine to delay its outgoing packets for 100-200 ms. And then run lots of benchmarks! -- 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] VIFF 0.7
I'm very happy to announce the release of VIFF version 0.7: Tar/GZ: http://viff.dk/release/viff-0.7.tar.gz Tar/BZ2: http://viff.dk/release/viff-0.7.tar.bz2 Zip: http://viff.dk/release/viff-0.7.zip Exe: http://viff.dk/release/viff-0.7.win32.exe The changes since version 0.6 are: PyOpenSSL is now used instead of GnuTLS and this enables secure connections on Windows. The code dealing with starting a player has been made much more robust and players can now be started in any order. Player can now also be reliably shutdown. New runtime based on homomorphic Paillier encryption supports just two players. Added a new protocol for equality testing with secret shared result. About VIFF: Virtual Ideal Functionality Framework is a framework for creating efficient and secure multi-party computations (SMPC). Players, who do not trust each other, participate in a joint computation based on their private inputs. The computation is done using cryptographic protocols which allows them to obtain a correct answer without revealing their private inputs. Operations supported include addition, multiplication, and comparison, all with Shamir secret shared outputs. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgphhpz1Z8ffK.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Patches
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 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] Upcoming release!
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 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] Upcoming release!
Martin Geisler [EMAIL PROTECTED] writes: You can find a list of the so-called simple bugs here: http://ln-s.net/2E+7 Here is another query which is interesting for the upcoming release: http://ln-s.net/2E+a It selects the bugs closed since the release of VIFF 0.6 (2008-05-28). -- 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] Python bindings for NaCl
Adam Langley [EMAIL PROTECTED] writes: On Thu, Sep 4, 2008 at 5:05 AM, Martin Geisler [EMAIL PROTECTED] wrote: Thanks for the vote of confidence. I think NaCl gets paged into my brain tomorrow. I'll see if I can get the shared library support done. See the patch set at http://imperialviolet.org/binary/nacl-20080714-agl-20080904.tar.bz2 That contains patches for several curve25519 implementations, shared library building and the python bindings. To build the python bindings (which are in bindings/python) first install the libnacl.so into /usr/lib, the include files into /usr/include/nacl then: % bash generate.sh % python setup.py build I have not tested this yet, so maybe there is no problem... But I think we must support installing to a custom prefix since most people who use this wont have root access to their machines (at least not the machines at the university). I'm always installing Python stuff with python setup.py install --home=~/opt and other stuff with ./configure --prefix=$HOME/opt make make install That has worked quite well with the other VIFF dependencies, so it would be great if NaCl would have a similar build infrastructure. There may be ELF visibility issues with some of the code that I'm not building here (like the curve25519/athlon code). If you don't find libnacl.so in build/$(hostname)/lib/$abi-pic then email me your build/$(hostname)/log. Thanks, I'll let you know of any problems when I get this tested, maybe some time next week. -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgpACFnwaVSu9.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Python bindings for NaCl
Adam Langley [EMAIL PROTECTED] writes: On Wed, Sep 3, 2008 at 1:41 AM, Martin Geisler [EMAIL PROTECTED] wrote: Okay. If you want to, you can get all the repository- and web-space you want on viff.dk. Or maybe you could put up the bindings on pypi? Thanks for the offer. I'm not sure where it'll end up at the moment. I often use code.google.com for these things. Okay, that's another fine choice! I'm only concerned that we get something out to the real world and not just in some locked SVN repository somewhere... I think it would look great if NaCL and pyNaCL (if that is the right name?) would be put out there as small open source projects. Then we would actually have produced something concrete for others to use in the CACE project. Agreed. You just have to persuade Dan to use source control and host NaCl somewhere :) Hmm... no version control?! grumble... :-) Dan and Tanja: I'm sure you guys have plenty of hosting options already, but just let me know if you would like NaCl to be hosted with or near VIFF. From the sample above it looks exactly like I imagined: simple, straight forward, and with minimum fuzz! Thanks for the vote of confidence. I think NaCl gets paged into my brain tomorrow. I'll see if I can get the shared library support done. Okay, sounds good. Then we'll have to see where we can make use of the NaCl bindings first. We're currently using a total ad-hoc pseudo-random function implementation which uses SHA-1 to generate numbers. Replacing that by one of the stronger SHA variants supported by NaCl might be an easy place to start: http://hg.viff.dk/viff/file/ff249565fa3a/viff/prss.py#l260 And then there is the Shamir sharing and recombination stuff here, which requires fast bignum addition and multiplication: http://hg.viff.dk/viff/file/ff249565fa3a/viff/shamir.py but I think Dan plans to make custom code for that. -- 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] Python bindings for NaCl
Adam Langley [EMAIL PROTECTED] writes: Hi Adam djb suggested I email this list and solicit any suggestions for Python bindings for NaCl. I sent an RFC patch to djb last week containing a suggested set of bindings which worked like this: Python 2.5.2 (r252:60911, Jul 31 2008, 17:31:22) [GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2 Type help, copyright, credits or license for more information. import nacl nacl.hash('test') '\xee\xb0\xddJ\xf7\xe7I\xaa\x1a\x8e\xe3\xc1\n\xe9\x92?a\x89\x80w.G?\x88\x19\xa5\xd4\x94\x0e\r\xb2z\xc1\x85\xf8\xa0\xe1\xd5\xf8O\x88\xbc\x88\x7f\xd6{\x1472\xc3\x04\xcc_\xa9\xad\x8eoW\xf5\x00(\xa8\xff' nacl.hash_md5('test') \t\x8fk\xcdF!\xd3s\xca\xdeN\x83'\xb4\xf6 dir(nacl) ['__doc__', '__file__', '__name__', 'auth', 'auth_hmacmd5', 'auth_hmacsha256', 'auth_hmacsha512', 'hash', 'hash_md5', 'hash_sha256', 'hash_sha512', 'secretbox_salsa20hmacsha512', 'streamxor', 'streamxor_salsa20', 'streamxor_salsa2012', 'streamxor_salsa208', 'verify16', 'verify32'] Thus the bindings match the C interface very closely. There's a default function (i.e. 'hash') and a series of specific functions (i.e. 'hash_sha256'), again like the C interface. The arguments to the functions match the C interface where: * outputs are returned, rather than passing a pointer in Nice! :-) * 'string' inputs can be unicode and will be serialised using the default codec I think I would have used plain bytestrings here too and require that the application takes care of encoding the Unicode string in a suitable way (UTF-8 or whatever works for the application). The default encoding is still ASCII as far as I know, so it will probably not work anyway when the bindings try to convert the Unicode strings. * 'key' inputs must be plain strings Good, makes sense. This is for Python 2.x. For 3.0 the the two types of strings are more distinct. Milestones on the path: * Getting NaCl to build as a shared library. I've already managed this with a hack but it needs to be done properly * Getting the ELF DSO visibility correct for all the symbols. Fiddly. I don't have the current patch on this box, but it's available on request. Okay. If you want to, you can get all the repository- and web-space you want on viff.dk. Or maybe you could put up the bindings on pypi? I think it would look great if NaCL and pyNaCL (if that is the right name?) would be put out there as small open source projects. Then we would actually have produced something concrete for others to use in the CACE project. There's also bitbucket.org which provides Mercurial repository hosting, an issue tracker, and a wiki. In combination with pypi I think this would provide a nice setup for a small project. Comment away. Or just email me Python code that you wished worked and I'll see if I can make it so. From the sample above it looks exactly like I imagined: simple, straight forward, and with minimum fuzz! I had not expected Python bindings so soon, so this is just like an early Christmas present :-) -- 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] Exceptions?
Thomas Jakobsen [EMAIL PROTECTED] writes: Hi Thomas, This is just some scattered thoughts... [...] logging and for sending to the VIFF developers for debugging. For logging information as we go along I suggest we use one of the standard Python frameworks, see: http://tracker.viff.dk/issue5 Another question is how this could be implemented in VIFF. As far as I know, exceptions in Python take an array of arguments, so we could define the first to be the user message and the second to be a detailed msg. Exceptions are just classes which normally derive from the Exception class (I'm not even sure this is a hard requirement). But they can take any arguments you like. Old-style syntax was raise ValueError bad idea but that has been deprecated and replaced by raise ValueError(bad idea) There are some info about the standard exceptions here: http://docs.python.org/lib/module-exceptions.html But how do we then distinguish exceptions with nice user messages from other exceptions? One way could be to use a custom exception class that has a userMsg and a detailedMsg field: raise NiceCustomException(user message, detailed message) The standard class Exception (or BaseException in Python 2.5) has an args attribute for the constructor arguments, and a message attribute for a single message. or simply raise NiceCustomException(message) if there is no need to distinguish. Further, if we let the NiceCustomException have room for an inner exception, we have the opportunity to intercept an exception from somewhere else and equip it with an appropriate user message, e.g.: try: externalLib.doComplicatedDecryptStuff() except BadPaddingException, inst: raise NiceCustomException(Could'nt decrypt, wrong password?, inner=inst) Again, this will allow the programmer of a VIFF-based application to expose the user to a short and descriptive explanation while keeping access to all detailed info about the problem that has occured. When we use the custom exception solution, he will also be able to distinguish between an exception with a nice user message and, say, some unpredictable and hairy RuntimeException where the user is most happy knowing only that Some exception occured. We could do something like that. And then we will also have to take into account the way exceptions are used with Twisted. I think this picture explains it quite well: http://twistedmatrix.com/projects/core/documentation/howto/defer.html#auto2 -- Martin Geisler VIFF (Virtual Ideal Functionality Framework) brings easy and efficient SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/. pgpkoRtAwESWX.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Bitonic sort
Ivan Bjerre Damgaard [EMAIL PROTECTED] writes: Martin Geisler [EMAIL PROTECTED] writes: I began looking at card shuffling because I want to make a small tutorial for VIFF, something that will explain how to make a program. And for that I figured that some card game would be cool. I don't know which game yet, so let let me know if you have any good idea! Blackjack perhaps? seems simple in that you just draw cards until you win or loose. Can also be played with 3 people, one being the bank - so you don't necessarily need 2-party computing. Yeah, I guess Blackjack would work. I don't know much about card games, so I looked up the rules on Wikipedia and found that they were a lot more complicated than I thought :-) http://en.wikipedia.org/wiki/Blackjack But if we simplify things to the core, then I think it would be okay to program, even for a tutorial. So the game would go like this: * Cards are shuffled. Using MPC here gives us a fair shuffle where neither the bank nor the players learns anything about the order. * Each player is dealt two cards == two secret shares are opened to each player. For the dealer one opening is done to all players. * Each player can now choose either hit (get a new card) or stand (finished). * When everybody stands, the dealer would normally reveal his unopened card and the one with the best hand wins (as long as the hand is less than 21). We could do the comparisons securely instead instead of opening here and I guess that would remove some of the chance for card counting. * When the comparisons are done the winners and loosers are announced to everybody and a new round can begin using the remaining cards. That doesn't sound too bad... I don't know when I'll get around to implementing it and you guys are welcome to beat me to it! :-) -- Martin Geisler pgpcrGL6eJv5y.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Bitonic sort
Martin Geisler [EMAIL PROTECTED] writes: It does 466 comparisons to sort 52 numbers (32-bit) and it takes about 4 minutes both share and sort the numbers on thyra{01,02,03} on DAIMI. In case nobody has noticed, I wanted to see how long it would take to sort 52 numbers since doing so would give me a way to shuffle a deck of cards: assign a random number to each card and sort the random numbers. If there are no collisions in the random numbers you will get back a nicely shuffled deck. I began looking at card shuffling because I want to make a small tutorial for VIFF, something that will explain how to make a program. And for that I figured that some card game would be cool. I don't know which game yet, so let let me know if you have any good idea! -- Martin Geisler pgpFbMUIg6zBc.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Bitonic sort
Hi guys, I have just implemented a so-called bitonic sort in VIFF. This is a sorting algorithm which is data-independent -- the comparisons are fixed beforehand. This makes it good for something like VIFF, I hope. The code is here: http://hg.viff.dk/viff/file/tip/apps/sort.py#l113 and you should compare it to the Java code found here: http://iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/oddn.htm#section4 It does 466 comparisons to sort 52 numbers (32-bit) and it takes about 4 minutes both share and sort the numbers on thyra{01,02,03} on DAIMI. -- Martin Geisler pgpFWVfLTQQKY.pgp Description: PGP signature ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue60] Make local xor fast
New submission from Martin Geisler [EMAIL PROTECTED]: Like mul, Runtime.xor should do a local computation if one of the operands is a known constant. Right now it just wraps whatever it gets and calls add and mul, and because of the wrapping a slow multiplication will take place. Maybe the wrapping is wrong? Or maybe we should start tracking the sharing degree of all Share objects. I think that would be the most general and most precise solution, and it would also enable the lazy Shamir sharing talked about in Issue 9. -- messages: 157 nosy: mg priority: feature status: unread title: Make local xor fast VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue60 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] PRSS zero- and double-sharings
Mikkel Krøigård [EMAIL PROTECTED] writes: Well, there are many more or less interesting conclusions to draw from your benchmark, Martin. Not surprisingly, matrix multiplication turns out to be expensive. Hmm... I did see that there were a bunch of calls to __mul__ in matrix.py, but I thought they came from the initialization of _hyper in ActiveRuntime. The the initialization of _hyper does not use any matrix multiplications, so this is wrong?! When the mul method uses prss_get_triple, then _hyper should never be used or even initialized and so there should be no matrix stuff going on... I think I measured the wrong code somehow :-) One thing I really do find interesting about the table is the amount of time spent in inc_pc_wrapper. Perhaps it is possible to improve this somehow? It only used 0.5 seconds of its own time -- the 21 seconds are the total time spend in the child-calls made by inc_pc_wrapper. Since it wraps all important functions its clear that the cumulative time will be big: ncalls tottime percall cumtime percall 48003/60030.5180.000 21.1950.004 But any optimization would be good -- if we can same a tiny bit for each of the 48000 calls it might sum up :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] PRSS zero- and double-sharings
Martin Geisler [EMAIL PROTECTED] writes: Strangely the time for preprocessing has not improved... It stayed at an average time of about *20 ms* for a multiplication triple both before and after the change -- I don't understand that :-( I do now! :-) It turned out that the preprocessing was still done with the old code. Using the new PRSS-based code brings the time down to *5 ms* pr triple, so it cuts the time by a factor of four. Thanks to Mikkel for making me think about why there were matrix multiplications in the profile information... -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] PRSS zero- and double-sharings
Mikkel Krøigård [EMAIL PROTECTED] writes: It only used 0.5 seconds of its own time -- the 21 seconds are the total time spend in the child-calls made by inc_pc_wrapper. Since it wraps all important functions its clear that the cumulative time will be big: ncalls tottime percall cumtime percall 48003/60030.5180.000 21.1950.004 But any optimization would be good -- if we can same a tiny bit for each of the 48000 calls it might sum up :-) My observation was just that wrapping is somewhat expensive. I do not quite know what to do about this. We have already discussed the alternatives to using this method, and they were not particularly promising. Function calls are unfortunately quite expensive in Python. One idea is to use Psyco (http://tracker.viff.dk/issue51) since it supposedly should be able to write optimized code on the fly, maybe even do inlining -- I'm not sure. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] www.bitbucket.org (was: Which operations for HSM (Hardware Crypto))
Martin Geisler [EMAIL PROTECTED] writes: I would of course be happy to setup repositories for all of you guys! Another option would be to put a clone here: http://www.bitbucket.org/ I have heard a lot of good feedback about them. They offer free hosting of Mercurial repositories up to 150 MB, which is about 100 times more than VIFF needs right now :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] PRSS zero- and double-sharings
Martin Geisler [EMAIL PROTECTED] writes: I'm thinking that there might be some unfortunate overhead in the preprocessing book-keeping. We should try running benchmark.py under a profiler to see where the time is spent. There is now support for a --profile flag, and running benchmark.py with it gives (1000 actively secure multiplications, 4 players): 2706417 function calls (2113774 primitive calls) in 37.755 CPU seconds Ordered by: internal time, call count List reduced from 301 to 40 due to restriction 40 ncalls tottime percall cumtime percall filename:lineno(function) 586.6420.115 34.6400.597 selectreactor.py:82(doSelect) 230033/170146.0110.000 29.8500.002 defer.py:306(_runCallbacks) 305044/2490233.0990.0009.9370.000 defer.py:168(addCallbacks) 350001.6370.0008.0420.000 runtime.py:1088(mul) 465041.3380.0004.2180.000 runtime.py:184(__init__) 1051151.3100.0001.7800.000 field.py:371(__mul__) 1883071.2690.0001.2690.000 field.py:339(__init__) 20001.0530.001 12.0170.006 matrix.py:128(__mul__) 117027/210140.9920.000 27.1290.001 defer.py:283(_startRunCallbacks) 720000.8480.0001.4860.000 field.py:342(__add__) 192023/1580170.8200.0008.2830.000 defer.py:185(addCallback) 117027/210140.8070.000 27.2820.001 defer.py:229(callback) 370000.7990.0002.3820.000 runtime.py:137(clone) 1155120.7620.0001.3680.000 runtime.py:70(__init__) 150060.6030.0000.6030.000 runtime.py:574(_expect_data) 102008/670060.5250.0008.9530.000 runtime.py:208(_callback_fired) 48003/60030.5180.000 21.1950.004 runtime.py:353(inc_pc_wrapper) 360000.5140.0006.2010.000 runtime.py:742(add) 90000.4940.0001.2850.000 shamir.py:95(recombine) 435040.3730.0005.0850.000 runtime.py:216(gather_shares) 190060.3400.0001.0510.000 runtime.py:306(sendData) 700.3360.005 27.8190.397 basic.py:345(dataReceived) 150090.3280.000 27.4830.002 runtime.py:267(stringReceived) 1170260.2870.0000.2870.000 defer.py:162(__init__) 190090.2720.0000.5170.000 abstract.py:164(write) 60000.2630.0000.4550.000 matrix.py:201(transpose) 30000.2490.0002.5070.001 runtime.py:719(exchange) 20000.2490.0001.0530.001 shamir.py:30(share) 360000.2330.0001.1740.000 runtime.py:754(lambda) 15000/40000.2030.0003.7750.001 runtime.py:534(schedule_callback) 150060.1970.0001.2490.000 runtime.py:608(_expect_share) 190090.1950.0000.7120.000 basic.py:357(sendString) 340000.1870.0000.6970.000 runtime.py:1102(lambda) 20000.1780.0001.2540.001 prss.py:69(convert_replicated_shamir) 5040.1760.0000.2630.001 defer.py:458(__init__) 880000.1670.0000.1670.000 matrix.py:72(__getitem__) 60000.1600.0000.1600.000 prss.py:260(__init__) 60000.1550.0000.1550.000 prss.py:326(__call__) 370000.1500.0004.2250.000 runtime.py:144(split_result) 340000.1460.0005.5000.000 runtime.py:105(__rmul__) I'm not really sure how to interpret this... If any of you want to investigate, then here's a link to the manual: http://docs.python.org/lib/module-profile.html :-) -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [issue49] Test OpenSSL under Mac OS X [status=resolved]
Jakob Illeborg Pagter [EMAIL PROTECTED] writes: Har installeret PyOpenSSL og kørt millionaires uden problemer. Rækker det? Yes, of course -- thanks! This mail should close the bug if everything works like they are supposed to. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] PRSS zero- and double-sharings
Hi everybody, Ivan told me how we can implement pseudo-random zero-sharing over a degree 2t polynomial. It even uses most of the stuff we already have so I went ahead and implemented it. I then make a prss_generate_triple method which uses PRSS-based methods instead of the single_ and double_share_random methods (they had all the hyper-invertible matrix stuff going on for validation). Strangely the time for preprocessing has not improved... It stayed at an average time of about *20 ms* for a multiplication triple both before and after the change -- I don't understand that :-( At first I had only replaced the double_share_random method (but kept the single_share_random) and there the time for preprocessing did go down from about 20 ms to 12 ms. I'm thinking that there might be some unfortunate overhead in the preprocessing book-keeping. We should try running benchmark.py under a profiler to see where the time is spent. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue57] Get rid of Runtime._shamir_share
New submission from Martin Geisler [EMAIL PROTECTED]: The _shamir_share and shamir_share methods overlap in functionality and one should probably be implemented in terms of the other. -- messages: 148 nosy: mg priority: feature status: unread title: Get rid of Runtime._shamir_share VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue57 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Which operations for HSM (Hardware Crypto)
Brian Graversen [EMAIL PROTECTED] writes: I have talked to IBM, and we are currently waiting for a license for the tool required to load application code into the IBM 4758 cards. We should get such a license at the beginning of august. The code is just basic C-code, so we can start writing the applications right now. The RSA encryption is available i the box, so it is just the secret share code that we need for now. Okay -- that code should be simple, see viff.shamir for a straight forward implementation of Shamir's secret sharing scheme. If we let the 4758 do all the secret sharing, it can keep the shares stored encrypted on disk, using an internal 3DES key, and the encryption of the shares would then be an internal part of the secret share mechanism in the 4758. I think that is a very nice interface: you give an input in clear text and you get encrypted shares back. I think I would start by making a subclass of viff.runtime.Runtime, and in this subclass you can override the shamir_share and _recombine methods. That should make the shamir-share-open.py example work. Overriding the add and mul methods should take care of most of the other examples! I would love to see this code online, and if you want we can setup a repository at hg.viff.dk where you can push to. I know that it is only you who can test the code, but I'm still curious :-) If we do this, then the code flow (time flows left to right) would look like this: viff --- o --- o --- o --- o --- o ... \ \ \ \ \ \ hsm --- o --- o --- o --- o --- o --- o ... which is meant to say that you can develop in your own pace in the hsm repository and then once in a while you can pull in new stuff from the viff repository. The hsm repository will then mostly be a superset of the viff repository. When we are happy with the hsm stuff we can then do a pull in the other direction. If you find a bug in the main viff code, then the change should be applied to the viff repository and then pulled into the hsm repository. But if we forget about this, then don't worry -- there is a transplant extension to Mercurial that allows us to recover. I would of course be happy to setup repositories for all of you guys! -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue58] Remove old warning
New submission from Martin Geisler [EMAIL PROTECTED]: The installation guide says that there are problems with Twisted 8.0.1. But now that Issue 37 is fixed, this warning should be removed. The newest version of Twisted is 8.1.0 and that should be mentioned in the guide. -- keyword: documentation, simple messages: 149 nosy: mg priority: bug status: unread title: Remove old warning VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue58 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue56] Switch from /doc/latest/foo to /doc/foo
New submission from Martin Geisler [EMAIL PROTECTED]: There are some links on the webpage (and probably also in the documentation) which points to http://viff.dk/doc/latest/ They should be changed to just http://viff.dk/doc/ now since this is where the current version will be from now on. -- keyword: beginner, documentation messages: 146 nosy: mg priority: bug status: unread title: Switch from /doc/latest/foo to /doc/foo VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue56 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Why all the bug reports?!
Martin Geisler [EMAIL PROTECTED] writes: Because I wanted to remind you guys that there are many low-hanging fruits where you can help... But nobody replied... :-/ I have begun fixing Issue 52: http://tracker.viff.dk/issue52 This means that we now have the latest HTML and API documentation easily accesable on the homepage. So if you fix something in the documentation it will appear now instead of after the next release. The documentation updates should be especially easy. I have tagged the easy ones with a 'simple' keyword, you can see: http://ln-s.net/25kK This is in the spirit of the Gnome Love project which you may have heard about: http://live.gnome.org/GnomeLove -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue44] Update NEWS with info on two player runtime
New submission from Martin Geisler [EMAIL PROTECTED]: The release notes in the NEWS file should be updated with information about the two player runtime found in viff.paillier. -- messages: 130 nosy: mg status: unread title: Update NEWS with info on two player runtime VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue44 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue45] Documentation for viff.paillier
New submission from Martin Geisler [EMAIL PROTECTED]: The code for the Paillier crypto system needs documentation, as does the runtime based on it. -- messages: 131 nosy: mg status: unread title: Documentation for viff.paillier VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue45 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue47] New mailinglists
New submission from Martin Geisler [EMAIL PROTECTED]: We now have three mailinglists (see http://lists.viff.dk/) but the documentation only mentions viff-devel. -- messages: 133 nosy: mg status: unread title: New mailinglists VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue47 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue46] Doc update needed: players can start in any order
New submission from Martin Geisler [EMAIL PROTECTED]: The players can now be started in any order and the documentation needs to be updated to reflect that. At least the installation guide is outdated. -- messages: 132 nosy: mg status: unread title: Doc update needed: players can start in any order VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue46 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue49] Test OpenSSL under Mac OS X
New submission from Martin Geisler [EMAIL PROTECTED]: As far as I know nobody has tested the SSL functionality of VIFF since we switched to PyOpenSSL almost two weeks ago (rev facc9f1f0bb1). Please test it and close this bug if it works. -- messages: 135 nosy: mg status: unread title: Test OpenSSL under Mac OS X VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue49 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue48] Test PyOpenSSL under Windows
New submission from Martin Geisler [EMAIL PROTECTED]: As far as I know nobody has tested the SSL functionality of VIFF since we switched to PyOpenSSL almost two weeks ago (rev facc9f1f0bb1). Please test it and close this bug if it works. -- messages: 134 nosy: mg status: unread title: Test PyOpenSSL under Windows VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue48 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue50] Stop reconnecting after X failed attempts
New submission from Martin Geisler [EMAIL PROTECTED]: Add an option which will make the players stop trying to reconnect after a certain number of attempts. This is will be important for Issue 40 so that we can run a set of players from a script and exit with an error if the network is down or some other problem prevents the players from connecting to each other. -- messages: 136 nosy: mg priority: feature status: unread title: Stop reconnecting after X failed attempts VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue50 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Why all the bug reports?!
Because I wanted to remind you guys that there are many low-hanging fruits where you can help... The documentation updates should be especially easy. I also keep reminding myself that I should look into or update all these different things -- now there is at least a chance that someone will help with that. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk