Author 
Topic: Secure Multiplication (Read 2081 times) 

nakli
Junior Member
Gender:
Posts: 62


Secure Multiplication
« on: Oct 23^{rd}, 2012, 2:50am » 
Quote Modify

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 ) explanation, the source is http://cstheory.stackexchange.com/questions/10372/securecomputationfor 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 coz we are calculating average.

« Last Edit: Oct 23^{rd}, 2012, 3:14am by nakli » 
IP Logged 
I was born naked on a bed with a lady.



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Secure Multiplication
« Reply #1 on: Oct 25^{th}, 2012, 12:59am » 
Quote Modify

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.


IP Logged 



birbal
Full Member
Gender:
Posts: 250


Re: Secure Multiplication
« Reply #2 on: Oct 28^{th}, 2012, 12:06am » 
Quote Modify

on Oct 25^{th}, 2012, 12:59am, 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].


IP Logged 
The only thing we have to fear is fear itself!



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Secure Multiplication
« Reply #3 on: Oct 28^{th}, 2012, 12:01pm » 
Quote Modify

on Oct 28^{th}, 2012, 12:06am, 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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



