Why is the blockchain so passionate about secure multiparty computing?

Secure multi-party computing is a very active area of ​​research in cryptography and is considered a good medicine for solving the problem of collaborative computing for privacy protection. Secure multi-party computing has the characteristics of input privacy, computational correctness and decentralization, which enables data to be kept private and used, thus releasing the great value of private data sharing, private data analysis and private data mining.

Secure multi-party computing technology is also commonly used in the blockchain domain. It plays a unique role in technologies such as privacy intelligence contracts, key management, and random number generation . In this paper, we will unveil the mystery of secure multi-party computing, and introduce you to the use scenarios of secure multi-party computing, the current level of technological application development, and the important role in the blockchain field.

What kind of problem does safe multi-party computing solve?

Secure multi-party computing solves the problem of two or more users collaborating to perform a computing task without leaking their private input information in a multi-user network that they do not believe. Let us give an example.

Example: Suppose, you, Xiao Wang and Xiao Li want to know the average salary of the three people, but do not want to disclose their specific salary, then what method should be used to achieve this goal?

Solution 1 : Traditionally, if there is a trusted third party, the problem is easy to solve. For example, you, Xiao Wang and Xiao Li have a boss who trusts each other. You can tell your boss about your salary. The boss promises not to disclose any salary and calculate the average salary of the three. Finally, tell everyone about the average salary.

Solution 2 : In reality, it is not always possible to find such a trusted third party. In this case, you can use safe multiparty computing to solve the problem. In short, it is to replace the trusted third party with an algorithm.

We introduce an easy-to-understand secure multiparty computing protocol based on secret sharing. First, we need to review a simple mathematical theory. Two points can determine a straight line, and three points determine a parabola. The process of the agreement is divided into three steps.

The first step: you, Xiao Wang and Xiao Li, each choose a parabola, the intersection of the parabola and the Y axis is their own salary. For example, if your salary is 100, you choose a parabola y = 2x 2 + x + 100. Then, take 3 points (1, 103), (2, 110), (3, 121) on this parabola. Keep one point (1, 103) and secretly encrypt the other two points (2, 110) and (3, 121) to Xiao Wang and Xiao Li respectively. Similarly, Xiao Wang and Xiao Li also do this operation, secretly pass the point of x=1 to you, point x=2 to Xiao Wang, and point x=3 to Xiao Li.

Step 2: Each of the three people has three cipher fragments (points on different parabola), you have (1,103), (1, y 2 ) from Xiao Wang, and (1, y 3 ) from Xiao Li. You can calculate a point (1, 103+y 2 +y 3 ). This point is on a special parabola. The intercept of this parabola and the y-axis is exactly the sum of the three people's salary.

The third step: the three people will calculate the different three points, and restore a parabola together. Get the intercept of the parabola. Divide the intercept by 3 and get the sum of the three people's salary.

Under this scheme, on the one hand, the salary of three people is confidential. Because each person only gets a point of the parabola of the other party and cannot restore the parabola of the other party, so the intercept cannot be calculated, that is, the salary of others. And, if Xiao Wang and Xiao Li collude, they can't figure out your salary, because they have only 2 points in the parabola about your salary. The parabola cannot be restored at 2 points because 3 points determine a parabola. On the other hand, the sum of the salary of three people can be calculated. You, Xiao Wang and Xiao Li, the parabola obtained from the sum of the three parabola, must have a intercept equal to the sum of the intercepts of the three parabolas.

As explained here, a definition of security for secure multiparty computing naturally comes to the fore. We refer to the use of trusted third-party computing in Solution 1 as the " ideal world ", and Solution 2, which is not a trusted third party, to achieve collaborative computing through a secure multi-party computing protocol. ". For a secure multi-party computing protocol, if a person is in the real world, the level of understanding of each party's private data does not exceed the level of understanding in the ideal world, then this agreement is safe. Simply put, using a secure multiparty computing protocol does not reveal more personal data privacy than using a trusted third party.

Safe multi-party computing development level

The "safe multi-party computing protocol" for specific mission-specific purposes dates back to the late 1970s. But universal safety multiparty computing, which can safely calculate any function, originated in 1982. Yao Zhizhi raised the issue of millionaires and officially introduced a two-party secure computing method based on obfuscated circuits. Later, he gradually produced a variety of algorithms based on obfuscated circuits and based on secret sharing. We can divide the history of secure multiparty computing into three phases:

Phase 1 : The introduction of two-party security computing from Yao Zhizhi has been around for more than 30 years. Later, various different security multi-party calculation algorithms appeared. Most of these work is only theoretical, because they are too inefficient and not practical.

Phase 2 : To address efficiency issues, cryptographers have developed highly optimized, dedicated, secure multiparty algorithms for a variety of use cases. But designing for each application from scratch does not promote the widespread use of secure multiparty computing.

Phase 3 : Since the late 2000s, specifically since 2010, a generic compiler for performing secure multiparty computations on arbitrary functions has been developed. These projects have rapidly improved existing technology and are beginning to enable non-professional users to use secure multiparty computing. Significant improvements in secure computing algorithms and steady growth in hardware performance make secure multiparty computing a viable solution to a large number of real-world problems. Modern security multiparty computing protocols are fast enough to safely evaluate complex functions on medium to large data sets, such as numerous implementations of secure regression analysis with tens to hundreds of thousands of observations.

There are now a variety of open source, secure, multiparty computing frameworks for developers to use. In a speech at the Security and Privacy 2019 Security and Privacy 2019, held on May 23, 2019, "SoK: A Common Framework for Secure Multiparty Computing," summarizes and contrasts the current popular security computing framework:

Among them, the black dot means "yes", the white dot means "no", and the half white half black means only a small number of documents, a small number of examples or part of open source. Different frameworks support different security protocols. Users can select the applicable framework according to actual scenario requirements. Specific secure multiparty computing algorithms, performance, and application examples are covered in our future articles.

Secure multiparty calculation for blockchain

Secure multi-party computing, support individuals who do not trust each other, and perform privacy protection calculations without a trusted third party. This is in line with the blockchain industry, which is closely related to the decoupling network of the blockchain, the decentralization feature, and the goal of solving the trust problem.

Blockchain security multi-party computing market, privacy smart contract. Sometimes, people are more interested in statistical analysis of the data associated with this person than obtaining a single personal privacy data, and it usually makes more sense to get a summary answer. Blockchain security multi-party computing markets or privacy smart contracts can solve such problems. Secure multi-party computing enables untrusted multi-party, joint computing of sensitive data, intersection of sensitive data, and joint modeling of sensitive data. This process, combined with smart contracts, enables privacy smart contracts, automated payments, and a secure multi-party computing market .

There are many such projects, such as Datum personal information sharing market, Data Broker DAO's IoT data sharing market, matrix elements of JUGO, iCube, ARPA and so on. As a concrete example, MIT Engima's design in the medical field combines secure multi-party computing and blockchain. They plan to use blockchains for medical data sharing and privacy calculations. They divide the system into three levels, the bottom layer is the blockchain network; the middle layer is the encryption facility layer provided by Engima, providing secret sharing and secure computing functions; the upper layer is the data warehouse layer, there is a data warehouse providing traditional medical data, and there are also Smart contracts, etc.

Enigma allows smart contract developers to write what the team calls "secret contracts." A secret contract is essentially a smart contract that works with private data. Enigma's secret contract will have code that is partially executed on a public chain (such as the Enigma blockchain) and that is implemented on Enigma's decentralized out-of-band privacy computing network. The public chain will be used primarily as a security measure to store auditable evidence that the executable code is properly executed. This part of the evidence is called proof-of-MPC.

Key management based on secure multiparty computing . The private key that owns the account in the digital currency indicates ownership of the funds. In order to improve asset security, especially large-value assets, there are currently two options: multi-signature and secret sharing.

l Multi-signature . Usually, there are multiple private keys N, and the assets can be used only when the signatures of the M private keys are involved. Therefore, it is indeed safe to give the private key to different people for safekeeping. Even if some of the private keys are compromised, the assets are safe as long as they do not go beyond the scope of fault tolerance.

l Secret sharing . The Secret Sharing Scheme (SSS) mode divides the key into multiple parts and stores them in a redundant manner. When a transaction is initiated, a certain number of keys are reassembled into a key for signing. This solution can also tolerate the risk of partial key theft, and solves the shortcomings of the above-mentioned multi-signal cost. However, SSS has one major drawback: when the key is reassembled, it gives the attacker an opportunity to get the key.

Recently, KZen announced the new ZenGo wallet, a wallet that does not require mnemonics and passwords. Greatly improved the user experience. KZen's key management uses a threshold signature method, which combines the advantages of multiple signatures and secret sharing . On the one hand, multi-signatures are usually carried out on the chain, and the threshold signature line is performed at a lower cost than the multi-signature. On the other hand, threshold signatures do not require refactoring of keys, which is more secure than secret sharing.

It is based on multi-party secure computing technology and uses two independent (partial) keys instead of the traditional single private key pattern. One of the keys is stored on the phone (accessed with TouchID/FaceID) and the other is stored on the ZenGo server. When the transaction is in progress, the phone and the ZenGo server communicate to complete the signature.

Random number generation based on secure multiparty calculations . The generation of random numbers in decentralized systems is a problem. Some blockchain systems use a secure multi-party calculation method to generate fair random numbers that are not manipulated by a single individual.

For example, in the small ant consensus algorithm, after the bookkeeper is voted for, a person will be randomly selected to come out. The bookkeeper uses Shamir's Secret Sharing Scheme (SSSS) to collaborate to generate random numbers. The SSSS scheme is usually used for password sharing. Through the SSSS scheme, N ciphertext fragments can be generated by ciphertext S, and the ciphertext S can be restored by holding the K shares. The bookkeeper (assuming there are N +1) can reach a consensus on the random number through three steps.

Step 1: Each biller chooses a random number, generates the N pieces by the SSSS scheme, encrypts them with the other N biller's public keys, and broadcasts them to other billers.

Step 2: After receiving the broadcasts of the other N billers, decrypt the part that can be decrypted by yourself and broadcast it.

Step 3: After collecting at least K ciphertext fragments, solve the random number; after obtaining the random numbers of all the billers, merge and generate the block random numbers.

Random numbers are generated collaboratively by individual billers, and as long as there is an honest biller involved, even if all other billers collude, the random number cannot be predicted or constructed.

to sum up

In summary, the framework of secure multi-party computing technology is constantly evolving, which improves the general-purpose and performance of secure multi-party computing. The application of secure multi-party computing will appear in large numbers . At the same time, its role in the blockchain system is constantly being explored, and blockchain multi-party computing has become the next high-tech highlight . Especially in the past two years, in March 2018, the MIT Engima team planned a new blueprint for “privacy contract”; Ant Jinfu established a blockchain Moss security computing platform; Wanxiang blockchain lab and matrix element jointly established the PlatOn project. The blockchain security multi-party calculation algorithm will be released in Q3 in 2019.

Of course, the development of technology takes time. The blockchain + secure multi-party computing project needs to overcome two technical difficulties .

1. Network latency, transmission rate, packet loss, and number of nodes can seriously affect the amount of data stored in secure multiparty computing, memory allocation, and transmission. In the blockchain system, especially in the public chain system, how to overcome the difficulty and improve efficiency is one of the difficulties.

2. How to cooperate with the chain and the chain, how to verify that the participants correctly performed the safe multi-party calculation is another difficulty.

Although there are technical difficulties, I believe that secure multi-party computing technology is a very promising technology. And after years of development, it has been very close to landing. The combination of secure multi-party computing and blockchain technology is also very suitable. In the future, it may become a common infrastructure together with the blockchain, solve the trust problem and release great value.

Author: Dipperin