Name: Wang Lezhang

Student ID: 19011110177

/p/68116569

/p/25770963

/p/59108808

The Multi-Party Secure Computation (MPC: Secure Muti-Party Computation) theory was developed by Mr. Yao Qizhi to solve the problem of protecting private information between a group of mutually distrustful participants and the absence of a trusted third party. A theoretical framework proposed under the premise of collaborative computing problems. Multi-party secure computing can simultaneously ensure the privacy of input and the correctness of calculation. It uses mathematical theory to ensure that the input information of all parties participating in the calculation is not exposed without a trusted third party, and at the same time, accurate calculation results can be obtained.

As early as 1982, Mr. Yao Qizhi proposed the famous Yao Millionaire Problem in his article "Protocols for Secure Computation", and also introduced bilateral secure computing for the first time. The concept was used to solve the problem and its feasibility was verified. Two millionaires, Alice and Bob, want to conclude who is richer without any trusted third party and without revealing their wealth.

Let’s introduce Teacher Yao’s ingenious solution ---

Assume that the rich man Wang has assets of i billion and Li has assets of j billion. Wang chooses a public key that allows Li to pass the encrypted message.

First, Li selected a random large integer x, encrypted it with Wang's public key, and obtained the ciphertext K. Li sends k-j to Wang.

After Wang received the ciphertext c=k-j, he decrypted c+1, c+2,..., c+10 and obtained ten numbers. Then choose a prime number p of appropriate size, and record the remainders after dividing these ten numbers by p as d1, d2,..., d10.

.Note: These ten numbers should look completely random. The key is that the equation dj=x mod p holds.

Finally, Wang performed the following operations on this string of numbers: the first i numbers remained unchanged, each subsequent number was incremented by one, and then sent back to Li.

After such a complicated operation, Li checks the jth number. If it is equal to x mod p, it means that the number has not been added by one, so i >= j. Otherwise, then i < j.

The wonderful thing about this process is that after the agreement is completed, Wang does not know the specific value of j, and Li does not know the value of i, but both parties know who has more wealth. This is the multi-party Secure computing. Generally speaking, when A only knows x and B only knows y, both parties can cooperate to calculate a function f(x,y). When the protocol is complete, only the function values ??are public, and neither party knows the other's input values.

From the previous examples, we found the characteristics of multi-party secure computing:

1. Two or more parties participate in calculations based on their respective private or secret data inputs.

2. None of the participating parties is willing to let any other third party know their input information.

Before the emergence of multi-party secure computing, the strategy to solve the above problems was to assume that there was a trusted service provider or that there was a trusted third party. But in today’s volatile and malicious environment, this is extremely risky. Therefore, secure multi-party computation has become increasingly important as a technology that can solve the privacy-preserving collaborative computing problem among a group of mutually distrustful participants.

At present, the Internet has completed the transformation from the IT era to the DT era, and data has become the core competitiveness of enterprises in the DT era. As a new energy, data can only generate value if it flows. However, most companies are very cautious about data sharing due to issues such as data security and personal privacy. MPC has important theoretical and practical significance for breaking down data silos and realizing controllable sharing of data.

MPC solutions can be mainly divided into two types: those based on Garbled Circuit (GC) and those based on secret sharing.

Oblivious Transfer (Oblivious Transfer)

First, a basic secure multi-party computing protocol is introduced: Oblivious Transfer (OT).

Let’s look at an example: Suppose a travel agency has travel information on N attractions. Xiao Tao wants to visit attraction A among them, and hopes to purchase relevant information from the travel agency to do his travel homework. But Xiaotao cares about his privacy very much and does not want to reveal his destination to the travel agency.

Therefore, both parties hope that this transaction can meet the following privacy conditions:

Xiaotao does not want to disclose the information "I am going to attraction A" to the travel agency;

The travel agency only wants to sell Xiaotao The information that Xiaotao paid to purchase without revealing the N-1 information that Xiaotao did not purchase;

At first glance, this privacy condition seems to be unsatisfactory: the travel agency only needs to provide the information of attraction A to When you go to Xiaotao, you will definitely understand the information that "Xiaotao is paying attention to attraction A"; unless the travel agency gives out all N pieces of information, but this goes against the interests of the travel agency;

But the magic OT can allow transactions to be completed under such "impossible conditions". In short, in the OT protocol, the travel agency encrypts the N pieces of information it owns using an encryption algorithm and parameters agreed upon by both parties, and then sends them to Xiaotao; Xiaotao can decrypt A's information from the ciphertext, The other N-1 pieces of information cannot be decrypted.

In addition to being directly used to construct MPC solutions, OT is also the cornerstone of many MPC solutions such as GC.

Confused circuits

We know that any function is ultimately represented by adders, multipliers, shifters, selectors and other circuits within the computer language, and these circuits are ultimately It can be composed of only two logic gates, AND and XOR. A gate circuit is actually a truth table. For example, the truth table of an AND gate is:

For example, the lower right cell indicates that when both input wires (wire) are 1, the output wire=1: that is 1 AND 1 = 1.

Suppose we encrypt each wire with a different key and change the truth table to this:

For example, the lower right cell indicates that if the inputs of the gate are b and d , then output the encrypted f (the keys are b and d). This gate is still the same from the perspective of control flow, except that the input and output are encrypted, and the output must use the corresponding input to decrypt, and the decrypted f can be used as the input of the subsequent gate. This encryption method is called "Garbled Circuit (GC)".

By encrypting all the gates in the circuit in order, we will get a function represented by GC. This function receives encrypted input and outputs the encrypted result.

Assume that there are two participants A and B each providing data a and b, and hope to safely calculate the agreed function F(a,b), then a secure two-party calculation protocol process based on GC can The informal description is as follows:

Careful students will definitely point out: How can A access B's input b in step 4? Doesn't this violate the assumption of secure multi-party computation? Here you need to use OT, A plays the role of Sender, and B plays the role of Receiver. Let B get Encrypt(b) from A without revealing the content of b to A. As shown in the figure:

It should be noted that the above process is only a loose description of the original GC method. There are many detailed optimizations such as Point & Permute, Free XOR, Half Gates, etc. in the follow-up of GC. With the research progress in recent years, the performance of GC is almost practical. Taking the Hamming Distance of two million-dimensional vectors as an example (the application scenario is to find similarity between two pieces of data without leaking the data content to each other), such a secure two-party calculation can be completed in about 1.5 seconds. .

Security model of secure multi-party computation

Semi-honest behavior model and malicious behavior model

More careful students will further ask: "How to ensure that A gives Is B's

a correct GC? For example, A and B agree on a larger size than a and b, and agree on F(a,b)=a>b?1:0, but A can make it. The GC of another function, such as F(a,b)=the first bit of b, will obviously infringe on B's privacy, but since the function is sent to B in the form of GC, B has no way to discover this. Problem?"

This is indeed a security issue. In fact, GC also has other security issues such as selective failure. Before introducing the solution, we need to define the security model of secure multi-party computation.

The security model of secure multi-party computation includes content from multiple perspectives. In the above context, we focus on the "behavior model", that is, what behaviors participants may perform to obtain the privacy of other parties. . Common behavioral models include "Semi Honest" and "Malicious". The former assumes that all participants faithfully follow the protocol steps and just want to infer the privacy of other parties through the protocol content, while the latter assumes that malicious participants do not follow the protocol content in order to obtain the privacy of other parties.

To use a loose analogy with poker, a semi-honest player will try to infer the hands of others from his own hand and the cards that have been played, but he still follows the rules of poker; A malicious player will use all kinds of tricks such as changing cards and stealing cards.

It can be seen that the issues raised at the beginning of this section belong to the category of malicious behavior, and the original GC can only be said to be safe under the semi-honest behavior model and cannot resist malicious behavior attacks. There are many improvements to the GC scheme that can achieve security under the malicious behavior model, but they all require a large performance cost: Still taking the Hamming distance of two million-dimensional vectors as an example, the fastest method is It also takes 10 seconds+, which is more than 7 times slower than the equivalent semi-honest scheme. In fact, after our research, if we want to truly implement MPC products that support large-scale data, we can basically only consider semi-honest solutions. This seriously affects the practicality of secure multi-party computation.

Some applications of multi-party secure computing

Play an important role in electronic elections, electronic voting, electronic auctions, secret sharing, threshold signatures and other scenarios.

Conclusion

The formulation and answer of the millionaire problem vividly illustrate the challenges faced by multi-party secure computing and the ideas for solving the problem, which have attracted great attention from the academic community. Four years later, Mr. Yao Qizhi made another major breakthrough. In 1986, he proposed a universal solution based on confusion circuits, which further verified the universal feasibility of multi-party secure calculations and laid the theoretical foundation for modern computer cryptography. Since then, through further research and innovation by scholars such as Oded Goldreich and Shafi Goldwasser, multi-party secure computing has gradually developed into an important branch of modern cryptography.