Secure multiparty computing
Before discussing secure multiparty computing (using MPC below), let’s discuss the setup of secure multiparty computing. Of all the participants in the MPC, some participants may be controlled by an adversary (attacker), and the participant under the control of the adversary is called a corrupted party, which will follow the instructions of the adversary to attack the protocol during its execution. A secure agreement should withstand attack by any adversary. In order to formally describe and prove that a protocol is “secure”, we need a precise definition of MPC security.

Step 1: Security

The security specification for secure multiparty computing is defined by an Ideal/Real Paradigm. In an ideal world, there is a Trusted Third Party (TTP), where each participant provides their own secret data to a trusted third party through a secure channel, and the third party computes the function on the joint data, and after completing the calculation, the trusted third party sends the output to each participant. Since the only action that each participant can perform during the computation is to send the secret data to a trusted third party, the only action that the attacker can perform is to select the input of the corrupted participant, and the attacker cannot obtain any information other than the result of the computation.

The ideal world corresponds to the real world, where there are no trusted third parties, where participants participate in protocol execution without the help of any external nodes, and where some participants may be “corrupted” or colluded by attackers. Therefore, a security protocol in the real world is subject to attack by any adversary in the real world, and when the same adversary attack exists in the ideal world, the joint distribution of input/output data between the adversary and the honest participant in the ideal world is computationally indistinguishable from the joint distribution of input/output data in the real world. That is, it simulates real-world protocol execution in an ideal world.

The ideal world/real world paradigm is designed to ensure that multiple attributes implied by “security” are met.

1) Privacy: Neither party should obtain more output than it has specified, and in particular should not obtain input information from other partners from the output information. An attacker in an ideal world could not obtain any information other than the output of the corrupted party, and the same is true in the real world.

2) Correctness: Ensure that the output received by each party is correct. The output an honest participant gets in the real world is the same as the output from a trusted third party in the ideal world.

3) Input independence: The input chosen by the corrupted participant must be independent of the input of the honest participant. In an ideal world of protocol enforcement, a corrupted participant would not have access to any input from an honest participant when sending input to a trusted third party.

4) Guarantee output: Corrupted participants should not be able to prevent honest participants from obtaining output.

5) Fairness: The corrupted participant can obtain the output if and only if the honest participant obtains the output, that is, there is no case where the corrupted participant obtains the output and the honest participant does not obtain the output. In an ideal world, a trusted third party would always return the output to all participants. Thus output and fairness are guaranteed. This also means that in the real world, honest participants get the same output as in the ideal world.

2. Participants

We need to define the participants of the MPC: The participants of the MPC are the parties involved in the protocol, and each participant can be abstracted as an interactive Turing machine with a Probabilistic Polynomial Time Algorithm (PPT Algorithm). Corrupted participants can be classified into three types of adversaries based on their ability/power to control participants during the execution of the agreement.

1) Semi-honest adversary: This participant will follow the steps required by the agreement. However, a semi-honest adversary will try to obtain all the information during the execution of the protocol (including the execution script and all the messages received) and try to derive additional privacy information.

2) Malicious enemy: In the process of implementing the protocol, such participants execute all steps of the protocol in full accordance with the instructions of the attacker, and will not only disclose all inputs, outputs, and intermediate results to the attacker, but also change the input information according to the intention of the attacker, forge intermediate and output information, and even terminate the agreement.

3) Secret Adversary: This type of adversary may conduct malicious attacks on the protocol, and once it launches an attack, there is a certain probability that it will be detected. If it is not detected, then it may have completed a successful attack (the attack was launched to obtain additional information).

Therefore, according to the attack behavior of different participants in the secure multi-party computing protocol in the real world, the security model of the protocol can be divided as follows.

1) The Semi-Honest Model: During the execution of the protocol, participants execute according to the process specified in the protocol, but malicious attackers may monitor and obtain their own input and output during the execution of the protocol, as well as information obtained during the operation of the protocol.

2) The Malicious Model: During the execution of the agreement, attackers can use the participants under their control to analyze the private information of honest participants through illegal input or malicious tampering of input, and can also terminate the agreement by early termination or refusal to participate.

In addition, depending on when and how the opponent controls the player, the opponent’s corruption strategy can be divided into the following three models.

1) Static Corruption Model: In this model, an adversary controls a fixed set of partners before the agreement begins. An honest partner is always honest, and a corrupt partner is always corrupt.

2) Adaptive Corruption Model: The adversary can decide which participant to corrupt at what time, and it should be noted that once a participant is corrupted, it will always remain corrupted.

3) Proactive Security Model: Honest participants may be corrupted at some point, and corrupt participants may become honest participants at some point. The active security model is from the point of view of an external adversary who may invade a network, service, or device. When the network is repaired, the adversary loses control of the machine, and the corrupted actor becomes an honest actor.

In the real world, MPC protocols do not run in isolation, usually by modularization combinations of protocols or by parallel (running) combinations with other protocols to get a larger protocol to run on.

It has been shown that if an MPC protocol is run sequentially within a larger protocol, it still follows the real/ideal world paradigm where a trusted third party executes the protocol and outputs the corresponding result. This theory is called “modular composition,” and it allows for the construction of larger protocols in a modular manner using secure subprotocols, as well as the analysis of a larger system that uses MPC for certain computations.

For the case of parallel running of the protocol, when there are other protocols running in parallel with the current protocol, if the protocol does not require other parallel protocols to send any messages, this assumption can be called the independent setting of the protocol, which is also the basic security definition of MPC security. In an independent setting, a protocol running in parallel behaves like a trusted third party.

Finally, in some other scenarios, the MPC protocol may run in parallel with other instances of the protocol, or other MPC protocols, or other insecure protocols, and the protocol instance may need to interact with other instances, in which case the operation of the protocol may be insecure. In the ideal world, the protocol does not involve interaction with other protocols (functional functions), while in the real world, it needs to cross tiles with another functional function, and there are different execution conditions than the simulation of the ideal world (the real world at this time can be called the mixed world). In this case, the prevailing approach is to define security in terms of “Universal Composability,” in which any protocol that is proven to be secure is guaranteed to perform as desired, regardless of whether it is executed in parallel with any other protocol.

Specifically, if an MPC protocol is secure in the real world, then for a practitioner using the MPC protocol, he can only consider the implementation of the MPC protocol in an ideal world, that is, for non-cryptographic users of the MPC protocol. You can ignore how the MPC protocol works, or whether the protocol is secure, because the ideal model provides a clearer and simpler abstraction of the MPC’s functionality.

Although the ideal model provides a simple abstraction, there are situations in which the following problems can easily arise.

1) In the real world, an adversary may enter any value, and the MPC protocol has no universal solution to prevent this. For example, in the “millionaire” problem, the opponent can enter any amount of wealth of the corrupted participant (such as directly entering the maximum), and the corrupt opponent will always be the “winning” side. If the application of an MPC protocol depends on the correct input of the participant, then the correctness of the participant input needs to be enhanced/verified by other techniques.

2) The MPC protocol only guarantees the security of the calculation process, but cannot guarantee the security of the output. Output of the MPC protocol After the disclosure of each participant, the output given may reveal the input of other participants. For example, if the average of the salaries of two participants needs to be calculated, the MPC protocol can guarantee that no information other than the average salary will be output. However, it is perfectly possible for one participant to calculate the salary of the other participant based on his or her own salary and the average salary. Therefore, using MPC does not mean that all information is protected.

In practice, considering the calculation and communication overhead of MPC, the semi-honest model is usually used as the main security setting. Therefore, the MPC protocols discussed in this book are mainly protocols based on the semi-honest model. Although some MPC protocols can support both semi-honest and malicious security, this article focuses on the semi-honest setting of MPC protocols.

cryptography
Cryptography is an important basis of privacy computing technology and is often used in various technical routes of privacy computing. The theoretical system of cryptography is very large and complex, and interested readers can refer to Modern Cryptography and its applications and other books to expand their learning. This paper only gives a brief introduction to the basic knowledge of cryptography and common cryptographic primitives used in privacy computing.

In MPC, two types of data encryption are often used: symmetric encryption and asymmetric (public key) encryption.

1) Symmetric encryption is an earlier encryption algorithm, and its technology is mature. Because encryption and decryption use the same key, it is called symmetric encryption. Common symmetric encryption algorithms include DES, AES, IDEA, and so on.

2) Asymmetric encryption is also known as public key encryption. Unlike symmetric encryption, asymmetric encryption algorithms require two keys: the public key and the private key, and the two appear in pairs. The private key is kept by the user and cannot be disclosed. A public key is a public key that can be obtained by anyone. Data is usually encrypted using a public key and decrypted using a private key. Another use of asymmetric encryption is digital signature, where data is signed using a private key and verified using a public key. Digital signatures allow the public key holder to verify the identity of the private key holder and prevent the content posted by the private key holder from being tampered with. Common asymmetric encryption algorithms include RSA, EIGamal, D-H, ECC, and so on.

1. Elliptic curve encryption

Elliptic curve encryption is a kind of public key encryption technology, which is often combined with other public key encryption algorithms to obtain the corresponding elliptic curve version encryption algorithm. It is generally believed that elliptic curves can achieve higher security with shorter keys. Elliptic curve encryption is an encryption algorithm based on the discrete logarithm difficulty problem, which restricts the elliptic curve addition group on the real number field to the prime number field. An elliptic curve over a field of real numbers can usually be defined by a binary cubic equation, using the commonly used Weierstrass elliptic curve equation as an example:

Where, a and b are configurable parameters. All the corresponding solutions of the elliptic curve equation (all points on the curve of the equation in the two-dimensional plane) plus a point 0 at infinity (the identity of the group, point 0) form the set of elements of the elliptic curve. On the set of these points, the corresponding addition calculation and inverse calculation satisfying the properties of closure, commutation and association can be defined to form the addition group of elliptic curves. By modifying different parameters a and b of elliptic curves, different groups of circular curves can be obtained, as shown in Figure 1.

Figure 1. Elliptic curve groups with different parameters

For the two points P and Q on the elliptic curve, the line passing through the two points and the intersection point R with the elliptic curve are first defined. The addition of P and Q on the elliptic curve results in a symmetric point of R with respect to the X-axis. The addition operation definition covers a variety of cases, as shown in Figure 2.

Figure 2. Addition of four different points of the elliptic curve

1) P and Q are not tangential points and not reciprocal elements, then there is a third intersection R, then P+Q=-R.

2) P or Q is the tangent point (assuming 0), then the line after P and 0 are connected is called the tangent line, then R=O is defined, then P+Q+Q=0. The result of addition is P+O=-Q.

3) If the line between P and Q is perpendicular to the X-axis, then there is no intersection between the line and the elliptic curve, then the intersection is considered to be at infinity, that is, P+Q=0.

4) If P=Q, then the line is considered to be the tangent line of the elliptic curve at point P; If the tangent has an intersection R with the elliptic curve, the result is -R; otherwise, the intersection is considered a point at infinity.

The addition of elliptic curves is implemented by calculating the slope of the line between P and Q

Then calculate the coordinates of the intersection point R according to Veda’s theorem:

If P and Q are the same point, the slope calculation is modified to

Then calculate the coordinates of R according to the above formula.

Scalar multiplication of an elliptic curve (or multifold point operation) can be achieved by adding points many times, such as nP means adding nP points:

Since the elliptic curve addition group satisfies the commutative and associative laws, it can be optimized by the Double-and-Add algorithm.

When the elliptic curve addition group is applied to encryption, it is usually necessary to restrict the elements of the elliptic curve to a prime number field, so the discrete logarithm problem can be constructed based on its scalar multiplication. The elliptic curve of a prime number field is defined as follows:

The distribution of elliptic curve points in a prime number field of a=-1 and b=3 is shown in Figure 3.

Figure 3

For a field defined in prime numbers

Upper ellipsometer