A paper on the technology behind cross-chain, key management, contract privacy, you must know the safe multi-party computing (MPC)

Secure multi-party computing has been recognized as an important cryptographic technology and tool in the development of blockchain. It plays a unique role in transaction or contract privacy protection, wallet key management, cross-chain trading, blockchain expansion and other issues. effect.

However, because its specific technology involves many cryptographic algorithms and mathematical background knowledge, there will be no clue in the beginning of learning and development in the corresponding fields .

This paper hopes to connect the concepts of secure multi-party computing into a system with limited space, so that readers can quickly learn and build knowledge networks. At the same time, the two branches that use the most in secure multiparty computing are: " Secure Multiparty Computing Based on Confused Circuits " and " Secure Multiparty Computing Based on Secret Sharing ".

In the first article of Secure Multi Party Computation, we have described how secure multiparty computing provides a solution to the conflict between data value and privacy protection, and how this problem was raised by Mr. Yao Zhizhi. And how to play a role in real life.

• Proficient in IPFS: IPFS boot boot function
• Not just EOS, they also want to debut in June C.
• Getting started with blockchain | Anonymous blockchain, why do you still need KYC authentication?

So before we introduce the further application of secure multi-party computing, and how to combine it with the blockchain, we open a "process" to go deep into the safe multi-party computing technology, and give a simple and clear demonstration of its implementation technology .

From these examples we can see the difference between secure multiparty computing and plaintext computing. How does this cryptographic scheme achieve its claimed functions, the relationships and differences between different implementations, and secure multicomputing and other cryptographic algorithms. The relationship between . This article will cover some basic cryptographic algorithms and mathematical content, but this will not affect the understanding of the idea of ​​secure multiparty computing itself.

Proposed multi-party computing

In the article "Safety Computing Agreement" published by Andrew C. Yao in 1982, he mentioned that " two millionaires want to know who is richer, however, they do not want to get extra information about the other's wealth. How should they conduct this conversation? ".

This "millionaire puzzle" is a special case of secure multiparty computing. The generalized secure multiparty calculation is an interactive protocol between n participants, and the n parties hold data x1, x2, … xn, respectively. The functions y1, y2, …, yn = f(x1, x2, … xn) are calculated above the input, and the i-th party can only obtain yi without obtaining other information.

This definition does not seem to bring intuitive understanding. We might think of another way of thinking: in an ideal world (the ideal world paradigm), there is a credible third party that is completely neutral and does not collude with anyone. Everyone gives the data to him, then he calculates and distributes the results accordingly . This completes a safe calculation.

Then in the real world (real world paradigm), the secure multiparty computing protocol accomplishes the same task without the existence of this trusted third party. This gives people a more concise reference to safe multi-party computing power and defects.

For example, it does not guarantee that the input provides the correct input, nor does it generalize the information of the hidden function f (code obfuscation). On the other hand, can we ensure that all participants can get or not get the results (fairness) at the same time, can we guarantee that there are several parties in the participants to collude or try to spy on other people's input information, the calculation can still be safe To carry out (robustness), these issues are the focus of cryptographers in constructing different secure multiparty computing protocols.

There are not only one protocol in reality, nor the exact same ones, but a series of cryptographic protocols with different efficiencies, different security models, and different implementation methods . This is also the most complicated and compelling place for secure multiparty computing . In this paper, we will introduce the two most used branches in secure multiparty computing – "safe multiparty computing based on obfuscated circuits" and "secure multiparty computing based on secret sharing". "."

Secure multi-party calculation based on obfuscated circuit

Mr. Yao Zhizhi has given a solution to this type of problem in his article: Garbled Cirtuit and Oblivious Transfer .

This kind of protocol is mainly suitable for two-party security computing. There is a lot of work devoted to extending this algorithm to multiple parties (n>2). However, we will see that it is only suitable for two parties, but the two-party operation can already help. We have solved many specific problems.

This technique is called "circuit" because it first expresses the function that needs to be calculated as a Boolean circuit. Just like the logic in modern integrated circuits, the basic unit is the logic gate, and each logic gate is defined as two. Enter an output but can have multiple fanouts (the output can be used as an input to multiple gates in the next stage).

If the topological relationship of the circuit is determined, the calculation of the overall circuit can be achieved by performing the sequence of input and output connections. Then we will implement the safe multi-party calculation of the function as a door implementation, that is to say, we construct a "safety gate" that can be equivalent to the ideal world in real life, then we can generalize the whole circuit Transformation.

The Boolean circuit confusing (Garbling) technology provided by Mr. Yao Zhizhi also utilizes inadvertent transmission. Inadvertent transmission is a cryptographic tool that can be used independently. Let's take 1-out-of-2 Oblivious Transfer as an example. As shown in the figure below, the core purpose is that the receiver (Bob) wants to obtain one of the two messages (m1, m2) specified by the sender (Alice), but cannot obtain another information. On the other hand, Alice could not know the specific value of b.

Inadvertent transmission

From the above figure, we can get a conclusion: any valid casual transfer protocol represents a secure two-party computing protocol based on it .

Then we can observe how this is achieved. If Alice is a "circuitmaker" and Bob is a "circuit computing party", the two parties want to calculate f(x,y) together, where x is from Alice and y is from Bob. Then Alice is responsible for providing circuit generation, without loss of generality. Let's take a logic and gate as an example. We choose a pair of keys for each of its line signals (Wire).

Represents 0 and 1 of this signal, respectively. After that, we use a double-key symmetric encryption function to obtain Table 1, which is called a confusion gate. At this point the obfuscation circuit completes the construction.

Confused with the door

Confusion and door comparison table

Alice passes the obfuscation circuit to Bob, and x inputs the corresponding key value. At this time, Bob can obtain the key value corresponding to his own y input by inadvertent transmission. Then, after experiencing the decryption attempt, Bob obtains the corresponding result. When using an encryption algorithm that satisfies the IND-CCA scheme, Bob tries to decrypt the error ciphertext, and the decryption algorithm rejects it.

As mentioned in the first section, secure multiparty computing guarantees that one party's input will not be obtained by the other party, rather than the input cannot be inferred from the output.

Secure two-party calculation

This is the basic flow of confusing circuits. However, this structure is very preliminary and inefficient . After the publication of this article, many improvements have been slowly put forward by research work. From the aspects of safety and operational efficiency, the technology of this branch has been greatly improved, making it practical. Become feasible.

Some of the more important technologies include Free-XOR, Half AND, which reduce the cost of special logic gates, and Point-and-permute, Row reduction, which reduces the complexity of the wheel.

In application, the first implementation was the Fairplay system released in 2004, and an article in Asiacrypt in 2009 used a confusing circuit to implement a secure two-party version of AES, which made AES's private key not recoverable during the calculation process. Thanks to the majority of AES's XOR gates, Free XOR technology can be used to reduce consumption.

Secure multiparty computing based on secret sharing

The rest of the multi-party security calculations, unlike the two-party security calculations, utilize the secret sharing technique. A major difference between the two is that all participants in the secret sharing are equal, and the obfuscating circuit distinguishes between the manufacturer and the computing party.

At this time, the input is not a key value corresponding to the bit value, and the function is not a logic circuit. The input is secretly shared between the participants, and the function is mapped to an operation on a finite field. This operation can be represented by addition and multiplication, which is called an arithmetic circuit relative to the logic circuit.

Before we move on to this scenario, let's take a brief look at secret sharing. Secret sharing is a cryptographic tool used by n participants to distribute a secret s between participants. It is often used to store important sensitive information such as encryption keys and missile launch codes .

The protocol mainly consists of two functions: a secret distribution function (Distribution) and a reconstruction function (Reconstruction).

The distribution function splits the secret s into secret share values ​​[s] and distributes them to all participants, a process typically performed by the original holder of s. The reconstruction function allows all collections of participants that satisfy the reconstruction conditions to recover the secret. The secret sharing method was independently proposed by Shamir and Blakley in 1979. One of the secret sharing methods we use is Shamir's secret sharing.

In 1989, Brickell proposed a generalized secret sharing scheme called the Linear Secret Sharing Scheme. In this scheme, the Access Structure is used to constrain which party associations can reconstruct the secret .

Use a set of mathematical languages ​​to describe how to split secrets, how to assign secrets, and use linear algebra to prove the security of this mathematical description. The inspiration of this linear secret sharing scheme is that for n participants, I can arbitrarily specify access rights (as long as they satisfy monotony, that is, a group of participants can re-establish secrets, then one party can still re-establish secrets) . This is more general than Shamir's secret sharing.

Based on this generalized secret sharing scheme, Cramer et al. demonstrated in the article that we can construct secure multiparty computing. The key to this construction is how to perform multiplication calculations. The implementation of addition on linear sharing is obvious . This process introduces a recombination operation. If we can find the recombination vector r=(r1,r2,…rn) for any secret x and y,

Then you can build multiplication on this secret sharing without revealing information, * means vector dot multiplication.

The general calculation [x*y] given in the article is as follows, each party calculates [x]i*[y]i=ci, after which the value is secretly shared to all parties, and then each party calculates

You can complete the multiplication.

However, this method only works when the security model is weak. For stronger security assumptions, more complicated methods are needed to complete the multiplication.

to sum up

In the most concise way, this paper introduces the two technical branches of secure multi-party computing, hoping to provide a vague knowledge framework. Since secure multiparty computing is an extremely complex system that includes multiple cryptography techniques, this article can only be traced, but through this article, we hope to connect these points together to provide a panorama.

In practical applications, secure multi-party computing can be used not only for collaborative work between data providers, but also with SaaS systems, cloud services to improve the security of corporate and personal privacy data, and increase the possibility of data joint analysis. The contradiction between data privacy and utilization. Such as ARPA secure multi-party computing platform.

In future articles, we will continue to share how some secure multi-party computing platforms can open data flow channels, enabling secure multi-party computing to be applied in key management, data security query, cloud data sandbox, joint credit reporting and advertising. Case.

How about, after reading this brain-burning article, is it helpful to you? Leave a message to tell the battalion commander!

*About the author

Su Guantong, ARPA cryptographic algorithm engineer, Ph.D., Ph.D., Tsinghua University, has seven years of cryptographic algorithm and chip design and research experience. For the secure multi-party computing protocol, the bilinear pairing algorithm, the lattice public key cryptography algorithm has been deeply studied and published in many related fields.

Author | Su Guantong

Editor | Aholiab

Produced | Blockchain Base Camp, ARPA

We will continue to update Blocking; if you have any questions or suggestions, please contact us!