Author |
Topic: Secure Multiplication (Read 2076 times) |
|
nakli
Junior Member
 
Gender: 
Posts: 62
|
 |
Secure Multiplication
« on: Oct 23rd, 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/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 coz we are calculating average.
|
| « Last Edit: Oct 23rd, 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 25th, 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 28th, 2012, 12:06am » |
Quote Modify
|
on Oct 25th, 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 28th, 2012, 12:01pm » |
Quote Modify
|
on Oct 28th, 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print