wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Secure Multiplication
        
(Message started by: nakli on Oct 23^rd, 2012, 2:50am)

Title: Secure Multiplication
Post by nakli on Oct 23^rd, 2012, 2:50am

N people are each holding either 0 or 1 in their minds.
We need to securely calculate the product of total number of 1s with total number of 0s, but no one should get to know anyone else's number. Also Sum of all (representing the total number of 1s) is sensitive and no one should get to know that too.

R = (sum of all) x (N - sum of all)

Everyone should get to know R only. Take 2 cases, First, no one should also get to know the total number of people N. Case 2, N can be revealed.

For a more mathematical (and perhaps clearer for some :P) explanation, the source is http://cstheory.stackexchange.com/questions/10372/secure-computation-for-multiplication

On first reading it it looks to me like an advanced version of 'calculating average salary' problem. There N is not revealed but the 'sum' is revealed. It has to be :P coz we are calculating average.

Title: Re: Secure Multiplication
Post by Grimbal on Oct 25^th, 2012, 12:59am

If you have
R = k x (N - k)
you can rewrite it
k^2 + N*k - R = 0
and you can determine k down to 2 possibilities.

So the problem is to hide which one of the 2 it is.

Title: Re: Secure Multiplication
Post by birbal on Oct 28^th, 2012, 12:06am

on 10/25/12 at 00:59:10, Grimbal wrote:

If you have
R = k x (N - k)
you can rewrite it
k^2 + N*k - R = 0
and you can determine k down to 2 possibilities.

So the problem is to hide which one of the 2 it is.

Could you explain in more detail with an example. Lets say we have numbers like [1,0,0,0,1,1,0,0,0,1].

Title: Re: Secure Multiplication
Post by towr on Oct 28^th, 2012, 12:01pm

on 10/28/12 at 00:06:11, birbal wrote:

Could you explain in more detail with an example. Lets say we have numbers like [1,0,0,0,1,1,0,0,0,1].

Then you have N = 10, R = 4x6 = 24
If you solve k^2 + 10k - 24 = 0, you get k=4 or k=6, so you know the number of ones is one of those two.

It's less of a problem when you don't know N, but since there's only a limited number of factorizations of R, you still have relatively much information about it when R is small.