Re: [viff-devel] [PATCH 0 of 4] Insecure ElGamal based two player runtime
Claudio Orlandi [EMAIL PROTECTED] writes: Good morning Claudio! 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 :) Okay, I'll see about implementing this soon. The asymmetry should actually no longer be a problem, the players can communication in any pattern now. Of course, the more complicated this pattern is, the more anoying it is to code, but it is possible :-) 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. Impressive, that is almost a 50% improvement on all figures! Security: - original: computational for both players. - modified: computational for P1, statistical in k for P2. Problems: - it doesn't scale for n2 - it might be complicated to implement it in VIFF, given that this is quite asymmetric while VIFF is highly symmetric. -- 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] [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 n2 - 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
Re: [viff-devel] [PATCH 0 of 4] Insecure ElGamal based two player runtime
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 ___ 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
Ivan Bjerre Damgaard [EMAIL PROTECTED] writes: 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. You're right, I'm pretty sure Claudio would never have known about the ElGamal or the Paillier runtimes otherwise... Maybe there should be a protocol development mail list? I think of this list as the general development list and so also the protocol development list. I got the idea for a separate more code-heavy list since I believe many people wont bother reading code posted here anyway. And I also got the impression that people would hold back with sending in patches since they did not want to disturb the others reading this list. But maybe it's a bad idea to split the attention like that... people interested in VIFF will now sort of have to be part of both lists to be updated with everything that is going on in VIFF. What do people think about this? -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
