Secure Multiplication and Match-Making

[table of contents]

To do general secure computation, we will of course need to do more than secure addition. It turns out that the secret sharing scheme from the previous subsection already allows us to do more: we can also do secure multiplication.


Suppose two numbers a,b \in \mathbb{Z}_p have been secret shared as described above, so that a= a_1+a_2+a_3\bmod p and b= b_1+b_2+b_3\bmod p, and we wish to compute the product ab\bmod p securely. We obviously have

ab= a_1b_1 + a_1b_2+ a_1b_3 +a_2b_1 + a_2b_2+ a_2b_3 + a_3b_1 + a_3b_2+ a_3b_3\bmod p.

It is now easy to see that if the a_i‘s and b_i‘s have been distributed as described above, it is the case that for each product a_i b_j, there is at least one player among the three who knows a_i and b_j and therefore can compute a_i b_j. For instance, \mathsf{P}_1 has been given a_2,a_3,b_2,b_3 and can therefore compute a_2b_2, a_2b_3, a_3b_2 and a_3b_3. The situation is, therefore, that the desired result ab is the sum of some numbers where each summand can be computed by at least one of the players. But now we are essentially done, since from Secure Addition, we already know how to add securely!

The protocol resulting from these observations is shown below. To argue why it works, one first notes that correctness, namely ab= u_1+u_2+u_3 \bmod p, follows trivially from the above. To show that nothing except ab\bmod p is revealed, one notes that nothing new about a,b is revealed in the first step, and because Secure Addition is private, nothing except the sum of the inputs is revealed in the last step, and this sum always equals ab\bmod p.

Secure Multiplication

Participants are \mathsf{P}_1, \mathsf{P}_2, \mathsf{P}_3, input for \mathsf{P}_1 is a\in \mathbb{Z}_p, input for \mathsf{P}_2 is b\in \mathbb{Z}_p, where p is a fixed prime agreed upon in advance. \mathsf{P}_3 has no input.

  1. \mathsf{P}_1 distributes shares a_1,a_2,a_3 of a, while \mathsf{P}_2 distributes shares b_1,b_2,b_3 of b.
  2. \mathsf{P}_1 locally computes u_1= a_2b_2+ a_2b_3+ a_3b_2\bmod p, \mathsf{P}_2 computes u_2= a_3b_3+a_1b_3+ a_3b_1\bmod p, and \mathsf{P}_3 computes u_3= a_1b_1+a_1b_2+a_2b_1\bmod p.
  3. The players use Secure Addition to compute the sum u_1+u_2+u_3\bmod p securely, where \mathsf{P}_i uses u_i as input.

It is interesting to note that even in a very simple case where both a and b are either 0 or 1, secure multiplication has a meaningful application: consider two parties Alice and Bob. Suppose Alice is wondering whether Bob wants to go out with her, and also Bob is asking himself if Alice is interested in him. They would very much like to find out if there is mutual interest, but without running the risk of the embarrassment that would result if for instance Bob just tells Alice that he is interested, only to find that Alice turns him down. The problem can be solved if we let Alice choose a\in \mathbb{Z}_p where a=1 if she is interested in Bob and a=0 otherwise. In the same way, Bob chooses b to be 0 or 1. Then we compute the function f(a,b)= ab\bmod p securely. It is clear that the result is 1 if and only if there is mutual interest. But on the other hand if, for instance, Alice is not interested, she will choose $a=0$ and in this case she learns nothing new from the protocol. To see why, notice that security of the protocol implies that the only (possibly) new information Alice will learn is the result ab\bmod p. But she already knows that result will be 0! In particular, she does not learn whether Bob was interested or not, so Bob is safe from embarrassment. By a symmetric argument, this is of course also the case for Alice.

This argument assumes, of course, that both players choose their inputs honestly according to their real interests. In the following section we discuss what happens if players do not follow the instructions and what we can do about the problems resulting from this.

From Secure Multiplication, we see that if Alice and Bob play the roles of \mathsf{P}_1 and \mathsf{P}_2, respectively, they just need to find a third party to help them, to do the multiplication securely. Note that this third party is not a completely trusted third party of the kind we discussed before: he does not learn anything about a or b other than ab\bmod p. Alice and Bob do have to trust, however, that the third party does not share his information with Bob or with Alice.

It is an obvious question whether one can do secure multiplication such that only Alice and Bob have to be involved? The answer turns out to be yes, but then information theoretic security. Instead one has to use solutions based on cryptography. Such solutions can always be broken if one party has enough computing power, but on the other hand, this is an issue with virtually all the cryptographic techniques we use in practice.

For completeness, we remark that Alice and Bob’s problem is a special case of the so-called match-making problem which has somewhat more serious applications than secure dating. Consider a set of companies where each company has a set of other companies it would prefer to do business with. Now we want that each pair of companies finds out whether there is mutual interest, but without forcing companies to reveal their strategy by announcing their interests in public.

Next we will investigate how to design protocols which remain secure even if some parties try to cheat in the protocols, i.e., we ask the question What if Players Do Not Follow Instructions?

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close