Messageless Secure Multi-Party Computations with Passive and Active Adversaries

Abstract

Disclosed are methods and systems for calculating an arithmetic function expressed as addition of groups of multiplications of a set of private input secrets held by dealer nodes. Random exponent blinding factors are generated, and each computing node receives polynomial shares from each exponent blinding factor and a polynomial share and a public generator from the multiplicative group of integers modulo a prime number. The indexing integers are partitioned among the computing nodes, and each computing node computes a set of shares from the polynomial shares then sent to the dealer nodes which reconstruct the corresponding dealer blinding factor, and use it to create and send a particle to the computing nodes. The computing nodes then calculate from the received particles a result share of a polynomial which, when combined by a result node, allow the evaluation of complete polynomial which includes the result of the arithmetic function.

Claims

1. A computer-implemented method, carried out between a plurality of D dealer nodes and N computing nodes, for use in calculating the result of an arithmetic function which can be expressed as the addition of A groups of multiplications of a set S of private input secrets {s.sub.0, s.sub.1, . . . , s.sub.S-1} such that: $f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=m_0+m_1+.Math.+m_{A-1}=\underset{a=0}{\overset{A-1}{.Math.}}{m}_a$ where each group of multiplications m.sub.a, a{0, 1, . . . , A1} is the product of M.sub.a secrets of said set S of private input secrets: $m_a=s_{i_{a,0}}.Math.s_{i_{a,1}}.Math..Math..Math.s_{i_{a,M_a-1}}=\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$ and the subindices i.sub.a,m for {0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} 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 s.sub.i.sub.a,m is known to one of said dealer nodes, wherein the method comprises: (a) providing each computing node n, n{0, 1, . . . , N1}, with a respective set of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n, for every addition a{0, . . . , A1} where L is a number chosen such that L>M.sub.a, a{0, 1, . . . , A1} and L>D, and such that: (i) the set of all the l-th shares [.sub.a,l].sub.n, l{0, . . . L1}, from the N computing nodes together represent shares of a degree-T polynomial that hide a respective secret exponent blinding factor .sub.a,l at a certain abscissa such as x=0, with NT+1; and (ii) the set of exponent blinding factors .sub.a,0, .sub.a,1, . . . , .sub.a,L1 for a given addition a are all elements of the multiplicative group (Z/pZ).sup.x of integers modulo a prime number p; (b) providing each computing node n, n{0, 1, . . . , N1}, with a respective set of shares [.sup..sup.a].sub.n, where: (i) is a public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p; (ii) .sub.a is a secret exponent which satisfies ${}_a=\underset{l=0}{\overset{L-1}{.Math.}}{}_{a,l}$ (iii) the set of all the shares [.sup..sup.a] from the N computing nodes together represent shares of a degree-T polynomial that hide the secret value .sup. at a certain abscissa such as x=0; (c) for each addition a comprising M.sub.a multiplications, providing each of the computing nodes with the same partition sets P.sub.a,0, P.sub.a,1, P.sub.a,M.sub.a.sub.1 of the indexing set {0, 1, . . . , L1} such that all partition sets are disjoint and non-empty; (d) each computing node computing, for each addition a, a set of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,M.sub.a.sub.1].sub.n according to: ${\left[{}_{a,m}\right]}_n=\underset{l{P}_{a,m}}{.Math.}{\left[{}_{a,l}\right]}_n$ for m{0, . . . , M.sub.a1}, wherein for a given addition a and multiplication m the set of the shares [.sub.a,m].sub.n for n{0, 1, . . . , N1} together represent shares of a degree-T polynomial that hide the secret dealer blinding factor .sub.a,m at a certain abscissa such as x=0; (e) each computing node n sending the respective share [.sub.a,m].sub.n for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1}, to the respective dealer node contributing the secret s.sub.i.sub.a,m to the computation; (f) each dealer node reconstructing, for each secret s.sub.i.sub.a,m which it contributes to the computation, the corresponding dealer blinding factor .sub.a,m; (g) each dealer node sending, for each secret s.sub.i.sub.a,m which it contributes to the computation, a particle v.sub.a,m to each of the computing nodes wherein:
v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m (h) each computing node calculating, for each addition a{0, 1, . . . , A1}, a share [r.sub.a].sub.n from a degree-T polynomial r.sub.a(x) where: ${\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$ (i) each computing node calculating a result share [r].sub.n from a degree-T polynomial r(x) where: ${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n$ (j) each computing node sending to one or more result node(s) their result share [r].sub.n whereby the result node(s) may reconstruct the evaluation r(0) of polynomial r(x) from the received result shares [r].sub.n, said evaluation r(0) being equal to the result of said arithmetic function .

2. A computer-implemented method according to claim 1, wherein N=T+1.

3. A computer-implemented method according to claim 1, wherein NT+1.

4. A computer-implemented method according to claim 3, wherein the reconstruction of at least one of said polynomials employs error correction codes.

5. A computer-implemented method according to claim 3 wherein N3T+1.

6. A computer-implemented method according to claim 1, wherein step (c) of providing each of the computing nodes with the same partition sets comprises each computing nodes calculating the partition sets according to a shared set of rules.

7. A computer-implemented method according to claim 1, wherein step (a) of providing each computing node n, n{0, 1, . . . , N1}, with a respective set of shares [.sub.a,0].sub.n, [.sub.a,1], . . . , [.sub.a,L1] comprises the calculation, by a trusted node, of said sets of shares.

8. A computer-implemented method according to claim 7, wherein the calculation of said sets of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n comprises the following steps by the trusted node: (i) computing, for each addition a{0, . . . , A1}, L random exponent blinding factors .sub.a,0, .sub.a,1, . . . , .sub.a,L1 (Z/pZ).sup.x; (ii) computing, for each of said exponent blinding factors .sub.a,l where l{0, . . . L1}, N shares [.sub.m].sub.0, [.sub.m].sub.1, . . . , [.sub.m].sub.N-1 of a degree-T polynomial that hides the value .sub.a,l at a certain abscissa such as x=0.

9. A computer-implemented method according to claim 1, wherein step (b) of providing each computing node n, n{0, 1, . . . , N1}, with a respective set of shares [.sup..sup.a].sub.n comprises the calculation, by a trusted node, of said sets of shares.

10. A computer-implemented method according to claim 9, wherein the calculation of said sets of shares [.sup..sup.a].sub.n comprises the following steps by the trusted node: (iii) computing, for each addition a{0, . . . , A1}, the value .sup..sup.a, where ${}_a=\underset{l=0}{\overset{L-1}{.Math.}}{}_{a,l}$ (iv) computing, for each value .sup..sup.a, N shares [.sup..sup.a], n{0, 1, . . . , N1}, of a degree-T polynomial that hides the value .sup..sup.a at a certain abscissa such as x=0.

11. A computer-implemented method according to claim 7, wherein the calculations of sets of shares by a trusted node are all carried out by the same trusted node.

12. A computer-implemented method according to claim 1, further comprising the evaluation, by said one or more result node(s), of the value r(0) of polynomial r(x).

13. A non-transitory computer-program product comprising instructions which, when executed by a processor, cause the processor to operate as a computing node in a computer-implemented method, carried out between a plurality of D dealer nodes and N computing nodes, for use in calculating the result of an arithmetic function which can be expressed as the addition of A groups of multiplications of a set S of private input secrets {s.sub.0, s.sub.1, . . . , s.sub.S-1} such that: $f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=m_0+m_1+.Math.+m_{A-1}=\underset{a=0}{\overset{A-1}{.Math.}}{m}_a$ where each group of multiplications m.sub.a, a{0, 1, . . . , A1} is the product of M.sub.a secrets of said set S of private input secrets: $m_a=s_{i_{a,0}}.Math.s_{i_{a,1}}.Math..Math..Math.s_{i_{a,M_a-1}}=\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$ and the subindices i.sub.a,m for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} 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 s.sub.i.sub.a,m is known to one of said dealer nodes, wherein the instructions cause the processor to operate as the n-th computing node, n{0, 1, . . . , N1} by: (a) receiving a respective set of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n, for every addition a{0, . . . , A1} where L is a number chosen such that L>M.sub.a, a{0, 1, . . . , A1} and L>D, and such that: (i) the set of all the l-th shares [.sub.a,l].sub.n, l{0, . . . L1}, from the N computing nodes together represent shares of a degree-T polynomial that hide a respective secret exponent blinding factor .sub.a,l at a certain abscissa such as x=0, with NT+1; and (ii) the set of exponent blinding factors .sub.a,0, .sub.a,1, . . . , .sub.a,L1 for a given addition a are all elements of the multiplicative group (Z/pZ).sup.x of integers modulo a prime number p; (b) receiving a respective set of shares [.sup..sup.a].sub.n, where: (i) p is a public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p; (ii) .sub.a is a secret exponent which satisfies ${}_a=\underset{l=0}{\overset{L-1}{.Math.}}{}_{a,l}$ (iii) the set of all the shares [.sup..sup.a] from the N computing nodes together represent shares of a degree-T polynomial that hide the secret value .sup. at a certain abscissa such as x=0; (c) for each addition a comprising M.sub.a multiplications, receiving the same partition sets P.sub.a,0, P.sub.a,1, . . . , P.sub.a,M.sub.a.sub.1 of the indexing set {0, 1, . . . , L1} such that all partition sets are disjoint and non-empty; (d) computing, for each addition a, a set of shares [.sub.a,0].sub.n, [.sub.a,1], . . . , [.sub.a,M.sub.a.sub.1].sub.n according to: ${\left[{}_{a,m}\right]}_n=\underset{l{P}_{a,m}}{.Math.}{\left[{}_{a,l}\right]}_n$ for m{0, . . . , M.sub.a1}, wherein for a given addition a and multiplication m the set of the shares [.sub.a,m].sub.n, for n{0, 1, . . . , N1} together represent shares of a degree-T polynomial that hide the secret dealer blinding factor .sub.a,m at a certain abscissa such as x=0; (e) sending the respective share [.sub.a,m].sub.n for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1}, to the respective dealer node contributing the secret s.sub.i.sub.a,m to the computation; (f) receiving, from each dealer node contributing a secret s.sub.i.sub.a,m to the computation, a particle v.sub.a,m wherein:
v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m (g) calculating, for each addition a{0, 1, . . . , A1}, a share [r.sub.a].sub.n from a degree-T polynomial r.sub.a(x) where: ${\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$ (h) calculating a result share [r].sub.n from a degree-T polynomial r(x) where: ${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n$ (i) sending to one or more result node(s) their result share [r].sub.n whereby the result node(s) may reconstruct the evaluation r(0) of polynomial r(x) from the received result shares [r].sub.n, said evaluation r(0) being equal to the result of said arithmetic function .

14. A computing system comprising a processor programmed to operate as a computing node in a computer-implemented method, carried out between a plurality of D dealer nodes and N computing nodes, for use in calculating the result of an arithmetic function which can be expressed as the addition of A groups of multiplications of a set S of private input secrets {s.sub.0, s.sub.1, . . . , s.sub.S-1} such that: $f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=m_0+m_1+.Math.+m_{A-1}=\underset{a=0}{\overset{A-1}{.Math.}}{m}_a$ where each group of multiplications m.sub.a, a{0, 1, . . . , A1} is the product of M.sub.a secrets of said set S of private input secrets: $m_a=s_{i_{a,0}}.Math.s_{i_{a,1}}.Math..Math..Math.s_{i_{a,M_a-1}}=\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$ and the subindices i.sub.a,m for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} 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 s.sub.i.sub.a,m is known to one of said dealer nodes, wherein the processor is programmed with instructions causing the computing system to operate as the n-th computing node, n{0, 1, . . . , N1} by: (a) receiving a respective set of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n, for every addition a{0, . . . , A1} where L is a number chosen such that L>M.sub.a, a{0, 1, . . . , A1} and L>D, and such that: (i) the set of all the l-th shares [.sub.a,l].sub.n, l{0, . . . L1}, from the N computing nodes together represent shares of a degree-T polynomial that hide a respective secret exponent blinding factor .sub.a,l at a certain abscissa such as x=0, with NT+1; and (ii) the set of exponent blinding factors .sub.a,0, .sub.a,1, . . . , .sub.a,L1 for a given addition a are all elements of the multiplicative group (Z/pZ).sup.x of integers modulo a prime number p; (b) receiving a respective set of shares [.sup..sup.a].sub.n, where: (i) p is a public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p; (ii) .sub.a is a secret exponent which satisfies ${}_a=\underset{l=0}{\overset{L-1}{.Math.}}{}_{a,l}$ (iii) the set of all the shares [.sup..sup.a].sub.n from the N computing nodes together represent shares of a degree-T polynomial that hide the secret value .sup. at a certain abscissa such as x=0; (c) for each addition a comprising M.sub.a multiplications, receiving the same partition sets P.sub.a,0, P.sub.a,1, . . . , P.sub.a,M.sub.a.sub.1 of the indexing set {0, 1, . . . , L1} such that all partition sets are disjoint and non-empty; (d) computing, for each addition a, a set of shares [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,M.sub.a.sub.1].sub.n according to: ${\left[{}_{a,m}\right]}_n=\underset{l{P}_{a,m}}{.Math.}{\left[{}_{a,l}\right]}_n$ for m{0, . . . , M.sub.a1}, wherein for a given addition a and multiplication m the set of the shares [A.sub.a,m].sub.n for n{0, 1, . . . , N1} together represent shares of a degree-T polynomial that hide the secret dealer blinding factor .sub.a,m at a certain abscissa such as x=0; (e) sending the respective share [.sub.a,m] for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1}, to the respective dealer node contributing the secret s.sub.i.sub.a,m to the computation; (f) receiving, from each dealer node contributing a secret s.sub.i.sub.a,m to the computation, a particle v.sub.a,m wherein:
v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m (g) calculating, for each addition a{0, 1, . . . , A1}, a share [r.sub.a].sub.n from a degree-T polynomial r.sub.a(x) where: ${\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$ (h) calculating a result share [r].sub.n from a degree-T polynomial r(x) where: ${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n$ (i) sending to one or more result node(s) their result share [r].sub.n whereby the result node(s) may reconstruct the evaluation r(0) of polynomial r(x) from the received result shares [r].sub.n, said evaluation r(0) being equal to the result of said arithmetic function .

15. A computer-implemented method, carried out between a dealer node and N computing nodes, for use in calculating the result of an arithmetic function which can be expressed as the addition of A groups of multiplications of a set S of private input secrets {s.sub.0, s.sub.1, . . . , s.sub.S-1} such that: $f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=m_0+m_1+.Math.+m_{A-1}=\underset{a=0}{\overset{A-1}{.Math.}}{m}_a$ where each group of multiplications m.sub.a, a{0, 1, . . . , A1} is the product of M.sub.a secrets of said set S of private input secrets: $m_a=s_{i_{a,0}}.Math.s_{i_{a,1}}.Math..Math..Math.s_{i_{a,M_a-1}}=\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$ and the subindices i.sub.a,m for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} identify private input secrets from the set of S secrets, and where the S secrets are selected from integers, real numbers or complex numbers, wherein the method comprises: (a) the dealer node computing, for each addition a{0, 1, . . . , A1} and each multiplication m{0, 1, . . . , M.sub.a1}, a random dealer blinding factor A.sub.a,m; (b) the dealer node computing, for each addition a{0, . . . , A1}: ${}_a=\underset{m=0}{\overset{M_a-1}{.Math.}}{}_{a,m}$ (c) the dealer node computing, for each addition a{0, . . . , A1}, N shares [.sup..sup.a].sub.0, [.sup..sup.a.sub.]1, . . . , [.sup..sup.a].sub.N-1 of a degree-T polynomial that hides the value .sup..sup.a at a certain abscissa such as x=0; (d) the dealer node computing, for each addition a{0, 1, . . . , A1} and each multiplication m{0, 1, . . . , M.sub.a1}, a respective particle v.sub.a,m where:
v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m (e) the dealer node communicating, to each computing node n, n{0, 1, . . . , N1}: iii. {v.sub.a,m}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1}, iv. {[.sup..sup.a].sub.n}.sub.a{0, . . . ,A1}; (f) each computing node calculating, for each addition a{0, 1, . . . , A1}, a share [r.sub.a].sub.n from a degree-T polynomial r.sub.a(x) where: ${\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$ (g) each computing node calculating a result share [r].sub.n from a degree-T polynomial r(x) where: ${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n$ (h) each computing node sending to one or more result node(s) their result share [r].sub.n whereby the result node(s) may reconstruct the evaluation r(0) of polynomial r(x) from the received result shares [r].sub.n, said evaluation r(0) being equal to the result of said arithmetic function .

16. A computer-implemented method according to claim 15, wherein: i. steps (d) and (e) are performed in a plurality of E execution stages, comprising a first execution stage and E1 subsequent execution stages; ii. the set of S private input secrets is partitioned into E disjoint sets corresponding to said E execution stages; iii. the particles v.sub.a,m computed in step (d) and communicated in step (e) are computed in each execution stage for the secrets of the disjoint set corresponding to the execution stage; and iv. the computing nodes calculate the shares share [r.sub.a].sub.n in step (f) after all of the required particles v.sub.a,m have been received following said repeated execution stages.

17. A computer-implemented method according to claim 16, wherein the communication to the computing nodes of {[.sup..sup.a].sub.n}.sub.a{0, . . . ,A1} occurs only in one execution stage.

18. A computer-implemented method according to claim 17, wherein the communication to the computing nodes of {[.sup..sup.a].sub.n}.sub.a{0, . . . ,A1} occurs in the first execution stage.

19. A computer-implemented method according to claim 16, wherein the partitioning of the secret variables is performed according to an index e corresponding with the execution stage, wherein the addition and multiplication subindices a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} are partitioned such that: $\left\{0,.Math.,A-1\right\}=\underset{e=1}{\stackrel{E}{.Math.}}{A}_e$ $\left\{0,.Math.,M_a-1\right\}=\underset{e=1}{\stackrel{E}{.Math.}}{M}_{a,e}$ where A.sub.e and M.sub.a,e represent, respectively, the indices of the additions and multiplications in each addition to which the dealer node contributes with input secret variables during the e-th execution stage.

20. A computer-implemented method according to claim 19, wherein in the first execution stage (e=1) the dealer node computes in step (d) and communicates in step (e) the particles v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m for aA.sub.1, mM.sub.a,1.

21. A computer-implemented method according to claim 20, wherein in each subsequent execution stage e, the dealer node computes in step (d) and communicates in step (e) the particles v.sub.a,m=S.sub.i.sub.a,m.Math..sup..sup.a,m for aA.sub.1,mM.sub.a,1.

22. A computer-implemented method according to claim 16, wherein in the first execution stage, the dealer node stores to a readable memory the random dealer blinding factors .sub.a,m for each addition and multiplication not used in the first execution.

23. A computer-implemented method according to claim 22, wherein in each subsequent execution stage, the dealer node retrieves from said readable memory the random dealer blinding factors .sub.a,m required for the additions and multiplications involved in that subsequent execution stage.

24. A computer-implemented method according to claim 16, wherein step (d) further comprises sending to each computing node:
{[.sub.a,m].sub.n}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1}.

25. A computer-implemented method according to claim 24, further comprising the computing nodes sending back to the dealer node, for a given value of a, m, the values v.sub.a,m, {[.sub.a,m].sub.n}.sub.n{0, . . . ,N-1}, and the dealer node reconstructing A.sub.a,m and recovering the secret input s.sub.i.sub.a,m from the corresponding particle v.sub.a,m.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0128] Embodiments of the invention will now be described, by way of example only, with reference to the accompanying schematic drawings, in which:

[0129] FIG. 1 shows a generic SMPC setup;

[0130] FIG. 2 illustrates the four phases of a generic SMPC protocol using LSS;

[0131] FIG. 3 is a flowchart of the message flows involved in Passive D-MLC, according to an embodiment of the invention;

[0132] FIG. 4 is a flowchart of the message flows involved in Active D-MLC, according to an embodiment of the invention; and

[0133] FIG. 5 is a flowchart of the message flows involved in Active 1-MLC, according to an embodiment of the invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

[0134] The focus of the embodiments 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.

[0135] 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 centralized server.

[0136] In this invention we present a new protocol called MLC (Messageless 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). MLC 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. MLC as presented in this invention is secure against passive and active adversaries: [0137] Passive adversaries follow the protocol specification but try to learn information about the private inputs s.sub.0, s.sub.1, . . . , s.sub.S-1 to the computation. [0138] Active adversaries may deviate from the protocol to try to learn information about the private inputs, to alter the result from a computation, or simply to prevent the computation from taking place. Active adversaries may therefore change the content of their messages, delay their messages or simply not send them.

[0139] The MLC protocol in the passive and active adversary settings requires a pre-processing phase. In this invention we describe the output of this phase and assume that it is carried out by a trusted third party.

[0140] We focus on the arithmetic setting and on functions returning only one number. We refer to Appendix A.3 of SPDZ [SPDZ12], which is incorporated herein by reference, for a description on how to extend this to any number of output values. Without loss of generality, this function can be expressed as the addition of A groups of multiplications of secrets:

[00034]$f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=m_0+m_1+.Math.+m_{A-1}=\underset{a=0}{\overset{A-1}{.Math.}}{m}_a$

where each group of multiplications m.sub.a, a{0, 1, . . . , A1} is a number resulting from the product of M.sub.a private input secrets:

[00035]$m_a=s_{i_{a,0}}.Math.s_{i_{a,1}}.Math..Math..Math.s_{i_{a,M_a-1}}=\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$$i=3$

[0141] Here, the subindices i.sub.a,m for a{0, 1, . . . , A1}, m{0, 1, . . . , M.sub.a1} are indexing private input secrets from the set of all S secrets {s.sub.0, s.sub.1, . . . , s.sub.S-1}. The S secrets may be integers, real or even complex numbers. They come from different Dealer Nodes who wish to keep them private and yet to use them as inputs to the joint evaluation of . In what follows, we make the following assumptions: [0142] Assumption 1: There are private point-to-point channels between different nodes in the network. [0143] Assumption 2: There is an authenticated broadcast channel [0144] Assumption 3: Without loss of generality, we assume that for every addition term m.sub.a there is at most only one input per dealer, since if a dealer contributes with more than one input variable to the product m.sub.a, it can always replace them with a new input variable equal to their product. [0145] Assumption 4: 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. For simplicity we will omit mod p.

[0146] The arithmetic function then be expressed more succinctly as:

[00036]$\begin{array}{cc}f=f\left(s_0,s_1,.Math.,s_{S-1}\right)=\underset{a=0}{\overset{A-1}{.Math.}}\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}& \mathrm{Eq}.1\end{array}$

[0147] We refer to the D-MLC protocol to an implementation for D Dealer Nodes. We distinguish between active and passive adversary settings. We proceed as follows: [0148] First, we describe in section 1 the pre-processing phase as an ideal functionality that is executed by a trusted third party, specifying its inputs and outputs. [0149] Second, we present in section 2 D-HLC in the passive adversary setting, [0150] Third we introduce in section 3 D-HLC in the active adversary setting, and [0151] Finally, we present in section 4 a special case of the D-HLC algorithm in the active setting for D=1 (i.e. there is only one dealer).

[0152] Section 1: Pre-Processing as an Ideal Functionality

[0153] The goal of the pre-processing phase is to compute some randomness and to distribute shares of that randomness to the Computing Nodes. The randomness is used for: [0154] The computation of multiplications by the Computing Nodes without the need to communicate, and [0155] The creation of a so-called particle to hide the information from the input variables contributed by every Dealer Node.

[0156] The idea is that the pre-processing takes place before we know how many dealers there will be involved in a computation, or how many multiplications the computation will comprise. Therefore, a key requirement for the pre-processing phase is that it should be de-coupled from the number of dealers and from the number of multiplications to be computed. To achieve this, the pre-processing phase relies on a vector of fine-granular randomness that we call the exponent blinding factors and represent by 0, .sub.1, . . . , .sub.L-1. The assumption is that L is larger than the maximum number of multiplications and larger than the maximum number Dealer Nodes in a computation.

[0157] The pre-processing phase comprises several executions (possibly in parallel) of the following pre-processing ideal functionality F.sub.pre run by a trusted node:

Algorithm: Pre-Processing Ideal Functionality F.SUB.pre

Inputs:

[0158] L: The number of exponent blinding factors to generate, [0159] N: The number of Computing Nodes in the MLC Network [0160] p: A prime number [0161] p: A public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p [0162] x.sub.0, . . . , x.sub.N-1 pre-agreed public abscissa for each one of the N MLC Computation Nodes, and [0163] T: Degree of the Shamir polynomials

Output:

[0164] Each Computing Node receives: [0165] Polynomial shares [.sub.0], [.sub.1], . . . , [.sub.L-1] from each exponent blinding factor .sub.0, .sub.1, . . . , .sub.L-1, and [0166] A polynomial share [.sup.] of .sup., where:

[00037]$\begin{array}{cc}=\underset{m=0}{\overset{L-1}{.Math.}}{}_m& \mathrm{Eq}.2\end{array}$

Purpose:

[0167] A trusted node generates and sends the required randomness to the MLC Computing Nodes so that they are able to process arithmetic operations without the need for inter-node communication.

Security Requirement:

[0168] The exponent blinding factors .sub.0, .sub.1, . . . , .sub.L-1, and .sup. are internal secrets that the trusted node does not reveal to anyone.

Algorithm Steps:

[0169] The following steps are executed by the trusted node: [0170] Step 1: Computation of the exponent blinding factors. [0171] Compute L random exponent blinding factors .sub.0, .sub.1, . . . , .sub.L-1(Z/pZ).sup.x [0172] Step 2: Computation of shares. [0173] For every exponent blinding factor m{0, . . . L1} compute N shares of a degree-T polynomial that hides the value .sub.m at x=0:

[.sub.m].sub.0,[.sub.m].sub.1, . . . ,[.sub.m].sub.N-1SHAMIR(.sub.m) [0174] Step 3: Computation of .sup.. [0175] Compute .sup., where

[00038]$=\underset{m=0}{\overset{L-1}{.Math.}}{}_m$ [0176] Step 4: Computation of shares. [0177] Compute N shares of a degree-T polynomial that hides the value .sup. at x=0:

[.sup.].sub.0,[.sup.].sub.1, . . . ,[.sup.].sub.N-1SHAMIR(.sup.) [0178] For each n{0, . . . , N1}, the trusted node then sends to the n-th node: [0179] [.sub.0].sub.n, [.sub.1].sub.n, . . . , [.sub.L-1].sub.n, and [0180] [.sup.].sub.n [0181] [End of Algorithm: Pre-processing Ideal Functionality F.sub.pre]

Section 2: Passive D-MLC

[0182] In a first implementation, there is provided a method to evaluate an arithmetic function, the method being described and illustrated below with the algorithm Passive D-MLC.

[0183] We now define the three phases of the Passive D-MLC to evaluate any arithmetic function. Without loss of generality, this function will comprise A additions and M.sub.a multiplication factors in the a-th addition. This means that M.sub.a Dealer Nodes will contribute M.sub.a secrets as multiplication factors to the a-th addition term.

[0184] The idea is that the MLC Computation Nodes follow the same pre-agreed deterministic algorithm to create a partition of the set {0, 1, . . . , L1} into M.sub.a disjoint, non-empty sets. That is, {0, 1, . . . , L1}=P.sub.a,0 P.sub.a,1 . . . P.sub.a,M.sub.a.sub.1. This partition dictates which exponent blinding factors need to be added in order to produce what we call a dealer blinding factor .sub.a,m. This blinding factor will be used by the Dealer Node to create a particle that masks its input to the m-th multiplication factor in the a-th addition.

[0185] To formalize this idea, let us denote:

P.sub.a,0,P.sub.a,1, . . . ,P.sub.a,M.sub.a.sub.1PARTITION(L,M.sub.a)

to the deterministic algorithm that creates a partition of the indexing set {0, 1, . . . , L1} with M.sub.a sets such that all partition sets are disjoint and non-empty. An example of such deterministic algorithm is the following:

Algorithm: PARTITION (L, M)

[0186] IF (L<M) THEN RETURN ERROR [0187] IF (L==M) THEN RETURN P.sub.0, P.sub.1, . . . , P.sub.M-1 with P.sub.i={i} [0188] Perform integer division L/M and obtain integer quotient Q and remainder R [0189] Split vector {0, 1, . . . ,L1} into M subsets P.sub.0, P.sub.1, . . . , P.sub.M-1 of equal size Q [0190] Add the R remaining unassigned elements in {0, 1, . . . , L1} to the last partition set P.sub.M-1. [0191] RETURN P.sub.0, P.sub.1, . . . , P.sub.M-1

[0192] [End of Algorithm: Pre-processing Ideal Functionality F.sub.pre]

[0193] For example, on inputs L=4 and M=3, this algorithm returns P.sub.0={0}, P.sub.1={1}, P.sub.2={2,3}. The particular choice of algorithm is irrelevant as long as the partition sets are disjoint and non-empty, and every MLC Computation Node executes the same partition algorithm. The skilled person will readily appreciate that they can use any arbitrary set of rules to allocate L integers into M.sub.a disjoint, non-empty partition sets.

[0194] Once computed, the partition P.sub.a,0, P.sub.a,1, . . . , P.sub.a,M.sub.a.sub.1 allows us to define the m-th dealer blinding factor as:

[00039]$\begin{array}{cc}{}_{a,m}=\underset{i{P}_{a,m}}{.Math.}{}_{a,i}& \mathrm{Eq}.3\end{array}$

[0195] Notice that since the partition sets are non-empty, every .sub.a,m is well-defined.

[0196] Notice also that since the partition sets are disjoint the following equation holds:

[00040]${}_a=\underset{m=0}{\overset{M_a-1}{.Math.}}{}_{a,m}=\underset{l=0}{\overset{L-1}{.Math.}}{}_{a,l}$

where .sub.a is the same A defined in Eq. 2.

[0197] In what follows, we assume that the MLC Computing Nodes have run the pre-processing phase. Specifically, we assume that each n-th MLC Computing Node has obtained the following shares for every addition a{0, . . . , A1}: [0198] [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n, and [0199] [.sup..sup.a].sub.n

Algorithm: Passive D-MLC

Inputs:

[0200] D Dealer Nodes, whereby the n-th node holds a subset S.sub.n of the total set of secrets S={s.sub.0, s.sub.1, . . . , s.sub.S-1}. The Dealer Nodes wish to compute an arithmetic function =(s.sub.0, s.sub.1, . . . , s.sub.S-1) over their secrets given by Eq. 1. Additional inputs follow: [0201] N=T+1: The number of Computing Nodes in the MLC Network, where T is the degree of the Shamir polynomials [0202] p: A prime number [0203] : A public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p [0204] x.sub.0, . . . , x.sub.N-1 pre-agreed public abscissa for each one of the N MLC Computation Nodes used

Output:

[0205] R result nodes reconstruct the function result =.sub.a=0.sup.A-1.sub.m=0.sup.M.sup.a.sup.1 s.sub.i.sub.a,m comprising A additions, whereby the a-th addition comprises M.sub.a multiplications. This function is evaluated by N computing nodes that are not able to see any of the input secrets.

Purpose:

[0206] 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 Steps:

[0207] The steps of the algorithm can be divided into three phases: Share Distribution, Computation and Result Reconstruction.

Phase 1Share Distribution

[0208] Step 1: [0209] For every addition a{0, . . . , A1}, each MLC Computing Node n: [0210] Runs the partition algorithm and independently obtains the same partition sets

P.sub.a,0,P.sub.a,1, . . . P.sub.a,M.sub.a.sub.1PARTITION(L,M.sub.a) [0211] Locally computes a share from each dealer blinding factor [.sub.a,m].sub.n from the shares of the exponent blinding factors [.sub.a,i].sub.n and the partition sets P.sub.a,0, P.sub.a,1, . . . , P.sub.a,M.sub.a.sub.1 as follows:

[00041]${\left[{}_{a,m}\right]}_n=\underset{i{P}_{a,m}}{.Math.}{\left[{}_{a,i}\right]}_n$ [0212] for m{0, . . . , M.sub.a1}. [0213] Sends their share [.sub.a,m] to Dealer Node d{0, 1, . . . , D1} if this Dealer Node contributes with secret s.sub.i.sub.a,m to the computation, for every addition a{0, . . . , A1} and every multiplication m{0, . . . , M.sub.a1}. Messages to the same Dealer Node can be merged into one single message. [0214] Step 2: [0215] Each Dealer Node d{0, 1, . . . , D1} receives the shares [.sub.a,m].sub.n, n{0, . . . , N1} from the previous step if they contribute with secret s.sub.i.sub.a,m to the computation of the multiplication comprising the a-th addition term in Eq. 1. This node reconstructs .sub.a,m using polynomial interpolation:

.sub.a,mINTERPOLATE([.sub.a,m].sub.0,[.sub.a,m].sub.1, . . . ,[.sub.a,m].sub.T) [0216] Recall that in s.sub.i.sub.a,m, i.sub.a,m acts as an index to the corresponding secret in the set s.sub.0, s.sub.1, . . . , s.sub.S-1. Recall also from Assumption 3 that each Dealer Node only contributes with at most one secret to the a-th addition term in Eq. 1. [0217] Step 3: [0218] Each Dealer Node then computes the particle v.sub.a,m from their secret input s.sub.i.sub.a,m using the dealer blinding factor .sub.a,m as follows:

v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m [0219] Step 4: [0220] Each Dealer Node sends one broadcast message to the N computing nodes containing one value v.sub.a,m for each addition term a to which they contribute a secret. Each value v.sub.a,m represents an MLC particle computed from their secret s.sub.i.sub.a,m.

[0221] Note on security. Notice that unless all N computing nodes were colluding, they would not know the value of the dealer blinding factors .sub.a,m because all they have is a Shamir polynomial share of these values. Therefore, the factor .sup..sup.a,m is effectively hiding the secret value s.sub.i.sub.a,m and algorithm MLC inherits the security features from SSS in the passive setup, namely, it is secure against T (or less) colluding nodes. Specifically, an adversary would have to corrupt all T+1 computing nodes in order to be able to reconstruct .sub.a,m and recover s.sub.i.sub.a,m from v.sub.a,m.

Phase 2Computation

[0222] Step 1: [0223] Each computing node n, n{0, 1, . . . , N1} calculates for each addition a, a{0, 1, . . . , A1} a share from a degree-T polynomial r.sub.a(x) which is a scaled version of the polynomial hiding .sup..sup.a as a secret:

[00042]$\begin{array}{cc}{\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}& \mathrm{Eq}.4\end{array}$ [0224] Notice that .sub.m=0.sup.M.sup.a.sup.1 v.sub.a,m is just a scalar and so r.sub.a(x) has the same degree-T as the polynomial hiding .sup..sup.a as a secret. [0225] Step 2: [0226] Each computing node n, n{0, 1, . . . , N1} calculates a share [r].sub.n from a degree-T polynomial .sub.a=0.sup.A-1 r.sub.a(x):

[00043]$\begin{array}{cc}{\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n& \mathrm{Eq}.5\end{array}$ [0227] This phase does not require any communication between the computing nodes since each node n can locally compute [r.sub.a].sub.n for each a{0, 1, . . . , A1}.

Phase 3Result Reconstruction

[0228] Each computing node n, n{0, 1, . . . , N1} sends their MLC share [r].sub.n of the result to the result nodes, which apply Lagrange interpolation to reconstruct the evaluation r(0) of polynomial r(x), which is equal to the output of the function we wanted to evaluate:

=r(0)INTERPOLATE([r].sub.0,[r].sub.1, . . . ,[r].sub.T)Eq. 6

[0229] [End of Algorithm::Passive D-MLC]

[0230] FIG. 3 is a flowchart of the message flows involved in Passive D-MLC. As it can be appreciated, the computation phase requires no message exchange among the computing nodes. Each one independently compute (see Eq. 4):

[00044]${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$

Proof for Eq. 6.

[0231] Now we provide a proof for the main result in Eq. 6.

[0232] Starting from Eq. 4 and 5 we have:

[00045]${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n=$$\underset{a=0}{\overset{A-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}=$$\underset{a=0}{\overset{A-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}.Math.p^{{}_{a,m}}=$$\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_{a,0}}.Math.{}^{{}_{a,1}}.Math..Math..Math.{}^{{}_{a,\mathrm{Ma}-1}}.Math.{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}=$$\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_{a,0}+{}_{a1}+.Math.+{}_{a,\mathrm{Ma}-1}}.Math.{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}=$$\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$

where the last step comes from the fact that .sub.a,0+.sub.a,1+ . . . +.sub.a,M.sub.a.sub.1=la, which follows from Eq. 2 and Eq. 3. By plugging this result into the right-hand side of Eq. 6 and taking into account Lagrange Interpolation for r(x) we get:

[00046]$r\left(0\right)=\underset{n=0}{\overset{N-1}{.Math.}}{\left[r\right]}_n.Math.\underset{\begin{array}{c}0mN-1\\ mn\end{array}}{.Math.}\frac{x_m}{x_m-x_n}=$$\underset{n=0}{\overset{N-1}{.Math.}}\underset{0mN-1}{.Math.}\frac{x_m}{x_m-x_n}\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.{\left[{}^{-{}_a}\right]}_n.Math.\stackrel{M_a-1}{\underset{m=0}{.Math.}}{s}_{i_{a,m}}=$$\underset{a=0}{\overset{A-1}{.Math.}}\underset{n=0}{\overset{N-1}{.Math.}}\underset{\begin{array}{c}0mN-1\\ mn\end{array}}{.Math.}\frac{x_m}{x_m-x_n}.Math.{}^{{}_a}.Math.{\left[{}^{-{}_a}\right]}_n\stackrel{M_a-1}{\underset{m=0}{.Math.}}{s}_{i_{a,m}}=$

[0233] Rearranging terms:

[00047]$r\left(0\right)=\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}\underset{n=0}{\overset{N-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{\begin{array}{c}0mN-1\\ mn\end{array}}{.Math.}\frac{x_m}{x_m-x_n}$

where the inner sum corresponds to the Lagrange interpolation at x=0 of a degree-T polynomial that hides the value .sup..sup.a and it is therefore equal to this value:

[00048]${}^{-{}_a}=\underset{n=0}{\overset{N-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{\begin{array}{c}0mN-1\\ mn\end{array}}{.Math.}\frac{x_m}{x_m-x_n}$

[0234] Replacing this we obtain:

[00049]$r\left(0\right)=\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.{}^{-{}_a}\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$

which corresponds to =(s.sub.0, s.sub.1, . . . , S.sub.s-1)=.sub.a=0.sup.A-1.sub.m=0.sup.M.sup.a.sup.1 s.sub.i.sub.a,m in Eq. 1..square-solid.

[0235] Section 3: Active D-MLC

[0236] In a second independent aspect of the invention, there is provided a method to evaluate an arithmetic function, the method being described and illustrated below with the algorithm Active D-MLC.

[0237] We now define the four phases of the Active MLC to evaluate any arithmetic function. As in the passive case, the idea is that the MLC Computation Nodes follow the same pre-agreed deterministic algorithm to create a partition of the set {0, 1, . . . , L1} into M.sub.a disjoint, non-empty sets. That is, {0, 1, . . . , L1}=P.sub.a,0 P.sub.a,1 . . . P.sub.a,M.sub.a.sub.1. This partition dictates which exponent blinding factors need to be added in order to produce what we call a dealer blinding factor .sub.a,m for the Dealer Node contributing with the m-th multiplication factor in the a-th addition. We denote as before:

P.sub.a,0,P.sub.a,1, . . . ,P.sub.a,M.sub.a.sub.1<PARTITION(L,M.sub.a)

to the deterministic algorithm that creates a partition of the indexing set {0, 1, . . . , L1} into M.sub.a sets such that all partition sets are disjoint and non-empty. The same considerations apply as in the passive case regarding the nature of this algorithm.

[0238] As in the passive case, we assume that each MLC Computing Node has computed in the pre-processing phase the following shares for every addition a{0, . . . , A1}: [0239] [.sub.a,0].sub.n, [.sub.a,1].sub.n, . . . , [.sub.a,L1].sub.n, and

[.sup..sup.a].sub.n

[0240] An important difference compared to the passive case is that now there are N shares with NT+1 (instead of T+1) from the degree-T polynomials hiding each one of the secrets above. The extra shares provide redundancy that will be used to detect and correct wrong shares that the corrupted parties might deliver for the reconstruction of a secret. A typical setup is to choose N3T+1, which can allow for the detection and correction of up to T shares from T corrupted parties in the reconstruction of a secret.

Algorithm: Active D-MLC

Inputs:

[0241] D Dealer Nodes, whereby the n-th node holds a subset S.sub.n of the total set of secrets S={s.sub.0, s.sub.1, . . . , s.sub.S-1}. The Dealer Nodes wish to compute an arithmetic function =(s.sub.0, s.sub.1, . . . , s.sub.S-1) over their secrets given by Eq. 1. Additional inputs follow: [0242] N>T+1: The number of Computing Nodes in the MLC Network, where T is the degree of the Shamir polynomials [0243] p: A prime number [0244] : A public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p [0245] x.sub.0, . . . , x.sub.N-1 pre-agreed public abscissa for each one of the N MLC Computation Nodes used

Output:

[0246] R result nodes reconstruct the function result =.sub.a=0.sup.A-1.sub.m=0.sup.M.sup.a.sup.1 s.sub.i.sub.a,m comprising A additions, whereby the a-th addition comprises M.sub.a multiplications. This function is evaluated by N computing nodes that are not able to see any of the input secrets.

Purpose:

[0247] N computing nodes can jointly evaluate any arithmetic function whilst keeping the dealers' secrets private and without any message exchange during the computation phase. A fraction of the nodes can be corrupted without compromising the correctness of the protocol.

Algorithm Steps:

[0248] The steps of the algorithm can be divided into three phases: Share Distribution, Computation and Result Reconstruction.

Phase 1Share Distribution

[0249] Step 1: [0250] For every addition a{0, . . . , A1}, each MLC Computing Node n: [0251] Runs the partition algorithm and independently obtains the same partition sets

P.sub.a,0,P.sub.a,1, . . . ,P.sub.a,M.sub.a.sub.1PARTITION(L,M.sub.a) [0252] Locally computes a share from each dealer blinding factor [.sub.a,m].sub.n from the shares of the exponent blinding factors [.sub.a,i].sub.n and the partition sets P.sub.a,0, P.sub.a,1, . . . , P.sub.a,M.sub.a.sub.1 as follows:

[00050]${\left[{}_{a,m}\right]}_n=\underset{i{P}_{a,m}}{.Math.}{\left[{}_{a,i}\right]}_n$ [0253] for m{0, . . . , M.sub.a1}. [0254] Sends their share [.sub.a,m].sub.n to Dealer Node d{0, 1, . . . , D1} if this Dealer Node contributes with secret s.sub.i.sub.a,m to the computation, for every addition a{0, . . . , A1} and every multiplication m{0, . . . , M.sub.a1}. Messages to the same Dealer Node can be merged into one single message. [0255] Step 2: [0256] Each Dealer Node d{0, 1, . . . , D1} receives the shares [.sub.a,m].sub.n from the previous step if they contribute with secret s.sub.i.sub.a,m to the computation of the multiplication comprising the a-th addition term in Eq. 1, and reconstructs .sub.a,m using error correction codes:

.sub.a,mECC([.sub.a,m].sub.0,[.sub.a,m].sub.1, . . . ,[.sub.a,m].sub.N-1)

Recall that in s.sub.i.sub.a,m, i.sub.a,m acts as an index to the corresponding secret in the set s.sub.0, s.sub.1, . . . , s.sub.S-1. Recall also from Assumption 3 that each Dealer Node only contributes with at most one secret to the a-th addition term in Eq. 1. [0257] Step 3: [0258] Each Dealer Node then computes the particle v.sub.a,m from their secret input s.sub.i.sub.a,m using the dealer blinding factor .sub.a,m as follows:

v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m [0259] Step 4: [0260] Each Dealer Node sends one broadcast message to the N computing nodes containing one value v.sub.a,m for each addition term a to which they contribute a secret. Each value v.sub.a,m represents an MLC particle computed from their secret s.sub.i.sub.a,m.

[0261] Note on security. Notice that T+1 nodes are required to collude to reconstruct the value of the dealer blinding factors .sub.a,m because all they have is a degree-T Shamir polynomial share of these values. Therefore, the factor .sup..sup.a,m is effectively hiding the secret value s.sub.i.sub.a,m and algorithm MLC inherits the security features from SSS in the passive setup, namely, it is secure against T (or less) colluding nodes.

Phase 2Computation

[0262] Step 1:

[0263] Each computing node n, n{0, 1, . . . , N1} calculates for each addition a, a{0, 1, . . . , A1} a share from a degree-T polynomial r.sub.a(x) which is a scaled version of the polynomial hiding .sup..sup.a as a secret:

[00051]$\begin{array}{cc}{\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}& \mathrm{Eq}.4\end{array}$

Notice that .sub.m=0.sup.M.sup.a.sup.1 v.sub.a,m is just a scalar and so r.sub.a(x) has the same degree-T as the polynomial hiding .sup..sup.a as a secret. [0264] Step 2:

[0265] Each computing node n, n{0, 1, . . . , N1} calculates a share from a degree-T polynomial r(x)=.sub.a=0.sup.A-1 r.sub.a(x):

[00052]$\begin{array}{cc}{\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n& \mathrm{Eq}.5\end{array}$

[0266] This phase does not require any communication between the computing nodes since each node n can locally compute [r.sub.a].sub.n for each a{0, 1, . . . , A1}.

Phase 3Result Reconstruction

[0267] Each computing node n, n{0, 1, . . . , N1} sends their MLC share [r].sub.n of the result to the result nodes, which apply Lagrange interpolation to reconstruct the evaluation r(0) of polynomial r(x), which is equal to the output of the function we wanted to evaluate:

=r(0)ECC([r].sub.0,[r].sub.1, . . . ,[r].sub.N-1)Eq. 6a

[0268] [End of Algorithm: Active D-MLC]

[0269] FIG. 4 is a flowchart of the message flows involved in Active D-MLC. As it can be appreciated, the computation phase requires no message exchange among the computing nodes. Each one independently computes (see Eq. 4):

[00053]${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}$

Proof for Eq. 6a.

[0270] Now we provide a proof for the main result in Eq. 6a.

[0271] Following the same reasoning from the first part of the proof of Eq. 6 in the passive adversary setup, we conclude that:

[00054]${\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.{\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}$

[0272] That is, [r].sub.n is a linear combination of the n-th share [.sup..sup.a], from A degree-T polynomials and hence it is the n-th share of a new degree-T polynomial r(x) hiding the value:

[00055]$r\left(0\right)=\underset{a=0}{\overset{A-1}{.Math.}}{}^{{}_a}.Math.{}^{-{}_a}.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}=\underset{a=0}{\overset{A-1}{.Math.}}\underset{m=0}{\overset{M_a-1}{.Math.}}{s}_{i_{a,m}}=f=f\left(s_0,s_1,.Math.,S_{S-1}\right)$

[0273] Hence, all we need to do is to interpolate the value r(0) of the polynomial r(x) from NT+1 shares given that some of them might have been altered by the corrupted parties producing wrong shares. This can be done using error correction codes. From this, we conclude that:

=r(0)ECC([r].sub.0,[r].sub.1, . . . ,[r].sub.N-1)

[0274] In a preferred implementation Reed Solomon codes are used with the Berlekamp-Welch decoder [Mann13], which is incorporated herein by reference. In another implementation, a different code and/or decoder is used. The skilled person is free to choose any interpolation available to one skilled in the art to reconstruct the value of the result from the result shares. The use of error correction codes, and the choice of such code schemes, is not a limitation of this method.

Section 4: Active 1-MLC

[0275] In a third implementation, there is provided a method to evaluate an arithmetic function, the method being described and illustrated below with the algorithm Active 1-MLC.

[0276] We describe the case where all the secret inputs are coming from a single Dealer Node. This case is important since: [0277] 1. Often the secrets in a computation are coming from just one Dealer Node. This is the case for example of authentication and signatures. [0278] a. In authentication, the Dealer Node registers a number of factors (device identifier, password, facial biometric, pin, etc.) with the network in the form of particles. They then return providing new versions of these factors, which are sent as new particles to the network of MLC Computing Nodes. The network then jointly computes a function that allows comparing these factors and returns TRUE if they match, and FALSE if they do not match. [0279] b. In signatures, the Dealer Node registers a private key in the form of particles. They then return providing a message to be signed by the network. The network of MLC Computing Nodes jointly computes a function that returns the signature for the given message. [0280] 2. The restriction D=1 allows for a modified protocol that is even safer than D-MLC for active adversaries [0281] 3. The restriction D=1 allows for a modified protocol that does not require pre-processing.

[0282] The method can operate with a number of execution stages. For example, the measurements and values from a captured facial image at REGISTRATION time are transformed into particles and stored by the nodes in the network. At this point, they are not passed through a function. The particle version of each one of these datapoints constitutes in effect a hashed value of some aspect of the captured image. These particles can be passed to the computing nodes from the dealer node at a first execution stage.

[0283] At LOGIN time the same process is applied to the (different) captured facial image, resulting in the dealer node computing and communicating to the computing nodes, in a further execution stage, a further set of particles characterising the LOGIN image.

[0284] At the end of this process the computing nodes have particles from measurements and values from two captured facial images during registration and login times. It is at this stage that the nodes process all of these particles in order to evaluate the function . What this function would typically do is to measure the distance between the measurements and values at registration and login times to see how similar they are. The result nodes take the individual elements of the calculated function and return a number representing this compound distance between all the measurements and values. If the number is below a threshold then we conclude that the two faces were the same.

[0285] Summarising, with the execution stage model, new particles are sent in each execution stage as the dealer gathers more and more information. Whenever all necessary particles have been collected in order to run the desired function , this function is locally evaluated and a result is produced.

[0286] In Active 1-MLC the Dealer Node does not rely on the network in order to carry out the pre-processing phase. It should be noted that although all the secrets come from the same node, they can be provided at different moments in time, as the authentication and signature examples suggest. In the following protocol description, we reflect this fact by describing two different processes in Phase 1: [0287] First Execution: This process is only executed the first time the Dealer Node wants to initiate an 1-MLC Computation (e.g. password registration in authentication, or private key registration in the signature example) [0288] Subsequent Executions: This process is executed whenever the Dealer Node wants to add some more information to the computation (e.g. login in authentication, or message signing in the signature example). It can be executed once or more than once.

[0289] The protocol makes use of two new functions [0290] STORE ({x.sub.1, . . . , x.sub.j}) [0291] {x.sub.1, . . . , x.sub.Je}LOAD(e)

[0292] The function STORE stores a collection of J of variables. The function LOAD(e) retrieves a collection comprising all the Je variables from execution number e. We treat these functions as generic now and then provide a few possible implementations.

[0293] We describe the protocol assuming no pre-processing has taken place between the MLC Computing Nodes.

Algorithm: Active 1-MLC

Inputs:

[0294] One Dealer Node providing all secret inputs S={s.sub.0, s.sub.1, . . . , s.sub.S-1} to a computation. The Dealer Node wishes to compute an arithmetic function =(s.sub.0, s.sub.1, . . . , s.sub.S-1) over their secrets given by Eq. 1. Additional inputs follow: [0295] N>T+1: The number of Computing Nodes in the MLC Network, where T is the degree of the Shamir polynomials [0296] p: A prime number [0297] : A public generator from the multiplicative group (Z/pZ).sup.x of integers modulo p [0298] x.sub.0, . . . , x.sub.N-1 pre-agreed public abscissa for each one of the N MLC Computation Nodes used

Output:

[0299] R result nodes reconstruct the function result =.sub.a=0.sup.A-1.sub.m=0.sup.M.sup.a.sup.1 s.sub.i.sub.a,m comprising A additions, whereby the a-th addition comprises M.sub.a multiplications. This function is evaluated by N computing nodes that are not able to see any of the input secrets.

Purpose:

[0300] N computing nodes can jointly evaluate any arithmetic function whilst keeping the dealer's secrets private and without any message exchange during the computation phase. A fraction of the nodes can be corrupted without compromising the correctness of the protocol.

Algorithm Steps:

[0301] The steps of the algorithm can be divided into three phases: Share Distribution, Computation and Result Reconstruction.

Phase 1Share Distribution

[0302] The Dealer Node contributes with a collection {s.sub.i.sub.a,m}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1} of input secret variables to the computation. We partition this collection according to the index corresponding with the execution. That is, if there is a total number of E executions then:

[00056]$\left\{0,.Math.,A-1\right\}=\stackrel{E}{\underset{e=1}{.Math.}}{A}_e$$\left\{0,.Math.,M_a-1\right\}=\stackrel{E}{\underset{e=1}{.Math.}}{M}_{a,e}$

where each set is disjoint, and A.sub.e and M.sub.a,e represent, respectively, the indices of the additions and multiplications in each addition to which the Dealer Node contributes with input secret variables during the e-th execution of Phase 1. We denote A.sub.e.sup.c and M.sub.a,e.sup.c to the complementary of sets A.sub.e and M.sub.a,e, respectively.
First Execution (e=1): [0303] Step 1: [0304] For every addition a{0, . . . , A1} and multiplication m{0, . . . , M.sub.a1}, the Dealer Node locally computes a random dealer blinding factor .sub.a,m [0305] Step 2: [0306] For every addition a{0, . . . , A1}, the Dealer Node computes:

[00057]${}_a=\underset{m=0}{\overset{M_a-1}{.Math.}}{}_{a,m}$ [0307] and a polynomial sharing for .sub.a:

[.sup.].sub.0,[.sup.].sub.1, . . . ,[.sup.].sub.N-1SHAMIR(.sup.) [0308] Step 3: [0309] For aA.sub.1, mM.sub.a,1 the Dealer Node then computes:

v.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m [0310] Step 4: [0311] The Dealer Node sends a message to the n-th MILC Computing Node for n E {0, . . . , N1} containing: [0312] 1. {v.sub.a,m}.sub.aA.sub.1.sub.,mM.sub.a,1, [0313] 2. {[.sub.a,m].sub.n}.sub.a{0, . . . ,A1},m{0, . . . ,M.sub.a.sub.1}, and [0314] 3. {[.sup..sup.a].sub.n}.sub.a{0, . . . ,A1}. [0315] Step 5: [0316] Run

STORE({.sub.a,m}.sub.aA.sub.1.sub.c.sub.,mM.sub.a,1.sub.c),

Subsequent Executions (e>1): [0317] Step 1: [0318] Run

{.sub.a,m}.sub.aA.sub.e.sub.,mM.sub.a,eLOAD(e) [0319] Step 2: [0320] For aA.sub.e, mM.sub.a,e, the Dealer Node then computes:

V.sub.a,m=s.sub.i.sub.a,m.Math..sup..sup.a,m [0321] Step 3: [0322] The Dealer Node sends a message to the n-th MILC Computing Node for n E {0, . . . , N1} containing {v.sub.a,m}.sub.aA.sub.e.sub.,mM.sub.a,e

[0323] Note on security. Notice that T+1 nodes are required to collude to reconstruct the values {.sup..sup.a}.sub.a{0, . . . ,A1} because all they have is a Shamir polynomial share of these values. Therefore, the factor .sup..sup.a,m is effectively hiding the secret value s.sub.i.sub.a,m and algorithm MLC inherits the security features from SSS in the passive setup, namely, it is secure against T (or less) colluding nodes.

Phase 2Computation

[0324] Step 0: [0325] Each Computing Node waits until it has received all v.sub.a,m for every addition a{0, . . . , A1} and multiplication m{0, . . . , M.sub.a1). [0326] Step 1: [0327] Each computing node n, n{0, 1, . . . , N1} calculates for each addition a, a{0, 1, . . . , A1} a share from a degree-T polynomial r.sub.a(x) which is a scaled version of the polynomial hiding .sup..sup.a as a secret:

[00058]$\begin{array}{cc}{\left[r_a\right]}_n={\left[{}^{-{}_a}\right]}_n.Math.\underset{m=0}{\overset{M_a-1}{.Math.}}{v}_{a,m}& \mathrm{Eq}.4\end{array}$ [0328] Notice that .sub.m=0.sup.M.sup.a1 v.sub.a,m is just a scalar and so r.sub.a(x) has the same degree-T as the polynomial hiding .sup..sup.a as a secret. [0329] Step 2: [0330] Each computing node n, n{0, 1, . . . , N1} calculates a share from a degree-T polynomial r(x)=.sub.a=0.sup.A-1 r.sub.a(x):

[00059]$\begin{array}{cc}{\left[r\right]}_n=\underset{a=0}{\overset{A-1}{.Math.}}{\left[r_a\right]}_n& \mathrm{Eq}.5\end{array}$

[0331] This phase does not require any communication between the computing nodes since each node n can locally compute [r.sub.a].sub.n for each a{0, 1, . . . , A1}.

Phase 3Result Reconstruction

[0332] Each computing node n, n{0, 1, . . . , N1} sends their MLC share [r].sub.n of the result to the result nodes, which apply Lagrange interpolation to reconstruct the evaluation r(0) of polynomial r(x), which is equal to the output of the function we wanted to evaluate:

=r(0)ECC([r].sub.0,[r].sub.1, . . . ,[r].sub.N-1)Eq. 6b

[0333] [End of Algorithm: Active 1-MLC]

[0334] FIG. 5 is a flowchart of the message flows involved in Active 1-MLC. As it can be appreciated, the computation phase requires no message exchange among the computing nodes. The correctness proof is the same as for the protocol Active D-MLC.

[0335] Notice that in Step 4 in the First Execution of Phase 1 the Dealer Node is sending the shares {[.sub.a,m].sub.n}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1} the n-th MLC Computing Node, for n{0, . . . , N1}. This way, for fixed a, m, the Dealer Node may instruct the MLC Computing Nodes to send back v.sub.a,m, {[.sub.a,m].sub.n}.sub.n{0, . . . ,N-1} so that it can reconstruct .sub.a,m and recover its secret input s.sub.i.sub.a,m from the corresponding particle v.sub.a,m. However, the shares {[.sub.a,m].sub.n}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1} are not required by the MLC Computing Nodes to run the computation. For this reason, in an alternative implementation, the Dealer Node does not send the shares {[.sub.a,m].sub.n}.sub.a{0, . . . ,A1}.Math.m{0, . . . ,M.sub.a.sub.1} in Step 4.2 to save bandwidth at the cost of not being able to reconstruct the inputs to the computation.

Possible Implementations for STORE and LOAD

[0336] In one implementation, the functions STORE and LOAD work on the client's device. For example, in a web browser implementation, variables are stored in cookies, or in the browser local storage, or in a mobile application they are stored in the mobile app, including the possibility of storing them in a Trusted Execution Environment or Secure Enclave.

[0337] In another implementation, variables are stored in a centralized server or group of servers, including the possibility of storing them in a Secure Enclave like Intel's SGX and/or of using encryption.

[0338] In another implementation, variables are stored in a decentralized network. For example, they are encrypted with the client's private key and sent over to a decentralized storage network, or each one is transformed into shares using for example Shamir's Secret Sharing and sent over to different nodes in a decentralized storage network.

[0339] The skilled person will appreciate that the choice of where to store and load from, and the details of implementation of the Store and Load functionality, are not limiting to the method as described.

REFERENCES

[0340] [Cra15] Cramer, R., Damgrd, I., & Nielsen, J. (2015). Secure Multiparty Computation and Secret Sharing. Cambridge: Cambridge University Press. doi:10.1017/CB09781107337756 [0341] [Sch13] Thomas Schneider and Michael Zohner. GMW vs. Yao? E_cient secure two-Party computation with low depth circuits. In Ahmad-Reza Sadeghi, editor, Financial Cryptography and Data Security, pages 275{292, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. [0342] [Jak15] Thomas P. Jakobsen. Practical Aspects of Secure MultiParty Computation. PhD thesis, Department of Computer Science, Aarhus University, 2015. [0343] [Yao08] Yanjun Yao. Secure multiParty computation. In Graduate Seminar on Cryptography. University of Tartu, 2008. [0344] [GMW87] Goldreich, Oded & Micali, S. & Wigderson, Avi. (1987). How to play ANY mental game. 218-229. 10.1145/28395.28420. [0345] [BGW88] M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In the 20th STOC, pages 1-10, 1988 [0346] [BMR90] 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 [0347] [GESS09] Kolesnikov, V. 2005. Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation. In: Advances in CryptologyASIACRYPT 2005. Ed. by B. K. Roy. Vol. 3788. Lecture Notes in Computer Science. Springer, Heidelberg. 136-155 [0348] [Mann13] Mann, Sarah Edge. The Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithm. (2013). [0349] [SPDZ12] Damgrd I., Pastro V., Smart N., Zakarias S. (2012) Multiparty Computation from Somewhat Homomorphic Encryption. In: Safavi-Naini R., Canetti R. (eds) Advances in CryptologyCRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol 7417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32009-5_38