Secure multi-party computation

Secure multi-party computation (also known as secure computation or multi-party computation/MPC) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private.

Definition and overview

In an MPC, a given number of participants, p1, p2, ..., pN, each have private data, respectively d1, d2, ..., dN. Participants want to compute the value of a public function on that private data: F(d1, d2, ..., dN) while keeping their own inputs secret.

For example, suppose we have three parties Alice, Bob and Charlie, with respective inputs x, y and z denoting their salaries. They want to find out the highest of the three salaries, without revealing to each other how much each of them makes. Mathematically, this translates to them computing:

F(x,y,z) = max(x,y,z)

If there were some trusted outside party (say, they had a mutual friend Tony who they knew could keep a secret), they could each tell their salary to Tony, he could compute the maximum, and tell that number to all of them. The goal of MPC is to design a protocol, where, by exchanging messages only with each other, Alice, Bob, and Charlie can still learn F(x, y, z) without revealing who makes what and without having to rely on Tony. They should learn no more by engaging in their protocol than they would learn by interacting with an incorruptible, perfectly trustworthy Tony.

In particular, all that the parties can learn is what they can learn from the output and their own input. So in the above example, if the output is z, then Charlie learns that his z is the maximum value, whereas Alice and Bob learn (if x, y and z are distinct), that their input is not equal to the maximum, and that the maximum held is equal to z. The basic scenario can be easily generalised to where the parties have several inputs and outputs, and the function outputs different values to different parties.

Informally speaking, the most basic properties that a multi-party computation protocol aims to ensure are:

There are a wide range of practical applications, varying from simple tasks such as coin tossing to more complex ones like electronic auctions (e.g. compute the market clearing price), electronic voting, or privacy-preserving data mining. A classical example is the Millionaire's Problem: two millionaires want to know who is richer, in such a way that neither of them learns the net worth of the other. A solution to this situation is essentially to securely evaluate the comparison function.

Security definitions

A key question to ask is; when is such a multiparty computation protocol secure? In modern cryptography, a protocol can only be deemed to be secure if it comes equipped with a "security proof". This is a mathematical proof that the security of the protocol reduces to that of the security of the underlying primitives. But this means we need a definition of what it means for a protocol to be secure. This is hard to formalize, in the case of MPC, since we cannot say that the parties should "learn nothing" since they need to learn the output and this depends on the inputs. In addition, we cannot just say that the output must be "correct" since the correct output depends on the parties’ inputs, and we do not know what inputs corrupted parties will use. A formal mathematical definition of security for MPC protocols follows the ideal-real-world paradigm, described below.

The ideal-real-world paradigm imagines two worlds. In the ideal world, there exists an incorruptible trusted party to whom each protocol participant sends its input. This trusted party computes the function on its own and sends back the appropriate output to each party. (In the Alice, Bob, and Charlie example above, Tony performed the role of trusted outside party.) In contrast, in the real-world model, there is no trusted party and all the parties can do is to exchange messages with each other. We say a protocol is secure if one can learn no more about each party's private inputs in the real world than one could learn in the ideal world. Since no messages between the parties are exchanged in the ideal world, this security definition implies that the real-world messages that were exchanged cannot have revealed any secret information.

We stress that the ideal-real-world paradigm provides a simple abstraction of the complexities of MPC that is of great use to anyone using an MPC protocol. Namely, it suffices to construct an application under the pretense that the MPC protocol at its core is actually an ideal execution. If the application is secure in this case, then it is also secure when a real protocol is run instead.

The security requirements on an MPC protocol are so stringent that it may seem that it is rarely possible to actually achieve. Surprisingly, in the late 1980s it was already shown that any function can be securely computed, with security for malicious adversaries.[1][2] This is encouraging news, but it took a long time until MPC became efficient enough to be used in practice. Unconditionally or information-theoretically secure MPC is closely related to the problem of secret sharing, and more specifically verifiable secret sharing (VSS), which many secure MPC protocols that protect against active adversaries use.

Unlike in traditional cryptographic applications, such as encryption or signatures, the adversary in an MPC protocol can be one of the players engaged in the protocol. In fact, in MPC we assume that corrupted parties may collude in order to breach the security of the protocol. If the number of parties in the protocol is n, then the number of parties who can be adversarial is usually denoted by t. The protocols and solutions for the case of t < n/2 (i.e., when an honest majority is assumed) are very different to those where no such assumption is made. This latter case includes the important case of two-party computation where one of the participants may be corrupted, and the general case where an unlimited number of participants are corrupted and collude to attack the honest participants.

Different protocols can deal with different adversarial powers. We can categorize adversaries according to how willing they are to deviate from the protocol. There are essentially two types of adversaries, each giving rise to different forms of security:

Since security against active adversaries is often only possible at the cost of reducing efficiency one is led to consider a relaxed form of active security called covert security, proposed by Aumann and Lindell.[3] Covert security captures more realistic situations, where active adversaries are willing to cheat but only if they are not caught. For example, their reputation could be damaged, preventing future collaboration with other honest parties. Thus, protocols that are covertly secure provide mechanisms to ensure that, if some of the parties do not follow the instructions, then it will be noticed with high probability, say 75% or 90%. In a way, covert adversaries are active ones forced to act passively due to external non-cryptographic (e.g. business) concerns. This sets a bridge between the two models in the hope of finding protocols, which are efficient yet secure enough for practice.

Like many cryptographic protocols, the security of an MPC protocol can rely on different assumptions:

The set of honest parties that can execute a computational task is related to the concept of access structure. "Adversary structures" can be static, i.e. the adversary chooses its victims before the start of the multi-party computation, or dynamic, i.e. it chooses its victims during the course of execution of the multiparty computation. Attaining security against a dynamic adversary is often much harder than security against a static adversary. An adversary structure can be defined as a "threshold structure" meaning that it can corrupt or simply read the memory of a number of participants up to some threshold, or be defined as a more complex structure, where it can affect certain predefined subsets of participants, modeling different possible collusions.

History

Secure computation was formally introduced as secure two-party computation (2PC) in 1982 by Andrew Yao,[4] the first recipient of the Knuth Prize. 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?'. The millionaire problem solution gave way to a generalization to multi-party protocols.[1][2]

Increasingly efficient protocols for MPC have been proposed, and MPC can be now used as a practical solution to various real-life problems such as distributed voting, private bidding and auctions, sharing of signature or decryption functions and private information retrieval.[5] The first large-scale and practical application of multiparty computation took place in Denmark in January 2008.[6]

Protocols used

There are major differences between the protocols proposed for two party computation (2PC) and multiparty computation (MPC).

Two-party computation

Main article: Garbled Circuit

The two party setting is particularly interesting, not only from an applications perspective but also because special techniques can be applied in the two party setting which do not apply in the multi-party case. Indeed, secure multi-party computation (in fact the restricted case of secure function evaluation, where only a single function is evaluated) was first presented in the two-party setting. The original work is often cited as being from one of the two papers of Yao; although the papers do not actually contain what is now known as Yao's garbled circuit protocol.

Yao’s basic protocol is secure against semi-honest adversaries and is extremely efficient in terms of number of rounds, which is constant, and independent of the target function being evaluated. The function is viewed as a Boolean circuit, with inputs in binary of fixed length. A Boolean circuit is a collection of gates connected with three different types of wires: circuit-input wires, circuit-output wires and intermediate wires. Each gate receives two input wires and it has a single output wire which might be fan-out (i.e. be passed to multiple gates at the next level). Plain evaluation of the circuit is done by evaluating each gate in turn; assuming the gates have been lexicographically ordered. The gate is represented as a truth table such that for each possible pair of bits (those coming from the input wires' gate) the table assigns a unique output bit; which is the value of the output wire of the gate. The results of the evaluation are the bits obtained in the circuit-output wires.

Yao explained how to garble a circuit (hide its structure) so that two parties, sender and receiver, can learn the output of the circuit and nothing else. At a high level, the sender prepares the garbled circuit and sends it to the receiver, who obliviously evaluates the circuit, learning the encodings corresponding to both his and the senders output. He then just sends back the senders encodings, allowing the sender to compute his part of the output. The sender sends the mapping from the receivers output encodings to bits to the receiver, allowing the receiver to obtain their output.

In more detail, the garbled circuit is computed as follows. The main ingredient is a double-keyed symmetric encryption scheme. Given a gate of the circuit, each possible value of its input wires (either 0 or 1) is encoded with a random number (label). The values resulting from the evaluation of the gate at each of the four possible pair of input bits are also replaced with random labels. The garbled truth table of the gate consists of encryptions of each output label using its inputs labels as keys. The position of these four encryptions in the truth table is randomized so no information on the gate is leaked.

To correctly evaluate each garbled gate the encryption scheme has the following two properties. Firstly, the ranges of the encryption function under any two distinct keys are disjoint (with overwhelming probability). The second property says that it can be checked efficiently whether a given ciphertext has been encrypted under a given key. With these two properties the receiver, after obtaining the labels for all circuit-input wires, can evaluate each gate by first finding out which of the four ciphertexts has been encrypted with his label keys, and then decrypting to obtain the label of the output wire. This is done obliviously as all the receiver learns during the evaluation are encodings of the bits.

The sender’s (i.e. circuit creators) input bits can be just sent as encodings to the evaluator; whereas the receiver’s (i.e. circuit evaluators) encodings corresponding to his input bits are obtained via a 1-out-of-2 Oblivious Transfer (OT) protocol. A 1-out-of-2 OT protocol, enables the sender, in possession of two values C1 and C2, to send the one requested by the receiver (b a value in {1,2}) in such a way that the sender does not know what value has been transferred, and the receiver only learns the queried value.

If one is considering malicious adversaries, further mechanisms to ensure correct behaviour of both parties need to be provided. By construction it is easy to show security for the sender, as all the receiver can do is to evaluate a garbled circuit that would fail to reach the circuit-output wires if he deviated from the instructions. The situation is very different on the sender's side. For example, he may send an incorrect garbled circuit that computes a function revealing the receiver's input. This would mean that privacy no longer holds, but since the circuit is garbled the receiver would not be able to detect this.

Multiparty protocols

Most MPC protocols, as opposed to 2PC protocols, make use of secret sharing. In the secret sharing based methods, the parties do not play special roles (as in Yao, of creator and evaluator). Instead the data associated to each wire is shared amongst the parties; and a protocol is then used to evaluate each gate. The function is now defined as a “circuit” over GF(p), as opposed to the binary circuits used for Yao. Such a circuit is called an arithmetic circuit in the literature, and it consists of addition and multiplication “gates” where the values operated on are defined over GF(p).

Secret sharing allows one to distribute a secret among a number of parties by distributing shares to each party. Three types of secret sharing schemes are commonly used; Shamir Secret Sharing, Replicated Secret Sharing and Additive Secret Sharing. In all three cases the shares are random elements of GF(p) that add up to the secret in GF(p); intuitively, security steams because any non-qualifying set shares looks randomly distributed. All three secret sharing schemes are linear, so the sum of two shared secrets, or multiplication a secret by a public constant, can be done locally. Thus linear functions can be evaluated for free.

Replicated Secret Sharing schemes are usually associated with passively secure MPC systems consisting of three parties, of which at most one can be adversarial; such as used in the Sharemind system. MPC systems based on Shamir Secret Sharing are generally associated with systems which can tolerate up to t adversaries out of n, so called threshold systems. In the case of information theoretic protocols actively secure protocols can be realised with Shamir Secret Sharing sharing if t<n/3, whilst passively secure ones are available if t<n/2. In the case of computationally secure protocols one can tolerate a threshold of t<n/2 for actively secure protocols. A practical system adopting this approach is the VIFF framework. Additive secret sharing is used when one wants to tolerate a dishonest majority, i.e. t<n, in which case we can only obtain MPC protocols "with abort", this later type is typified by the SPDZ[7] and (multi-party variant) of the TinyOT protocol.[8]

Other protocols

Virtual Party Protocol is a protocol which uses virtual parties and complex mathematics to hide the identity of the parties.[9]

Secure sum protocols allow multiple cooperating parties to compute sum function of their individual data without revealing the data to one another.[10]

In 2014 a "model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty" has been described for the Bitcoin network or for fair lottery.[11]

Scalable MPC

Recently, several multi-party computation techniques have been proposed targeting resource-efficiency (in terms of bandwidth, computation, and latency) for large networks. Although much theoretical progress has been made to achieve scalability, practical progress is slower. In particular, most known schemes suffer from either poor or unknown communication and computation costs in practice.[12]

Practical MPC systems

Many advances have been made on 2PC and MPC systems in recent years.

Yao-based protocols

One of the main issues when working with Yao-based protocols is that the function to be securely evaluated (which could be an arbitrary program) must be represented as a circuit, usually consisting of XOR and AND gates. Since most real-world programs contain loops and complex data structures, this is a highly non-trivial task. The Fairplay system[13] was the first tool designed to tackle this problem. Fairplay comprises two main components. The first of these is a compiler enabling users to write programs in a simple high-level language, and output these programs in a Boolean circuit representation. The second component can then garble the circuit and execute a protocol to securely evaluate the garbled circuit. As well as two-party computation based on Yao's protocol, Fairplay can also carry out multi-party protocols. This is done using the BMR protocol,[13] which extends Yao's passively secure protocol to the active case.

In the years following the introduction of Fairplay, many improvements to Yao's basic protocol have been created, in the form of both efficiency improvements and techniques for active security. These include techniques such as the free XOR method, which allows for much simpler evaluation of XOR gates, and garbled row reduction, reducing the size of garbled tables with two inputs by 25%.[14]

The approach that so far seems to be the most fruitful in obtaining active security comes from a combination of the garbling technique and the “cut-and-choose” paradigm. This combination seems to render more efficient constructions. To avoid the aforementioned problems with respect to dishonest behaviour, many garblings of the same circuit are sent from the constructor to the evaluator. Then around half of them (depending on the specific protocol) are opened to check consistency, and if so a vast majority of the unopened ones are correct with high probability. The output is the majority vote of all the evaluations. Note that here the majority output is needed. If there is disagreement on the outputs the receiver knows the sender is cheating, but he cannot complain as otherwise this would leak information on his input.

This approach for active security was initiated by Lindell and Pinkas.[15] This technique was implemented by Pinkas et al. in 2009,[14] This provided the first actively secure two-party evaluation of the Advanced Encryption Standard (AES) circuit, regarded as a highly complex (consisting of around 30,000 AND and XOR gates), non-trivial function (also with some potential applications), taking around 20 minutes to compute and requiring 160 circuits to obtain a 2-40 cheating probability.

As many circuits are evaluated, the parties (including the receiver) need to commit to their inputs to ensure that in all the iterations the same values are used. The experiments of Pinkas et al. reported[14] show that the bottleneck of the protocol lies in the consistency checks. They had to send over the net about 6,553,600 commitments to various values to evaluate the AES circuit. In recent results[16] the efficiency of actively secure Yao-based implementations was improved even further, requiring only 40 circuits, and much less commitments, to obtain 2-40 cheating probability. The improvements come from new methodologies for performing cut-and-choose on the transmitted circuits.

More recently, there has been a focus on highly parallel implementations based on garbled circuits, designed to be run on CPUs with many cores. Kreuter, et al.[17] describe an implementation running on 512 cores of a powerful cluster computer. Using these resources they could evaluate the 4095-bit edit distance function, whose circuit comprises almost 6 billion gates. To accomplish this they developed a custom, better optimized circuit compiler than Fairplay and several new optimizations such as pipelining, whereby transmission of the garbled circuit across the network begins while the rest of the circuit is still being generated. The time to compute AES was reduced to 1.4 seconds per block in the active case, using a 512-node cluster machine, and 115 seconds using one node. shelat and Shen[18] improve this, using commodity hardware, to 0.52 seconds per block. The same paper reports on a throughput of 21 blocks per second, but with a latency of 48 seconds per block.

Meanwhile, another group of researchers has investigated using consumer-grade GPUs to achieve similar levels of parallelism.[19] They utilize OT extensions and some other novel techniques to design their GPU-specific protocol. This approach seems to achieve comparable efficiency to the cluster computing implementation, using a similar number of cores. However, the authors only report on an implementation of the AES circuit, which has around 50,000 gates. On the other hand, the hardware required here is far more accessible, as similar devices may already be found in many people's desktop computers or games consoles. The authors obtain a timing of 2.7 seconds per AES block on a standard desktop, with a standard GPU. If they allow security to decrease to something akin to covert security, they obtain a run time of 0.30 seconds per AES block.It should be noted that in the passive security case there are reports of processing of circuits with 250 million gates, and at a rate of 75 million gates per second.[20]

See also

References

  1. 1 2 D. Chaum, C. Crepeau & I. Damgard. "Multiparty unconditionally secure protocols". STOC 1987.
  2. 1 2 O. Goldreich, S. Micali & A. Wigderson. "How to play any mental game or a completeness theorem for protocols with honest majority". STOC 1987.
  3. ↑ Y. Lindell & Y. Aumann. "Security against covert adversaries". TCC 2007.
  4. ↑ Andrew C. Yao, Protocols for secure computations (extended abstract)
  5. ↑ Claudio Orlandi: Is multiparty computation any good in practice?, ICASSP 2011
  6. ↑ Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, Jesper Buus Nielsen, Kurt Nielse, Jakob Pagter, Michael Schwartzbach and Tomas Toft (2008). "Multiparty Computation Goes Live". Cryptology ePrint Archive (Report 2008/068).
  7. ↑ I. Damgård, V. Pastro, N. Smart and S. Zakarias, "Multiparty computation from somewhat homomorphic encryption," Crypto 2012, vol. Springer LNCS 7417, pp. 643-662, 2012.
  8. ↑ J. Nielsen, P. Nordholt, C. Orlandi and S. Burra, "A new approach to practical active-secure two-party computation," Crypto 2012, vol. Springer LNCS 7417, pp. 681–700, 2012.
  9. ↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4, DOI 10.1007/978-3-642-02617-1
  10. ↑ Rashid Sheikh, Brijesh Kumar and Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online),Vol.6, No.2, Nov. 2009
  11. ↑ Iddo Bentov, Ranjit Kumaresan (2014). "How to Use Bitcoin to Design Fair Protocols" (PDF). Cryptology e print. International Association for Cryptologic Research (IACR) (129): 1–38. Retrieved 9 October 2014.
  12. ↑ Jared Saia and Mahdi Zamani. Recent Results in Scalable Multi-Party Computation. SOFSEM 2015: Theory and Practice of Computer Science. Springer Berlin Heidelberg. Volume 8939. pp 24–44. 2015. ISBN 978-3-662-46078-8
  13. 1 2 A. Ben-David, N. Nisan and B. Pinkas, "FairplayMP: a system for secure multi-party computation," ACM CCS 2008, pp. 257–266, 2008.
  14. 1 2 3 B. Pinkas, T. Schneider, N. Smart and S. Williams, "Secure two-party computation is practical," Asiacrypt 2009, vol. Springer LNCS 5912, pp. 250–267, 2009.
  15. ↑ Y. Lindell and B. Pinkas, "An efficient protocol for secure two-party computation in the presence of malicious adversaries," Eurocrypt 2007, vol. Springer LNCS 4515, pp. 52-78, 2007.
  16. ↑ Y. Lindell, "Fast cut-and-choose based protocols for malicious and covert adversaries," Crypto 2013, vol. Springer LNCS 8043, pp. 1-17, 2013.
  17. ↑ B. Kreuter, a. shalet and C.-H. Shen, "Billion gate secure computation with malicious adversaries," USENIX Security Symposium 2012, pp. 285–300, 2012.
  18. ↑ a. shelat and C.-H. Shen, "Fast two-party secure computation with minimal assumptions," ACM CCS 2013, pp. 523–534, 2013.
  19. ↑ T. Frederiksen and J. Nielsen, "Fast and maliciously secure two-pary computation using the GPU, "ACNS 2013, vol. Springer LNCS 7954, pp. 339–356, 2013.
  20. ↑ Y. Huang, J. Katz and D. Evans, "Efficient secure two-party computation using symmetric cut-and-choose.," CRYPTO, vol. Springer LNCS 8043, pp. 18-35, 2013.
This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.