Re: [viff-devel] VIFF needs at least 3 players always?
Citat af Kyung-Wook Hwang kwhw...@ee.columbia.edu: Hello, This is Kyung Hwang from Columbia University again. I have another question. Does Viff always need at least 3 participants? It seems to me it does. That depends on the runtime you use. If you are using the default passive security runtime, this is based on Shamir secret-sharing. Therefore there must be at least 3 parties, and the threshold will always be n/2. There is in fact also a two-party runtime based on the Paillier cryptosystem. You can check it out if you want, it's in paillier.py. But basically you have to select a runtime that gives you what you want. If you want 2-party MPC, you can't use the Shamir sharing based runtime. I modified beginner.py for two players because that file was simplest to modify, but when I ran the two players, I got the following errors: kwhw...@kwhwang-sim1:~/viff-1.0/apps$ python beginner2.py player-2.ini 20 --no-ssl Seeding random generator with random seed 3781 /home/kwhwang/opt/lib/python/viff/prss.py:43: DeprecationWarning: the sha module is deprecated; use the hashlib module instead import sha I am player 2 and will input 20 Not using SSL Listening on port 9002 Starting reactor ### Program started Error: [Failure instance: Traceback: type 'exceptions.KeyError': 3 /home/kwhwang/opt/lib/python/viff/runtime.py:317:stringReceived /home/kwhwang/opt/lib/python/viff/runtime.py:456:identify_peer /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:280:callback /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:354:_startRunCallbacks --- exception caught here --- /usr/lib/python2.6/dist-packages/twisted/internet/defer.py:371:_runCallbacks beginner2.py:69:protocol /home/kwhwang/opt/lib/python/viff/passive.py:493:input /home/kwhwang/opt/lib/python/viff/passive.py:550:shamir_share /home/kwhwang/opt/lib/python/viff/runtime.py:785:_expect_share /home/kwhwang/opt/lib/python/viff/runtime.py:749:_expect_data /home/kwhwang/opt/lib/python/viff/runtime.py:754:_expect_data_with_pc As you can see, it's using shamir_share. Shamir sharing requires at least 3 players. I also modified equality.py for two players to see if it works for only two players because that file actually compared only two players' inputs but not the third player's so that file essentially needs two players. But it gaves errors too with two players. I think Viff only works with at least three players. Am I correct? Same as above :) Regards, Mikkel Krøigård ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] Comparison problems
Hello, We've been trying to run an MPC LP solver (by Tomas Toft) for a while now and can't get it to work for examples of a more realistic size. One problem we're having right now is that using the Toft07 comparison, we can basically get VIFF to drop to 0% CPU usage and just sit there forever. What we did was run the compare.py test program from viff/apps but with Toft07 instead of Toft05, and with different bit lengths. Running it with anything up to and including 968 seems to work. 969 and beyond apparently makes VIFF freeze. If anyone has any ideas or can tell us what exactly we're doing wrong, it would be much appreciated. ___ 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 and random numbers
Indeed it should satisfy those properties. Say if you Shamir share something, the adversary might get t shares in order. If it can guess the next bit with non-negligible advantage, this will completely break our claim that the adversary has no information on the secret. Luckily it should not be hard to replace. I think we knew about this earlier but just forgot, actually. By the way, I am not sure we use any random numbers that should NOT secure in this way. Citat af Thomas P Jakobsen thomas@gmail.com: VIFF itself as well as most protocols implemented in VIFF uses the viff.util package for random number generation. This package in turn uses the random package in the Python standard library. This means that random numbers are generated using a Mersenne twister. As far as I can see, this is a problem, since Mersenne twister PRNGs are generally not suited for cryptographic usage. E.g. it is not known to pass the next-bit test and withstand the state compromise extensions, see http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator. One solution would be to use the os.urandom() function instead. This has specifically been designed to produce cryptographically secure random numbers. (We should probably keep the old random generator, too. It is probably faster and not all random numbers used in VIFF and VIFF programs need to be cryptographically secure.) Let me know what you think about this. Kind regards, Thomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] The primitives of MPC
I think it deserves to be mentioned that you can do conditional statements on secret values in some cases. A simple case is easy to implement with the other primitives, but then of course you can be annoying and start nesting them. Citat af Sigurd Torkel Meldgaard s...@cs.au.dk: Other nice 2. order operations are bitsplitting (and also recombination of the bits) and multiplicative inverse (works only if you can guarantee a non-zero element) And when you have the bits you would also like logic negation, xor, and and or. - Sigurd On Tue, Aug 25, 2009 at 9:22 AM, Tord Ingolf Reistadto...@stud.ntnu.no wrote: If you boil down VIFF, or any MPC program you can boil it down to 5 primitives. These primitives are x + y = z Addition x * y = z Multiplication -x = z Negation z = Share(x) Secret sharing z = Reveal(x) Revealing of a secret sharing My question is now: What are the second order primitives? What are the basic features that, make a programmers life easy but not essential. I would propose the following 5: z = f(x,y) Function calls for(0 to n) A for call with a fixed number of iterations. z = Rand(x) Generating random values in Zp x = y Equation x y Comparison while( x ) A while loop on x, where x is a revealed value The first 2 primitives are easy since they are already implemented using the underlying programming language. Should creating random values be on this list? Or should it maybe be among the first order primitives, a basic building block of MPC. Equation and comparison are obvious second order primitives and has been my research topic for many years. The last on the list is the while loop, I have included it because I have seen many times that you want to compute some function, open a variable, check some information and then redo the function if the revealed value was false. This can be found when creating random values less than some threshold, creating RSA primes, and many other algorithms. Also it is not trivial to program if you want it to be efficient. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Player thresholds
Citat af Håvard Vegge hava...@stud.ntnu.no:
Thanks for clarifying!
Guess there are a lot of different variations of the definitions,
notions, etc. regarding secret sharing and MPC...
One of my problems is that when running the included sort.py
protocol with n=5 and t=2, the sorting of the array fails:
Original array: [{33}, {61}, {95}, {67}, {37}]
Sorted array: [{6692966529242218069}, {35128728804386641877},
{6621921405115695795}, {27880759555216652877}, {34356088148296101764}]
Made 9 comparisons
Works with n=5 and t=1 though...
That definitely looks like a bug to me. It has been about forever
since I looked at the VIFF code, but I think I'll try this out, see if
I can get the bug as well.
Mikkel Krøigård wrote:
Citat af Håvard Vegge hava...@stud.ntnu.no:
Hi!
I'm trying to do some basic benchmarks with different number of
players. A few questions:
1. Why have VIFF defined the threshold t to be the number of
corrupt players, while the classical literature defines it as t
participants can reconstruct the message?
Well, in what I have read, it is most often referred to as the
threshold for the number of tolerated corruptions, though yes I
have also seen it described as the number of shares needed to
reconstruct. I don't think there's anything wrong with the way we
do it, as long as it is clearly defined.
2. Say I create the config files this way:
python generate-config-files.py -n 5 -t 2 localhost:9001
localhost:9002 localhost:9003 localhost:9004 localhost:9005
Would this indicate that the polynomial is quadratic (of degree 2)
and that 3 players in theory could reconstruct some secret?
Yes.
3. Assume three of these five players provide input, while the
last two players do not. Will all players still participate in the
actual computation, or are the last two just passive spectators
and receives only the output?
-n 5 indicates that 5 servers will participate, regardless of how
many will provide input. Think of it from the perspective of
security. If the input was shared to 3 servers, we could not
tolerate 2 corruptions.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Player thresholds
Citat af Håvard Vegge hava...@stud.ntnu.no: Hi! I'm trying to do some basic benchmarks with different number of players. A few questions: 1. Why have VIFF defined the threshold t to be the number of corrupt players, while the classical literature defines it as t participants can reconstruct the message? Well, in what I have read, it is most often referred to as the threshold for the number of tolerated corruptions, though yes I have also seen it described as the number of shares needed to reconstruct. I don't think there's anything wrong with the way we do it, as long as it is clearly defined. 2. Say I create the config files this way: python generate-config-files.py -n 5 -t 2 localhost:9001 localhost:9002 localhost:9003 localhost:9004 localhost:9005 Would this indicate that the polynomial is quadratic (of degree 2) and that 3 players in theory could reconstruct some secret? Yes. 3. Assume three of these five players provide input, while the last two players do not. Will all players still participate in the actual computation, or are the last two just passive spectators and receives only the output? -n 5 indicates that 5 servers will participate, regardless of how many will provide input. Think of it from the perspective of security. If the input was shared to 3 servers, we could not tolerate 2 corruptions. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [issue80] Broadcast
Citat af Ivan Bjerre Damgård i...@cs.au.dk: It can definitely be useful to have a broadcast method, for instance to complete the implementation of the asynchronous maliciously secure protocol, we will need broadcast. But one needs to be careful about what kind of security we want. There is a whole jungle of protocols, depending on whether it is unconditional or computational security, synchronous or asynchronous network, and what number of players you assume can be corrupt. I think a protocol of Bracha has in fact already been implemented in VIFF Indeed it has. It's located in the active runtime (active.py). ___ 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?
Citat af Marcel Keller mkel...@cs.au.dk: 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. Ah, but the numbers I had been shown did not indicate we were anywhere near running out of memory. That's not to say memory isn't important (it certainly will be in cases with huge amounts of operations), I just didn't think it had anything to do with our specific test cases for the paper. ___ 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
Tomas is right, of course. For the passive case, using the first 2t+1 players always works, and for the active case, we do not use the local-multiply-and-reshare method anyway. The thing is, I always just assumed that we always used the same set of shares, and it is kind of easy to miss if you just read quickly through it - it says what you expect. I guess that's why we all missed it until now. The unit tests should not be hardcoded to n=3, t=1 as they are now, because that's why we never found the problem in the first place. I can rewrite the unit tests to the general setting. It needs to be done. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] [issue69] Ship small libraries with VIFF
New submission from Martin Geisler [EMAIL PROTECTED]: I think we could think about shipping the ConfigObj library directly with VIFF. The ConfigObj library is self-contained in a single .py file, and including it with VIFF would save people using Windows the trouble of copying this file to their site-packages directory -- they would not even have to know that they have such a directory... :-) Well they don't as it is, they are instructed by the installation instructions to run python setup.py install :) But after going through the installation process on another computer yesterday, I have to say it was a bit annoying. And I already knew how to do it, there's just a lot to do. Anything we can do to eliminate some of the steps... Another small library which I would like to include is the decorator library: http://pypi.python.org/pypi/decorator which is available as a zip-file only -- in the zip file there is a single decorator.py file. Doesn't sound entirely necessary to zip that, but OK :) ___ 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
Citat Martin Geisler [EMAIL PROTECTED]: In both plots we see that the first multiplication takes very long, it is sort of waiting on the other multiplications. I think this is because we're not yielding to the reactor when we start all the multiplications. This also means that no network communication is started for the first multiplication until after all multiplications have been scheduled -- this is actually not what we want... Here are the plots, please let me know what you think of this. At a glance, it does look like the timing is being done correctly. Right now I can only confirm that there's definitely something funny going on in those plots. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Citat [EMAIL PROTECTED]: I think there was earlier some version where arithmetic was done by calling some external C code. We are easily able to switch between gmpy (which is implemented in C) and Python arithmetic, if that's what you mean. 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. Exercise: if you can measure 1) and 2), how do you measure 3)? :-) That's one tough equation. ___ 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
Well, there are many more or less interesting conclusions to draw from your benchmark, Marting. Not surprisingly, matrix multiplication turns out to be expensive. It is worth considering using a non-naive algorithm for this multiplication, but I am not convinced there is very much to gain. 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? ___ 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
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?! No the initialization of hyper should definitely not use matrix multiplications. 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 :-) Well somehow, matrices were multiplied. And not only that, a lot of time was spent doing it :) 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 :-) 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. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [issue2] Define a hierarchy for Runtime functionality
New submission from Mikkel Krøigård [EMAIL PROTECTED]: The Runtime class keeps growing as more and more functionality is put into it. An option would be to split it into a basic Runtime which provides communication and nothing else. More functionality could be provided by mix-in classes. See the discussion here: http://thread.gmane.org/gmane.comp.cryptography.viff.devel/61/ -- keyword: design messages: 2 nosy: mk priority: wish status: unread title: Define a hierarchy for Runtime functionality VIFF Issue Tracker [EMAIL PROTECTED] http://tracker.viff.dk/issue2 ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Where to put the documentation?
It would definitely be better to have an online HTML file. I think we should replace the the INSTALL file with a simple one like that: Installation Instructions == Please see http://viff.dk/installation.html What do people think of a scheme like this? Is it okay to ship the releases with pointers to the web documentation? The solution seems very simple to me. Include instructions both on the download page and in the INSTALL file. ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
