|
|
1.INTRODUCTIONSecret sharing (SS) is widely used in multi-party computation (MPC) because of its simple secret structure and low computational overhead. SS was first proposed by Shamir and Blakley in 19791-2. For secret sharing- secure multi-party computation (SS-MPC), participants calculate the secret shares of different secret data to obtain the shares of calculation results. A sufficient number of result shares can be combined to recover the calculation results. According to different secret splitting methods, SS-MPC is divided into polynomial interpolation based SS and additive SS. Compared with Shamir’s polynomial interpolation based SS, additive SS has less overhead and high efficiency in calculating linear operation, and is more widely used in SS-MPC. The early SS-MPC schemes have the characteristics of many interaction rounds and high communication overhead, such as GMW3, BMW4 and other schemes. Most SS-MPC schemes optimize these two indexes. AFL+165, ASTRA6 and other schemes optimize SS-MPC by reducing the number of communication rounds and interaction of SS-MPC to varying degrees. In 2011, Bendlin proposed BDOZ scheme7, which realized the SS-MPC operation with the majority of dishonest participants for the first time, and achieved the suspension security, that is, the protocol was suspended when the malicious behavior of the computing party was found. In order to solve the problem of storage overhead in BDOZ, Damgård proposed SPDZ scheme in 20128. SPDZ scheme is an SS-MPC scheme based on additive SS. At the same time, each participant stores a constant number of MAC codes to verify whether the data is maliciously tampered by the computing party. After that, References9-10 and other schemes have optimized the SPDZ scheme to varying degrees. At present, the importance of SS-MPC in MPC is obvious, and many studies are still ongoing. However, whether the dishonest computing party tampers with the data share is concerned or not, the existing SS-MPC scheme cannot solve the problem that all computing parties participate in collusion. If all computing parties are involved in collusion, all secret shares will be combined. To solve the above problems, this work proposes an SS-MPC scheme (PSCW) that can effectively deal with the collusion of all computing parties. Based on the calculation of additive SS, through the negotiation of redundant computing nodes and redundant security parameters between participants, it can ensure that even if all computing nodes collude to obtain all secret shares, they cannot recover the original data. At the same time, PSCW scheme can still carry out addition and multiplication correctly when adding redundant calculation nodes, which ensures the correctness of calculation results. This scheme solves the problem of collusion of all computing parties in SS-MPC scheme, optimizes the security level, and has high application value. 2.PRELIMINARYThe main idea of additive SS is that the secret distributor divides a secret x into n shares {x1,x2,…,xn} and sends them to the participant Pi, i = 1,2,… n respectively. All participants can cooperate and reconstruct the secret with these shares, the secrets cannot be recovered when the number of participants is less than n. In this paper, similar with Reference10, our scheme operates on ℤ2k, which consists of two algorithms (Sharing,Reconst) :
Because the additive secret SS has additive homomorphism11, given the share [x], [y] of the secret x, y, the participant can calculate the share [x + y] = [x] + [y] of the secret x + y, so arithmetic addition can be calculated. Given the share [x],[y] of the secret x, y, the participant can calculate arithmetic multiplication share [x·y] = [x]·[y]with beaver triple11. The specific calculation process is as follows:
3.PSCW SCHEMEThis work designs a secret sharing scheme PSCW, which can effectively solve the problem of collusion of all share holders. 3.1PSCW scheme modelThe model of the scheme is shown in Figure 1. The PSCW scheme involves the following roles: user, processing node, calculation node and coordination node. User provides the data required for calculation and negotiates that some nodes in the calculation nodes are redundant nodes. The scheme sets up a private data processing node for each user, which is responsible for secret share segmentation and aggregation of data. The computing node is responsible for calculating the data. The existence of redundant calculation node can ensure that the original data cannot be restored even if all computing nodes conspire. The coordination node is responsible for providing security parameters for all computing nodes for secret sharing multiplication. In the scheme, the number of participating users is 2, the original data value held is X,Y, and the number of calculation nodes is n. This scheme can be extended to the scenario of multiple participating users. 3.2Security assumption and security requirementsSecurity assumption: in PSCW scheme, there is the possibility that all computing nodes conspire to recover the original data. Security requirements: the security requirements of PSCW scheme include its correctness and confidentiality, which are introduced below:
3.3Introduction to scheme algorithmThe algorithm of PSCW scheme is described in detail below: Input: user U1,U2 ’s private data X, Y. Output: calculation result RS obtained according to user requirements.
4.1Correctness proofTheorem 1: PSCW scheme can correctly calculate addition X +Y and multiplication X ·Y in the state of secret sharing when adding redundant computing node RNode, so PSCW scheme can correctly compute calculation results obtained by user requirements. Proof: first consider the addition operation. According to preliminary, the addictive SS algorithm has the characteristics of additive homomorphism. Since only the effective computing node CNode holds the secret share [X],[Y] of the data X,Y to be calculated, while RNode holds the secret share [M],[N] of redundant data M,N, therefore, the data processing node only needs to recover the Reconst algorithm of [X +Y] = [X]+[Y] calculated by all CNode, that is, it can get the correct result of X +Y. Next, consider multiplication. As described in equation (2), multiplication operation needs to be realized with the help of beaver triples. Therefore, it is necessary to coordinate the nodes to send security parameters to each computing node. During the calculation, all CNode disclose [α] = [X]–[a] and [β] = [Y]–[a], all RNode disclose [μ] = [M]–[d] and [σ] = [N]–[e]. According to the preliminary, all CNode calculate Since the data processing node only needs to process the data sent by CNode, it does not need to consider the calculation results of RNode. Recover all the calculated [Z] by CNode by Reconst algorithm, that is, X·Y can be obtained correctly. To sum up, PSCW scheme meets the requirements of correctness. 4.2Confidentiality proofTheorem 2: if the secret sharing algorithm used in PSCW scheme is secure, the confidentiality of user data can be guaranteed in the calculation process. Proof: In the calculation process of PSCW scheme, the interactive parameters are the secret sharing share [X],[Y] of data X,Y, the secret sharing share [M],[N] of redundant data M,N and the secret sharing share of security parameters generated by the coordination node. Because the security parameters are randomly generated by the coordination node, and no data transmission between users is done, as long as the secret sharing algorithm is secure, PSCW scheme can ensure that the users’ respective real data X,Y will not be exposed in the calculation process. Theorem 3: in the case of all computing nodes conspire, PSCW scheme can ensure that the adversary cannot obtain the real information about user data. Proof: If all computing nodes conspire, the adversary can get all the secret sharing shares [X],[Y],[M],[N] of data X, Y and redundant data M, N. However, due to redundancy, computing nodes are negotiated between users, the calculation node cannot determine whether it is a redundant node. Therefore, if all calculation nodes participate in the conspiracy, the secret sharing share [M],[N]of the redundant data RNode will interfere with the Reconst algorithm when recovering data, so that the adversary cannot obtain the real information of user data. To sum up, PSCW scheme meets the requirements of confidentiality. 5.SCHEME COMPARISONTable 1 compares the safety of PSCW scheme with the existing ss-mpc scheme. Table 1.Security comparison between PSCW and other schemes.
According to Table 1, we can find that compared with other SS-MPC schemes, in terms of security, this scheme not only supports semi-honest computing parties and malicious computing parties at the same time, but also solves the problem of collusion of all computing parties, avoids the recovery of secret data and reach greater security. In terms of computational efficiency, this scheme uses additive SS secret sharing, which is not different from the above scheme, only the calculation part of redundant computing nodes is added. Therefore, our scheme does not sacrifice much in computational efficiency. 6.CONCLUSIONAiming at the problem that the existing SS-MPC scheme cannot deal with the collusion of all computing parties to recover the original data, this paper proposes PSCW scheme, which effectively solves this problem through the negotiation of redundant computing nodes on the basis of additive SS. The security proof shows that the scheme can still carry out addition and multiplication effectively when adding redundant computing nodes; our scheme can meet the confidentiality of data in the calculation process in the case of collusion of all nodes. Compared with the existing SS-MPC scheme, this scheme optimizes the security without sacrificing the computing efficiency, solves the security problem of collusion of all computing parties, and can be effectively applied to the MPC scenario. REFERENCESShamir, A.,
“How to share a secret,”
Communications of the ACM, 22
(11), 612
–3
(1979). https://doi.org/10.1145/359168.359176 Google Scholar
Blakley, G. R.,
“Safeguarding cryptographic keys,”
AFIPS, 313
(1979). Google Scholar
Goldreich, O., Micali, S. and Wigderson, A.,
“How to play any mental game, or a completeness theorem for protocols with honest majority,”
Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 307
–28
(2019). Google Scholar
Ben-Or, M., Goldwasser, S. and Wigderson, A.,
“Completeness theorems for non-cryptographic fault-tolerant distributed computation,”
STOC,
(1988). Google Scholar
Furukawa, J., Lindell, Y., Nof, A., et al.,
“High-throughput secure three-party computation for malicious adversaries and an honest majority,”
in Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques,
(2017). https://doi.org/10.1007/978-3-319-56614-6 Google Scholar
Patra, A. and Suresh, A.,
“BLAZE: Blazing fast privacy-preserving machine learning,”
in Network and Distributed System Security Symp.,
28
(2020). Google Scholar
Yehuda, L. and Ben, R.,
“Blazing fast 2PC in the offline/online setting with security for malicious adversaries,”
in Proc. of the 22nd ACM SIGSAC Conf. on Computer and Communications Security (CCS’15),
(2015). Google Scholar
Damgård, I., Pastro, V., Smart, N. and Zakarias, S.,
“Multiparty computation from somewhat homomorphic encryption,”
Advances in Cryptology-CRYPTO, 7417 643
–62 Springer, Berlin, Heidelberg
(2012). Google Scholar
Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P. and Smart, N. P.,
“Practical covertly secure MPC for dishonest majority-or: Breaking the SPDZ limits,”
ESORICS, 2013 1
–18
(2013). Google Scholar
Cramer, R., Damgrd, I., Escudero, D., Scholl, P. and Xing, C., Spdz2k: Efficient MPC mod 2k for dishonest majority,
(2018). Google Scholar
Beaver, D.,
“Efficient multiparty protocols using circuit randomization,”
CRYPTO, 1991 420
–32
(1992). Google Scholar
|
