Re: [viff-devel] Multiplication with two openings
Quoting Martin Geisler <[EMAIL PROTECTED]>: > I tried running benchmark using only my own computer, and there it takes > about 12 ms pr multiplication or a little more than 10 times as much as > the normal passively secure multiplication. > > This is not so strange -- I have skipped all the oppotunities for > preprocessing, everything is generated online (double sharings, triples, > matrix multiplication, etc...) But the protocol also lacks the > verifications needed to really make it secure, so I don't know how the > final results will look. One remark: I believe our standard passively secure protocol takes advantage of pseudorandom secret sharing, which the new stuff does not, and this may be another part of the explanation for the difference in timing. In fact pseudorandom secret sharing is a bigger advantage for active security: you can make guaranteed consistent sharings at exactly the same cost as in the passive case, assuming of course that the number of players is small. So it would be interesting to make an alternative implementation that generates the basic stuff using PRSS, where basic stuff means sharings [a]_t,[b]_t,[r]_t, [r]_2t for random a,b,r (subscripts refer to the degree). From this, the multiplication triples are straightforward to make. One needs a modification to PRSS to do the pairs [r]_t,[r]_2t, but I think this should be not too hard. regards, Ivan > > Please take a look at the TODO items in the source if you want to help! > > -- > 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] 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
Re: [viff-devel] [PATCH 0 of 4] Insecure ElGamal based two player runtime
Quoting Martin Geisler <[EMAIL PROTECTED]>: > Martin Geisler <[EMAIL PROTECTED]> writes: > > Hi everybody, > > I would just like to point out that I have kick-started the > viff-patches mailing list with a mostly-for-fun two player runtime > based on ElGamal. See the patches here: Isn't a mail list for patches a strange place to put something like this El Gamal protocol you just mailed about? If you had not "by chance" sent this to more people, you might not have received Claudio's useful comment. Maybe there should be a "protocol development" mail list? - 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] 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] Small VIFF language parser
Quoting Martin Geisler <[EMAIL PROTECTED]>: > Hi everybody, > > We have talked on and off about making a front-end compiler for VIFF and > today I figured that I would try making such a guy... This is nice, and indeed is exactly what we have talked about doing for some time. If for no other reason, because we promised to do this in CACE :-) Also, we have a new PhD student from August, Sigurd Meldgaard, co-supervised by me and Michael. Sigurd plans to do exactly this sort of thing we are talking about here, so it's important to get him integrated in this work asap. It will have to wait until August/September I guess before we can really do it, but I will at least tell him about what is going on.. 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] Which operations for HSM (Hardware Crypto)
Quoting Brian Graversen <[EMAIL PROTECTED]>: > Second, I'm not sure what is possible yet. Ivan said he know some guy that > could > do tricks with the HSM, so it would be possible to do all kinds of stuff, but > I > think we need to look at the performance side of it, perhaps a software > implementation would be faster, and if we cannot store the shares inside the > HSM, and make the operations without the data leaving the HSM, then the > security benifits would be minimal. I have just sent mail to the guys at Cryptomathic who know about these tricks with HSM's, will let you know asap. About what we should/could do in general: yes of course it's better to do everything inside the HSM - but just a word of warning: shares and secrets still have to be opened under certain circumstances, so it's also important that one cannot cheat the logic that controls this and this may be outside the box. Even if we cannot do the arithmetic inside the box, I think it is still worth it to have the box do the encryption for permanent storage: it gives a standard and secure solution to the key management problem for the encryption we use. In a software only solution you easily get into a situation where the encryption buys you nothing unless you force the user to key in the key all the time. 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] Which operations for HSM (Hardware Crypto)
Quoting "D. J. Bernstein" <[EMAIL PROTECTED]>: > > Martin Geisler writes: > > I would love to build a set of Python bindings for it and see it > > running in VIFF... :-) > > Python NaCl is on our essential-items todo list. It'd be great if you > have time to help out. Since this is CACE work I'd suggest the WP2 > mailing list as the central place to discuss the API. It's great to see some activity about this interface issue. I hope also Thomas from Alexandra will take part in this - I post this on the VIFF list, since then he'll see it. Thomas, if you are not on the WP2 list, you can get the Technikon guys to put you there.. 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] SMCL security notion
Quoting Martin Geisler <[EMAIL PROTECTED]>: > Hi everybody > > >> I am confused about the notion of security via adversary traces > >> presented in those papers. It is described via two properties: > >> > >> * Identity Property: a public state P can only lead to one other > >> public state P', regardless of the secret state. > >> > >> * Commutative Property: computing on secrets leads to the same > >> state as opening everything and computing on open values. > >> > >> I think you write that this is a new idea -- have you then looked > >> into how this relates to the more standard notion of Ideal > >> World/Real World simulation arguments in the UC framework? > > > > Yes this is a new formulation of the security guaranties in the > > programming language community. I have not compared this to UC, it > > would be nice to do so. > I guess the intuition here is that the identity property gives you privacy: namely the public history develops "independently" of the secret stuff. And the commutative property gives you correctness, namely the secret computation develops as if it had been done correctly in the open. One problem I see with this is that it doesn't seem to take into account what happens if you open some of the secret data before the computation is done. There are many examples where this is the right thing to do, the binary search in the double auction for instance. Such an action opens the possibility that the history of the secret data now influences the public part (in some limited way of course). At least superficially, it seems this would violate the identity property, but nevertheless the underlying protocol is secure.. Another issue is that it is known from the history of the UC definition that requiring correctness and privacy as separate properties is not the right thing to do, or rather it is not always enough. An example: consider an electronic election where people submit votes encrypted under some public key, where the secret key is shared among some servers. Then the servers do some secure computation to get the result of the election. Now, if you don't take special precautions, a voter could copy the ciphertext sent by some other voter and submit it as his own vote. This is actually both correct and private, but it is clearly not what we want: a voter should not be able to always vote the same as someone else. What is missing is a requirement that you actually know which input you are contributing, this is implied by the UC definition. This does not necessarily mean that Identity+Commutative property is weaker than UC, maybe it is most likely that they are incomparable, but it is an issue to be aware of.. > > > In the paper on page two, lower left, we write that each server > > party execute identical copies of the server program inn lock-step. > > Based on this assumption it is reasonable to consider the server as > > having a single well-defined state. However in Viff this is no > > longer true due to parallelism. But it would be very nice if we > > could consider the server as having a single well-defined state. > > I don't like this since it introduces a wide gap between the model and > the real world and I believe such a gap makes it easier to come up > with inefficient solutions. > > Sure you can implement a synchronous network on top of an asynchronous > network, you can run expensive agreement protocols to ensure that > everybody has seen every message and that they are all delivered in > the same order. I think what people do in real life is most often not to emulate synchronous via subprotocols - which is indeed expensive, but rather they make a physical assumption on the max delivery time of the network. This can make good sense on a LAN, for instance. Then you just make every synchronous round last the max delivery time plus a little bit to compensate for clock drifts and then you can assume that if you did not receive something from a player, he must be corrupt. This just to say that the lock-step assumption is not necessarily meaningless in real life. But the scope is limited of course. If you try the same on the Internet, each round has to last for MUCH more real time, and the protocol may become much slower than an asynchronous solution. I would say that it's OK to do this modeling in steps: do a first approximation that may be limited in scope, and then take it further afterwards. After all there should also be something for Sigurd 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
