Secure Multi-Party Computation (MPC) is a branch of cryptography that can safely compute data collaboratively and output results based on open computing logic without trusting third parties.
Even if only they know the data input by each party, they can still get the calculation results they want through the encryption algorithm, but they cannot infer the original encrypted data, thus ensuring privacy security.
MPC originated from the millionaire problem proposed by Academician Yao Qizhi in 1982. Since the establishment of MPC theory, there have been a number of technical branches, including confounding circuit, secret sharing, homomorphic encryption, casual transmission, privacy set intersection and differential privacy.
Confuse the circuit
Secret Sharing (SS) is also known as Yao’s encryption circuit. It was proposed by Professor Yao Qizhi in 1986, so it is also called Yao’s circuit.
Its core is to compile the security calculation function into the form of Boolean circuit and encrypt the circuit itself. There are two operations for confounding circuits:
One is to generate a confounding circuit, which is a Boolean circuit with a specific function. Then, based on this, a confounding circuit can be generated by converting the logic gate (true value) into a confounding gate (false value).
The other operation is called the evaluation operation, which uses the obfuscation circuit to calculate the output.
The obfuscation circuit can also be understood as a cryptographic protocol, which forms a secure computing protocol based on the obfuscation circuit, and derives the multi-party security protocol from the original two-party security protocol.
Secret sharing
Secret sharing (SS) was proposed by Shamir and Blakley in 1979. The secret sharing algorithm simplifies extremely complex circuit design into simple and efficient mathematical ideas.
In its basic form, each number is broken up into multiple numbers and distributed to multiple participants, each of whom receives only a portion of the original data.
As a result, the only way to get real data is to put the pieces together.
Secret sharing can be divided into polynomial interpolation-based secret sharing and additive secret sharing due to different secret splitting methods.
Additive arithmetic secret sharing can calculate linear operation and additive Boolean secret sharing can calculate nonlinear operation such as comparison size.
Additive secret sharing is widely used in MPC because it only requires simple computation and has low computational cost. The disadvantage of secret sharing is that the number of interactive rounds depends on the depth of the circuit.
Casual transmission
Oblivious transfer (0T) was proposed by Rabin in 1981. The message sender has multiple messages, and the receiver can only get a certain value of them, while the sender does not know the selection information of the receiver.
The derivative technology correlated careless transmission (COT) can generate random numbers with relation.
OT and COT are important cryptography components that can transmit wire labels for GC and generate relevant random numbers for SS. MPC protocol can also be implemented using only OT technology.
In the process of OT performance optimization, SYMMETRIC encryption is introduced in OT Extension technology to reduce computing overhead, and silent OT Extension technology locally expands random number seeds to reduce communication overhead.
Homomorphic encryption
The concept of homomorphic encryption (HE) was proposed by Rivest et al. in 1978 to perform computations directly on encrypted data without decryption.
In the development process, some homomorphic encryption schemes and shallow homomorphic encryption schemes have been proposed, until Gentry constructed the first full homomorphic encryption scheme in 2009.
The advantage of homomorphism encryption is that it can design MPC protocol with better number of rounds at the minimum communication cost, but the disadvantage is that multiplicative homomorphism operation will bring large calculation and storage overhead, and at present additive homomorphism is widely used in practice.
Difference of privacy
Differential Privacy (DP) technology is a new cryptography method proposed by Dwork in 2006 to solve the problem of database Privacy disclosure.
The mechanism is to add a specific distribution of noise to the source data or calculated results to ensure that participants cannot use the resulting data to determine whether a particular entity is contained in the data set.
Differential privacy includes local differential privacy and computed result differential privacy.
Local differential privacy refers to adding noise to data before aggregation and calculation, which is used in scenarios where the data collector is not trusted.
Differential privacy of calculation results refers to adding noise to the final calculation results before they are published.
Privacy set intersection
Private Set Intersection (PSI) is a classic problem in the field of multi-party secure computing. PSI requires participants to jointly calculate the Intersection of sets of multiple participants without disclosing the local Set to each other, and cannot disclose information other than the Intersection to any participant.
PSI is one of the key technologies of privacy computing and a key support technology for longitudinal federated learning.
In longitudinal federated learning scenarios, PSI is also known as Sample Alignment or database collision, that is, participants need to first calculate the intersection of their training Sample ID sets.
The subsequent longitudinal federation model training was carried out based on the ID intersection of training samples.
Zero knowledge proof
Zero-knowledge proof is a computing technique in which the prover is able to convince the verifier that an assertion is correct without providing any useful information to the verifier.
The principle of zero-knowledge proof is to construct a multi-party protocol, that is, a series of steps that the participating parties need to take to complete a task by completing these steps.
The prover proves and convinces the verifier that it knows or owns a message, but the proof process cannot reveal any information about the proven message to the verifier.
summary
At present, the most typical application scenario of MPC technology is privacy-preserving machine learning (PPML).
From algorithm, multiparty secure computation according to the input data in the parties do not leak under the premise of complete multilateral coordination analysis, processing characteristics and publish the results of this technology, extensive should be used for joint statistics, a federated query, joint model, combined prediction scenarios, such as can also support user-defined calculation logic general-purpose computing needs.
This article is an overview of multi-party secure computing, followed by technical features and how MPC technology can be used to implement PPML solutions.
reference
[1] Guo Juanjuan, Wang Qiongxiao et al. Applications of secure multi-party computing machines in machine learning. Computer Research and Development. 2021.06
[2] The Privacy Computing Consortium. White Paper on Privacy Computing (2021). 2021.07