Re: [viff-devel] VIFF needs at least 3 players always?
There is also an Orlandi runtime and a BeDOZa runtime (under development). They work for 2 parties and guarantee security against active adversaries (paillier.py is only for passive security). Claudio 2010/10/7 Mikkel Krøigård : > Citat af Kyung-Wook Hwang : > >> 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: : 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 >> --- --- >> >> /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 mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] OrlandiRuntime implementation
On Wed, Nov 4, 2009 at 3:18 PM, Marcel Keller wrote: > Claudio Orlandi schrieb: >> >> On Wed, Nov 4, 2009 at 10:15 AM, Marcel Keller wrote: >>> >>> Claudio Orlandi wrote: >>>> >>>> On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller wrote: >>>>> >>>>> Hi Claudio and Jesper, >>>>> >>>>> In the code review of the OrlandiRuntime we found two points, we want >>>>> to >>>>> discuss with you. >>>>> >>>>> Step 3 of the triple generation protocol says: Coin-flip a subset >>>>> \fancy_T >>>>> \subset \fancy_M of size \lambda(2d + 1)M. The current implementation >>>>> loops >>>>> over the elements in \fancy_M and decides fifty-fifty for every element >>>>> whether it should by in \fancy_T until there are enough elements in >>>>> \fancy_T. I however think that this choice should be biased according >>>>> to >>>>> the >>>>> size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be >>>>> put >>>>> in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M >>>>> = >>>>> \lambda / (1 + \lambda). Furthermore, I think the probability should be >>>>> updated whenever \fancy_M is processed completely and \fancy_T still is >>>>> not >>>>> big enough. Maybe it would be easier to choose \lambda(2d + 1)M times >>>>> a >>>>> random element of the remaining ones in \fancy_M instead. >>>> >>>> So you could loop the elements of M and include them in T with >>>> probability \lambda/(1+\lambda), but then you're not guaranteed that >>>> you have enough triplets left in M. >>> >>> Exactly, that's why I suggested the solution which in that case would >>> restart with an adapted probability. >>> >>>> Choosing the right number of >>>> >>>> random elements from M and include them in T is the right choice (or >>>> any solution that guarantees the size of M \ T to be 2(2d+1)M --- I >>>> don't know if the typo is in your email or in Step 3, but the size of >>>> the set M should be (1+\lambda)2(2d+1)M --- you miss a 2. >>> >>> I think the 2 is missing in your report and the code. >>> >> >> Wow. Then it really shouldn't work! >> The factors are: >> 1+lambda : because in the test we check a fraction lambda/1+lambda of >> the triplets >> 2 : because there is a test to check the correctness of the triplets >> that burns one triplet to ensure the other one is good >> 2d+1: because we do the shamir secret sharing multiplication > > Isn't the burning already done in TripleTest, so you really have just > (lambda+1)(2d+1)M triples when doing coin-flipping for the test set? > Oh that's fine. It would also be fine to do the test set first and the TripleTest after. Sorry for the confusion. >> I guess at some point I should also give a look at the code... >> >>>>> In step 6, the implementation generates a distributed random number in >>>>> Z_p >>>>> to determine a partition where one element should be put if there is >>>>> still >>>>> space there. I suggest to use the randomness more efficiently to save >>>>> communication. E.g., if a random number in Z_p is smaller than M^l with >>>>> l >>>>> \le log_M(p), one can extract l random numbers in Z_M. The same method >>>>> probably could be used in step 3 as well. >>>> >>>> Right. Actually if you want to save communication here you can also >>>> use a PRG using the distributed random number as the seed. >>>> >>>>> Best regards, >>>>> Marcel >>>>> >>>> If you have time, there are a lot of things that need to be done here. >>>> I already told Janus knows some of them, but said he can't work on >>>> them. Here is something nice we should do to reduce the online time of >>>> a factor (at least) 3: >>>> >>>> In the protocol there are Pedersen commitemnts with three base element >>>> g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes >>>> g^xh_1^r_1h_2^r_2. The protocol now does it in the following way: >>>> 1) compute a=g^x >>>> 2) compute b=h_1^r_1 >>>> 3) compute c=h_2^r_2 >>>> 4) co
Re: [viff-devel] OrlandiRuntime implementation
On Wed, Nov 4, 2009 at 10:15 AM, Marcel Keller wrote: > Claudio Orlandi wrote: >> >> On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller wrote: >>> >>> Hi Claudio and Jesper, >>> >>> In the code review of the OrlandiRuntime we found two points, we want to >>> discuss with you. >>> >>> Step 3 of the triple generation protocol says: Coin-flip a subset >>> \fancy_T >>> \subset \fancy_M of size \lambda(2d + 1)M. The current implementation >>> loops >>> over the elements in \fancy_M and decides fifty-fifty for every element >>> whether it should by in \fancy_T until there are enough elements in >>> \fancy_T. I however think that this choice should be biased according to >>> the >>> size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be >>> put >>> in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M = >>> \lambda / (1 + \lambda). Furthermore, I think the probability should be >>> updated whenever \fancy_M is processed completely and \fancy_T still is >>> not >>> big enough. Maybe it would be easier to choose \lambda(2d + 1)M times a >>> random element of the remaining ones in \fancy_M instead. >> >> So you could loop the elements of M and include them in T with >> probability \lambda/(1+\lambda), but then you're not guaranteed that >> you have enough triplets left in M. > > Exactly, that's why I suggested the solution which in that case would > restart with an adapted probability. > >> Choosing the right number of >> >> random elements from M and include them in T is the right choice (or >> any solution that guarantees the size of M \ T to be 2(2d+1)M --- I >> don't know if the typo is in your email or in Step 3, but the size of >> the set M should be (1+\lambda)2(2d+1)M --- you miss a 2. > > I think the 2 is missing in your report and the code. > Wow. Then it really shouldn't work! The factors are: 1+lambda : because in the test we check a fraction lambda/1+lambda of the triplets 2 : because there is a test to check the correctness of the triplets that burns one triplet to ensure the other one is good 2d+1: because we do the shamir secret sharing multiplication I guess at some point I should also give a look at the code... >>> In step 6, the implementation generates a distributed random number in >>> Z_p >>> to determine a partition where one element should be put if there is >>> still >>> space there. I suggest to use the randomness more efficiently to save >>> communication. E.g., if a random number in Z_p is smaller than M^l with l >>> \le log_M(p), one can extract l random numbers in Z_M. The same method >>> probably could be used in step 3 as well. >> >> Right. Actually if you want to save communication here you can also >> use a PRG using the distributed random number as the seed. >> >>> Best regards, >>> Marcel >>> >> >> If you have time, there are a lot of things that need to be done here. >> I already told Janus knows some of them, but said he can't work on >> them. Here is something nice we should do to reduce the online time of >> a factor (at least) 3: >> >> In the protocol there are Pedersen commitemnts with three base element >> g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes >> g^xh_1^r_1h_2^r_2. The protocol now does it in the following way: >> 1) compute a=g^x >> 2) compute b=h_1^r_1 >> 3) compute c=h_2^r_2 >> 4) compute d=a*b*c >> >> The complexity is dominated by the three exponentiation, that one >> implements using some ladder (square and multiply) >> >> There is no need to do three exponentiation if one does something a bit >> smarter: >> - precompute >> g001=g^0h_1^0h_2^1 >> g010=g^0h_1^1h_2^0 >> ... >> g010=g^1h_1^1h_2^1 >> >> Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking >> comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this >> is just one ladder, so virtually the same as just one of the above >> exponentiation. >> >> One can go further and precompute more elements, for instance >> g000 >> ... >> g333 >> And now you look at 2 bits of x,r_1,r_2 for every square in the >> square-and-multiply. This saves another factor 2 in time but you need >> to store a bigger table of size 8^2. >> >> What is the best strategy given our architecture? How many powers >> should we precompute? > > The commitments are computed by an external elliptic curve library, so I > can't answer anything here. Janus should know more about it. > Actually i think that the elliptic curve library offers method for square, multiply, and a multiplication, not for the commitments as an object... I seem to remember that Janus implemented them. > Regards, > Marcel > > ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] OrlandiRuntime implementation
On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller wrote: > Hi Claudio and Jesper, > > In the code review of the OrlandiRuntime we found two points, we want to > discuss with you. > > Step 3 of the triple generation protocol says: Coin-flip a subset \fancy_T > \subset \fancy_M of size \lambda(2d + 1)M. The current implementation loops > over the elements in \fancy_M and decides fifty-fifty for every element > whether it should by in \fancy_T until there are enough elements in > \fancy_T. I however think that this choice should be biased according to the > size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be put > in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M = > \lambda / (1 + \lambda). Furthermore, I think the probability should be > updated whenever \fancy_M is processed completely and \fancy_T still is not > big enough. Maybe it would be easier to choose \lambda(2d + 1)M times a > random element of the remaining ones in \fancy_M instead. So you could loop the elements of M and include them in T with probability \lambda/(1+\lambda), but then you're not guaranteed that you have enough triplets left in M. Choosing the right number of random elements from M and include them in T is the right choice (or any solution that guarantees the size of M \ T to be 2(2d+1)M --- I don't know if the typo is in your email or in Step 3, but the size of the set M should be (1+\lambda)2(2d+1)M --- you miss a 2. > In step 6, the implementation generates a distributed random number in Z_p > to determine a partition where one element should be put if there is still > space there. I suggest to use the randomness more efficiently to save > communication. E.g., if a random number in Z_p is smaller than M^l with l > \le log_M(p), one can extract l random numbers in Z_M. The same method > probably could be used in step 3 as well. Right. Actually if you want to save communication here you can also use a PRG using the distributed random number as the seed. > Best regards, > Marcel > If you have time, there are a lot of things that need to be done here. I already told Janus knows some of them, but said he can't work on them. Here is something nice we should do to reduce the online time of a factor (at least) 3: In the protocol there are Pedersen commitemnts with three base element g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes g^xh_1^r_1h_2^r_2. The protocol now does it in the following way: 1) compute a=g^x 2) compute b=h_1^r_1 3) compute c=h_2^r_2 4) compute d=a*b*c The complexity is dominated by the three exponentiation, that one implements using some ladder (square and multiply) There is no need to do three exponentiation if one does something a bit smarter: - precompute g001=g^0h_1^0h_2^1 g010=g^0h_1^1h_2^0 ... g010=g^1h_1^1h_2^1 Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this is just one ladder, so virtually the same as just one of the above exponentiation. One can go further and precompute more elements, for instance g000 ... g333 And now you look at 2 bits of x,r_1,r_2 for every square in the square-and-multiply. This saves another factor 2 in time but you need to store a bigger table of size 8^2. What is the best strategy given our architecture? How many powers should we precompute? Claudio ___ 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
Correct! On Thu, Oct 22, 2009 at 11:17 AM, 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] Homomorphic encryption
Hi Marc, Let me see if I understood the way you measured: it takes 496 msec on average to do an encryption with your code, right? Claudio On Fri, Jul 10, 2009 at 10:18 AM, Marc Makkes wrote: > Hi Janus, > > I think that I'd have reached the stage where you can test my code, but > still lacks some basic checks and is still prone to timing attacks and > is basically the same viffs current implementation, with some additional > speedups. So consequently, it code should only be used for testing purposes > only. > > I'm achieving the following speeds on my atom N270 ( 1.6Ghz ) testing > with key sizes of 2048 bit. > > Viff code: > -- > Encrypting: > 10 loops, best of 3: 4.42 sec per loop > Decrypting: > 10 loops, best of 3: 925 msec per loop > > My code: > > Encrypting: > 10 loops, best of 3: 496 msec per loop > Decrypting: > 10 loops, best of 3: 143 msec per loop > > For encrypting its almost a 9 fold speedup and for decrypting 6.5 times > with respect to the current implementation. > > In the tar ball you find the small makefile as well as a test.py file. > It shows the basic use of all functions. If you have any comments, issues > or questions please let me know. > > Happy testing, > > -Marc > > ___ > 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
Re: [viff-devel] Off topic question "multiparty" or "multi-party"
> I still insist on using "MP" as an abbreviation, just like you would > abbreviate "database" as "DB" and not just "D". So for me it's "SMPC" > and not just "SMC". I vote for MPC. It sounds better when you pronounce it. -- 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
Re: [viff-devel] Off topic question "multiparty" or "multi-party"
> I still insist on using "MP" as an abbreviation, just like you would > abbreviate "database" as "DB" and not just "D". So for me it's "SMPC" > and not just "SMC". I vote for MPC. It sounds better when you pronounce it. -- 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
Re: [viff-devel] New passive multiplication protocol (was: FW: Bug in ViFF)
Where is a description of the new protocol? > 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"? :) -- 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
Re: [viff-devel] Speed of ElGamal encryption
Could everyone specify the size of the field and the size of the secret keys used? Otherwise it's quite hard to understand the performance reported. Regards, Claudio On Sun, Sep 21, 2008 at 4:59 PM, Adam Langley <[EMAIL PROTECTED]> wrote: > On Sun, Sep 21, 2008 at 3:23 AM, Martin Geisler <[EMAIL PROTECTED]> wrote: >> Calling a ElGamal function in NaCl would be very cool and probably a bit >> faster since you wont have to do all the tuple packing and unpacking >> that you do in the Python version. > > NaCl has support for a primitive called a 'box'. The boxing function > takes these inputs: > * The message > * An nonce > * The recipient's public key > * The sender's private key > > Note that requiring the sender's private key makes this different from > most public key encryption functions. The unboxing function, > symmetrically, requires the sender's public key. (This boxing function > may be viewed as a encrypt+sign operation.) > > If this fits your model, then NaCl already contains everything you > need. In this case, the underlying primitive is not ElGamel, but > Diffie-Hellman. The two keys are combined with ECDH and the nonce > (which both sides must know, but need not be secret) diversifies the > long-term shared key into a per-message key. > > Based on timings for the x86-64 ECDH implementation, which I wrote, > 4*10^6 operations should take about 880 seconds for a short message. > > > AGL > > -- > Adam Langley [EMAIL PROTECTED] http://www.imperialviolet.org > ___________ > 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
Re: [viff-devel] [PATCH 0 of 4] Insecure ElGamal based two player runtime
One of the two is not a real issues: in fact we can implement this in VIFF as a "symmetric" protocol. Basically we just run 2 multiplication at once :) So we can interleave this protocol with one where P1,P2 want to compute shares of z=xy, and where P2 plays the role of P1. This should increase the effiency even more, as the parties don't have any more idle time. Claudio On Mon, Jun 30, 2008 at 10:26 AM, Claudio Orlandi <[EMAIL PROTECTED]> wrote: > It seems ok to me. > I just think that we can improve effiency (and security) a bit if we > do like this: > > P1 computes: > - A1= Enc(a1), B1=Enc(b1) > - Send A1,B1 to P2 > P2 computes: > - C1=A1^b2 * B1^a2 * Enc(r) // r random in [0, 2p^2 + 2^k] k security > parameter > - c2= a2b2 - (r mod p) mod p > - Send C1 to P1 > P1 computes: > - c1 = Dec(C1) + a1b1 mod p > > Now c1+c2=c=ab=(a1+a2)(b1+b2) > > Efficiency: in this way we reduced from: > - Encryptions: from 6 to 3 encryptions > - Decryptions: from 2 to 1 decryptions > - Communication: from 4 to 3 ciphertext > - Generated random numbers: from 2 to 1 > - Key pair needed: from 2 to 1. > > Security: > - original: computational for both players. > - modified: computational for P1, statistical in k for P2. > > Problems: > - it doesn't scale for n>2 > - it might be complicated to implement it in VIFF, given that this is > quite asymmetric while VIFF is highly symmetric. > > Claudio > > On Sun, Jun 29, 2008 at 2:15 PM, Martin Geisler <[EMAIL PROTECTED]> wrote: >> "Claudio Orlandi" <[EMAIL PROTECTED]> writes: >> >> Hi Claudio >> >>> if you are interested just in passive security for the 2 party case >>> you can implement the following protocol for multiplication. >> >> You never commented on my implementation of your multiplication >> protocol -- is there anything I should know security-wise before >> including it in VIFF proper? >> >> I did a simple benchmark with 10 multiplications and a multiplication >> takes about *3 seconds* when I run both playes on the same laptop. I >> have not yet tested on the DAIMI machines we normally compare with. >> >> The updated code is here: >> >> http://thread.gmane.org/gmane.comp.cryptography.viff.patches/14 >> >> -- >> Martin Geisler >> > > > > -- > Claudio Orlandi > > PhD student, > Department of Computer Science, Turing-223 > Aarhus Universitet, Denmark > http://www.daimi.au.dk/~orlandi > -- 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
Re: [viff-devel] [PATCH 0 of 4] Insecure ElGamal based two player runtime
It seems ok to me. I just think that we can improve effiency (and security) a bit if we do like this: P1 computes: - A1= Enc(a1), B1=Enc(b1) - Send A1,B1 to P2 P2 computes: - C1=A1^b2 * B1^a2 * Enc(r) // r random in [0, 2p^2 + 2^k] k security parameter - c2= a2b2 - (r mod p) mod p - Send C1 to P1 P1 computes: - c1 = Dec(C1) + a1b1 mod p Now c1+c2=c=ab=(a1+a2)(b1+b2) Efficiency: in this way we reduced from: - Encryptions: from 6 to 3 encryptions - Decryptions: from 2 to 1 decryptions - Communication: from 4 to 3 ciphertext - Generated random numbers: from 2 to 1 - Key pair needed: from 2 to 1. Security: - original: computational for both players. - modified: computational for P1, statistical in k for P2. Problems: - it doesn't scale for n>2 - it might be complicated to implement it in VIFF, given that this is quite asymmetric while VIFF is highly symmetric. Claudio On Sun, Jun 29, 2008 at 2:15 PM, Martin Geisler <[EMAIL PROTECTED]> wrote: > "Claudio Orlandi" <[EMAIL PROTECTED]> writes: > > Hi Claudio > >> if you are interested just in passive security for the 2 party case >> you can implement the following protocol for multiplication. > > You never commented on my implementation of your multiplication > protocol -- is there anything I should know security-wise before > including it in VIFF proper? > > I did a simple benchmark with 10 multiplications and a multiplication > takes about *3 seconds* when I run both playes on the same laptop. I > have not yet tested on the DAIMI machines we normally compare with. > > The updated code is here: > > http://thread.gmane.org/gmane.comp.cryptography.viff.patches/14 > > -- > Martin Geisler > -- 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
[viff-devel] Elliptic curves
> >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. It's also about security. I would like an implementation that deals, at least, with the most common side-channel attacks. Other issues are which curve do you use, which kind of point representation, ... > Yes, one can do that. But then people would need to install the > library on their machine to use VIFF. If the library provided binaries > for Windows then it's no problem, but for a smaller library there > might not be much Windows support. So Micheal used mostly pairing-friendly curves, that is really what we don't want here. Anyway, he suggested to have a look at the MIRACL library. The problem with this one is that is not open source, it's free just if you use it for fun... ___ 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
> 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. Claudio ___ 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 (was: [PATCH 0 of 4] Insecure ElGamal based two player runtime)
>> Converting this simple protocol to the active case is harder than >> expected, and I'm working on it right now. > > Great, I'm looking forward to it! :-) > Well, if you have a lot of spare time you can start some preprocessing :) In particular, I guess that the active protocol will almost surely need some commitment schemes. And to make them as efficient as we can, we will probably use some elliptic curves over Zp with p around 160 bits. Isn't it cool that 160bits is at the same time the size we need for security AND to avoid the overflows in the computation? :) Claudio ___ 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
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
