Technical Field

This invention relates to Secure Multi Party Computation (SMPC) protocols.

Background Art

Secure Multi Party Computation (SMPC) enables a set of parties to collaboratively compute a function over their inputs while keeping them private. There are several SMPC flavours described in the literature, including Yao's Garbled Circuits (Yao, Andrew Chi-Chih (1986). "How to generate and exchange secrets". 27th Annual Symposium on Foundations of Computer Science (SFCS 1986). Foundations of Computer Science, 1986., 27th Annual Symposium on. pp. 162-167. doi:10.1109/SFCS.1986.25. ISBN 978-0-8186-0740-0.), GMW (O. Goldreich, S. Micali, A. Wigderson, "How to play ANY mental game", Proceedings of the nineteenth annual ACM symposium on Theory of Computing, January 1987, Pages 218-229, doi:10.1145/28395.28420; and T. Schneider and M. Zohner, "GMW vs. Yao? Efficient secure two-party computation with low depth circuits," in Financial Cryptography and Data Security (FC' 13), ser. LNCS, vol. 7859. Springer, 2013, pp. 275-292.), BGW (Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In: Proc. ACM STOC '88, pp. 1-10 (1988)), SPDZ (Damgard I., Pastro V., Smart N., Zakarias S. (2012) Multiparty Computation from Somewhat Homomorphic Encryption. In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology - CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_38), BMR (Beaver, D., S. Micali, and P. Rogaway. 1990. "The Round Complexity of Secure Protocols (Extended Abstract)". In: 22nd Annual ACM Symposium on Theory of Computing. ACM Press. 503-513), and GESS (Kolesnikov, V. 2005. "Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation". In: Advances in Cryptology - ASIACRYPT 2005. Ed. by B. K. Roy. Vol. 3788. Lecture Notes in Computer Science. Springer, Heidelberg. 136-155).

There are two main constructions of SMPC: Circuit Garbling (CG) and Linear Secret Sharing (LSS). Circuit garbling requires encrypting keys in a specific order to simulate the function evaluation. Linear Secret Sharing computes shares from the inputs and distributes them among the nodes. In this disclosure we focus on SMPC flavours using LSS.

The following is a list of the main roles for the nodes participating in a SMPC computation: Dealer node: These nodes contribute inputs to the computation

Computing node: These nodes perform the actual SMPC computation on the inputs provided by dealer nodes

Result node: These nodes reconstruct the result from a finished SMPC computation

LSS SMPC protocols comprise the following three phases:

Phase 0 (optional)- Pre-processing: Some LSS SMPC protocols require nodes to run preliminary computations like the generation of multiplicative triplets in Beaver's version of BGW (Beaver, D. "Efficient Multiparty Protocols Using Circuit Randomization". In: Advances in Cryptology - CRYPTO'91. Ed. by J. Feigenbaum. Vol. 576. Lecture Notes in Computer Science. Springer, Heidelberg. 420-432), or in SPDZ. These computations are not related to the private inputs of any particular SMPC computation and therefore can take place in a previous offline phase.

Phase 1 - Share distribution: Each dealer node breaks down each private input to the computation into a number N of shares and sends each share to a different computing node. Each share reveals no information about the private input. It is only when all N shares from a private input are gathered that it can be reconstructed.

Phase 2 - Computation: Each computing node has one share from each private input to a computation. The computation consists of evaluating the output of a function over the private inputs. In order to do this, the computing nodes perform operations on their shares that depend on the specific function to be evaluated by the SMPC protocol.

Phase 3 - Result reconstruction: After Phase 2, each computing node has obtained a share from the result of the computation (i.e. the function to be evaluated). They send their share to one or several result nodes. After gathering all N shares from the result, a result node can reconstruct the output of the function that was jointly evaluated. For example, assume that two dealer nodes have each one string. They would like the network of computing nodes to evaluate the result from comparing the two strings and to communicate this result to a result node. The strings are private to the dealer nodes, so they should not be sent over to the computing nodes in plaintext or in encrypted form. Each dealer node breaks down their private string into N shares and send each share to a different computing node. After receiving one share per each one of the two strings to be compared, the computing nodes follow the SMPC protocol to obtain a share of the result from the computation. This result could be a Boolean representing a string match with a TRUE value and a string mismatch with a FALSE value. Each node sends their share of the result to a result node, which reconstructs the TRUE or FALSE result from the string comparison.

The main problem with SMPC is the communication complexity. A large number of message exchanges and/or communication bandwidth is required in order for the computing nodes to collaboratively obtain in Phase 2 a share of the result of the function being evaluated when this function is complex. By complex function we mean a function with a large number of inputs and a large number of operations on those inputs. Real-world applications of SMPC typically require complex functions, which severely affects the applicability of SMPC in production scenarios.

For example, in BGW SMPC computing nodes evaluate arithmetic functions on integer inputs comprising additions and multiplications. Computing nodes running BGW can process additions without the need to exchange any message. However, the evaluation of multiplications requires the exchange of messages. Complex functions will have additions and multiplications, making the overall BGW function evaluation slow.

We refer herein to SMPC flavours evaluating arithmetic functions as SMPC in the arithmetic setting. The focus of the invention is on the evaluation with SMPC of any function in the arithmetic setting. In the arithmetic setting, a function can be represented without loss of generality as the sum of groups of secret products. In this setting, secrets are natural, integer, real or complex numbers.

The evaluation of a general function requires the computation of products in the arithmetic setting. State-of-the-art SMPCs require nodes to exchange messages in order to jointly evaluate arithmetic products. The exchange of messages is many orders of magnitude slower than computations on a local CPU. This is the reason why the jointly evaluation of nontrivial functions in standard SMPCs is orders of magnitude slower than on a centralised server. Disclosure of the Invention

A secure multiparty computation method is provided which permits the computation of an arithmetic function f which can be expressed as the addition of A groups of multiplications of a set S of private input secrets Dealer nodes holding the secrets are provided with a base blinding factor p _α whose inverse is the sum of a set of pseudorandom numbers each of which is associated with a respective computing node and is not shared with other computing nodes. Each dealer node is further provided with an exponent blinding factor A _{a m} specific to the secret being contributed, where all of the exponent blinding factors sum to unity. The dealer nodes share with the computing nodes the product of the secrets with the base blinding factor raised to the exponent blinding factor. Each computing nodes can independently and without sharing computations, generate from the product of shares it receives from the dealer nodes a result share. Summing the result shares provides the result of the computation. In this way a sum of products can be computed by the computing nodes without requiring any messages to pass between the computing nodes during the computation.

In one aspect there is provided a computer-implemented method, carried out between a plurality of D dealer nodes and N computing nodes, of calculating the result of an arithmetic function f which can be expressed as the addition of A groups of multiplications of a set S of private input secrets {s ₀ , s _1; ... , Ss-jJ such that: where each group of multiplications m _a , a Ε {0,1, ... , A — 1} is the product of M _a secrets of said set S of private input secrets: and the subindices { } { } identify private input secrets from the set of S secrets, and where the S secrets are selected from integers, real numbers or complex numbers, and each secret is known to one of said dealer nodes, wherein the method comprises: a) providing each dealer node contributing a secret to a group of multiplications m _α with a base blinding factor p _α which is common to all secrets contributing to said group of multiplications m _α , wherein the base blinding factor p _α satisfies (modulo p, where p is a prime number): for a set of (N x A) random or pseudorandom numbers X each associated with a respective one of the N computing nodes; b) providing each dealer node contributing a secret s _iam to a group of multiplications m _a with an exponent blinding factor _{a m} which is specific to said secret s _iam , wherein the set of exponent blinding factors _{a m} collectively satisfy (modulo p): c) storing said set of (N x A) random or pseudorandom numbers X _{n a} for n E either (i) at the computing nodes in a first mode of operation ("network mode") whereby each of the N computing nodes stores a subset of A random or pseudorandom numbers unique to that node, or (ii) at the dealer nodes in a second mode of operation ("edge mode") whereby each dealer node stores at least the subset of the (N x A) random or pseudorandom numbers X _{n a} corresponding to the additions to which that dealer contributes a secret; d) each dealer node computing, for each secret s _iam , one or more shares for that secret wherein in the network mode of operation a single share is computed, modulo p, as: and wherein in the edge mode of operation a plurality of N shares are computed, using the N random or pseudorandom numbers X associated with the group of multiplications m _a to which the secret contributes, modulo p, as: e) each dealer node sending to each of the computing nodes a respective share message which, in the network mode of operation contains the same single share v _{a m} , and in the edge mode of operation contains a respective one of the N shares v _{n a m} such that each of the N computing nodes receives the shares indexed to a unique value f) each computing node calculating, for the received shares v _{a m} or v _{n a m} associated with each group of multiplications m _a , a local product result which in the network mode of operation is calculated, modulo p, as: and which in the edge mode of operation is calculated, modulo p, as: g) each computing node calculating a local addition result from the set of local product results, modulo p, as: h) computing an output of the function f by combining the local addition results from the N computing nodes to compute:

By providing the dealer nodes with the two different kinds of blinding factors defined above, i.e. the base blinding factors and the exponent blinding factors, the shares sent from the dealers are obfuscated in a way that perfectly hides the secrets from the computing nodes, and that also allows the computing nodes to independently each perform a computation resulting in a result share, where the result shares can be combined without knowledge of the blinding factors or the secrets to reveal the result of the computation.

The methods of the invention employ a new flavour of SMPC called NMC (Nil Message Compute) which can evaluate any function in the arithmetic setting without the computing nodes having to exchange any message during the computation phase (Phase 2). NMC therefore removes the main performance problem from standard SMPC and it is capable of evaluating nontrivial functions over a large number of private inputs and using a large number of computing nodes in essentially the same time as it takes in a centralized computation where all information is available in clear inside of a single server. NMC as presented in this invention is secure against passive adversaries who are able to corrupt up to N-l from a total of N computing nodes. Passive adversaries by definition follow the protocol specification but try to learn information about the private inputs to the computation. The methods in their most basic form focus on the arithmetic setting and on functions returning only one number. The same methods can be readily extended to any number of output values using the techniques described in Appendix A.3 of Damgard I., Pastro V., Smart N., Zakarias S. (2012) "Multiparty Computation from Somewhat Homomorphic Encryption". In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology - CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_38. The contents of this reference are incorporated herein by reference for this purpose.

Preferably, step h) comprises:

(i) each computing node sending a local addition result r _n to one or more result nodes; and

(ii) the one or more result nodes performing the summation of the received local addition results to determine the result of an arithmetic function f.

Preferably, step a) comprises:

(i) each computing node n, n E {0,1, ... , N — 1} generating a random number X _{n a} ;

(ii) each computing node computing a share p _a (n + 1) of a polynomial p _a (x) of degree N-l such that (mod p):

(iii) each computing node sending its share of each p^ ¹ to each dealer node d, d E {0,1, ..., £) — 1}; and

(iv) each dealer node reconstructing from the received shares the corresponding base blinding factor p^ ¹ .

Preferably, step (ii) comprises: providing a collection of random number generators G _{n q} for n, q E {0, ... , N — 1} with n #= q, such that G _{n q} is a generator that computing nodes n and q run in sync with one another; each computing node n generating N-l random shares from the random number generators G _{n q} for each q E {0, ... , N — 1}, with q #= n to generate a respective random evaluation of a polynomial p _n (q + 1); each computing node n computing the coefficients of the polynomial p _n (x) which satisfies each of the random evaluations p _n (q + 1) and satisfies p _n (0) = each computing node n computing from said coefficients and X _{n a} a share p _n (n + 1) of the polynomial p _n (x); each computing node n generating p _q (n + 1) from the random number generators G _{n q} for each q E {0, ... , N — 1}, as its own share of the polynomial p _q (x) from every other computing node q; each node computing 2q=o Pq( ⁿ + 1) mod p to provide a share p(n + 1) of the polynomial p _a (x) evaluated at n+1; each computing node sending its share p(n + 1) of p _a (x) each dealer node contributing to the group of multiplications m _a such that each dealer node can reconstruct the independent coefficient of p _a (x) corresponding to x°, which is which is equal to the sum of the secrets

Further preferable aspects of the method include the generation of the exponent blinding factors in a collaborative manner to satisfy the constraint ⁼ 1- This is preferably done using the algorithm GenerateBlindingFactors described further below.

There is provided, as a further and independent aspect of invention, a method of distributing the initial shares from a secret sharing mechanism without sending any message as described below under the algorithm ZeroMessageShareDistribution. This can be applied, outside the context of the multiparty computation methods described herein, to any secret sharing mechanism that makes use of the generation of random numbers.

There is also provided, as yet a further and independent aspect of invention, a method of N nodes jointly adding N secrets and revealing the result of the sum of the secrets to one or more output nodes, while keeping the individual secrets private, as described below under the algorithm AddSecretsWithoutSendingTheirShares. It will be appreciated that this too can be applied outside the context of the multiparty computation methods described herein.

There is also provided, as yet a further and independent aspect of invention, a method of 1 nodes jointly generating M _a secret numbers such that their sum equals one without sharing these numbers amongst themselves, as described below under the algorithm GenerateBlindingFactors. It will be appreciated that this too can be applied outside the context of the multiparty computation methods described herein.

Brief Description of the Drawings

Fig. 1 is a network diagram of a conventional SMPC network of dealer nodes, computing nodes and result nodes;

Fig. 2 is a network diagram of the computing nodes and dealer nodes of Fig. 1 implementing the Network NMC algorithm disclosed herein;

Fig. 3 is a flowchart including message flows, illustrating the Network NMC algorithm;

Fig. 4 is a network diagram of the computing nodes and dealer nodes of Fig. 1 implementing the Edge NMC algorithm disclosed herein; and

Fig. 5 is a flowchart including message flows, illustrating the Edge NMC algorithm.

Detailed Description of Preferred Embodiments

Fig. 1 is a network diagram showing a plurality of nodes that co-operate to perform a secure multiparty computation (SMPC). The nodes are categorised as dealer nodes 10, computing nodes 12, and result nodes 14.

Not all of the nodes are labelled with a reference numeral but it should be understood that all nodes in the same group are of the same type i.e. all nodes in the left vertical line are dealer nodes 10, all nodes in the central octagonal group are computing nodes, and all nodes in the right vertical line are result nodes.

It should also be understood by the skilled person that the arrangement and number of nodes is not intended to represent any specific reality, and nodes are likely to be arranged into logical rather than physical groups, with nodes able to communicate with any other node via a network address on a public or private network which could be a local area network, or a wide area network. Nodes could be even part of the same computing system e.g. different processors or cores in a multiprocessor system. Communication protocols are at the choice of the system designer and are likely to be dictated by the application and security requirements of the system in which they are implemented. Each node may be implemented in a processor of a computing system which is programmed to perform the relevant methods and algorithms disclosed herein, and further has access to a memory, and a network connection. In many implementations, each node will be a suitably programmed computer system.

The dealer nodes 10 contribute inputs to the computation. Specifically, they are provided with secret inputs, and create shares from these secret inputs and distribute them among the computing nodes 12. The computing nodes perform the actual SMPC computation and each computing node 12 provides a share of a computation output to each result node 14. The result nodes 14 reconstruct the result from the received result shares.

In what follows, we make the following assumptions:

Assumption 1: A dealer node cannot be a computing node. Otherwise, a node can have more than one role.

Assumption 2: The number of computing nodes is equal or larger than the number of dealer nodes.

Assumption 3: There are secure point-to-point channels between different nodes in the network. In addition, message broadcasting is also supported.

Assumption 4: Without loss of generality, we assume that for every addition term m _a there is at most only one input per dealer, because if a dealer contributes with more than one input variable to the product m _a , it can always replace them with a new input variable equal to their product.

Assumption 5: Without loss of generality, we work with finite field arithmetic Z/pZ. That is, secrets are all represented as integers modulo p, where p is a prime number. All the computations that follow are therefore performed modulo p, represented as mod p. The arithmetic function /defined in claim 1 can then be expressed more succinctly as:

Assumption 6: We are working in the semi-honest adversary model, also known as security in the presence of passive adversaries. That is, the nodes in the network may use any means to try to obtain information about the secret inputs from the messages they receive but they follow the steps described in the NMC protocol.

First, we describe below three novel algorithms which constitute building blocks for NMC. Second, we describe two flavours of NMC, one in which most of the computations corresponding to the pre-processing phase are done by the SMPC computing nodes, and one in which they are done by the dealer nodes.

Building Blocks

In this section we present three algorithms. The first one, ZeroMessageShareDistribution, is based on a novel idea that allows distributing the initial shares from a secret sharing mechanism without sending any message. The second, AddSecretsWithoutSendingTheirShares, makes use of this idea to allow computing nodes to add numbers without requiring the dealer nodes to send their shares. The third, GenerateBlindingFactors, makes use of AddSecretsWithoutSendingTheirShares in order for N nodes to come up with M _a numbers A once again without initially distributing any shares.

The general principle of algorithm ZeroMessageShareDistribution can be applied to any secret sharing mechanism that makes use of the generation of random numbers. We present this algorithm for GMW SMPC and then we show in Phase 1 of algorithm AddSecretsWithoutSendingTheirShares how it is instantiated for BGW SMPC.

1) Description of Algorithm: ZeroMessageShareDistribution for GMW SMPC

Inputs: N input nodes, whereby node n has a secret x _n , n E {0,1, ... , N — 1}

Output: Each node ends up with a share of each other node's secret

Purpose: The shares are distributed without any message exchange

In GMW SMPC, each dealer n contributing with a secret bit x _n generates N-l random bits ^Y setting Then, dealer n sends random number x _{n q} to Node q, for q #= i.

That is, each node n is sending N-l messages. That is a total number of N(N-l) messages.

Instead of sending all these messages, the dealers can use random number generators in sync as follows. Let G _{n q} be a collection of random number generators, for n, q G {0, ... , N — 1} with n #= q, such that G _{n q} is a generator that nodes n and q run in sync, and which generates random bits.

That is, nodes n and q can independently obtain the same sequence of random numbers from &n,q-

We write g <- G _{n q} to denote when a node runs the number generator G _{n q} to produce a random bit g. Each node n proceeds as follows in order to generate N shares x _{n 0} , x _{n l} , ... , x _n ,N-i from their secret bit x _n :

Step 1 - Generate (/V — 1) random shares. Node n uses G _{n q} for each q E {0, ... , N — 1}, with q #= n to generate a random share (i.e. a random bit) x _{n q} <- G _{n q} for their secret bit x _n .

Step 2- Generate their own share. Node n now has N-l shares for their secret bit x _n . With one more evaluation the total set of shares will be complete. Node n choses x _{n n} = x _n ® (®q*n ^x n,/) ^as their own share to their secret bit.

In step 1 above, node n uses G _{n q} to generate the random share x _{n q} from their secret bit x _n that needs to be sent to node q, with n #= q. However, both nodes n and q have an instance of the same random number generator G _{n q} running in sync. Therefore, node q can independently obtain x _{n q} <- G _{n q} , without any need for communication. Following this principle, every node n is able to generate their own share x _{n n} from the 2-step process described above, and their share x _{n q} from the secret bit x _q from every other input node q using x _{q n} <- G _{q n} without ever having to receive or send a single message. This constitutes the novel procedure that allows the input nodes to distribute the shares from their secret bits without exchanging any message.

This ends the description of the algorithm ZeroMessageShareDistribution.

BGW SMPC makes use of Shamir's Secret Sharing (SSS) mechanism in order for the nodes to generate shares from their secret input values to the SMPC computation. The main idea in SSS is for a node n to hide their secret x _n E Z/pZ inside a polynomial: with random coefficients a _{l n} , a _{2 n} , a _{N-l n} such that the polynomial evaluated at x=0 is equal to the secret: p _n (0) = x _n . Given that N points are enough to uniquely determine a polynomial of degree N-l, the n-th dealer generates N polynomial evaluations p _n (l), p _n (2), ... , p _n (N) at a set of predetermined abscissae x = 1,2, . . . , N and sends a different evaluation to each one of the computing nodes. At the end of this process, each computing node J, J E {0, ..., N — 1} ends up with a share p _n (j + 1) evaluated at its assigned abscissa x = j + 1 from a polynomial p _n (x),n E {0, ..., N — 1} that hides a secret x _n at Pn(^) ^x n-

Algorithm ZeroMessageShareDistribution can be used with any secret sharing mechanism that makes use of the generation of random numbers. Such is the case of Shamir's Secret Sharing mechanism in BGW SMPC, which works with random polynomial coefficients. We now show how this algorithm can be instantiated in the BGW SMPC case in order to allow the input nodes to send their shares from their secret inputs without any message exchange. This constitutes Phase 1 of algorithm AddSecretsWithoutSendingTheirShares. This algorithm shows how N nodes can add N secrets without disclosing them.

2) Description of Algorithm: AddSecretsWithoutSendingTheirShares

Inputs: N input nodes, whereby node n has a secret x _n , n E {0,1, ... , N — 1}

Output: One or several output nodes reconstruct the sum 2n=o ^x n mod p

Purpose: N nodes can jointly add N secrets and reveal the result of the sum to the output nodes whilst keeping their secrets private.

The algorithm comprises the 3 standard SMPC phases, whereby Phase 1 is an instantiation of algorithm ZeroMessageShareDistribution for Shamir's Secret Sharing mechanism. Phases 2 and 3 are the same as in the standard BGW SMPC.

Phase 1 - Share Distribution

We describe the instantiation of algorithm ZeroMessageShareDistribution for Shamir's Secret Sharing mechanism.

Let G _{n q} be a collection of random number generators, for n, q E {0, ... , N — 1} with n #= q, such that G _{n q} is a generator that nodes n and q run in sync, and which generates random numbers in Z/pZ.

That is, nodes n and q can independently obtain the same sequence of random numbers from G _{n q} . A simple implementation of G _{n q} is a cryptographic hash function that takes its output as an input to produce the next number provided that both nodes n and q start with the same initial input value. However, any pseudo-random number generator that outputs random numbers in Z/pZ will work.

We write g «- G _{n q} to denote when a node runs the number generator G _{n q} . Each node n proceeds as follows in order to generate N evaluations from their polynomial p _n (%):

Step 1 - Generate (N — 1) random shares p _n (q + 1), n #= q. Node n uses G _{n q} for each q E {0, ... , N — 1}, with q #= n to generate a random evaluation of its polynomial p _n (q + 1) <- G _{n q} . This evaluation constitutes a share from secret x _n .

Step 2- Generate its own share p _n (n + 1). Node n now has N-l evaluations (shares) of a polynomial of degree N-l. With one more evaluation the polynomial will be fully characterised. Node n choses p _n (0) = x _n as the N-th evaluation. The polynomial p _n (x) is now fully characterised but p _n (0) cannot be a valid share because it is equal to the secret x _n . In order to obtain the missing share p _n (n + 1) node n performs polynomial interpolation (e.g. using Lagrange) and obtains the coefficients a _{l n} , ■■■> ^a N-i,n °f i ^ts polynomial p _n (x) = x _n + a _{l n} x + a _{2 n} x ² + — F aN-i,n ^xN ~ ¹ mod p. With these coefficients and x _n , node n computes p _n (n + 1) through direct evaluation, which is their share to their own polynomial.

In step 1 above, node n uses G _{n q} to generate the random evaluation of their polynomial p _n (q + 1) that needs to be sent to node q, with n #= q. However, both nodes n and q have an instance of the same random number generator G _{n q} running in sync. Therefore, node q can independently obtain p _n (q + 1) <- G _{n q} , without any need for communication. Following this principle, every node n is able to generate their own share p _n (n + 1) from the 2-step process described above, and their share p _q (n + 1) from the polynomial p _q (x) from every other computing node q using p _q (n + 1) <- G _{q n} without ever having to receive or send a single message. This constitutes the novel procedure that allows the computing nodes to distribute the shares from their secret without exchanging any message so that they can jointly compute their sum using BGW SMPC.

Phase 2 - Computation

This part of the algorithm follows the standard BGW SM PC. Every node n now has a share p _q (n + 1) from a polynomial p _q (x) of degree N-l such that p _q (0) = x _q is the secret from node q E {0,1, ... , N — 1}, q n. We define the polynomial:

This is a polynomial of degree N-l such that p(0) = 2n=o ^x n mod p. This is the sum of all the secrets and it constitutes the output of this algorithm. Following the standard BWG SMPC, by adding all their shares p(n + 1) = ^q=o Pq( ⁿ + 1) mod p, node n can compute their share p(n + 1) of p(x) evaluated at n+1.

Phase 3 - Result Reconstruction

Continuing with the standard BGW SMPC, each node sends their share p(n + 1) of p(x) to one or several output nodes. When an output node has received all the shares, it performs polynomial interpolation and reconstructs the independent coefficient a ₀ (i.e. the one that corresponds to x°) which is equal to the sum of the secrets: a ₀ = En=o ^x n-

This ends the description of the algorithm AddSecretsWithoutSendingTheirShares.

3) Description of Algorithm: GenerateBlindingFactors

Inputs: M _a -1 input nodes.

Output: M _a output nodes, whereby the m-th result node, m E {0,1, — 1} reconstructs the blinding factor A _m , such that

Purpose: M _a -1 nodes jointly generate M _a blinding factors A _o , A _x , such that their sum equals one without sharing these factors amongst themselves. This algorithm allows the input nodes to reveal the m-th blinding factor A _m to each node m from a total of M _a dealer nodes.

Step 1: Each input node m, m E {0,1, ... , M _a — 2} generates a random number A _m . That is, each one generates a number in the series A _o , ... , A _MQ-2 (all lambdas in the sum except for the last one

Step 2: Each input node m, m E {0,1, ... , M _a — 2} runs algorithm

AddSecretsWithoutSendingTheirShares using as their secret input:

At the end of Phase 1 in algorithm AddSecretsWithoutSendingTheirShares, each input node m, m G {0,1, ... , M _a — 2} ends up having a polynomial share + 1), ..., p _Ma-2 (m + 1) from each random number

AoMi, ... ,A _Ma-2 , respectively

At the end of Phase 2 in algorithm AddSecretsWithoutSendingTheirShares, each input node m, m E {0,1, ... , M _a — 2} ends up having a polynomial share p^(m + 1) from a polynomial p^-(x) that is equal to the sum of ... , A _{M 2} when evaluated

Each input node m calculates (mod p):

PM„-IO + 1) = 1 - P _t O + 1) with its local share p^(m + 1) of p^-(x). Since Shamir Secret Sharing is linear, PM _a -i_(m + 1) turns out to be a share of a polynomial PM _U -I ( ^X ) hiding the value (1 — mod p when evaluated at x=0. That is, we define A _{M x} as follows (mod p):

This ensures that (mod p):

To summarise, each input node m, m E {0,1, ... , M _a — 2} has now a polynomial share p ₀ (m + lX piCm H- 1), ...,p _M( _ ₁ (m + 1) from M _a polynomials p ₀ 00, Pi 00, -< PM _a -iW hiding secrets A _o , A such that Eq. 3 holds.

At the end of Phase 3 from algorithm AddSecretsWithoutSendingTheirShares, each input node m, m E {0,1, — 2} then sends each polynomial share p _k (m + 1) of A _fc to the k - th output node, with k E {0,1, — 1}, so that output node k can reconstruct A _fc .

This ends the description of the algorithm GenerateBlindingFactors.

NMC SMPC - Formal Definition

Recall from Eq. 1 the general form of a function in the arithmetic setting We have D dealer nodes contributing secrets from the set {s ₀ , s _1; ... , Ss-jJ to the computation of a generic arithmetic function given by Eq. 1. This computation is carried out by N computing nodes, and the corresponding result is revealed to R result nodes. We present two flavours of the novel NMC SMPC to solve this problem:

1) Network NMC: in this flavour the bulk of the computational load in the pre-computing phase is carried out by the N computing nodes.

2) Edge NMC: in this flavour the bulk of this load is carried out by the D dealer nodes.

Instead of directly applying a linear secret sharing (LSS) schema to the secret inputs, the idea underpinning both NMC flavours is to mask the secret inputs using blinding factors and then to use LSS (such as Shamir) to store some of these factors in the network of computing. More specifically:

1) In the Network NMC the masked value v from input secret s is given by v = s • p\ where Shamir shares from p and A are generated and stored by the network of computing nodes

2) In the Edge NMC the masked value v from input secret s is given by v = s • X • p ^A where Shamir shares from A are generated and stored by the network of computing nodes, and X and p are generated by the dealer nodes

We now define the four phases of the Network NMC SMPC to evaluate this function.

Description of algorithm Network NMC

Inputs: D dealer nodes, whereby the n-th node holds a subset S _n of the total set of secrets The dealer nodes wish to compute an arithmetic function f = over their secrets given by Eq. 1

Output: R result nodes reconstruct the function result ^m °d p comprising A additions, whereby the a-th addition comprises M _a multiplications. This function is computed by N computing nodes that are not able to see any of the input secrets.

Purpose: N computing nodes can jointly evaluate any arithmetic function whilst keeping the dealers' secrets private and without any message exchange during the computation phase. Algorithm Network NMC comprises four phases: Pre-processing, Share Distribution, Computation and Result Reconstruction.

Phase 0 - Pre-processing

This phase deals with the computation of a base blinding factor p _α and M _a exponent blinding factors , _a Q for each addition a, a E

The following steps are executed in parallel for each addition a, a E {0,1, ... , A — 1}:

Step 1 (computation of the base blinding factor):

Each computing node n, n E {0,1, ... , N — 1} generates a random number X _{n a} .

Step 2 (computation of the base blinding factor):

Each computing node n runs algorithm AddSecretsWithoutSendingTheirShares, using X _{n a} as their secret input value in order to jointly calculate At the end of Phase 2 in this algorithm, each node n has a share p _a (n + 1) of a polynomial p _a (x) of degree N-l such that (mod p):

We denote this by p„ ^x = p _a (0), the inverse of the baseline blinding factor. In the Result Reconstruction phase of algorithm AddSecretsWithoutSendingTheirShares, each computing node sends their share of each p„ ^x to each dealer node d, d E {0,1, ... , D — 1}. Each dealer node is then able to reconstruct (mod p):

Eq. 2

Step 3 (computation of the exponent blinding factors):

In parallel to the two steps presented above, the N computing nodes organise themselves in X subsets 1 computing nodes, respectively. For each addition the computing nodes from the a-th subset S _a work in collaboration to compute M _a random values (blinding factors) such that (mod p). They achieve this by running GenerateBlindingFactors with S _a as the subset of input nodes. That is, as a result from the parallel execution of A instances of algorithm GenerateBlindingFactors, each dealer node d, d E {0,1, ... , D — 1} can reconstruct A _{a m} , if they participate with secret Sj _am in the computation of the product corresponding to the a-th addition in Eq. 1, such that for every a E fulfils:

Note of the A subsets S ₀ , S ₁ , ... ,5^-^ of computing nodes: These subsets can be chosen according to any arbitrary method. Assumption 2 guarantees that such subsets exist. In another embodiment, the a-th subset S _a of M _a — 1 computing nodes is expanded to any arbitrary number N _a , M _a — 1 < N _a < N of computing nodes by adding N — (M _a — 1) nodes, whereby the m-th added node generates A _{a m} = 0 in Step 1 of algorithm GenerateBlindingFactors, for all a E {0,1, ...,A — 1}, so that Eq. 3 is not altered.

Note on performance: The computation of p _a ^-1 and of A _{a m} for each addition a, a E {0,1, ...,A — 1} requires the execution of Phase 3 from algorithm AddSecretsWithoutSendingTheirShares. This phase comprises the transmission of messages to every dealer node. By aggregating all the messages to a dealer node in one, each computing node needs to send only one message per dealer node. This is a total number of N • D messages in the network, where D is the number of dealer nodes.

At the end of the NMC pre-processing phase, each dealer node d, d E {0,1, ... , D — 1} ends up with the blinding factors p _a ^-1 (and hence p _a ) and A _{a m} , a E {0,1, ... , A — 1}, m E for every secret s _iam they contribute with to the overall SMPC computation.

This phase is completely independent of the secrets s ₀ , s _1; ... , s _s-17 which are the inputs to the evaluation of the arithmetic function. Therefore, it can be executed before (e.g. months) the actual evaluation of the arithmetic function running NMC SMPC and it can be processed in batch.

Phase 1 - Share Distribution

Step 1: Each dealer node masks their secret (mod p): if they contribute with secret s _iam to the computation of the multiplication comprising the a-th addition term in Eq. 1. Recall that in s _iam , i _{a m} acts as an index to the corresponding secret in the set s ₀ , s _1; ... , Recall also from Assumptions 3 that each dealer node only contributes with at most one secret to the a-th addition term in Eq. 1.

Step 2: Each dealer node d E {0,1, ..., D — 1} sends one broadcast message to the N computing nodes containing one value v _{a m} for each addition term a to which they contribute a secret. Each value v _{a m} represents a NMC share their secret s _iam .

Note on security. Notice that the N computing nodes do not know the value of the base blinding factor p _a or of the exponent blinding factors A _{a m} because all they have is a polynomial share of these values. Therefore, the factor p _a ^ ^am is effectively hiding the secret value s _iam and algorithm NMC inherits the security features from SSS, namely, it is secure against N-l (or less) colluding nodes in the passive adversary model. Specifically, an adversary would have to corrupt all N computing nodes in order to be able to reconstruct p _α and A _{a m} in order to recover s, ^L a,m from v _n a, _m frc .

Phase 2 -Computation

Step 1: Each computing node n, n E {0,1, ... , N — 1} calculates for each addition a, a E

{0,1, ...,A — 1} (mod py.

Step 2: Each computing node n, n G {0,1, ... , N — 1} calculates (mod p):

This phase does not require any communication between the computing nodes since each node n can locally compute r _{n a} for each a E {0,1, ... , A — 1}.

Phase 3 - Result Reconstruction Each computing node n, n E {0,1, ..., N — 1} sends their NMC share r _n of the result to the result nodes, which compute:

This ends the description of the algorithm Network NMC.

Fig. 2 shows the computing nodes 12 and the dealer nodes 10 from Fig. 1, carrying out the steps of Phase 0 - Pre-processing for the Network NMC implementation.

Referring additionally to Fig. 3, this is a flowchart which includes message flows between the nodes for the Network NMC implementation.

In step 20, each computing node n of the N computing nodes n E {0,1, ... , N — 1}, generates a random number X _{n a} . This is done in parallel for each addition a, a E {0,1, ... , A — 1} as described for Step 1 of Phase 0 above.

In step 22, the computing nodes each run the algorithm AddSecretsWithoutSendingTheirShares using X _{n a} as their secret input value as described in the first part of Step 2 of Phase 0 above. This results in each computing node having a share of each p^ ¹ which can be sent to the dealer nodes.

In step 24, the computing nodes run GenerateBlindingFactors in parallel in A instances to compute shares of λ _{a m} as described in the first part of Step 3 of Phase 0.

In step 26, the computing nodes send the shares calculated in steps 22 and 24 of Fig. 3 to the dealer nodes as described in the latter parts of Steps 2 and 3 of Phase 0.

In step 28, the dealer nodes reconstruct the blinding factors λ. _a ,m , Pa using Shamir Secret Sharing's polynomial interpolation (e.g. using Lagrange's method). As noted at the end of the description of Phase 0 above, the steps leading to the reconstruction of the blinding factors can be carried out a long time in advance of the share blinding and distribution steps of Phase 1.

It should also be noted that alternative ways of providing the blinding factors are envisaged. For example, in another embodiment, a trusted node carries out the computations from the pre-processing phase and sends for each addition to the dealer nodes.

In another embodiment, the N computing nodes carry out the computations from the preprocessing phase using another SMPC flavour different from the one described in algorithm AddSecretsWithoutSendingTheirShares and send messages to the dealer nodes that allow them to reconstruct p _a ^-1 and of _{a m} for each addition a, a E {0,1, ... , A — 1}.

In another embodiment, homomorphic encryption is used by one or several nodes, for instance using Full Homomorphic Encryption, or Somewhat Homomorphic Encryption as described in SPDZ (Damgard I., Pastro V., Smart N., Zakarias S. (2012) Multiparty Computation from Somewhat Homomorphic Encryption. In: Safavi-Naini R., Canetti R. (eds) Advances in Cryptology - CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg, https://doi.org/10.1007/978-3-642-32009-5_38), to carry out the computations from the pre-processing phase and sends p _a ^-1 and of _{a m} for each addition a, a E {0,1, ... , A — 1} to the dealer nodes.

In another embodiment, one or several nodes use secure enclaves or trusted execution environments to carry out the computations from the pre-processing phase and send p _a ^-1 and of _{a m} for each addition to the dealer nodes.

Returning to Fig. 3, in step 30, and as is described above in Phase 1, each dealer node 10 may compute for the secret contributed to the computation of the multiplication comprising the a-th addition term.

In step 32, the result of each such computation is broadcast by the dealer node creating the computation to the computing nodes.

In step 34, and as described above for Phase 2, each computing node calculates a share r _n of the result of the NMC computation, and does so without any communication between the computing nodes.

In step 36, each computing node sends its share r _n to the result nodes.

In step 38, the result nodes reconstruct the result of the function /as the sum of the result shares mod p, according to Eq. 6. It can be shown that this reconstruction, arrived at without any communication between the computing nodes, is indeed a valid result of a multi-party computation of a function in the arithmetic setting by the following proof. Starting from Eq. 4 and 5 we have (mod p): where the last step comes from the fact that A which follows from Eq. 3. By plugging this result into the right-hand side of Eq. 6 we get (mod p): which corresponds to f = /(s ₀ , s _1; ... , in Eq. 1. It will be recalled from Assumption 4 that every dealer contributes with at most 1 secret to the product corresponding to the a-th addition term in f. In another embodiment, we force every dealer node m to contribute with exactly one secret s to the product corresponding to the a-th addition term, for every addition term

We achieve this as follows: (1) if the dealer was already contributing with one secret to the a- th term, then we do nothing, (2) if the dealer was not contributing with a secret, then it forces its secret to be equal to one: s _iam = 1. This way, the product ^a 'th ^term ' ^s not altered but every dealer node contributes with exactly one secret to it. This allows replacing M _a = D for every addition term a, and making all random vectors A _{a m} be equal to a single random vector A _m , whereby Eq. 3 becomes and the same are used for each addition term. This allows a reduction in the amount of information sent by the computing nodes to the dealer nodes at the end of Phase 0. Instead of sending shares for they just send shares for

As discussed previously, as an alternative to the Network NMC algorithm the same outcome can be achieved, again without any communication between the computing nodes, using an algorithm referred to as Edge NMC.

We now define the four phases of the Edge NMC SMPC for the joint evaluation of the arithmetic function in Eq. 1 without revealing any input secret value. In Edge NMC SMPC we push most of the complexity in the pre-processing phase to the dealer nodes. This involves changing (relative to the Network NMC algorithm) Steps 1 and 2 in Phase 0, the whole Phase 1 and Step 1 in Phase 2 as follows:

Description of algorithm Edge NMC

Inputs: As in Network NMC

Output: As in Network NMC

Purpose: As in Network NMC Phase 0: Pre-processing

New Step 1 (replacing the old one):

All D dealer nodes run a random number generator in sync. That is, by running it, they independently obtain the same N • A random numbers X _{n a} without any message exchange,

New Step 2 (replacing the old one):

Every dealer node d G {0,1, ... , D — 1} locally computes:

Step 3 remains the same.

The N computing nodes compute the shares of the exponent blinding factors by running GenerateBlindingFactors as described for the Network NMC Algorithm, then reveal the shares of { to the different dealers allowing them to reconstruct the blinding factor that hides their secret s, ^c a,m

Phase 1: Share Distribution (replacing the old one):

Step 1: Each dealer node computes (mod p): for f they contribute with secret s _iam to the computation of the multiplication comprising the a-th addition term in Eq. 1. Notice that there are the N shares correspond to every secret s _iam .

Step 2: Each dealer node d E {0,1, ... , D — 1} sends each one of the N shares that correspond to every secret s _{ia m} owned by node d to a different computing node.

Phase 2: Computation

Step 1 (replacing the old one):

Each computing node n, n E {0,1, ... , N — 1} calculates for each addition a, a E {0,1, ...,A — 1} (mod p)-. Eq. 4, alternative version

Step 2: As in Network NMC.

Phase 3 - Result Reconstruction

As in Network NMC.

This ends the description of the algorithm Edge NMC.

Fig. 4 shows the computing nodes 12 and the dealer nodes 10 from Fig. 1, carrying out the steps of Phase 0 - Pre-processing for the Edge NMC implementation.

Referring additionally to Fig. 5, this is a flowchart which includes message flows between the nodes for the Edge NMC implementation.

In step 40, the computing nodes run GenerateBlindingFactors in parallel in A instances to compute shares of A _{a m} as described in the first part of Step 3 of Phase 0 of the Edge NMC algorithm above.

In step 42 (which may be carried out before, after or in parallel with step 20), each dealer node runs a random generator in sync to generate the same set of random numbers X _{n a} without any message exchange, as described in Step 1 of Phase 0.

In step 44, each dealer node locally computes p _a (or p ^-1 _a ) as set out in Step 2 of Phase 0.

In step 46, the computing nodes send the shares of X _a , _m calculated in step 40 to the dealer nodes.

In step 48, the dealer nodes reconstruct X _a , _m from the revealed shares. The skilled person will appreciate that the same options exist for providing the blinding factors to the dealer nodes as in the Network NMC algorithm.

In step 50, as described above in Phase 1, each dealer node 10 computes the N shares that correspond to every secret as described for Step 1 of Phase 1. In step 52, these shares are sent to the respective computing nodes as described for Step 2 of

Phase 1.

In step 54, the computing nodes calculated the modified version of the result shares r _n according to Phase 2.

In step 56, the result shares are sent to the result nodes, and in step 58, the result nodes reconstruct the result of the function /.

The proof for the Edge NMC flavour is almost the same as that for Eq. 6 in the Network NMC flavour, the only difference being that instead of X _{n a} ■ ^v a,m i ⁿ Edge NMC we have Both are equal since by definition

Sometimes, dealer nodes just want to use the network of computing nodes to store and reconstruct an input secret value. We now discuss this process in both NMC protocols.

In Phase 1 of the Network NMC protocol, a dealer node masks a secret using v _{a m} = s _iam ■ p _a ^a,m and broadcasts it to the network of computing nodes, whereby each computing node has a share from p _α and A _{a m} . When the dealer node wants to reconstruct its secret it requests the network of computing nodes to send their share from p _α and X _{a m} as well as v _{a m} . Using Shamir Secret Sharing, the dealer node reconstructs p _α and X _{a m} and computes its secret input value as follows (mod p):

In Phase 1 of the Edge NMC protocol, a dealer node masks a secret using ^v n,a,m = ^s t _am ' P _a ^am ' %n,a and broadcasts it to the network of computing nodes, whereby each computing node has a share from A _{a m} . Notice that this does not allow for the reconstruction of the secret input We now describe a modification of Phase 1 so that this reconstruction is possible. In the modified version of Phase 1, the dealer uses a linear secret sharing scheme such as Shamir's in order to compute and distribute among the computing nodes the shares from X _{n a} and p _a . When the dealer node wants to reconstruct its secret, it requests the network of computing nodes to send their share from p _a , X _{n a} and X _{a m} as well as v _{n a m} . Using Shamir Secret Sharing, the dealer node reconstructs p _a , X _{n a} and A _{a m} and computes its secret input value as follows (mod p): s _iam = v _{n a m} ■ p _a ^a,m ■ X^.

T1