Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Suppose there are $N$ parties $p_j$, each with a binary $b_j\in{\{0,1\}}$. The problem needs to compute the multiplication of number of ones times that of zeros, that is, $R=(\sum{b_j})\times(N-\sum{b_j})$.

The computation should be secure in the sense that no party can know more than the final result $R$. For example, it's not ok to perform secure sum, because then $\sum{b_j}$ is known, which is sensitive in my problem. So, is there any existing secure computation protocol that fits my demand?

share|improve this question
    
What if N = 6 and it turns out that R = 9? –  Henrick Hellström Feb 24 '12 at 19:56
    
good point!... but that's just fine to my problem. actually, $\sum{b_j}$ is sensitive only when it's big, like equal to 6. –  Richard Feb 24 '12 at 20:10

2 Answers 2

I'm no expert, but homomorphic encryption may work for this. I believe you can use a system that supports unlimited additions and one multiplication.

share|improve this answer

Well, I am unaware of any published work on this precise problem, however I believe I do have a solution.

First of all, I would note that your problem is equivalent to the problem "if each party has a bit $b_i$, can they securely compute a value $k$ with either $k = \sum b_i$ or $k = N - \sum b_i$ (without giving any further information, including which of those values it might be)". So, we can use a secure sum as part of the solution, as long as we're careful not to give any information about which sum it is.

Here is how my protocol works; it takes 4 rounds and $4N$ messages between party members. In each round, the party members arrange themselves in a cycle; each party member takes a value from the previous party member (or the data from the start of the cycle for the first party member), does some computation on the values, and then passes it along to the next party member. I also do not assume that the message between party members are private.

In an initialization phase, the party members agree on a group where the Diffie-Hellman problem is hard, and two group members $A$ and $B$ such that $A \neq 2^k \cdot B$ and $B \neq 2^k \cdot A$ for any value of $0 \leq k \leq N$ (note: I'm using additive notation for the group, if you're using a multiplicative group, that would normally be written $A \neq B ^ {2^k}$ and $B \neq A ^ {2^k}$)

Now, round 1: we start with the data consisting of the pair $(A, B)$. Each party member takes the pair that they get $(X, Y)$, selects an integer $c_i$, randomly selects either $(c_i \cdot X, c_i \cdot Y)$ or $(c_i \cdot Y, c_i \cdot X)$, and sends that pair to the next party member.

  • The point of this round is that the output from the final party will be either $(c \cdot A, c \cdot B)$ or $(c \cdot B, c \cdot A)$ (for some blinding factor $c$) without anyone being able to determine which.

Now, round 2: we start with the data from the last round. Each party takes the pair they get $(X, Y)$, selects another integer $d_i$, and then if their bit $b_i$ is zero, computes $(2 \cdot d_i \cdot X, d_i \cdot Y)$, and if their bit $b_i$ is one, computes $(d_i \cdot X, 2 \cdot d_i \cdot Y)$, and sends that pair to the next party member

  • The point of this round is to gather the votes; the first of the pair collects the zero vots, and second of the pair collects the one votes (again, with a blinding factor so no one can see what someone else voted).

Now, round 3: we start with the data from the last round. Each party member takes the pair that they get $(X, Y)$, selects an integer $e_i$, randomly selects either $(e_i \cdot X, e_i \cdot Y)$ or $(e_i \cdot Y, e_i \cdot X)$, and sends that pair to the next party member (except the last party member; they random select either $(e_N \cdot X)$ or $(e_N \cdot Y)$ and sends that

  • The point of this round is to disguise which of the pair was the '0' vote, and which was the '1' vote; the last member returns one of them, but no one knows which one it has.

Now, round 4: we start with the data from the last round. Each party member takes the value that they get $(X)$ and removes the blinding factors they applied; that is, computes $((c_i \cdot d_i \cdot e_i) ^ {-1} \cdot X)$, and passes that to the next part member.

The result of the last party member will be either $2^k \cdot A$ or $2^k \cdot B$; we can recover the value $k$ in $\sqrt N$ time, and that is our result.

Note that:

  • It will be $2^k \cdot A$ if an even number of party members decided to swap during round 1, and $2^k \cdot B$ if an odd number decided to swap. Because each party member selected this randomly and independently of anything else, tthis is unbiased, and uncorrelated to anything.

  • The computed $k$ will be $\sum b_i$ if an odd number of party members decided to swap during round 3, and $N - \sum b_i$ if an even number decided to swap (and for the last party member, we count him as swapping if he selected $(e_N \cdot Y)$. Again, because each party member selected this randomly and independently of anything else, this is unbiased, and uncorrelated to anything.

share|improve this answer
    
Thinking about this, I realized that while this protocol works in the "honest but curious" model, it is vulnerable to cheaters which don't follow the protocol. For example, if someone in round 2 gave their output as $(x \cdot X, y \cdot Y)$ (for values of $x$ and $y$ they knew), then the could deduce the value of $\sum b_i$ for everyone else at the end of the protocol. Whether or not this matters would depend on whether this attack model is relevent. –  poncho Feb 24 '12 at 22:49
    
'honest but curious' model is just fine to the problem. –  Richard Feb 24 '12 at 22:57
    
this does not work! 'cause first party can simply know $k$ by comparing the result of round 1 and that of round 2. –  Richard Feb 26 '12 at 7:45
    
There doesn't appear to be a problem. If N=3 (for example), and if the result of round 1 was $(X,Y)$, then the result of round two is $(2^{3-k}d_1 d_2 d_3 \cdot X, 2^k d_1 d_2 d_3 \cdot Y)$, where the first party doesn't know the values $d_2, d_3$. Verifying a guessed value of k would involve solving a decisional Diffie-Hellman problem, and we assumed that they picked a group where that problem was hard. –  poncho Feb 26 '12 at 17:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.