Hi Martin, if you are interested just in passive security for the 2 party case you can implement the following protocol for multiplication.
Suppose you are sharing a,b in Zp. Call n the RSA modulo for the Paillier cryptosystems in the system. Then you can run the following protocol: - P1 Paillier-encrypts his value (say a) and sends to P2 - P2 computes (exploiting the additively homomorphic property) E(ab+r mod n) with r chosen in a suitable way (see next). - P1 gets and decrypts s=ab+r mod n Now P1 sets c1= s mod p; P2 sets c2 = - (r mod p); now c1+c2= ab mod p For the protocol to be passive secure, with statistical security k bits, you have to choose r uniformly at random in [0, p^2 + 2^k]. For the protocol to be correct, you need no overflow to happen, so you need n big enough. This shouldn't be a problem as you have probably to choose |n|>1024 bits, and we usually compute in Zp with p almost 160 bits, right? So you have plenty of space for the randomness. Converting this simple protocol to the active case is harder than expected, and I'm working on it right now. I don't think that the ElGamal case is that interesting, as it basically the parties could simply send to each other a,b, and they will get the same result and security (none) in less time :) Claudio On Mon, Jun 23, 2008 at 1:25 PM, Martin Geisler <[EMAIL PROTECTED]> wrote: > 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: > > http://news.gmane.org/gmane.comp.cryptography.viff.patches > > and the introductory mail here: > >> These patches are an example of a runtime for two players based on >> ElGamal. It is not secure, but it is simple :-) >> >> The inspiration for this came from Mikkel who sent me some code that >> implemented the Paillier crypto system, which is additively >> homomorphic. So I figured that I could use this for two player MPC >> by implementing multiplication of additively secret shared values as >> follows: a = a1 + a2 and b = b1 + b2, where Pi has ai and bi. >> >> So >> >> a * b + (a1 + a2) * (b1 + b2) = a1 b1 + a1 b2 + a2 b1 + a2 b2 >> >> which means that the only difficulity is calculating the mixed >> products. But here I figured that P1 could simply send E(a1) to P2 >> who would then use the homomorphic property of the Paillier >> encryption to calculate E(a1 b2) and send that back to P1. Likewise >> for a2 b1. >> >> But with Paillier each player calculates in a different field! So we >> would get (a1 b2) mod m1 and (a2 b1) mod m2 and have no good way of >> combining them... Actually the players would want to calculate >> >> a1 b2 - r and r >> >> such that seeing a1 b2 - r does not reveal anything about b2. >> >> With ElGamal all players can do calculations in the same field, but >> alas, the scheme is multiplicatively homomorphic instead of >> additively homomorphic. So although we can easily calculate a1 b2, >> we cannot easily calculate a1 b2 - r which is needed for security. >> >> I'm posting it anyway so that people can see how one could implement >> something like a two player protocol in VIFF. >> _______________________________________________ >> viff-patches mailing list >> [EMAIL PROTECTED] >> http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk > > -- > Martin Geisler > _______________________________________________ > viff-devel mailing list (http://viff.dk/) > viff-devel@viff.dk > http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk > -- Claudio Orlandi PhD student, Department of Computer Science, Turing-223 Aarhus Universitet, Denmark http://www.daimi.au.dk/~orlandi _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
