Re: [viff-devel] VIFF and random numbers
It is not good to use the wrong kind of PRG, it should be fixed as soon as possible. But do we know that os.urandom will be OK on any platform, or is this OS -dependent at the end of the day? - Ivan On 06/07/2010, at 15.22, Thomas P Jakobsen wrote: 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] Orlandi preprocessing
I have not been following the discussion in detail, but it's true that the more items you request, the smaller the amortized cost, at least in theory. I also think it would be a very good idea to involve either Jesper or Claudio in this, if there is any place where you are in doubt at all. regards, Ivan On 22/10/2009, at 20.17, Marcel Keller wrote: Hi Janus, I remember you saying today that the preprocessing in the OrlandiRuntime is more efficient per item the more items are requested. Is that correct? I ask because in my optimizations, I limited the items being preprocessed per call in order to save memory. I would of course drop that because it doesn't really affect the other cases. Best regards, Marcel ___ 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] [issue80] Broadcast
Quoting Janus Dam Nielsen j...@cs.au.dk: In the simple case I want to shout out a number to everybody, even somebody who is eavesdropping. But secrecy of what you shout is not the real problem. The problem is to make sure everyone agrees on what was said. This is not obvious in the case where people may not follow the protocol. For instance, if you want a solution that does not depend on computational assumptions, then if a third or more of the players are corrupt, then there is NO solution. Think of 3 players A,B and C, where A wants to broadcast a message, say 0 or 1. One player may be corrupt. So A is supposed to send a bit b to both B and C. Say B hears 0 from A. He doesn't know if A said the same to C. He can ask C what he heard, but if C says A said 1 to me, there is no way to tell if A or C is lying.. regards, Ivan -- Janus Den 10/03/2009 kl. 12.23 skrev Ivan Bjerre Damgård: 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 regards, Ivan Quoting Janus Dam Nielsen trac...@viff.dk: New submission from Janus Dam Nielsen janus.niel...@alexandra.dk: I would like to see a broadcast method in the Runtime class. The purpose of the broadcast method should be to distribute a public value among all parties (or some subset of parties). A case: All parties in a computation needs to read a value from standard in, and it is a different value for each party. We want to tell the value to everybody else. An example use could be like the input method: a,b,c = runtime.broadcast([1,2,3], value) Similarly, broadcast can be used in a conditional if only some subset of parties wants to distribute a value. -- assignedto: mg messages: 310 nosy: jdn, mas, mg status: chatting title: Broadcast type: wish VIFF Issue Tracker trac...@viff.dk http://tracker.viff.dk/issue80 ___ 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 ___ 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
Hi,
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 current implementation of active
security has
a preprocessing step based on either PRSS or hyper invertible matrices, and a
computation phase where all we do is that we open shared values. Neither phase
has the problem encountered here.
regards, Ivan
Quoting [EMAIL PROTECTED]:
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.
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.
Regards,
Tomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] What to benchmark
Quoting Martin Geisler [EMAIL PROTECTED]: Note that I am not saying we are in that situation, in fact I don't think so - but I am saying that it is important to find out ASAP! Agreed! I would be very happy to hear suggestions as to how we can measure things in VIFF and/or Twisted. Well, it seems to me it makes sense to split the time spent in 3 classes 1) necessary local computing (such as arithmetic on shares, computing PRF's etc.) 2) idle time, while waiting for messages from the others 3) anything else and the most basic information we want is how large these three are relative to each other. 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. 2) I suppose can be measured by hooking into the event loop of Twisted Exercise: if you can measure 1) and 2), how do you measure 3)? :-) regards, Ivan ___ 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
Quoting Mikkel Krøigård [EMAIL PROTECTED]: 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. Well I guess that's part of what I meant. Certainly, if you can measure how much time is spent inside the C code, this will say how much raw time is spent on arithmetic. This assumes, however, that all arithmetic, even down to simple additions are done this way. Then there are other things, such as computing PRF's that I suppose is not done using gmp?. This would have to be measured separately Exercise: if you can measure 1) and 2), how do you measure 3)? :-) That's one tough equation. Many years of experience as a university teacher allows me to ask almost impossible questions with surprising ease.. regards, Ivan ___ 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
Quoting 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 agree with Mikkel that it seems to make sense that it looks this way. But of course we would have been happier if the first multiplication did not have to wait for so long. In particular it seems it is waiting longer the more multiplications you ask for in total, right? This is certainly something we don't want. I don't nearly enough about how this works to say what to do about it.. regards, Ivan ___ 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
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. But at least it is good news that Sigurd saw a speed-up from using C, albeit on large numbers. It indicates that the raw computing time is not completely dwarfed by bookkeeping etc. It is not completely unimaginable, however, that someone would want to know how much actually goes on inside gmpy (arithmetic on big numbers, the data) and how much goes on outside (counting variables, various kinds of overhead). That someone is me. I think it is important to know what fraction of the time we spend on computing we HAVE to do. regards, Ivan ___ 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
Quoting Martin Geisler [EMAIL PROTECTED]:
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!
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.
Poker is also a posibility, but more complex, I guess.
regards, Ivan
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Elliptic curves
Quoting Martin Geisler [EMAIL PROTECTED]: Claudio Orlandi [EMAIL PROTECTED] writes: From reading the Wikipedia page linked below it seems very simple to implement. But if it should be fast, then a library is of course much better than a home-grown Python version. A general remark about all this: if we see it in a bigger CACE etc. context it seems to me we should not use lots of energy on integrating some library. WP2 in CACE is supposed to provide this kind of stuff for us, and even with an interface we can influence and with security against side channels. If you find something that's easy to integrate it may be fine to have something to play with, but the next half year, I think time is better spent on integration with WP2. regards, Ivan ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Paillier based two player runtime
Quoting Claudio Orlandi [EMAIL PROTECTED]: Cool -- that sounds like a good opportunity to finally sit down and create a slow-but-simple elliptic curve library for VIFF. I suggest you to use some library instead. Some of the algorithms are quite involved... I'm sure you can find C/C++ good stuff out there, and as far as I understood, you can embed them into Python right? There is a list here http://en.wikipedia.org/wiki/Elliptic_Curve_Cryptography but I have no clue about what is good and what is not. A good person to ask is Michael (Østergaard, email [EMAIL PROTECTED]) I think he worked with some of these libraries.. regards, Ivan ___ 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: Switch to prss_share_bit_double in comparisons.
Quoting Martin Geisler [EMAIL PROTECTED]: .. but this makes viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest go into what looks like a never-ending loop?! You you have a better solution, then I'm all ears! :-) What is wrong with just doing a single normal secure multiplication, and then open the result? If we want to optimize, we have to have a way to PRSS-create a random degree 2t polynomial that is 0 in 0. This is close to what we discussed at the meeting today. Given that, we first make a random shared a, and a random degree 2t polynomial g, with g(0)=0. Then locally square your share in a, add to your share in g and broadcast. This will securely compute a^2, with passive security if t n/2. If you want active security, it's more complicated, and it may be easier as a first step to just call a normal multiplication to get a^2. Then you get whatever security that multiplication offers. regards, Ivan regards, Ivan ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
