wu :: forums « wu :: forums - Secure Multiplication » Welcome, Guest. Please Login or Register. Sep 12th, 2024, 11:11am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: william wu, ThudnBlunder, Icarus, SMQ, Grimbal, towr, Eigenray)    Secure Multiplication « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Secure Multiplication  (Read 2081 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »