Secure multi-party computations
Secure multi-party computations (also known as multi-party computations (MPC)) is a subfield of cryptography with the goal to create methods for parties to jointly compute a function of their inputs so that certain security properties (like privacy and correctness) are preserved, and keeping these inputs private. Formally a secure multiparty computation protocol for the evaluation of a function f on inputs x1,...,xn is a protocol that outputs f(x1,...,xn), but does not reveal anything more about the inputs x1,...,xn.
In an MPC, a given number of participants p1, p2, ..., pn each have private data, respectively x1, x2, ..., xn. Participants want to compute the value of a public function F on n variables at the point (x1, x2, ..., xn). An MPC protocol is secure, if no participant can learn more from the description of the public function and the result of the global calculation than what he/she can learn from his/her own entry — under particular conditions depending on the model used.
The Figure 1 illustrates how a Secure Multiparty Computation system may look like. In this situation a number of participants submit encrypted information (e.g. bids on an auction). The information is kept encrypted forever and the 5 assigned TTPs (Trusted Third Parties) do the required computations collectively. Only the result is decrypted. As illustrated several of the TTPs may in fact be corrupt without compromising the system (illustrated by the two TTPs with horns). We will consider TTP corrupted if it does not behave consistently with any of its values and yet another TTPs don't not detect it.
Secure computation was formally introduced as secure two-party computation in 1982 by Andrew C. Yao in his work Protocols for secure computations (extended abstract). It is also referred to as Secure function evaluation (SFE), and is concerned with the question: 'Can two party computation be achieved more efficiently and under weaker security assumptions than general MPC?'.
Early on work in cryptography research has demonstrated that every functionality can be computed securely. However, for a long time MPC has been considered too impractical for any real application because of the efficiency overhead that it incurs. In the recent years this perception has gradually started to change and there have been multiple efforts towards implementation of MPC techniques. While these results have demonstrated working implementations of generic MPC protocols, which makes secure computation a much more tangible option for practical solutions, the functionalities and the inputs that these implementations handle are still far from the complexity and scale of many real world systems that need to deal with privacy preserving computation.
For definiteness, suppose Alice has i millions and Bob has j millions, where 1 < i, j < 10. We need a protocol for them to decide whether i < j, such that this is also the only thing they know in the end (aside from their own values). Let M be the set of all N-bit nonnegative integers, and QN be the set of all 1-1 onto functions from M to M. Let Ea be the public key of Alice, generated by choosing a random element from QN . The protocol proceeds as follows:
- Bob picks a random N -bit integer, and computes privately the value of Ea(x); call the result k.
- Bob sends Alice the number k−j+1;
- Alice computes privately the values of yu = Da (k−j+u) for u=1,2,...,10.
- Alice generates a random prime p of N/2 bits, and computes the values zu = yu (mod p) for all u; if all zu differ by at least 2 in the mod p sense, stop; otherwise generates another random prime and repeat the process until all zu differ by at least 2; let p, zu denote this final set of numbers;
- Alice sends the prime p and the following 10 numbers to B: z1, z2,..., zi followed by zi + 1, zi + 1 + 1, . . . , z10 + 1; the above numbers should be interpreted in the mod p sense.
- Bob looks at the j-th number (not counting p) sent from Alice, and decides that i ≥ j if it is equal to x mod p, and i < j otherwise.
- Bob tells Alice what the conclusion is.
This protocol clearly enables Alice and Bob to decide correctly who is the richer person.
There are two other solutions to the millionaires’ problem based on different principles. The first of them assumes that Alice and Bob each owns a private one-way function, where these functions satisfy the commutativity property, i.e. EaEb(x) = EbEa(x). The other solution makes use of a probabilistic encryption method invented by Goldwasser and Micali.
Security in multiparty computations
Let consider the model where an adversarial entity controls some subset of the parties and wishes to attack the protocol execution. The parties under the control of the adversary are called corrupted, and follow the adversary’s instructions. Secure protocols should withstand any adversarial attack. In order to formally claim and prove that a protocol is secure, a precise definition of security for multiparty computation is required. A number of different definitions have been proposed and these definitions aim to ensure a number of important security properties that are general enough to capture most (if not all) multiparty computation tasks.
No party should learn anything more than its prescribed output. In particular, the only information that should be learned about other parties’ inputs is what can be derived from the output itself. For example, in an auction where the only bid revealed is that of the highest bidder, it is clearly possible to derive that all other bids were lower than the winning bid. However, this should be the only information revealed about the losing bids.
Each party is guaranteed that the output that it receives is correct. To continue with the example of an auction, this implies that the party with the highest bid is guaranteed to win, and no party including the auctioneer can alter this.
Independence of Inputs
Corrupted parties must choose their inputs independently of the honest parties’ inputs. This property is crucial in a sealed auction, where bids are kept secret and parties must fix their bids independently of others. We note that independence of inputs is not implied by privacy. For example, it may be possible to generate a higher bid without knowing the value of the original one. Such an attack can actually be carried out on some encryption schemes (i.e., given an encryption of $100, it is possible to generate a valid encryption of $101, without knowing the original encrypted value).
Guaranteed Output Delivery
Corrupted parties should not be able to prevent honest parties from receiving their output. In other words, the adversary should not be able to disrupt the computation by carrying out a “denial of service” attack.
Corrupted parties should receive their outputs if and only if the honest parties also receive their outputs. The scenario where a corrupted party obtains output and an honest party does not should not be allowed to occur. This property can be crucial, for example, in the case of contract signing. Specifically, it would be very problematic if the corrupted party received the signed contract and the honest party did not.
The practical application of multi-party computations
For example, consider the following applications:
- Alice thinks that she may have some genetic disease, and she wants to investigate it herself. She also knows that Bob has a database containing DNA patterns about various diseases. After Alice gets a sample of her DNA sequence, she sends it to Bob, who will then tell Alice the diagnosis. However, if Alice is concerned about her privacy, the above process is not acceptable because it does not prevent Bob from knowing Alice’s private information–both the DNA and the query result.
- After a costly market research, company A decided that expanding its market share in some region will be very beneficial. However A is aware that another competing company B is also planing to expand its market share in some region. Strategically, A and B do not want to compete against each other in the same region, so they want to know whether their regions overlap without giving away location information (not only would disclosure of this information cost both companies a lot of money, it can also cause significant damage to the company if it is disclosed to other parties, e.g. another bigger competitor could then immediately occupy the market there before A or B even starts; or some real estate company could actually raise their price during the negotiation if they know A or B is very interested in that location). Therefore, they need a way to solve the problem while maintaining the privacy of their locations.
- Two financial organizations plan to cooperatively work on a project for their mutual benefit. Each organization would like its own requirements being satisfied (usually, these requirements are modeled as linear equations or linear inequalities). However, their requirements are proprietary data that includes the customer’s projects of the likely future evolution of certain commodity prices, interest and inflation rates, economic statistics, portfolio holdings. Therefore, nobody likes to disclose its requirements to the other party, or even to a “trusted” third party. How could they cooperate on this project while preserving the privacy of the individual information?
The common property of the above three examples is the following: two or more parties want to conduct a computation based on their private inputs, but neither party is willing to disclose its own input to anybody else.
Also multi-party computations are used in:
- Electronic voting
- Elections over the Internet
- Private bidding and auctions
- Privacy-preserving data mining
- Sharing of signature or decryption functions
Go to Bibliography
Back to Table of Contents