Misplaced Pages

#796203

79-522: The Danish Sugar Beet Auction was the first large-scale and practical application of secure multi-party computation , which took place in January 2008. An electronic double auction was successfully run by a multiparty computation involving representatives of Denmark's only sugar beets processor ( Danisco ), the Danish sugar beet growers' association, and a research group responsible for implementing and running

158-525: 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, 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

237-467: A broadcast channel allows the system to tolerate up to 1/2 misbehaving minority, whereas connectivity constraints on the communication graph were investigated in the book Perfectly Secure Message Transmission. Over the years, the notion of general purpose multi-party protocols became a fertile area to investigate basic and general protocol issues properties on, such as universal composability or mobile adversary as in proactive secret sharing . Since

316-401: 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 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

395-413: 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

474-466: 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

553-551: 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

632-399: 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

711-421: A practical perspective. The above results are in a model where the adversary is limited to polynomial time computations, and it observes all communications, and therefore the model is called the `computational model'. Further, the protocol of oblivious transfer was shown to be complete for these tasks. The above results established that it is possible under the above variations to achieve secure computation when

790-464: A public function on that private data: F(d 1 , d 2 , ..., d N ) 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: If there were some trusted outside party (say, they had

869-406: A setup phase, which may only be secure against a computationally bounded adversary. A number of systems have implemented various forms of MPC with secret sharing schemes. The most popular is SPDZ, which implements MPC with additive secret shares and is secure against active adversaries. In 2014 a "model of fairness in secure computation in which an adversarial party that aborts on receiving output

SECTION 10

#1732844739797

948-522: A simple abstraction of the complexities of MPC to allow the construction of an application under the pretense that the MPC protocol at its core is actually an ideal execution. If the application is secure in the ideal case, then it is also secure when a real protocol is run instead. The security requirements on an MPC protocol are stringent. Nonetheless, in 1987 it was demonstrated that any function can be securely computed, with security for malicious adversaries and

1027-407: 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 topologically 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

1106-452: A small overhead comparing to the semi-honest protocol. Most MPC protocols, as opposed to 2PC protocols and especially under the unconditional setting of private channels, 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 with each wire is shared amongst the parties, and a protocol

1185-480: A special model of private protocols. Later on, other solutions that are based on secret sharing were published – one by Bhavani Shankar, Kannan Srinathan, and C. Pandu Rangan , and another by Tamir Tassa. In the early seventies Stephen Wiesner introduced a primitive called multiplexing in his seminal paper "Conjugate Coding", which was the starting point of quantum cryptography . Unfortunately it took more than ten years to be published. Even though this primitive

1264-413: 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. 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. One of the primary applications of secure multi-party computation is allowing analysis of data that

1343-467: A trusted third party. Traditionally, cryptography was about concealing content, while this new type of computation and protocol is about concealing partial information about data while computing with the data from many sources, and correctly producing outputs. By the late 1980s, Michael Ben-Or, Shafi Goldwasser and Avi Wigderson, and independently David Chaum, Claude Crépeau, and Ivan Damgård, had published papers showing "how to securely compute any function in

1422-418: A work which invented for this purpose the often used `share of shares idea' and a protocol that allows one of the parties to hide its input unconditionally. The GMW paradigm was considered to be inefficient for years because of huge overheads that it brings to the base protocol. However, it is shown that it is possible to achieve efficient protocols, and it makes this line of research even more interesting from

1501-467: Is complete for secure multiparty computation : that is, given an implementation of oblivious transfer it is possible to securely evaluate any polynomial time computable function without any additional primitive. In Rabin's oblivious transfer protocol, the sender generates an RSA public modulus N = pq where p and q are large prime numbers , and an exponent e relatively prime to λ(N) = ( p  − 1)( q  − 1). The sender encrypts

1580-550: Is a mathematical proof where the security of a protocol is reduced to that of the security of its underlying primitives. Nevertheless, it is not always possible to formalize the cryptographic protocol security verification based on the party knowledge and the protocol correctness. For MPC protocols, the environment in which the protocol operates is associated with the Real World/Ideal World Paradigm. The parties can't be said to learn nothing, since they need to learn

1659-406: Is a special case of generalized oblivious transfer, which was presented by Ishai and Kushilevitz. In that setting, the sender has a set U of n messages, and the transfer constraints are specified by a collection A of permissible subsets of U . The receiver may obtain any subset of the messages in U that appears in the collection A . The sender should remain oblivious of the selection made by

SECTION 20

#1732844739797

1738-459: Is a strengthening of private information retrieval , in which the database is not kept private. Claude Crépeau showed that Rabin's oblivious transfer is equivalent to 1–2 oblivious transfer. Further work has revealed oblivious transfer to be a fundamental and important problem in cryptography. It is considered one of the critical problems in the field, because of the importance of the applications that can be built based on it. In particular, it

1817-545: Is a sufficient assumption in order to construct 1-out-of-2 Oblivious Transfer. 1-out-of- n oblivious transfer protocol with sublinear communication was first constructed (as a generalization of single-server PIR) by Eyal Kushilevitz and Rafail Ostrovsky . More efficient constructions were proposed by Moni Naor and Benny Pinkas , William Aiello , Yuval Ishai and Omer Reingold , Sven Laur and Helger Lipmaa . In 2017, Kolesnikov et al. , proposed an efficient 1-n oblivious transfer protocol which requires roughly 4x

1896-410: Is an alternative that aims to allow greater efficiency in exchange for weakening the security definition; it is applicable to 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

1975-517: Is forced to pay a mutually predefined monetary penalty" has been described for the Bitcoin network or for fair lottery, and has been successfully implemented in Ethereum . Many advances have been made on 2PC and MPC systems in recent years. 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

2054-423: Is general, but can be instantiated using RSA encryption as follows. A 1-out-of- n oblivious transfer protocol can be defined as a natural generalization of a 1-out-of-2 oblivious transfer protocol. Specifically, a sender has n messages, and the receiver has an index i , and the receiver wishes to receive the i -th among the sender's messages, without the sender learning i , while the sender wants to ensure that

2133-475: Is held by multiple parties, or blind analysis of data by third parties without allowing the data custodian to understand the kind of data analysis being performed. Oblivious transfer In cryptography , an oblivious transfer ( OT ) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred. The first form of oblivious transfer

2212-459: 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

2291-664: 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 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. They utilize oblivious transfer extensions and some other novel techniques to design their GPU-specific protocol. This approach seems to achieve comparable efficiency to

2370-460: Is the Millionaires' 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. A multi-party computation protocol must be secure to be effective. In modern cryptography, the security of a protocol is related to a security proof. The security proof

2449-437: Is the majority vote of all the evaluations. 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. This technique was implemented by Pinkas et al. in 2009, This provided the first actively secure two-party evaluation of

Danish Sugar Beet Auction - Misplaced Pages Continue

2528-567: Is then used to evaluate each gate. The function is now defined as a "circuit" over a finite field, 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 a finite field. Secret sharing allows one to distribute a secret among a number of parties by distributing shares to each party. Two types of secret sharing schemes are commonly used; Shamir secret sharing and additive secret sharing. In both cases

2607-438: 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

2686-491: 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 {\displaystyle 2^{-40}} cheating probability. As many circuits are evaluated, the parties (including

2765-423: The adversary in an MPC protocol is one of the players engaged in the system (or controlling internal parties). That corrupted party or parties may collude in order to breach the security of the protocol. Let n {\displaystyle n} be the number of parties in the protocol and t {\displaystyle t} the number of parties who can be adversarial. The protocols and solutions for

2844-410: The case of t < n / 2 {\displaystyle t<n/2} (i.e., when an honest majority is assumed) are different from 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

2923-445: 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

3002-407: The computation. Due to European Union sugar market policy reforms which reduced sugar subsidies and lowered prices, as well as the recent closure of one of Danisco's sugar processing plants, the Danish sugar beet industry needed to reallocate production contracts to farmers nation-wide in an attempt to retain market efficiency. The decision made was to hold an electronic double auction to find

3081-442: The cost of 1-2 oblivious transfer in amortized setting. Brassard , Crépeau and Robert further generalized this notion to k - n oblivious transfer, wherein the receiver obtains a set of k messages from the n message collection. The set of k messages may be received simultaneously ("non-adaptively"), or they may be requested consecutively, with each request based on previous messages received. k - n Oblivious transfer

3160-404: The defense harder. An adversary structure can be defined as a threshold structure or as a more complex structure. In a threshold structure the adversary can corrupt or read the memory of a number of participants up to some threshold. Meanwhile, in a complex structure it can affect certain predefined subsets of participants, modeling different possible collusions. There are major differences between

3239-438: The encodings corresponding to both his and the sender's output. He then just sends back the sender's 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

Danish Sugar Beet Auction - Misplaced Pages Continue

3318-417: 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 possessing 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

3397-414: 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%. The approach that so far seems to be the most fruitful in obtaining active security comes from a combination of the garbling technique and

3476-544: The function on its own and sends back the appropriate output to each party. (ii) 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. A protocol is said to be 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. In the ideal world, no messages are exchanged between parties, so real-world exchanged messages cannot reveal any secret information. The Real World/Ideal World Paradigm provides

3555-429: 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

3634-402: The honest participants. Adversaries faced by the different protocols can be categorized 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 (and each fits into different real world scenario): Security against active adversaries typically leads to a reduction in efficiency. Covert security

3713-439: 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. However, it is possible to efficiently apply Zero-Knowledge proofs to make this protocol secure against malicious adversaries with

3792-430: The late 2000s, and certainly since 2010 and on, the domain of general purpose protocols has moved to deal with efficiency improvements of the protocols with practical applications in mind. Increasingly efficient protocols for MPC have been proposed, and MPC can be now considered as a practical solution to various real-life problems (especially ones that only require linear sharing of the secrets and mainly local operations on

3871-515: The logistics of such a novel auction, the actual computation of the market clearing price and each bidder's positions only took about 30 minutes to complete. Ultimately, the auction resulted in the transfer of 25 thousand tons of production rights between farmers. Secure multi-party computation The foundation for secure multi-party computation started in the late 1970s with the work on mental poker, cryptographic work that simulates game playing/computational tasks over distances without requiring

3950-401: The majority of users are honest. The next question to solve was the case of secure communication channels where the point-to-point communication is not available to the adversary; in this case it was shown that solutions can be achieved with up to 1/3 of the parties being misbehaving and malicious, and the solutions apply no cryptographic tools (since secure communication is available). Adding

4029-418: The message m as m mod N . If the receiver finds y is neither x nor − x modulo N , the receiver will be able to factor N and therefore decrypt m to recover m (see Rabin encryption for more details). However, if y is x or − x  mod  N , the receiver will have no information about m beyond the encryption of it. Since every quadratic residue modulo N has four square roots,

SECTION 50

#1732844739797

4108-407: The new market clearing price of sugar beets, where the role of the "auctioneer" was played by a computer program implementing a secure multi-party computation (SMPC) between the farmers and Danisco. The use of SMPC not only reduced expenses of the auction process (when compared to hiring an external consultancy to run the auction), but also allowed farmers' bids to remain private from Danisco ,

4187-444: The only sugar beets processor on the Danish market and the seller of production contracts. This was important as farmers' bids can reveal their individual economic positions and productivities, which Danisco could have hypothetically used to their advantage when selling contracts. In a survey of the auction participants, 80% of respondents indicated that it was important to them that the bids were kept confidential. Aside from organizing

4266-499: The other initial works mentioned before. Despite these publications, MPC was not designed to be efficient enough to be used in practice at that time. Unconditionally or information-theoretically secure MPC is closely related and builds on to the problem of secret sharing , and more specifically verifiable secret sharing (VSS), which many secure MPC protocols use against active adversaries. Unlike traditional cryptographic applications, such as encryption or signature, one must assume that

4345-448: The output of the operation, and the output depends on the inputs. In addition, the output correctness is not guaranteed, since the correctness of the output depends on the parties’ inputs, and the inputs have to be assumed to be correct. The Real World/Ideal World Paradigm states two worlds: (i) In the ideal-world model, there exists an incorruptible trusted party to whom each protocol participant sends its input. This trusted party computes

4424-401: 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

4503-439: 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

4582-407: 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 mechanism sets a bridge between both models in the hope of finding protocols which are efficient and secure enough in practice. Like many cryptographic protocols ,

4661-470: The power of the adversary. The Shamir secret sharing scheme is secure against a passive adversary when t < n 2 {\displaystyle t<{\frac {n}{2}}} and an active adversary when t < n 3 {\displaystyle t<{\frac {n}{3}}} while achieving information-theoretic security, meaning that even if the adversary has unbounded computational power, they cannot learn any information about

4740-401: The probability that the receiver learns m is 1/2. In a 1–2 oblivious transfer protocol, Alice the sender has two messages m 0 and m 1 , and wants to ensure that the receiver only learns one. Bob, the receiver, has a bit b and wishes to receive m b without Alice learning b . The protocol of Even, Goldreich, and Lempel (which the authors attribute partially to Silvio Micali )

4819-407: The protocols proposed for two party computation (2PC) and multi-party computation (MPC). Also, often for special purpose protocols of importance a specialized protocol that deviates from the generic ones has to be designed (voting, auctions, payments, etc.) The two party setting is particularly interesting, not only from an applications perspective but also because special techniques can be applied in

SECTION 60

#1732844739797

4898-448: The queried value. If one is considering malicious adversaries, further mechanisms to ensure correct behavior of both parties need to be provided. By construction it is easy to show security for the sender if the OT protocol is already secure against malicious adversary, 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

4977-488: The receiver receive only one of the n messages. 1-out-of- n oblivious transfer is incomparable to private information retrieval (PIR). On the one hand, 1-out-of- n oblivious transfer imposes an additional privacy requirement for the database: namely, that the receiver learn at most one of the database entries. On the other hand, PIR requires communication sublinear in n , whereas 1-out-of- n oblivious transfer has no such requirement. However, assuming single server PIR

5056-407: 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 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 the efficiency of actively secure Yao-based implementations

5135-432: The receiver, while the receiver cannot learn the value of the messages outside the subset of messages that he chose to obtain. The collection A is monotone decreasing, in the sense that it is closed under containment (i.e., if a given subset B is in the collection A , so are all of the subsets of B ). The solution proposed by Ishai and Kushilevitz uses the parallel invocations of 1-2 oblivious transfer while making use of

5214-474: The secret underlying a share. The BGW protocol, which defines how to compute addition and multiplication on secret shares, is often used to compute functions with Shamir secret shares. Additive secret sharing schemes can tolerate the adversary controlling all but one party, that is t < n {\displaystyle t<n} , while maintaining security against a passive and active adversary with unbounded computational power. Some protocols require

5293-457: The secure channels setting". Special purpose protocols for specific tasks started in the late 1970s. Later, secure computation was formally introduced as secure two-party computation (2PC) in 1982 (for the so-called Millionaires' Problem , a specific problem which is a Boolean predicate), and in generality (for any feasible computation) in 1986 by Andrew Yao . The area is also referred to as Secure Function Evaluation (SFE). The two party case

5372-418: 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, where the adversary chooses its victims before the start of the multi-party computation, or dynamic, where it chooses its victims during the course of execution of the multi-party computation making

5451-414: The shares are random elements of a finite field that add up to the secret in the field; intuitively, security is achieved because any non-qualifying set of shares looks randomly distributed. Secret sharing schemes can tolerate an adversary controlling up to t parties out of n total parties, where t varies based on the scheme, the adversary can be passive or active, and different assumptions are made on

5530-620: The shares with not much interactions among the parties), such as distributed voting, private bidding and auctions, sharing of signature or decryption functions and private information retrieval . The first large-scale and practical application of multi-party computation was the execution of an electronic double auction in the Danish Sugar Beet Auction , which took place in January 2008. Obviously, both theoretical notions and investigations, and applied constructions are needed (e.g., conditions for moving MPC into part of day by day business

5609-401: 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

5688-453: 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

5767-469: The very basic general scheme to be followed by essentially all future multi-party protocols for secure computing. This work introduced an approach, known as GMW paradigm, for compiling a multi-party computation protocol which is secure against semi-honest adversaries to a protocol that is secure against malicious adversaries. This work was followed by the first robust secure protocol which tolerates faulty behavior graciously without revealing anyone's output via

5846-405: Was advocated and presented in ). In 2020, a number of companies working with secure-multiparty computation founded the MPC alliance with the goal of "accelerate awareness, acceptance, and adoption of MPC technology." In an MPC, a given number of participants, p 1 , p 2 , ..., p N , each have private data , respectively d 1 , d 2 , ..., d N . Participants want to compute the value of

5925-437: Was developed later by Shimon Even , Oded Goldreich , and Abraham Lempel , in order to build protocols for secure multiparty computation . It is generalized to "1 out of n oblivious transfer" where the user gets exactly one database element without the server getting to know which element was queried, and without the user knowing anything about the other elements that were not retrieved. The latter notion of oblivious transfer

6004-473: Was equivalent to what was later called 1–2 oblivious transfer , Wiesner did not see its application to cryptography. Protocols for oblivious transfer can be implemented with quantum systems . In contrast to other tasks in quantum cryptography , like quantum key distribution , it has been shown that quantum oblivious transfer cannot be implemented with unconditional security, i.e. the security of quantum oblivious transfer protocols cannot be guaranteed only from

6083-441: Was followed by a generalization to the multi-party by Oded Goldreich, Silvio Micali, and Avi Wigderson. The computation is based on secret sharing of all the inputs and zero-knowledge proofs for a potentially malicious case, where the majority of honest players in the malicious adversary case assure that bad behavior is detected and the computation continues with the dishonest person eliminated or his input revealed. This work suggested

6162-529: Was improved even further, requiring only 40 circuits, and a much smaller number of commitments, to obtain 2 − 40 {\displaystyle 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. describe an implementation running on 512 cores of

6241-445: Was introduced in 1981 by Michael O. Rabin . In this form, the sender sends a message to the receiver with probability 1/2, while the sender remains oblivious as to whether or not the receiver received the message. Rabin's oblivious transfer scheme is based on the RSA cryptosystem. A more useful form of oblivious transfer called 1–2 oblivious transfer or "1 out of 2 oblivious transfer",

#796203