Patent Publication Number: US-2021167946-A1

Title: One-Round Secure Multiparty Computation of Arithmetic Streams and Evaluation of Functions

Description:
FIELD OF INVENTION 
     The present invention relates to the field of distributed computation. More specifically, the present invention relates to a system and method for performing secure multiparty computation of arithmetic streams and evaluation of functions in a single round of communication. 
     BACKGROUND OF THE INVENTION 
     Cloud services for storage and computing has significant benefits in price, speed, and manageability and therefore, became very popular. Companies like Amazon, Google, Microsoft, IBM, etc., are offering storage devices and computing engines to both private users and organizations. However, such services require users to send their information to an untrusted third party. In some cases, the information held by a user is confidential and the distribution of the information to untrusted parties should be avoided. 
     One existing solution to this problem may be a cryptographic scheme that enables a user to upload encrypted data to the cloud, perform computations in the cloud over the encrypted data and retrieve the encrypted version of the desired result, as shown in  FIG. 1  (prior art). Such an encryption scheme enables the user to take advantage of the storage and computing power provided by the cloud without compromising the confidentiality of the data. 
     Other existing solutions are Secure MultiParty Computation (SMPC) schemes over a distributed system, as shown in  FIG. 2  (prior art). These schemes are information-theoretically secure and support such computations at the cost of communication between participants. At each round of communication, each participant sends at most one message to each of the other participants, performs arbitrary computations and/or receives at most one message from each of the other participants (not necessarily in this order). Typically, communication between participants is used for reducing the degree of the polynomial that encrypts the data after each multiplication during the computation. 
     Other existing solutions are fully homomorphic encryption schemes, which suggest a centralized (rather than distributed) computationally secure solutions to the above mentioned problem. However, these solutions are only computationally secure (rather than information-theoretically secure) and are currently too slow to be used in practice. 
     Ben-Or, Goldwasser and Wigderson [BOGW88] showed that every function of N inputs can be efficiently computed by N participants with a threshold of N/2 in case of honest-but-curious participants, or N/3 in case of malicious participants. Their methods are based on Shamir&#39;s secret sharing scheme [Sha79] and their protocols require multiple rounds of communication, proportional to the depth of the arithmetic circuit. Substantial efforts have been spent to achieve a better communication complexity in such tasks. Bar-Ilan and Beaver [BIB89] were the first to suggest a way to evaluate functions in a constant number of rounds of communication, followed by further works that attempt to minimize communication complexity of SMPC protocols. Gennaro, Ishai, Kushilevitz and Rabin [GIKR02] proved that, in the presence of malicious participants, some functions do not admit SMPC protocols with less than three rounds of communication. Specifically, they have shown that the functions XOR 2   n  and AND 2   n  do not admit protocols of SMPC with only two rounds of communication, while assuming that malicious participants are present. Nonetheless, they have shown that functions that depend only on the inputs of a single participant can be securely computed in two rounds of communication. When relaxing the assumptions and considering honest-but-curious participants, the round complexity of general SMPC protocols is reduced to two rounds of communication [BOGW88,IK02]. 
     It is therefore an object of present invention to provide a method and system for performing secure multiparty computation of arithmetic streams and functions, which requires one-round of communication. 
     It is another object of the present invention to provide a method and system for performing secure multiparty computation of arithmetic streams and functions, without decrypting the secrets during the course of the computation. 
     It is a further object of the present invention to provide a method and system for performing secure multiparty computation of arithmetic streams and functions, which is information-theoretically secure with a threshold of all active participants. 
     It is still another object of the present invention to provide a method and system for performing secure multiparty computation of arithmetic streams and functions, which can support boolean circuits. 
     It is yet another object of the present invention to provide a method and system for performing secure multiparty computation of arithmetic streams and functions, which is not saved as plaintext anywhere and keeps the computation state of the stream secure at all times. 
     Other objects and advantages of this invention will become apparent as the description proceeds. 
     SUMMARY OF THE INVENTION 
     A method for performing, in a single round of communication and by a distributed computational system, Secure MultiParty Computation (SMPC) of an arithmetic function ƒ:   p   k →   p  represented as a multivariate polynomial over secret shares for a user, comprising the steps of:
         a. sharing secrets among participants being distributed computerized systems, using multiplicative shares, the product of which is the secret, or additive shares, that sum up to the secret by partitioning secrets to sums or products of random elements of the field;   b. implementing sequences of additions of secrets locally by addition of local shares or sequences of multiplications of secrets locally by multiplication of local shares; and   c. separately evaluating the monomials of ƒ by the participants; and   d. adding the monomials to obtain secret shares of ƒ.   In one aspect, two sets of participants are used by a dealer to securely outsource a computation of an arithmetic stream by:   a. providing a first set of participants consists of n 1  M.parties, that locally handle sequences of multiplications;   b. providing a second set consists of n 2  A.parties that locally handle sequences of additions;   c. switching from sequences of multiplications to sequences of additions and vice versa without decrypting the information;   d. eliminating the previous sets whenever there is a switch between sequences of multiplications to sequences of additions.       

     A method for performing, by a distributed computational system, Secure MultiParty Computation (SMPC) of a function ƒ:   k →  over k non-zero elements S=(s 1 , . . . , s k )∈   k , where the minimal multivariate polynomial representation of ƒ is 
       ƒ( x   1   , . . . ,x   k )=Σ l=(l     0     , . . . ,l     k     )∈     l   0   ·x   1   l     1      . . . x   k   l     k   , ={0,1, . . . } k+1  
         over secret shares for a user, comprising the steps of:   a. providing k non-zero elements S=(s 1 , . . . , s k )∈   k  of the user;   b. providing n honest-but-curious participants,    (1) , . . . ,    (n)  belonging to the distributed computational system and having a private connection channel with then honest-but-curious participants,    (1) , . . . ,    (n) ;   c. for s j , 1≤j≤k, performing mult.-random-split of s j  to multiplicative shares, m ij , such that s j =Π i=1   n  m ij ;   d. distributing m ij  to    (i) ;   e. evaluating the monomials of ƒ separately by the participants and adding the monomials to obtain secret shares of ƒ(s 1 , . . . , s k ), where for l∈ , the l&#39;th monomial is l 0 ·x 1   l     1    . . . x k   l     k   ; and   f. for each l, calculating additive shares such U i  of the l&#39;th monomial of ƒ evaluated on S, such that each participant    (i)  obtains such U i  for each of the monomials of ƒ.       

     A method for performing, by a distributed computational system, Secure MultiParty Computation (SMPC) of a p-bounded arithmetic function ƒ:   p   k →   p  over k elements S=(s 1 , . . . , s k )∈   p   k , where the minimal multivariate polynomial representation of ƒ is 
       ƒ( x   1   , . . . ,x   k )=Σ l=(l     0     , . . . ,l     k     )∈     l   0   ·x   1   l     1      . . . x   k   l     k   , ={0, . . . , p− 1} k+1  
         over secret shares for a user, comprising the steps of:   a. providing k elements S=(s 1 , . . . , s k )∈   p   k  of the user;   b. providing n honest-but-curious participants,    (1) , . . . ,    (n)  belonging to the distributed computational system and having a private connection channel with then honest-but-curious participants,    (1) , . . . ,    (n) ;   c. for s j , 1≤j≤k, performing mult.-random-split of s j  to multiplicative shares, m ij , such that s j =Π i=1   n  m ij ;   d. distributing m ij  to    (i) ;   e. evaluating the monomials of ƒ separately by the participants and adding the monomials to obtain secret shares of ƒ(s 1 , . . . , s k ), where for l∈ , the l&#39;th monomial is l 0 ·x 1   l     1    . . . x k   l     k   ; and   f. for each l, calculating additive shares such U i  of the l&#39;th monomial of ƒ evaluated on S, such that each participant    (i)  obtains such U, for each of the monomials of ƒ.       

     The l&#39;th monomial may be evaluated by:
         a. sending l to the participants;   b. performing matrix-random-split of 1 to C∈M n (   p ) according to the following steps:
           b.1) perform add.-random-split of 1∈   p  to γ 1 + . . . +γ n .   for 1≤i≤n:   b.2) choose uniformly at random n−1 non-zero elements of    p , c ij , for 1≤j≤n, j≠i;   b.3) set c ii =γ i /δ where δ=c i,1  . . . c i,j−1 ·c i,j+1  . . . c i,n ;   b.4) distribute to each    (i)  the i&#39;th column [C] i  of C., where C=(c ij ) i,j=1   n ∈M n (   p ).   b.5) each    (i)  computes the alpha vector α i  of participant    (i) ;   b.6) for 1≤i≤n, each of the participants sends the i&#39;th entry of the alpha vector, computed in the previous stage, to    (i) ; and   b.7) each of the participants multiplies the values received in the previous stage and computes:   
               

         U   i   =l   0 ·(α 1 ) i · . . . ·(α n ) i .
 
     In one aspect, the method further comprises the step of adding additive shares of two functions that ƒ 1  and ƒ 2  evaluated on S, held by the participants to obtain additive shares of ƒ 1 (S)+ƒ 2 (S). 
     In one aspect, the methods further comprises the step of calculating a linear combination if additive shares of an arbitrary number of functions ƒ 1 , . . . , ƒ d  evaluated on S, to obtain additive shares of ƒ 1 (S)+ƒ 2 (S)+ . . . +ƒ d (S). 
     The SMPC of the product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k    for a given l may be performed by generating a matrix-random-split of ƒ(S) using the additive shares of ƒ(S) held by the participants. 
     Additive shares of the product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k    may be held by the participants, by:
         a. allowing each participant    (i)  to perform mult.-random-split of γ i  to c i1 · . . . ·c in , where γ 1 , . . . , γ n  are the additive shares of ƒ(S) held by the participants at the end of the evaluation procedure and the c ij &#39;s constitute a matrix-random-split of ƒ(S);   b. allowing each participant    (i)  to distribute the multiplicative shares of its additive share of ƒ(S) to the other participants in a way that each participant    (i)  receives the i&#39;th column of C.       

     Switching from multiplicative shares of s to additive shares of s j  is implemented using evaluation to perform SMPC of the function ƒ(x 1 , . . . , x k )=s j  and switching from additive shares of s j  to multiplicative shares of s j  is implemented e for computing a product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k   . 
     In one aspect, some of the secret shares are zero. 
     The number of participants may be extended to n 1  M.parties+n 2  A.parties (n 1 , n 2 ≥2) by:
         a. taking n 1 −1 random non-zero elements of the field, x 1 , . . . , x n     1     −1 ; computing the x n     1    that yields ø i=1   n     1    x i =m; and   b. taking n 2 −1 random non-zero elements of the field, x 1 , . . . , x n     2     −1 ; computing the x n     2    that yields Σ i=1   n     2    x i =m.       

     Additive shares of the secret shared data may be produced from multiplicative shares of the secret shared data by shifting information from n 1  M.parties to n 2  A.parties according to the following steps:
         a. if n 1  M.parties,    (i) , 1≤i≤n 1 , hold n 1  multiplicative shares, x i , of an element m, to achieve n 2  additive shares of m held by n 2  A.parties, splitting x 1  to n 2  additive shares b j , 1≤j≤n 2  by    (1)  add.-random;   b. sending each b j  to the j&#39;th A.party;   c. sending x i  to each of the A.parties by the rest of the M.parties,    (i) , 2≤i≤n 1 ;   d. eliminating the M.parties;   e. multiplying the received values by the A.parties, to obtain additive shares of m.   where,       

         m=Π   i=1   n     1     x   i   =x   1 ·Π i=2   n     1     x   i =(Σ j=1   n     2     b   j )·Π i=2   n     1     x   i =Π i=1   n     2   ( b   j ·Π i=2   n     1     x   i ).
 
     Multiplicative shares of the secret shared data may be produced from additive shares of the secret shared data by shifting information from n 2  A.parties to n 1  M.parties according to the following steps:
         a. if n 2  A.parties,    (i) , 1≤i≤n 2 , hold n 2  additive shares, x i , of an element m, obtain n 1  multiplicative shares of m held by n 1  M.parties, splitting 1 to n 1  multiplicative shares by mult.-random;   b. sending n 1 −1 M.parties one (distinct) multiplicative share of 1;   c. sending the last share of 1 to all of the A.parties;   d. multiplying, by each of the A.parties, the multiplicative share of 1 received by its additive share of m;   e. sending the product to the last M.party;   f. eliminating the A.parties; and   g. adding the values received by the last M.party, such that the M.parties hold multiplicative shares of m.       

     Secure MultiParty Computation (SMPC) of Boolean circuits may be computed by working in    2 . 
     Secure MultiParty Computation (SMPC) of arithmetic functions over inputs held by k users    (1) , . . . ,    (k) , each of whom is holding a set of secret values in    p , may be performed by the following steps: 
     a. each of the users distributes shares of his secrets; 
     b. one of the users sends the relevant information to the other participants; 
     c. the participants send their outputs to all of the users; and 
     d. each of the users obtains the result of evaluating ƒ over the entire set of secrets by adding the outputs. 
     Arithmetic streams may be secured by performing, at each stage of computation, both addition and multiplication operations that yield the same result that are obtained by one of the operations. 
     If the information held by the user is m=(m 1 , . . . , m n )∈   p   n , an arithmetic function ƒ may be secured by the following steps:
         a. taking redundant copies of each (or some) of the m i &#39;s;   b. taking redundant variables that equal 1∈   p ,   c. taking redundant variables that equal 0∈   p ;   d. permute them all to obtain m′=(m′ 1 , . . . , m′ r ) which contains the information began with, along the added redundancy; and   e. evaluating ƒ:   p   n →   p  over m by taking a suitable ƒ′:    p   r →   p  and evaluating ƒ′ over m′ such that ƒ(m)=ƒ′(m′), where ƒ(m)= a i ·A i , a i ∈   p , and A i  is the i&#39;th monomial.       

     In one aspect, the method further comprises the step of detecting incorrect outputs caused by malicious participants by repeating the same computations while using different sets of participants. 
     In one aspect, the method further comprises the step of detecting incorrect outputs caused by malicious participants by computing different representations of the same function. 
     In one aspect, the method further comprises the step of detecting incorrect outputs caused by malicious participants by computing the same circuit several times using the same n participants with different randomization in each computation and different representations of the same circuit in each iteration. 
     Functions may be evaluated over inputs being held by all of the participant. 
     In one aspect, the user may be one of the participants. 
     A computerized system for performing, in a single round of communication and by a distributed computational system, Secure MultiParty Computation (SMPC) of an arithmetic function ƒ:   p   k →   p  represented as a multivariate polynomial over secret shares for a user, comprising:
         a. at least one processor, adapted to:
           a.1) share secrets among participants being distributed interconnected computerized systems, using multiplicative shares, the product of which is the secret, or additive shares, that sum up to the secret by partitioning secrets to sums or products of random elements of the field;   a.2) implementing sequences of additions of secrets locally by addition of local shares or sequences of multiplications of secrets locally by multiplication of local shares; and   a.3) evaluating the monomials of ƒ by the participants separately; and   a.4) add the monomials to obtain secret shares of ƒ; and   
           b. a plurality of private connection channels between each participant and the user, for securely exchanging encrypted data consisting of a combination of secret shares.       

    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       In the drawings: 
         FIG. 1  (prior art) shows a cryptographic scheme that enables a user to upload encrypted data to the cloud, perform computations in the cloud over the encrypted data and retrieve the encrypted version of the desired result; 
       as shown in  FIG. 2  (prior art) a Secure MultiParty Computation (SMPC) scheme over a distributed system; 
         FIG. 3  illustrates an example of performing multiplications by splitting the information between two parties    (1)  and    (2)  in multiplication mode, according to an embodiment of the invention; 
         FIG. 4  illustrates an example of switching from multiplication mode to addition mode, according to an embodiment of the invention; 
         FIG. 5  illustrates an example of performing additions by splitting the information between two parties    (1)  and    (2)  in addition mode, according to an embodiment of the invention; 
         FIG. 6  illustrates an example of switching from addition mode to multiplication mode, according to an embodiment of the invention; 
         FIG. 7  illustrates an example of a distribution protocol, which is invoked by the user to secret share m=(m 1 , . . . , m n )∈   p   n  amongst the M.parties; 
         FIG. 8  illustrates an example of Shifting from the M.parties to A.parties, while eliminating the M.parties, and the A.parties multiply the values received; 
         FIG. 9  illustrates an example of performing mult.-random-split of 1∈   p  to two multiplicative shares x m+1  and r, and sending x m+1  to    (1)  and r to the A.parties. Each of the A.parties multiplies r by u k , k=3,4, and sends the product to    (2) , while eliminating the A.parties; 
         FIG. 10  illustrates an example of distribution, where perform mult.-random-split of s j  to multiplicative shares, m ij  is performed, such that s j =Π i=1   n  m ij  and distribute m ij  to    (i) ; 
         FIG. 11  illustrates stages 2 and 3 of the evaluation process for each monomial; 
         FIG. 12  illustrates an example of distribution of information between millionaires wish to find out who of them is the wealthiest, while not revealing to each other the exact number of millions they possess; and 
         FIG. 13  illustrates a system for performing distribution for s j , 1≤j≤k, by performing mult.-random-split of s j  to multiplicative shares, m ij , among n participants    (1) , . . . ,    (n) . 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention proposes efficient Secure MultiParty Computation (SMPC) schemes over secret shares in scenarios in which the secrets are elements of a finite field    p , which are information-theoretically secure with a threshold of all active participants. Any function ƒ:   p   n →   p  is represented as a multivariate polynomial and the evaluation of ƒ is implemented in a single round of communication. The proposed SMPC schemes are based on partitioning secrets to sums or products of random elements of,    p . Secrets are shared using either multiplicative shares, the product of which is the secret, or additive shares, that sum up to the secret. Sequences of additions of secrets are implemented locally by addition of local shares, which require no communication among participants. Sequences of multiplications of secrets are implemented locally by multiplication of local shares, which require no communication among participants. The shift to handle a sequence of additions from the execution of multiplications or vice versa is efficiently handled as well, with no need to decrypt the secrets in the course of the computation. The proposed schemes can also be used to support SMPC of boolean circuits (that perform boolean commutation, rather than arithmetic). 
     The present invention proposes several schemes for information-theoretically SMPC of arithmetic streams and for evaluation of arithmetic functions in a single round of communication. 
     In a first exemplary schemes for SMPC of arithmetic streams, two sets of participants are used by a dealer to securely outsource a computation of an arithmetic stream. The first set of participants consists of n 1  M.parties, that locally handle sequences of multiplications, and the second set consists of n 2  A.parties that locally handle sequences of additions. Switching from sequences of multiplications to sequences of additions and vice versa are made without decrypting the information. These schemes require the user to perform, practically, as much computational work as he would have needed to if computing the arithmetic stream on his hardware. The main purpose of these schemes is to keep the computation state of the stream secure at all time, not saved as plaintext anywhere. 
     These schemes are composed of (a) two procedures that enable computations in each mode; (b) two procedures that are used to switch between modes. These procedures give rise to SMPC schemes for evaluation of arithmetic functions in one round of communication. Since over finite fields every function may be written as a polynomial, these procedures may be used to outsource storage of information to untrusted participants (honest-but-curious) while allowing outsourcing of computations over the distributed data. 
     These schemes use two sets of participants and require the elimination of the previous set whenever there is a switch between modes. That need for ongoing elimination of participants is solved by presenting schemes for SMPC of arithmetic functions using one set of n participants for both operations. This solution costs in communication complexity in the following way. In the schemes proposed for stream computation and for SMPC of arithmetic functions in one round of communication, the procedures M→A and SMA require sending a total of n 1 ·n 2  messages between the participants. The procedures A→M or Cascading require sending a total amount of 2n 2 +n 1 −1 messages between the participants. 
     In the schemes for handling both operations by the same participants, in each round of communication the number of messages sent between participants is n 2 . 
     The present invention proposes two pairs of schemes for outsourcing arithmetic computations in a finite field,    p . The first pair of schemes assumes that the computation state or the distributed values are non-vanishing in the field. The second pair of schemes solves the case where the mentioned values may vanish in    p  by embedding    p  in    q  (for large enough q). Such a q always exists. However, for some functions/streams, the resulting scheme is impractical since q is too large to work with. The schemes for the non-vanishing case are practical whenever the polynomial representation of the function is not too large to work with. 
     The proposed schemes allow evaluation of any arithmetic function in exactly one round of communication, assuming that the participants are honest-but-curious. This approach is based on representing each secret either as a sum of secret shares or as a product of secret shares, while shifting between representations when necessary. In schemes that use two sets of participants, at each stage, only one of the sets holds shares of the secrets. The participants in the first set handle multiplications and are called the multiplication participants, or the M.parties. The participants in the second set handle additions and are called the addition participants, or the A.parties. 
     The operations of the participants in a sequence of the same operation and the communication between them when there is a switch in operations and the immediate elimination of the previous participants (virtual machines, containers, etc.), are described. These schemes require communication among participants only when switching between operations, and support communicationless sequences of multiplications followed by communicationless sequences of additions and vice versa. These schemes are information-theoretically secure against attacks of coalitions that consist of all-but-one of the active participants. 
     The main ideas used to construct these two-set schemes give rise to a scheme that uses only one set of participants and allows evaluation of arithmetic functions in one round of communication. 
     Example of Stream Computation 
     a user receives a stream of values and arithmetic operations produced by some source and wishes to perform an arithmetic computation over the values received according to the operations received on the fly. The stream begins with an initial value, denoted by m 0 . At this stage, the user sets a value, referred to as the computation state and denoted by st, and initializes st as m 0 . Afterward, at each stage, a pair of value and arithmetic operation are produced by the source and received by the user, who in turn updates the computation state st accordingly. Explicitly, at stage i (for i≥1) a pair, consisting of a value m, and arithmetic operation op i  are produced, where op i  is either addition ‘+’ or multiplication ‘·’. The user updates the state either by multiplying st by m i  or by adding m i  to st, according to op i . Namely, st:=st op i  m i . 
     It is assumed that the values received from the source are confidential, and so is the computation state that they yield at each stage. The user cannot keep (and update) st on his hardware, since it might be hacked by an adversary. Therefore, the desired cryptographic scheme is a cryptographic scheme that will allow the user to outsource the aforementioned computation, while keeping the values m, and st information-theoretically secure at all stages, without keeping st as plaintext at any stage. The value m, should also be eliminated at the end of each stage. The user should be able to retrieve st at any desired time. 
     Usually, outsourcing of computation considers a user that wishes to use a remote strong computer to run a computation over private data, where the main reason for outsourcing the computation is computing power. One of the main interests in such scenarios is to involve the user in the computation as little as possible and to shift most of the computational tasks to the cloud. Since the values are produced by the source and received by the user on-the-fly, the user must be on-line during the computation and take an active part in the computation. It is assumed that the user does have enough computing power to run the computation, but since the values and the computation state produced during computation are confidential, the user cannot save them as plaintext anywhere. 
     Schemes for Outsourcing Stream Computations 
     Scheme 1: A Non-Vanishing Stream 
     This scheme performs secure outsourcing of stream computation under the following assumptions. For the particular example detailed in the sequel, it is assumed that the values m i  are elements of the field    p  of prime order p (in which the arithmetic operations are carried out), and that the values and operations produced never yield st=0. Such a stream is non-vanishing. It is assumed that the user has a secure connection channel with (at least) four honest-but-curious (Honest-but-curious means that all parties follow the protocol honestly, and a protocol is private if any parties who collude at the end of the protocol learn nothing beyond their own outputs from their transcripts) servers denoted    (j)  (for 1≤j≤4). The basic four participants scheme can be generalized to one with a larger number of participants. The scheme for the case of four participants is first presented. In this proposed scheme, some of the participants hold shares of the computation state st, denoted by st (j) . The shares do not reveal any information about st and enable extrapolation of st by the user at any stage. 
     The proposed scheme has two modes: multiplication mode and addition mode.    (1)  and    (2)  are the M.parties and the rest of the servers are the A.parties. The proposed scheme is consists of five procedures as follows:
         Init—Initializing.   MinM—Multiplication in multiplication mode.   M→A—Switching mode from multiplication to addition.   AinA—Addition in addition mode.   A→M—Switching mode from addition to multiplication.       

     The general idea behind the scheme is that multiplications are handled by the M.parties and additions by the A.parties. At stage i, some of the procedures are invoked to update st according to op i  and shift (if necessary) the shares from one set of participants to another, while eliminating the previous set of participants. When the shares of st are being held by the M.parties (respectively, A.parties), it is determined that the scheme is in multiplication (respectively, addition) mode. When the shares of st are being held by the A.parties, it is determined that the scheme is in addition mode. 
     The scheme stages are as follows:
         Run Init—distributing (multiplicative) shares of m 0  to    (1)  and    (2) .   At stage i, upon receiving (m i , op i ):
           If the received operation op i  does not match the current mode (i.e., receiving op i =‘·’ in addition mode or op i =‘+’ in multiplication mode), then run M→A or A→M to switch mode and eliminate the previous set of participants.   Run AinA or MinM to update the shares of st according to (m i , op i ).   
               

     All operations are carried out in    p . 
     Procedure 1: Init—Initializing 
     This procedure (called mult.-random-split of an element of    p   x  into two multiplicative shares) is invoked by the user and the M.parties only at stage zero, when the initial value m 0  is produced and received by the user. At the first step, the user picks a non-zero element x 0  of    p  uniformly at random and computes y 0 , such that x 0 ·y 0 =m 0 . At the next step, the user sends x 0  to    (1)  and y 0  to    (2) , who in turn set st (1)  to x 0  and st (2)  to y 0 , respectively. The values st (1)  and st (2) , kept by the M.parties after the execution of this protocol, are their shares of st. Since x 0  is picked randomly, y 0  is also random. Hence, no information concerning m 0  is revealed to the M.parties. 
     Procedure 2: MinM—Multiplication in Multiplication Mode 
     This procedure is invoked by the user and the M.parties at stages i such that op i  is multiplication (after switching to multiplication mode if necessary, using A→M). As described in  FIG. 3 , and similarly to Init, first the user mult.-random-splits m i  to x·y. Then the user sends x to    (1)  and y to    (2) . The M.parties in turn update the shares of st they hold.    (1)  sets st (1)  to st (1) ·x and    (2)  sets st (2)  to st (2) ·y. Now, the shares of the M.parties are updated according to the current computation state. The fact that x and y are random implies that no information is revealed to the participants neither about m, nor about st. 
     Procedure 3: M→A—Switching Mode from Multiplication to Addition 
     This procedure (called add.-random-split of an element of    p  into two additive shares, a and b) is invoked by all the participants at stages i such that op i  is addition and the current mode is multiplication: First,    (1)  picks an element a of    p  and computes b such that a+b=st (1) . Then, as described in  FIG. 4 ,    (1)  sends a to    (3)  and b to    (4) , while    (2)  sends st (2)  to both    (3)  and    (4) . At this stage the M.parties are eliminated. Then, the A.parties multiply the values they received and set st (j)  (j=3,4) to the appropriate products. 
     In this case: 
         st=st   (1)   ·st   (2) =( a+b )· st   (2)   =a·st   (2)   +b·st   (2)   =st   (3)   +st   (4) .
 
     Namely, from the two mult.-random-split shares of st that were held by the M.parties, the A.parties receive add.-random-split shares of st. Since a and b are random elements of the field, the A.parties gain no information about st and the M.parties are eliminated. 
     Procedure 4: AinA —Adding in Addition Mode 
     This procedure is invoked by the user and the A.parties at stages i such that op i  is addition (after switching to addition mode if necessary, using M→A). As described in  FIG. 5 , the user add.random-splits m i  to x+y and sends x to    (3)  and y to    (4) . Then, in order to update its share of the computation state, each A.party adds the value it received from the user to st (j) , (j=3,4). Since x and y are random elements of the field, neither of the A.parties gain any information about m i  or about the current state. 
     Procedure 5: A→M—Switching Mode from Addition to Multiplication. 
     This procedure is invoked by the user and all the participants at stages i such that op i  is multiplication and the current mode is addition. As described in  FIG. 6 , the user mult.-random-splits 1∈   p  to r·r −1 , and sends r −1  to    (1)  and r to the A.parties. Then,    (1)  sets st (1)  to r −1 . Each of the A.parties,    (j) , (j=3,4), multiplies r by st (j)  and sends the product to    (2) . At this stage the A.parties are eliminated. Then    (2)  adds the values received and sets st (2)  to the sum. 
     In this case, 
         st=st   (3)   +st   (4)   =r   −1 ·( r ·( st   (3)   +st   (4) ))= r   −1 ·( r·st   (3)   +r·st   (4) )= st   (1)   ·st   (2) .
 
     Thus, from the two add.-random-split shares of st that were held by the A.parties, the M.parties receive mult.-random-split shares of st. At this stage,    (1)  obviously has no information about st. Since st≠0 and r is random,  ( 2 ) also has no information about the current state. 
     At any stage of the scheme:
         The computation state is not saved as plaintext anywhere.   Whenever a value m i ∈   p  is received by the user, she immediately random-splits it, eliminates it and distributes its shares.   None of the participants gains any information about the values m, or st.   The user can retrieve the shares of st from the participants and efficiently compute st.       

     This scheme allows a user to perform information-theoretically secure outsourcing of any non-vanishing stream using four participants. 
     Scheme 2: A Bounded Stream 
     In the scheme proposed for a Non-vanishing stream, the depth and length of the arithmetic circuit are practically unbounded. This fact can be used to outsource arbitrarily long computation streams, containing any number of multiplications and additions in    p . There is a constraint, though, on the possible result of each stage of the computation. Namely, none of them may be zero. In some cases, one has a computation stream that does not meet this limitation. 
     According to an embodiment of the invention, it is possible to outsource stream computations that may vanish by assuming that the depth and length of the stream are bounded. The proposed scheme is based on the non-vanishing scheme. Similarly to the assumptions of the non-vanishing scheme, it is assumed that the values m, are elements of a finite field    q  (q is prime), and that the arithmetic operations are multiplication and addition in    q . 
     Assuming that M=(m 0 , m 1 , . . . , m n )∈   q   n+1  is a sequence of values produced by a source in some stream computation, and that OP=(op 1 , . . . , op n )∈{‘+’,‘·’} n  is the sequence of operations produced by it corresponding to M, at each stage of the computation, the computation state st is the result of applying the operations in OP to the corresponding values in M, where operations are carried out in    q . One gets the exact same result by performing the computation over the positive integers and taking the result modulo q. Formally, for each entry m i  of M, let a i ∈{1, 2, . . . , q}⊆  denote the minimal positive integer such that a i ≡m i (mod q). The a i &#39;s are the integer correspondents of the m i &#39;s. Then, by performing the stream computation over the a i &#39;s (while using the same operations over the integers), an integer result st     is obtained, such that s ≡st(mod q). Assuming a computation stream over elements in    q  is such that, when performing the corresponding stream computation over the integers, an integer-computation state, s , that never exceeds a large prime p is obtained. Such a computation stream is called p-bounded. 
     The following scheme is proposed to perform information-theoretically secure outsourcing of a p-bounded computation stream. As in the non-vanishing scheme, it is assumed that the user has a secure connection channel with four honest-but-curious participants    (j)  (1≤j≤4). The general idea behind the scheme is to run at each stage the procedures described above over the integer correspondents of the m i &#39;s, modulo p, where operations are carried in    p . 
     The scheme stages are:
         Upon receiving the initial value m 0 ∈   q , run Init to distribute multiplicative shares of a 0 (mod p) to    (1)  and    (2) , where a 0  is the integer correspondent of m 0 .   At stage i, upon receiving m i ∈   q  and an operation op i :
           If op i  does not match the current mode, then run M→A or A→M to switch mode eliminating the M.parties or the A.parties.   Run MinM or AinA to update the computation state shares according to a i (mod p) and op i .   
               

     The user can extrapolate st∈   q  at any stage by retrieving the shares from the participants, computing the computation state modulo p, and then taking the integer correspondent to the result modulo q. The correctness of the scheme is derived from the fact that the stream is p-bounded. The security of this scheme for p-bounded streams is derived from the security of the non-vanishing stream scheme, since from the participants perspective, there is no difference between the cases. 
     SMPC of Arithmetic Functions in One Round of Communication 
     The solutions used to outsource stream computations, give rise to SMPC schemes that allow evaluation of arithmetic functions in one round of communication. The present invention propose schemes that support this task in two different cases: the non-vanishing case and the p-bounded case. In the proposed schemes st, the set of variables over which the function is evaluated may be dynamic, and so may be the function itself. 
     One-Round SMPC of Arithmetic Functions Over Non-Zero Elements 
     The present invention proposes an SMPC scheme that allows a user to securely outsource storage and computations of data under the following assumptions.
         The user holds a sequence m=(m 1 , . . . , m n )∈   p   n .   The user has a private connection channel with four participants    (k) , (1≤k≤4). As in the arithmetic streams scenario, this scheme can be generalized to one with a larger number of participants.   The participants are honest-but-curious.       

     At each stage of the proposed scheme, the participants hold shares of m. This proposed enables a user to secret share m=(m 1 , . . . , m n ) amongst honest-but-curious servers in a way that allows the user to evaluate ƒ(m) using computing engines provided by the servers, where ƒ:   p   n →   p . 
     Since    p  is a finite field, any function ƒ:   p   n →   p  can be represented as a multivariate polynomial. The fact that x p ≡x(mod p) implies that this representation is not unique (generally, there are infinitely many polynomials of n variables and only a finite number of functions ƒ:   p   n →   p ). Given a function ƒ, it is desired to assign ƒ with a minimal multivariate polynomial representation of it. To this end, a representation of ƒ as a multivariate polynomial such that the degree of each variable is at most p−1 is used. For any given ƒ there is exactly one such multivariate polynomial denoted by Q ƒ  and ƒ is assigned with Q ƒ  as its minimal multivariate polynomial representation. 
     The total degree 1  of Q ƒ  (The total degree of a multivariate polynomial is the maximal sum of exponents in a single monomial of it) is at most n(p−1) and write 
       ƒ( m )=   a   i   ·m   2   i     1      . . . m   n   i     n   ,
 
     where  ={0, . . . , p−1} n  and a i ∈   p . There are p p     n    such functions. For example, if n=6, p=11, then one of these functions is 3m 1   3 m 2   3 m 5 +6m 3   4 m 1 +2m 3 m 6 . The fact that each variable in each monomial can appear with any exponent between 0 and p−1 implies that there are p n  different monomials. For most functions ƒ used in practice, most of the monomials are irrelevant since they have leading coefficient 0. Nevertheless, in general the number of monomials in the representation of ƒ as a multivariate polynomial is exponential in n. For i=(i 1 , . . . , i n )∈ , the monomial function m 1   i     1    . . . m n   i     n    is denoted by A i , where A i  is the i&#39;th monomial. 
     The proposed scheme consists of two protocols:
         The Distribution protocol—invoked by the user to secret share m amongst the participants.   The Evaluation protocol—invoked by the user to perform SMPC of a function ƒ over m using the participants.       

     As in the arithmetic stream schemes presented above,    (1)  and    (2)  are the M.parties and    (3)  and    (4)  are the A.parties. In the distribution protocol, the user secret shares m amongst the M.parties. The Evaluation protocol is composed of four stages: 
     At the first stage, the user sends information regarding ƒ to the participants, and the M.parties perform operations over their shares of m that correspond to SMPC of each of the (non-zero leading coefficient) monomials A i  of ƒ. 
     At the second stage, the M.parties send to the A.parties information that allows the A.parties to achieve additive shares of each of the monomials of ƒ. At this point the M.parties are eliminated. 
     At the third stage, the A.parties use the information they received from the M.parties to achieve shares of ƒ(m). 
     At the fourth stage, the user can choose between either retrieving the shares of ƒ(m) from the A.parties and computing ƒ(m), or shifting the information from the A.parties to a new set of M.parties (as in A→M) to allow further computations over (m, ƒ(m)) without decrypting ƒ(m). 
     The Distribution Protocol 
     This Distribution protocol is invoked by the user to secret share m=(m 1 , . . . , m n )∈   p   n  amongst the M.parties. For each m j , 1≤j≤n, as described in  FIG. 7 , the user mult.-random-splits m j  to a product of multiplicative shares x j ·y j . Then, the user distributes (x 1 , . . . , x n ) to    (1)  and (y 1 , . . . , y n ) to    (2) . 
     The Evaluation Protocol 
     This protocol is invoked by the user to perform SMPC of a function ƒ over m using the participants. The protocol has four stages. 
     Stage 1—MonEv—Monomial evaluation 
     At this stage, the user sends information about ƒ to the participants. The M.parties compute multiplicative shares of the monomials of ƒ. ƒ can be writ in the form ƒ the/monomials 
       ƒ( m   1   , . . . ,m   n )=   a   i   ·A   i ,
 
     where A i  is the i&#39;th monomial and is determined by i=(i 1 , . . . , i n ). At this stage, for each monomial A i  with non-zero leading coefficient, the user sends i∈  to the M.parties and a i ∈   p  to the A.parties. Each of the M.parties evaluates each monomial A i  over his shares.    (1)  sets A x     i   : =Π j=1   n x j   i     j    and    (2)  sets A y     i   :=Π j=1   n y j   i     j   . A x     i    and A y     i    are multiplicative shares of A i  evaluated at m: 
         A   x     i     ·A   y     i   =Π j=1   n   x   j   i     j   ·Π j=1   n   y   j   i     j   =Π j=1   n ( x   j   y   j ) i     j   =Π j=1   n   m   j   i     j     =A   i .
 
     Stage 2—SMA—Shift from M.parties to A.parties 
     At this stage, for each i received from the user, the M.parties manipulate the multiplicative shares of A x     i    and A y     i    and send information to the A.parties that enables the A.parties to achieve additive shares of A i . For each i received, as described in  FIG. 8 ,    (1)  add.-random-splits A x     i    into a sum of two additive shares b i +c i  in    p . Then,    (1)  sends b i  to    (3)  and c i  to    (4) , while    (2)  sends A y     i    to the A.parties. The M.parties are now eliminated and the A.parties multiply the values received. Denote the products calculated by    (3)  and    (4)  by α i  and β i , respectively. 
     The multiplicative shares of A i  that were held by the M.parties, the A.parties achieve additive shares of A i : 
         A   i   =A   x     i     ·A   y     i   =( b   i   +c   i )· A   y     i     =b   i   ·A   y     i     +c   i   ·A   y     i   =α i +β i .
 
     Since a i  and b i  are random, the A.parties gain no information about A i .
 
Stage 3—fEv—Evaluation of ƒ
 
     At this stage the A.parties compute additive shares of ƒ(m) using the information received from the user at stage 1 and the additive shares of A i  obtained at stage 2.
             (3)  computes u 3 : = a i ·α i .       (4)  computes u 4 : = a i ·β i .   Observe that u 3  and u 4  are additive shares of ƒ(m):       

         u   3   +u   4   =Σ     a   i ·α i   +     a   i ·β i   =     a   i ·(α i +β i )=   a   i   ·A   i =ƒ( m ).
 
     Stage 4—RetCas—Retrieving/Cascading 
     At this stage, the user has a choice between two options: retrieving and cascading. In the retrieving option, the user retrieves the additive shares of ƒ(m) from the A.parties and adds them to obtain ƒ(m). In the cascading option, the user has the A.parties manipulate the shares they hold and send information to a new set of M.parties (in the same fashion as in procedure A→M described above). Then the A.parties are eliminated and the user may begin a new computation over (m 1 , . . . , m n , ƒ(m)). 
     The Cascading Option: 
     As described in  FIG. 9 , the user performs mult.-random-split of 1∈ F p  to two multiplicative shares x m+1  and r, and sends x m+1  to    (1)  and r to the A.parties. Each of the A.parties multiplies r by u k , k=3,4, and sends the product to    (2) . At this stage, the A.parties are eliminated. Now    (2)  adds the values received and sets y m+1  to the sum. 
       ƒ( m )= u   3   +u   4   =x   m+1 ·( r ·( u   3   +u   4 ))= x   m+1   ·y   m+1 .
 
     Thus, from the additive shares of ƒ(m) that were held by the A.parties, the M.parties obtain multiplicative shares of ƒ(m), and further functions can be evaluated over (m 1 , . . . , m n , ƒ(m)) by the user and the participants using stages 1-3 of this protocol. This option is secure only if ƒ(m)≠0, since if ƒ(m) vanishes, then so does y m+1 . 
     Since each m j  is secret shared independently, the set of secrets over which any function can be evaluated is dynamic and further secrets can be shared on the fly. The fact that each monomial is evaluated over the secret shares independently implies that the function itself is dynamic in the sense that new monomials can be evaluated and added on the fly. 
     One-Round SMPC of p-Bounded Arithmetic Functions 
     In the scenario considered above, SMPC of arithmetic functions over non-zero elements, there is a limitation on the possible values that the m j &#39;s may take. Namely, they cannot be zero. Moreover, if the user wishes to perform further computations over (m, ƒ(m)) without first decrypting ƒ(m), then ƒ(m) must be non-zero, as well. 
     It is possible to avoid these limitations over the m j &#39;s and ƒ(m). In a possible scenario, in which some of the m j &#39;s may be zero and ƒ may vanish, the present invention proposes a scheme that overcomes the limitations of the previous scenario assuming ƒ is p-bounded for small enough p. The term p-bounded is defined below. 
     Similarly to the assumptions of the previous scenario, it is assumed that the values m j  are elements of a finite field of prime order q, denoted    q . 
     It is assumed that the user holds m=(m 1 , . . . , m n )∈   q   n  and wishes to evaluate ƒ(m) for some ƒ. It is possible to compute ƒ(m) by performing operations in    q  on m according to a representation of ƒ as a multivariate polynomial. The same result is obtained if one computes ƒ(m) over the positive integers and then takes the result modulo q. Formally, for each entry m j  of m let a j ∈{1, 2, . . . , q}⊆  denote the minimal positive integer such that a j ≡m j (mod q). Then, by performing the computation over the a j &#39;s using integer operations, an integer result ƒ  is obtained, such that ƒ ≡ƒ(m)(mod q). A function ƒ:   q   n →   q  is p-bounded (considering the minimal multivariate polynomial representation of ƒ, actually, all functions ƒ:   q   n →   q  are p-bounded for p≥q nq+1 . This fact is not useful for large p) such that for every m∈   q   n , computation of ƒ(m) over the integers yields an integer result, ƒ , which is strictly smaller than a large prime p. 
     The proposed scheme is based on that suggested in the previous case for non-zero elements and enables SMPC of p-bounded functions over elements, some of which may be zero. As in the non-zero scheme, it is assumed that the user has a secure connection channel with four honest-but-curious servers,    (k) , 1≤k≤4. The general idea behind the scheme is to run at each stage the same procedures as in the scheme suggested in the previous case, over the integer correspondents of the m j &#39;s modulo p. 
     The scheme stages are as follows: 
     For m=(m 1 , . . . , m n )∈   q   n , let {tilde over (m)}=({tilde over (m)} 1 , . . . , {tilde over (m)} n )∈   p   n  denote the element of    p   n  corresponding to m. That is, {tilde over (m)} j :=a j (mod q) for 1≤j≤n. Similarly, for ƒ:   q   n →   q , let {tilde over (ƒ)}:   p   n →   p  denote the function corresponding to ƒ in the p-world. The Distribution and Evaluation protocols are as follows: 
     Distribution 
     For m∈   q   n  use the Distribution protocol of the non-zero scheme to secret share {tilde over (m)}∈   p   n  among the M.parties. 
     Evaluation 
     For ƒ:   q   n →   q  use the Evaluation protocol of the non-zero scheme to evaluate {tilde over (ƒ)} over {tilde over (m)}:
         The first three stages are the same as in the non-zero protocol.   At the fourth stage, RetCas:
           Decryption is done by retrieving {tilde over (ƒ)}({tilde over (m)}) by the dealer and taking the integer corresponding to {tilde over (ƒ)}({tilde over (m)}) modulo q.   Cascading (performing further computations over (m 1 , . . . , m n , ƒ(m)) without first decrypting ƒ(m)) can be done under the following assumptions. Assume the user wishes to perform SMPC of g:    q   n+1 →   q  over (m 1 , . . . , m n , ƒ(m)). Use Q ƒ  to write gas a function from    q   m  to    q . If g is p-bounded considering its representation as a multivariate polynomial obtained by using Q ƒ  to write g as a function from    q   m  to    q , then SMPC of g over (m 1 , . . . , m n , ƒ(m)) can be done with no need to first decrypt ƒ(m) by the user.   
               

     This protocol has the same dynamic attributes as those suggested in the previous scenario and it requires a single round of communication. 
     The schemes presented above are perfectly secure against attacks of coalitions, smaller than the number of currently active participants. 
     Handling Both Operations by the Same Participants 
     It is possible to perform SMPC of arithmetic functions over secret shares using the same set of participants for both operations. 
     A Scheme for the Non-Vanishing Case: 
     Similarly to the scenarios mentioned above, SMPC of arithmetic functions over secret shares, some of which may be zero, can be performed assuming the function is p-bounded. It is assumed that a user, holding k non-zero elements S=(s 1 , . . . , s k )∈   p   k , has a private connection channel with n honest-but-curious participants,    (1) , . . . ,    (n) . 
     Distribution: 
     For s j , 1≤j≤k, perform mutt.-random-split of s j  to multiplicative shares, m ij , such that s j =Π i=1   n  m ij  and distribute m ij  to    (i) . This is illustrated in  FIG. 10 . 
     Evaluation: 
     Assuming a user that wishes to perform SMPC of a function ƒ:   p   k →   p  over S, where the minimal multivariate polynomial representation of ƒ is 
       ƒ( x   1   , . . . ,x   k )=Σ l=(l     0     , . . . ,l     k     )∈     l   0   ·x   1   l     1      . . . x   k   l     k    
 
     and  ={0, . . . , p−1} k+1 . In the this procedure, the monomials of ƒ are evaluated by the participants separately and then added to obtain secret shares of ƒ(s 1 , . . . , s k ). For l∈ , the l&#39;th monomial is l 0 ·x 1   l     1    . . . x k   l     k   . To evaluate the l&#39;th monomial:
         1. Send l to the participants.   2. Perform matrix-random-split of 1 to C∈M n (   p ):
           (a) Perform add.-random-split of 1∈   p  to γ 1 + . . . +γ n .   (b) For 1≤i≤n:
               i. Choose uniformly at random n−1 non-zero elements of    p , c ij , for 1≤j≤n, j≠i. Denote δ=c i,1  . . . c i,j−1 ·c i,j+1  . . . c i,n .   ii. Set c ii =γ i /δ.   
               (c) Denote C=(c ij ) i,j=1   n ∈M n (   p ).   
           3. Distribute to each    (i)  the i&#39;th column [C] i  of C.   4. Each    (i)  computes:       

       α i : =(Π j=1   k   m   ij   l     j   )·[ C ] i .
 
     α i  is    (i) &#39;s alpha vector.
         5. For 1≤i≤n, each of the participants sends the i&#39;th entry of the alpha vector, computed in the previous stage, to    (i) .   6. Each of the participants multiplies the values received in the previous stage and computes:       

         U   i   =l   0 ·(α 1 ) i · . . . ·(α n ) i .
 
     For each l, the U i &#39;s obtained by the participants at stage 6 of the evaluation protocol are additive shares of the l&#39;th monomial of ƒ evaluated on S. One has 
     
       
         
           
             
               
                 
                   
                     U 
                     i 
                   
                   = 
                   
                     
                       
                         l 
                         0 
                       
                       · 
                       
                         
                           ( 
                           
                             α 
                             1 
                           
                           ) 
                         
                         i 
                       
                       · 
                       … 
                       · 
                       
                         
                           ( 
                           
                             α 
                             n 
                           
                           ) 
                         
                         i 
                       
                     
                     = 
                     
                       
                         l 
                         0 
                       
                       · 
                       
                         ( 
                         
                           
                             c 
                             
                               i 
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           · 
                           
                             
                               ∏ 
                               
                                 j 
                                 = 
                                 1 
                               
                               k 
                             
                              
                             
                                 
                             
                              
                             
                               m 
                               
                                 1 
                                  
                                 j 
                               
                               
                                 l 
                                 j 
                               
                             
                           
                         
                         ) 
                       
                       · 
                       … 
                       · 
                       
                         ( 
                         
                           
                             c 
                             in 
                           
                           · 
                           
                             
                               ∏ 
                               
                                 j 
                                 = 
                                 1 
                               
                               k 
                             
                              
                             
                                 
                             
                              
                             
                               m 
                               nj 
                               
                                 l 
                                 j 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         l 
                         0 
                       
                       · 
                       
                         ( 
                         
                           
                             c 
                             
                               i 
                                
                               
                                   
                               
                                
                               1 
                             
                           
                           · 
                           … 
                           · 
                           
                             c 
                             in 
                           
                         
                         ) 
                       
                       · 
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           
                             ( 
                             
                               
                                 ∏ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 n 
                               
                                
                               
                                   
                               
                                
                               
                                 m 
                                 ij 
                               
                             
                             ) 
                           
                           
                             l 
                             j 
                           
                         
                       
                     
                     = 
                     
                       
                         l 
                         0 
                       
                       · 
                       
                         γ 
                         i 
                       
                       · 
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           
                             s 
                             j 
                             lj 
                           
                           . 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             Hence 
             , 
             
               
 
             
              
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                     
                 
                  
                 
                   U 
                   i 
                 
               
               = 
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     n 
                   
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         l 
                         0 
                       
                       · 
                       
                         γ 
                         i 
                       
                       · 
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             1 
                           
                           k 
                         
                          
                         
                             
                         
                          
                         
                           s 
                           j 
                           lj 
                         
                       
                     
                     ) 
                   
                 
                 = 
                 
                   
                     l 
                     0 
                   
                   · 
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         1 
                       
                       k 
                     
                      
                     
                         
                     
                      
                     
                       
                         s 
                         j 
                         lj 
                       
                       · 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                             
                         
                          
                         
                           
                             γ 
                             i 
                           
                           . 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Since Σ i=1   n  γ i =1, the sum of the U i &#39;s equals to the l&#39;th monomial of ƒ evaluated on S. 
     Now, following the procedure described above, each participant    (i)  obtains such U i  for each of the monomials of ƒ. Denote by U i   (l)  the U i  obtained by    (i)  regarding the l&#39;th monomial of ƒ. Adding the U i   (l) &#39;s, the i&#39;th participant obtains an additive share of ƒ evaluated on S. These shares can be used to perform consecutive computations in the following way: 
     Assuming that ƒ 1  and ƒ 2  are two functions evaluated on S as suggested above, the additive shares of ƒ 1 (S) and ƒ 2 (S) held by the participants can be added by the participants to obtain additive shares of ƒ 1 (S)+ƒ 2 (S). The same holds for a linear combination of an arbitrary number of functions ƒ 1 , . . . , ƒ d  evaluated on S. 
     SMPC of the product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k    for given l can be performed by generating a matrix-random-split of ƒ(S) using the additive shares of ƒ(S) held by the participants. Denote by γ 1 , . . . , γ n  the additive shares of ƒ(S) held by the participants at the end of the evaluation procedure. Similarly to stage 2 of it, each participant    (i)  performs mult.-random-split of γ i  to c i1 · . . . ·c in . The c ij &#39;s constitute a matrix-random-split of ƒ(S). Each participant distributes the multiplicative shares of its additive share of ƒ(S) to the other participants in a way that each participant    (i)  receives the i&#39;th column of C. Now, SMPC of the product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k    can be performed following stages 4-6 of Evaluation. In the end of which, additive shares of the product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k    are held by the participants. 
     The procedures described above allow SMPC of arithmetic functions over secret shares in one round of communication using one set of participants. A variation of these procedures allows SMPC of arithmetic streams using one set of participants. The procedures MinM and AinA, described in Section 2, are implemented in the same way in this case. Switching from multiplicative shares of s j  to additive shares of s j  is implemented using Evaluation to perform SMPC of the function ƒ(x 1 , . . . , x k )=s j . Switching from additive shares of s j  to multiplicative shares of s j  is implemented as described above for computing a product ƒ(S)·l 0 ·s 1   l     1    . . . s k   l     k   . This covers the non-vanishing case. 
     The case where S may contain zeros is handled in the same way as in Section 3, assuming the function is q-bounded for some large prime q. 
     The scheme presented above is perfectly secure against coalitions of up to all but one of the participants. 
     Extensions: 
     An Example of More than Four Participants 
     The schemes described above employ four participants. However, the ideas behind the procedures, from which the schemes are composed, generalize to a larger number of participants. Assuming that one wishes to run the schemes using n 1  M.parties and n 2  A.parties (n 1 , n 2 ≥2), the present invention proposes ways to generalize the procedures described above to suit n 1 +n 2  participants. 
     Random-Split 
     The procedure mult.-random-split described above can be generalized to n 1  M.parties by taking n 1 −1 random non-zero elements of the field, x 1 , . . . , x n     1     −1 , and computing the x n     1    that yields Π i=1   n     1    x i =m. The generalization of add.-random-split. to n 2  participants is analogous. 
     Additive Shares from Multiplicative Shares 
     Procedure M→A of the arithmetic streams scenario and procedure SMA of the Evaluation protocol in the arithmetic functions scenario demonstrate shifting of information from two M.parties,    (1)  and    (2) , to two A.parties,    (3)  and    (4) . These procedures are used to produce additive shares of the secret shared data from multiplicative shares of it. These procedures may be generalized to be procedures by which information is shifted from n 1  M.parties to n 2  A.parties in the following way. Assuming that n 1  M.parties,    (i) , 1≤i≤n 1 , hold n 1  multiplicative shares, x i , of an element m, to achieve n 2  additive shares of m held by n 2  A.parties,    (1)  add.-random-splits x 1  to n 2  additive shares b j , 1≤j≤n 2 , and sends each b j  to the j&#39;th A.party. The rest of the M.parties,    (i) , 2≤i≤n 1 , send x i  to each of the A.parties. At this stage, the M.parties are eliminated and the A.parties multiply the values received to obtain additive shares of m. 
     Observe that: 
         m=Π   i=1   n     1     x   i   =x   1 ·Π i=2   n     1     x   i =(Σ j=1   n     2     b   j )·Π i=2   n     2   ( b   j ·Π i=2   n     1     x   i ).
 
     Multiplicative Shares from Additive Shares 
     Procedure A→M of the arithmetic streams scenario and procedure RetCas of the Evaluation protocol (the cascading options of RetCas) in the arithmetic functions scenario demonstrate shifting of information from two A.parties to two M.parties. These procedures are used to produce multiplicative shares of the secret shared data from additive shares of its. These procedures generalize to procedures by which information is shifted from n 2  A.parties to n 1  M.parties in the following way. Assume n 2  A.parties,    (i) , 1≤i≤n 2 , hold n 2  additive shares, x i , of an element m. To obtain n 1  multiplicative shares of m held by n 1  M.parties, the user mult.-random-splits 1 to n 1  multiplicative shares. The user sends n 1 −1 M.parties one (distinct) multiplicative share of 1, and sends the last share of 1 to all of the A.parties. Each of the A.parties then multiplies the multiplicative share of 1 received by its additive share of m and sends the product to the last M.party. At this stage, the A.parties are eliminated and the last M.party adds the values received. Now the M.parties hold multiplicative shares of m. 
     Evaluation of boolean circuits. The schemes suggested in Sections 2 and 3 may be used to perform computations of boolean streams and SMPC of boolean circuits by working in    2 . A True boolean value is 1∈   2  and a False boolean value is 0∈   2 . Boolean operations may be identified with field operations in the following way. The A operation is identified with    2  multiplication, the ⊕ operation with    2  addition, and the ┐ operation with adding 1 in    2 . The V operation of two literals is identified with x+y+x·y, where x and y are the elements of    2  corresponding to the literals. Then, given a boolean circuit C over boolean literals b 1 , . . . , b n ∈{True, False}, one can use the schemes, suggested above for p-bounded functions, to perform boolean streams computation and SMPC of boolean circuits by taking m 1 , . . . ,m n ∈   2 , where the m i &#39;s are the    2  correspondents of the b i &#39;s. The boolean circuit C: {True, False} n →{True, False} will be taken as a function {tilde over (C)}:    2   n →   2 . 
     Evaluating functions over inputs held by more than one participant. The schemes suggested in Sections 3 and 4 can be used to perform SMPC of arithmetic functions over inputs held by several participants. Instead of having only one participant holding inputs, assume    (1) , . . . ,    (k)  are k users, each of whom is holding a set of secret values in    p . The users wish to privately evaluate a function ƒ over the entire set of variables. Following the distribution protocol, each of the users distributes shares of her secrets. Let one of the users invoke the evaluation protocol, sending the relevant information to the other participants. At the final stage of the evaluation protocol, the participants send their outputs to all of the users. Adding these outputs, each of the users obtains the result of evaluating ƒ over the entire set of secrets. This way, the proposed scheme is extended to support SMPC of functions over inputs held by several participants. 
     Three Millionaires Example: 
     His example describes how the scheme suggested in Section 4 may be used to perform secure multiparty computation. Consider the following scenario. Three millionaires wish to find out who of them is the wealthiest, while not revealing to each other the exact number of millions they possess. Denote the three millionaires by    (1) ,    (2) ,    (3)  and the number of millions they possess by s 1 , s 2 , s 3 , respectively. For simplicity, assume s i  (1≤i≤3) are positive integers between 1 and 10 (other cases may be solved similarly). The first step is distribution, where p=11. For 1≤i≤3,    (i)  mult.-random-splits s i  to a product of multiplicative shares m 1,i ·m 2,i  and distributes m 1,i  to    (1)  and m 2,i  to    (2) . 2  This is illustrated in  FIG. 12 . 
       FIG. 13  illustrates a system for performing distribution for s j , 1≤j≤k, performing mult.-random-split of s j  to multiplicative shares, m ij , among n participants    (1) , . . . ,    (n) , such that s j =Π i=1   n  m ij . Each of the participants may be an untrusted computing cloud or another untrusted computerized system. 
     In order to find out which of them is the wealthiest, the participants may evaluate ƒ(x 1 , x 2 , x 3 ) at (s 1 , s 2 , s 3 ), where ƒ:   11   3 →   11  (one may correctly state that, the procedure mult.-random-split is defined for elements of    p , while the s i &#39;s are integers. Hence, for 1≤i≤3, one should consider  s   i ∈   p  such that  s   i ≡s i (mod 11) and work with the  s   i &#39;s. s i  is written instead of  s   i  occasionally) is the function that returns (a) 0, if x 1 =x 2 =x 3 ; (b) i, if x i  is larger (as an integer) than the two other variables; (c) i+j+1, if x i =x j  (where i≠j) and x i , x j  are both larger (as integers) than the other variable. The (minimal) representation of ƒ as a multivariate polynomial is given in the appendix. Let: 
       ƒ( x   1   ,x   2   ,x   3 )=Σ i,j,k=0   10   a   i,j,k   ·x   1   i   x   2   j   x   3   k .
 
         (3)  takes the role of the user, performing, for each monomial a i,j,k ·x 1   i x 2   j x 3   k  of ƒ, an independent matrix-random-split of 1∈   11  to 
     
       
         
           
             
               
                 C 
                 
                   i 
                   , 
                   j 
                   , 
                   k 
                 
               
               = 
               
                 ( 
                 
                   
                     
                       
                         c 
                         11 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                             , 
                             k 
                           
                           ) 
                         
                       
                     
                     
                       
                         c 
                         12 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                             , 
                             k 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         c 
                         21 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                             , 
                             k 
                           
                           ) 
                         
                       
                     
                     
                       
                         c 
                         22 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                             , 
                             k 
                           
                           ) 
                         
                       
                     
                   
                 
                 ) 
               
             
             , 
           
         
       
     
     and sending the left column of C i,j,k  to    (1)  and the right column to    (2) . Subsequently, for each column vector they receive,    (1)  and    (2)  compute 
     
       
         
           
             
               
                 α 
                 1 
                 
                   ( 
                   
                     i 
                     , 
                     j 
                     , 
                     k 
                   
                   ) 
                 
               
                
               
                   
               
                
               
                 := 
               
                
               
                   
               
                
               
                 m 
                 11 
                 i 
               
                
               
                 m 
                 12 
                 j 
               
                
               
                 
                   m 
                   13 
                   k 
                 
                 · 
                 
                   ( 
                   
                     
                       
                         
                           c 
                           11 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                               , 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           c 
                           21 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                               , 
                               k 
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
               
                
               
                   
               
                
               and 
                
               
                   
               
                
               
                 α 
                 2 
                 
                   ( 
                   
                     i 
                     , 
                     j 
                     , 
                     k 
                   
                   ) 
                 
               
                
               
                   
               
                
               
                 := 
               
                
               
                   
               
                
               
                 m 
                 21 
                 i 
               
                
               
                 m 
                 22 
                 j 
               
                
               
                 
                   m 
                   23 
                   k 
                 
                 · 
                 
                   ( 
                   
                     
                       
                         
                           c 
                           12 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                               , 
                               k 
                             
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           c 
                           22 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                               , 
                               k 
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
               
             
             , 
           
         
       
     
     respectively. For each alpha vector,    (1)  sends the second entry of α 1   (i,j,k) , denoted by (α 1   (i,j,k) ) 2 , to    (2) , while    (2)  sends the first entry of α 2   (i,j,k) , denoted by (α 2   (i,j,k) ) 1 , to    (1) . Using the values received,    (1)  computes 
         A=Σ   i,j,k   a   i,j,k ·(α 1   (i,j,k) ) 1 ·(α 2   (i,j,k) ) 1 ,
 
     while    (2)  computes 
         B=Σ   i,j,k   a   i,j,k ·(α 1   (i,j,k) ) 2 ·(α 2   (i,j,k) ) 2 .
 
     Eventually,    (1)  and    (2)  publish A and B. Observe that 
     
       
         
           
             
               
                 
                   A 
                   = 
                   
                     
                       Σ 
                       
                         i 
                         , 
                         j 
                         , 
                         k 
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         a 
                         
                           i 
                           , 
                           j 
                           , 
                           k 
                         
                       
                       · 
                       
                         ( 
                         
                           
                             m 
                             11 
                             i 
                           
                            
                           
                             m 
                             12 
                             j 
                           
                            
                           
                             
                               m 
                               13 
                               k 
                             
                             · 
                             
                               c 
                               11 
                               
                                 ( 
                                 
                                   i 
                                   , 
                                   j 
                                   , 
                                   k 
                                 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                       · 
                       
                         ( 
                         
                           
                             m 
                             21 
                             i 
                           
                            
                           
                             m 
                             22 
                             j 
                           
                            
                           
                             
                               m 
                               23 
                               k 
                             
                             · 
                             
                               c 
                               12 
                               
                                 ( 
                                 
                                   i 
                                   , 
                                   j 
                                   , 
                                   k 
                                 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       Σ 
                       
                         i 
                         , 
                         j 
                         , 
                         k 
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         a 
                         
                           i 
                           , 
                           j 
                           , 
                           k 
                         
                       
                       · 
                       
                         s 
                         1 
                         i 
                       
                     
                      
                     
                       s 
                       2 
                       j 
                     
                      
                     
                       
                         s 
                         3 
                         k 
                       
                       · 
                       
                         c 
                         11 
                         
                           ( 
                           
                             i 
                             , 
                             j 
                             , 
                             k 
                           
                           ) 
                         
                       
                       · 
                       
                         
                           c 
                           12 
                           
                             ( 
                             
                               i 
                               , 
                               j 
                               , 
                               k 
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
     Similarly, 
         B=Σ   i,j,k   a   i,j,k   ·s   1   i   s   2   j   s   3   k   ·c   21   (i,j,k)   ·c   22   (i,j,k) . 
       Adding, one obtains 
         A+B=Σ   i,j,k   a   i,j,k   ·s   1   i   s   2   j   s   3   k ·( c   11   (i,j,k)   ·c   12   (i,j,k)   ·c   21   (i,j,k)   ·c   22   (i,j,k) ).
 
     The fact that each C i,j,k  is a matrix-random-split of 1 implies that 
         A+B=Σ   i,j,k   a   i,j,k   ·s   1   i   s   2   j   s   3   k ·=ƒ( s   1   ,s   2   ,s   3 ).
 
     Keeping the Circuits Secure 
     In the schemes suggested in Sections 2 and 3, some information about the circuit itself is revealed to the participants. In the arithmetic streams schemes, the M.parties (respectively, A.parties) know exactly how many consecutive multiplications (respectively, additions) are computed in a specific part of the circuit. In the SMPC schemes, some information about ƒ itself is revealed to the participants, as according to the Evaluation protocol, the user sends the relevant elements i∈  to the M.parties and the corresponding a i &#39;s to the A.parties. That leakage of information may be prevented by adding noise to the procedure in cost of communication complexity. 
     Securing Arithmetic Streams 
     The arithmetic streams schemes are adjusted to prevent leakage of information about the computation circuit itself. At each stage of the computation, perform both addition and multiplication operations that yield the same result that would have been obtained normally. If at stage i one has op i =‘·’ (meaning that the user needs to multiply st by m i ), then
         use MinM to multiply st by m i ,   use M→A to switch from multiplication mode to addition mode and eliminate the M.parties,   use AinA to add 0 to st,   use A→M to switch back from addition mode to multiplication mode, using a new set of M.parties, and eliminate the A.parties.       

     If at stage i the user needs to add m i  to st, then
         use MinM to multiply st by 1,   use M→A to switch from multiplication mode to addition mode and eliminate the M.parties,   use AinA to add m i  to st,   use A→M to switch back from addition mode to multiplication mode, using a new set of M.parties, and eliminate the A.parties.       

     This adjustment costs in communication complexity, but it keeps the arithmetic circuit secure in a way that none of the participants can tell what are the arithmetic operations that are actually being performed. 
     Securing Arithmetic Functions 
     The information held by the user is m=(m 1 , . . . , m n )∈   p   n . It is possible to take redundant copies of each (or some) of the m i &#39;s, take redundant variables that equal 1∈   p , take redundant variables that equal 0∈   p , and permute them all to obtain m′=(m′ 1 , . . . , m′ r ) which contains the information began with, along the added redundancy. This expansion of m costs in communication complexity but now it is possible to hide ƒ in several ways. 
     Recall that 
       ƒ( m )=   a   i   ·A   i   , a   i ∈   p ,
 
     where A i  is the i&#39;th monomial. In most applications, most of the a i &#39;s are zero, and their corresponding monomials are called the zero monomials. The other monomials are called the non-zero monomials. Now, one can mask ƒ by the following procedures. To evaluate ƒ:   p   n →   p  over m, take some suitable ƒ′:   p   r →   p  and evaluate it over m′ in such a way that ƒ(m)=ƒ′(m′). 
     An appropriate choice of ƒ′ may mask ƒ in the following ways:
         The non-zero monomials of ƒ can be represented in various forms. Since m′ contains redundant copies of the variables of m and redundant 1-variables, one can compute monomials of ƒ by various choices of monomials of ƒ′. For example, if one of the monomials of ƒ is x 1   8 , and m′ contains redundant copies of m 1 , m′ 2 =m′ 3 =m′ 4 =m 1  and m′ 5 =1, then the corresponding monomial of ƒ′ may be x 2   2 x 3   3 x 4   3 x 5   3 .   Since m′ contains redundant 0-variables, one can take an ƒ′ which contains redundant monomials with a redundant 0-variable. For example, if ƒ(m)=m 1   2 , then one can take ƒ′(m′)=m′ 1   2 +4m′ 6   3 m′ 8 , where m′ 1 =m 1  and m′ 6  or m′ 8  equal zero. The user should keep in mind the indices of the redundant variables.       

     These procedures add noise to the computation circuit but cost in an expansion of m and communication complexity. 
     Malicious Participants and Threshold Analysis 
     The correction and security of our schemes are based on the assumption that the participants are honest-but-curious, and that they do not form coalitions. Therefore, it is assumed that each of the participants follows the exact directions of each procedure of the scheme and is not sending to any of the other participants information not supposed to be sent. Nevertheless, it is assumed that the participants are trying to learn information about the secret shared inputs and about the computation circuits through the data received during the execution of the scheme. In case of deviation of a participant from the directions of the scheme, either the scheme might yield an incorrect solution or the security of the secret shared data may be compromised. 
     The following description discusses ways to detect incorrect outputs caused by malicious participants and analyze the threshold for ensuring the security of the schemes against coalitions of participants. 
     Output Verification 
     Detection of incorrect output caused by malicious participants is achieved either by repeating the same computations while using different sets of participants, or by computing different representations of the same function. Assume one runs our scheme using a total of n participants. Fora positive integer, s, one can uses sets of n participants, where in each set the participants run the same protocol independently. As s is taken to be larger, the correction of the output can be verified with higher certainty. Another approach to detect an incorrect output is to compute the same circuit several times using the same n participants with different randomization in each computation and different representations of the same circuit in each iteration. In this case, one may use schemes for masking the computation as described above, thus ensuring that the participants cannot force repeated incorrect output in successive computations of the same circuit. A repeated incorrect zero output can be forced by a malicious M.party by outputting zero regardless of the inputs received. These two approaches can be combined to reveal malicious participants in the following way. The user can use more than n participants and repeat the same computations (independently) using different n participants on each iteration. Assuming the user receives different outcomes, she can eliminate both sets of participants and repeat the process until identical results are obtained. 
     Security 
     The security of the proposed schemes against attacks of coalitions of participants that join their shares of m in an attempt to learn information about the secret shared inputs will be described. Assume a user runs a scheme, as suggested above, using n 1  M.parties and n 2  A.parties. For each product of n 1 −1 non-zero elements of a finite field, x i , 1≤i≤n 1 −1, and for each non-zero element m of the field, there exists exactly one element x n     1    in the field such that the product of all the n 1  elements x i  yields m. This fact implies that in case of an attack of a coalition of M.parties, if the size of the coalition is up to n 1 −1, then no information about the secret shared input can be gained by the coalition. Similarly, For each sum of n 2 −1 elements of a finite field, x i , 1≤i≤n 2 −1, and for each element m of the field, there exists exactly one element x n     2    in the field such that the sum of all the n 2  elements x i  yields m. Hence, in case of an attack of a coalition of A.parties, if the size of the coalition is up to n 2 −1, no information about the secret shared input can be gained by the coalition. Therefore, the threshold of the schemes is the number of currently-active participants. 
     In Section 4 the description showed how to perform SMPC of arithmetic functions over secret shares using the same set of n participants for both operations. That scheme is information-theoretically secure against coalitions of up to n−1 honest-but-curious participants. The security of the distribution protocol is derived from the same arguments as in the two sets scenario. 
     The security of the evaluation protocol of the single set scenario: 
     Assuming that    (1) , . . . ,    (n−1)  is a coalition of n−1 participants joining the information they received in an attempt to extract information regarding the values of the s i &#39;s. The coalition is referred to as the adversary and summarize the information held by it by the following equations. 
     During the distribution protocol, the adversary receives the following information regarding the secrets: 
         s   1   =m   n,1 ·Π i=1   n−1   m   i1  
 
         s   k   =m   n,k ·Π i=1   n−1   m   ik   (1)
 
     The unknowns in (1) are m n,j , s j  for 1≤j≤k. The products Π i=1   n−1  m ij  for 1≤j≤k are known. 
     By same arguments as in the two sets scenario, the adversary gains no information regarding the s i &#39;s from (1). 
     During stage 3 of the evaluation protocol, the adversary receives the following information regarding C=(c ij ) i,j=1   n , the matrix-random-split of 1∈   p : 
         c   1,n ·Π i=1   n−1   c   1i   + . . . +c   n,n ·Π i=1   n−1   c   ni =1  (2)
 
     The unknowns in (2) are c i,n  for 1≤i≤n. The products Π i=1   n−1 c ji  for 1≤j≤n are known. The matrix C is generated at stage 2 of Evaluation for the computation of the l&#39;th monomial. C is independent of S (and of the l&#39;th monomial), and hence the adversary cannot gain any information regarding S from (2). 
     Assuming that the l&#39;th monomial of ∂ is l 0 ·A(x 1 , . . . ,x k ), where A(x 1 , . . . ,x k )=x 1   l     1   · . . . ·x k   l     k   . During stage 5 of Evaluation, the participants send to each other information. The information received by the adversary from    (n)  may be summarized by the following equations: 
     
       
         
           
             
               
                 
                   
                     
                       
                         ( 
                         
                           α 
                           n 
                         
                         ) 
                       
                       1 
                     
                     = 
                     
                       
                         c 
                         
                           1 
                           , 
                           n 
                         
                       
                       · 
                       
                         A 
                          
                         
                           ( 
                           
                             
                               m 
                               
                                 n 
                                 , 
                                 1 
                               
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               m 
                               
                                 n 
                                 , 
                                 k 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       
                         ⋮ 
                          
                         
                           
 
                         
                         ( 
                         
                           α 
                           n 
                         
                         ) 
                       
                       
                         n 
                         - 
                         1 
                       
                     
                     = 
                     
                       
                         c 
                         
                           
                             n 
                             - 
                             1 
                           
                           , 
                           n 
                         
                       
                       · 
                       
                         
                           A 
                            
                           
                             ( 
                             
                               
                                 m 
                                 
                                   n 
                                   , 
                                   1 
                                 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 m 
                                 
                                   n 
                                   , 
                                   k 
                                 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     The values (α n ) j  for 1≤j≤n−1, appearing in (3), are known to the adversary, since these are the first n−1 entries of the alpha vector, α n , computed by    (n)  at stage 4 of the distribution protocol, and sent to the adversary at stage 5 of the protocol. The rest of the quantities in (3) are unknown. Since the s i &#39;s are non-zero, by (3), for every possible (m n,1 , . . . , m n,k )∈   p   k  with non-zero entries there exists a (c 1,n , . . . , c n−1,n )∈   p   n  with non-zero entries such that m n,1 , . . . , m n,k , c 1,n , . . . , c n−1,n  form a solution of (3). For each such a solution, substituting in (2), one obtains 
       Σ j=1   n−1 (Π i=1   n   c   ji )+ c   n,m ·Π i=1   n−1   c   n,i =1.
 
     Since all other variables are known, solving for c n , and obtaining 
     
       
         
           
             
               c 
               
                 n 
                 . 
                 n 
               
             
             = 
             
               
                 
                   1 
                   - 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         1 
                       
                       
                         n 
                         - 
                         1 
                       
                     
                      
                     
                         
                     
                      
                     
                       ( 
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                             
                         
                          
                         
                           c 
                           ji 
                         
                       
                       ) 
                     
                   
                 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       1 
                     
                     
                       n 
                       - 
                       1 
                     
                   
                    
                   
                       
                   
                    
                   
                     c 
                     
                       n 
                       , 
                       i 
                     
                   
                 
               
               . 
             
           
         
       
     
     For every possible choice of non-zero (m n,1 , . . . ,m n,k ), the system of equations (2)+(3) has a unique solution, implying that no further information regarding the s i &#39;s or A(s 1 , . . . , s k ) can be gained by the adversary. Hence, the fact that each monomial is evaluated independently (as shown in  FIG. 11 ) implies that the scheme is information-theoretically secure with a threshold of n−1. The security of the scheme in the p-bounded case follows from that of the scheme in the non-vanishing case, using the same argumes in the two set scenarios. 
     Although embodiments of the invention have been described by way of illustration, it will be understood that the invention may be carried out with many variations, modifications, and adaptations, without exceeding the scope of the claims. 
     REFERENCES 
     
         
         [BIB89] Judit Bar-Ilan and Donald Beaver. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, pages 201-209. ACM, 1989. 
         [BMR90] Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols. In Proceedings of the twenty-second annual ACM Symposium on Theory of Computing, pages 503-513. ACM, 1990. 
         [BOGW88] Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 1-10. ACM, 1988. 
         [BP16] Zvika Brakerski and Renen Perlman. Lattice-based fully dynamic multi-key fhe with short ciphertexts. In Annual Cryptology Conference, pages 190-213. Springer, 2016. 
         [CCD88] David Chaum, Claude Crépeau, and Ivan Damgard. Multiparty unconditionally secure protocols. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 11-19. ACM, 1988. 
         [DFK+06] Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In Theory of Cryptography Conference, pages 285-304. Springer, 2006. 
         [DGL15] Shlomi Dolev, Niv Gilboa, and Ximing Li. Accumulating automata and cascaded equations automata for communicationless information theoretically secure multi-party computation. In Proceedings of the 3rd Inter-national Workshop on Security in Cloud Computing, pages 21-29. ACM, 2015. 
         [DIK10] Ivan Damgård, Yuval Ishai, and Mikkel Køigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 445-465. Springer, 2010. 
         [DL16] Shlomi Dolev and Yin Li. Secret shared random access machine. In Algorithmic Aspects of Cloud Computing, pages 19-34. Springer, 2016. [DLY07] Shlomi Dolev, Limor Lahiani, and Moti Yung. Secret swarm unit reactive k-secret sharing. In International Conference on Cryptology in India, pages 123-137. Springer, 2007. 
         [Gen09] Craig Gentry. A fully homomorphic encryption scheme. Stanford University, 2009. 
         [GHS12] Craig Gentry, Shai Halevi, and Nigel P Smart. Fully homomorphic encryption with polylog overhead. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 465-482. Springer, 2012. 
         [GHS16] Craig B Gentry, Shai Halevi, and Nigel P Smart. Homomorphic evaluation including key switching, modulus switching, and dynamic noise management, Mar. 8 2016. U.S. Pat. No. 9,281,941. 
         [GIKR02] Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. On 2-round secure multiparty computation. In Annual International Cryptology Conference, pages 178-193. Springer, 2002. 
         [IK02] Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In International Colloquium on Automata, Languages, and Programming, pages 244-256. Springer, 2002. 
         [KN06] Eyal Kushilevitz and Noam Nissan. Communication Complexity. Cambridge University Press, United Kingdom, 2006. 
         [Sha79] Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612-613, 1979. 
         [SV10] Nigel P Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. In International Workshop on Public Key Cryptography, pages 420-443. Springer, 2010. 
         [VDGHV10] Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 24-43. Springer, 2010. 
         [XWZ+18] Jian Xu, Laiwen Wei, Yu Zhang, Andi Wang, Fucai Zhou, and Chong-zhi Gao. Dynamic fully homomorphic encryption-based merkle tree for lightweight streaming authenticated data structures. Journal of Network and Computer Applications, 107:113-124, 2018. 
       
    
     APPENDIX 
     The minimal multivariate polynomial representation of ƒ: ƒ(x, y, z)=x 10 +7x 2 y+6x 4 y+7x 6 y+9x 8 y+3x 9 y+10x 10 y+4xy 2 +10x 3 y 2 +x 5 y 2 +8xy 2 +3x 8 y 2 +5x 9 y 2 +x 2 y 3 +2x 4 y+7x 3 y 3 +3x 7 y 3 +7x 8 y 3 +5xy 4 +9x 3 y 4 +6x 5 y 4 +3x 6 y 4 +8xy 4 +10xy 5 +5x 4 y 5 +3x 5 y 5 +2x 6 y 5 +4xy 6 +4x 3 y 6 +3x 4 y 6 +9x 5 y 6 +3x 2 y 7 +3x 3 y 7 +3x 4 y 7 +2xy 8 +3x 2 y 8 +4x 3 y 8 +3xy 9 +6x 2 y 9 +2y 10 +xy 10 +7x 10 y 10 +3x 2 z+x 4 z+3x 6 z+7x 8 z+8x 9 z+9x 10 z+8xyz+9x 3 yz+3x 4 yz+2x 5 yz+10xyz+5xyz+5x 8 yz+10x 9 yz+8x 10 yz+7y 2 z+3x 2 y 2 +7x 3 y 2 +8x 4 y 2 +2x 5 y 2 z+5x 7 y 2 +10x 8 y 2 z+10x 9 y 2 z+4x 0 y 2 z+6x 2 y 3 z+x 2 y 3 z+3x 3 y 3 z+4x 4 y 3 z+6x 5 y 3 z+3x 6 y 3 z+7x 7 y 3 z+x 9 y 3 z+7x 10 y 3 z+6y 4 z+4x 2 y 4 z+7x 3 y 4 z+x 4 y 4 z+2x 5 y 4 z+9x 6 y 4 z+x 8 y 4 z+9x 9 y 2 z+5x 10 y 4 z+6xy 5 z+10x 2 y 5 z+7x 3 y 5 z+x 4 y 5 z+5x 5 y 5 z+2x 6 y 5 z+x 7 y 5 z+7x 8 y 5 z+4x 9 y 5 z+6x 10 y 5 z+7y 6 z+2x 2 y 6 z+7x 3 y 6 z+3x 4 y 6 z+8x 5 y 6 z+x 6 y 6 z+6x 6 y 6 z+4x 8 y 6 z+3x 9 y 6 z+4x 10 y 6 z+8xy 7 z+3x 2 y 7 z+9x 3 y 7 z+6x 4 y 7 z+x 5 y 7 z+5x 6 y 7 z+4x 7 y 7 z+5x 8 y 7 z+x 9 y 7 z+7x 10 y 7 z+9y 8 z+10xy 8 z+5x 2 y 8 z+7x 3 y 8 z+x 4 y 8 z+4x 5 y 8 z+4x 6 y 8 z+6x 7 y 8 z+x 8 y 8 z+9x 9 y 8 z+2x 10 y 8 z+2y 9 z+xy 9 z+3x 2 y 9 z+x 3 y 9 z+2x 4 y 9 z+4x 5 y 9 z+8x 6 y 9 z+x 7 y 9 z+2x 8 y 9 z+6x 9 y 9 z+10x 10 y 9 z+10y 10 z+8x 2 y 10 z+4x 3 y 10 z+10x 4 y 10 z+5x 5 y 10 z+8x 6 y 10 z+4x 7 y 10 z+4x 8 y 10 z+8x 9 y 10 z+8xz 2 +9x 3 z 2 +2x 5 z 2 +5x 7 z 2 +8x 8 z 2 +10x 9 z 2 +4yz 2 +x 2 yz 2 +6x 3 yz 2 +3x 5 yz 2 +6x 6 yz 2 +x 7 yz 2 +7x 8 yz 2 +7x 9 yz 2 +7x 10 yz 2 +10xy 2 z 2 +7x 3 y 2 z 2 +x 5 y 2 z 2 +7x 6 y 2 z 2 +5x 7 y 2 z 2 +7x 8 y 2 z 2 +x 10 y 2 z 2 +10y 3 z 2 +10xy 3 z 2 +x 2 y 3 z 2 +7x 4 y 3 z 2 +5x 5 y 32 +10x 6 y 3 z 2 +3x 7 y 3 z 2 +10x 8 y 3 z 2 +2x 9 y 3 z 2 +x 10 y 3 z 2 +10xy 4 z 2 +2x 3 y 4 z 2 +6x 4 y 4 z 2 +5x 5 y 4 z 2 +10x 6 y 4 z 2 +10x 7 y 4 z 2 +x 8 y 4 z 2 +7x 9 y 4 z 2 +9x 10 y 4 z 2 +y 5 z 2 +xy 5 z 2 +8x 2 y 5 z 2 +8x 4 y 5 z 2 +6x 5 y 5 z 2 +10x 6 y 5 z 2 +9x 7 y 5 z 2 +3x 8 y 5 z 2 +5x 9 y 5 z 2 +10x 10 y 5 z 2 +3xy 6 z 2 +10x 2 y 6 z 2 +9x 3 y 6 z 2 +2x 4 y 6 z 2 +10x 5 y 6 z 2 +2x 6 y 6 z 2 +3x 7 y 6 z 2 +3x 8 y 6 z 2 +99y 6 z 2 +9x 10 y 6 z 2 +8y 2 z 2 +6xy 7 z 2 +6x 2 y 7 z 2 +5x 3 y 7 z 2 +10x 4 y 7 z 2 +2x 5 y 7 z 2 +3x 6 y 7 z 2 +8x 8 y 7 z 2 +6x 9 y 7 z 2 +3x 10 y 7 z 2 +2y 8 z 2 +10xy 8 z 2 +10x 3 y 8 z 2 +7x 4 y 8 z 2 +3x 5 y 8 z 2 +10x 6 y 8 z 2 +8x 7 y 8 z 2 +6x 8 y 8 z 2 +4x 9 y 8 z 2 +2x 10 y 8 z 2 +5y 9 z 2 +8xy 9 z 2 +2x 2 y 9 z 2 +9x 3 y 9 z 2 +4x 4 y 9 z 2 +6x 5 y 9 z 2 +5x 7 y 9 z 2 +5x 8 y 9 z 2 +6x 9 y 9 z 2 +4x 10 y 9 z 2 +3xy 10 z 2 +2x 3 y 10 z 2 +6x 4 y 10 z 2 +9x 5 y 10 z 2 +3x 6 y 10 z 2 +6x 7 y 10 z 2 +4x 9 y 10 z 2 +7x 10 y 10 z 2 +2x 2 z 3 +4x 4 z 3 +3x 6 z 3 +8x 7 z 3 +3x 8 z 3 +3xyz 3 +5x 2 yz 3 +8x 4 yz 3 +7x 5 yz 3 +6x 6 yz 3 +3x 7 yz 3 z+4x 8 yz 3 +10x 9 yz 3 +3x 10 yz 3 +y 2 z 3 +4xy 2 z 3 +6x 2 y 2 z 3 +2x 4 y 2 z 3 +4x 5 y 2 z 3 +9x 6 y 2 z 3 +9x 7 y 2 z 3 +x 8 y 2 z 3 +4x 9 y 2 z 3 +10x 10 y 2 z 3 +8xy 3 z 3 +8x 3 y 3 z 3 +3x 4 y 3 z 3 +7x 5 y 3 z 3 +3x 6 y 3 z 3 +6x 8 y 3 z 3 +3x 10 y 3 z 3 +2y 4 z 3 +4xy 4 z 3 +3x 2 y 4 z 3 +10x 3 y 4 z 3 +9x 4 y 4 z 3 +2x 5 y 4 z 3 +x 8 y 4 z 3 +9x 10 y 4 z 3 +9xy 5 z 3 +9x 2 y 5 z 3 +4x 3 y 5 z 3 +9x 4 y 5 z 3 +4x 6 y 5 z 3 +8x 7 y 5 z 3 +4x 8 y 5 z 3 +2x 9 y 5 z 3 +7y 6 z 3 +2xy 6 z 3 +7x 2 y 6 z 3 +6x 5 y 6 z 3 +8x 6 y 6 z 3 +6x 8 y 6 z 3 +5x 9 y 6 z 3 +4x 10 y 6 z 3 +2y 7 z 3 +xy 7 z 3 +6x 2 y 7 z 3 +x 4 y 7 z 3 +8x 5 y 7 z 3 +3x 6 y 7 z 3 +5x 7 y 7 z 3 +x 8 y 7 z 3 +10x 9 y 7 z 3 +3x 10 y 7 z 3 +7y 8 z 3 +4xy 8 z 3 +3x 2 y 8 z 3 +9x 4 y 8 z 3 +x 5 y 8 z 3 +8x 6 y 8 z 3 +6x 7 y 8 z 3 +3x 8 y 8 z 3 +2x 9 y 8 z 3 +2x 10 y 8 z 3 +8xy 9 z 3 +2x 2 y 9 z 3 +6x 3 y 9 z 3 +2x 4 y 9 z 3 +7x 5 y 9 z 3 +x 6 y 9 z 3 +6x 7 y 9 z 3 +2x 8 y 9 z 3 +7x 9 y 9 z 3 +8x 10 y 9 z 3 +7xy 10 z 3 +9x 2 y 10 z 3 +7x 4 y 10 z 3 +8x 5 y 10 z 3 +8x 6 y 10 z 3 +2x 7 y 10 z 3 +x 9 y 1 z 3 +10yz 4 +7x 3 z 4 +x 5 z 4 +8x 6 z 4 +5x 7 z 4 +5yz 4 +8xyz 4 +3x 2 yz 4 +3x 3 yz 4 +8x 4 yz 4 +10x 6 yz 4 +5x 7 yz 4 +10x 8 yz 4 +7x 9 yz 4 +6x 10 yz 4 +6xy 2 z 4 +3x 3 y 2 z 4 +10x 4 y 2 z 4 +9x 5 y 2 z 4 +8x 6 y 2 z 4 +x 7 y 2 z 4 +5x 8 y 2 z 4 +4x 9 y 2 z 4 +3x 10 y 2 z 4 +9y 3 z 4 +7xy 3 z 4 +9x 2 y 3 z 4 +6x 3 y 3 z 4 +3x 4 y 3 z 4 +4x 5 y 3 z 4 +1x 7 y 3 z 4 + 
     10x 8 y 3 z 4 +9x 9 y 3 z 4 +2x 10 y 3 z 4 +4xy 4 z 4 +3x 2 y 4 z 4 +8x 3 y 4 z 4 +3x 6 y 4 z 4 +4x 8 y 4 z 4 +5x 10 y 4 z 4 +6y 5 z 4 +8xy 5 z 4 +5x 2 y 5 z 4 +2x 3 y 5 z 4 +7x 5 y 5 z 4 +7x 6 y 5 z 4 +3x 8 y 5 z 4 +3x 8 y 5 z 4 +9x 9 y 5 z 4 +5x 10 y 5 z 4 +2y 6 z 4 +xy 6 z 4 +9x 2 y 6 z 4 +7x 5 y 6 z 4 +4x 6 y 6 z 4 +7x 7 y 6 z 4 +8x 8 y 6 z 4 +5x 9 y 6 z 4 +4x 10 y 6 z 4 +8y 7 z 4 +5xy 7 z 4 +3x 2 y 7 z 4 +10x 3 y 7 z 4 +8x 4 y 4 z 4 +0x 5 y 7 z 4 +9x 6 y 7 z 4 +8x 7 y 7 z 4 +9x 8 y 7 z 4 +8x 9 y 7 z 4 +x 10 y 7 z 4 +8xy 8 z 4 +4x 2 y 8 z 4 +5x 3 y 8 z 4 +8x 5 y 8 z 4 +9x 6 y 8 z 4 +4x 7 y 8 z 4 +8x 8 y 8 z 4 +9x 9 y 8 z 4 +5x 10 y 8 z 4 +9xy 9 z 4 +9x 2 y 9 z 4 +9x 3 y 9 z 4 +10x 4 y 9 z 4 +6x 5 y 9 z 4 +7x 6 y 9 z 4 +3x 7 y 9 z 4 +8x 8 y 9 z 4 +10x 9 y 9 z 4 +xy 10 z 4 +5x 2 y 10 z 4 +4x 3 y 10 z 4 +10x 5 y 10 z 4 +4x 6 y 10 z 4 +9x 7 y 10 z 4 +7x 8 y 10 z 4 +9x 2 z 5 +10x 4 z 5 +8x 5 z 5 +4x 6 z 5 +10xyz 5 +8x 2 yz 5 +9x 3 yz 5 +9x 4 yz 5 +9x 5 yz 5 +5x 6 yz 5 +10x 7 yz 5 +3x 8 yz 5 +7x 9 y 5 +x 10 yz 5 +10y 2 z 5 +9xy 2 z 5 +4x 2 y 2 z 5 +5x 3 y 2 z 5 +4x 4 y 2 z 5 +x 6 y 2 z 5 +7x 7 y 2 z 5 +8x 8 y 2 z 5 +10x 9 y 2 z 5 +x 10 y 2 z 5 +10xy 3 z 5 +4x 2 y 3 z 5 +x 3 y 3 z 5 +7x 4 y 3 z 5 +9x 6 y 3 z 5 +3x 7 y 3 z 5 +3x 8 y 3 z 5 +9x 9 y 3 z 5 +3x 10 y 3 z 5 +5y 4 z 5 +7xy 4 z 5 +8x 2 y 4 z 5 +9x 3 y 4 z 5 +4x 6 y 4 z 5 +4x 7 y 4 z 5 +8x 8 y 4 z 5 +3x 9 y 4 z 5 +6x 10 y 4 z 5 +2y 5 z 5 +2xy 5 z 5 +5x 2 y 5 z 5 +4x 4 y 5 z 5 +4x 6 y 5 z 5 +7x 8 y 5 z 5 +5x 10 y 5 z 5 +2y 6 z 5 +3xy 6 z 5 +3x 2 y 6 z 5 +5x 3 y 6 z 5 +x 4 y 6 z 5 +7x 6 y 6 z 5 +5x 7 y 6 z 5 +4x 8 y 6 z 5 +3x 9 y 6 z 5 +7x 10 y 6 z 5 +8xy 7 z 5 +9x 2 y 7 z 5 +9x 3 y 7 z 5 +x 4 y 7 z 5 +5x 5 y 7 z 5 +x 6 y 7 z 5 +10x 7 y 7 z 5 +7x 8 y 7 z 5 +2x 9 y 7 z 5 +8x 10 y 7 z 5 +7xy 8 z 5 +2x 2 y 8 z 5 +10x 3 y 8 z 5 +7x 4 y 8 z 5 +5x 6 y 8 z 5 +4x 7 y 8 z 5 +9x 8 y 8 z 5 +5x 9 y 8 z 5 +10xy 9 z 5 +5x 2 y 9 z 5 +10x 3 y 9 z 5 +5x 4 y 9 z 5 +8x 5 y 9 z 5 +4x 6 y 9 z 5 +6x 7 y 9 z 5 +x 8 y 9 z 5 +6xy 10 z 5 +2x 2 y 10 z 5 +3x 3 y 10 z 5 +x 4 y 10 z 5 +6x 5 y 10 z 5 +10x 6 y 10 z 5 +x 7 y 10 z 5 +8xz 6 +8x 3 z 6 +8x 4 z 6 +7x 5 z 6 +4yz 6 +xyz 6 +10x 2 yz 6 +3x 3 yz 6 +9x 4 yz 6 +6x 5 yz 6 +10y 6 yz 6 +x 7 yz 6 +7x 8 yz 6 +6x 9 yz 6 +7x 10 yz 6 +5xy 2 z 6 +2x 2 y 2 z 6 +7x 3 y 2 z 6 +3x 4 y 2 z 6 +x 5 y 2 z 6 +8x 7 y 2 z 6 +4x 8 y 2 z 6 +2x 9 y 2 z 6 +6x 10 y 2 z 6 +4y 3 z 6 +6y 3 z 6 +6xy 3 z 6 +3x 2 y 3 z 6 +8x 3 y 3 z 6 +2x 5 y 3 z 6 +3x 6 y 3 z 6 +8x 7 y 3 z 6 +5x 8 y 3 z 6 +4x 9 y 3 z 6 +7x 10 y 3 z 6 +2y 4 z 6 +10xy 4 z 6 +x 2 y 4 z 6 +8x 4 y 4 z 6 +4x 5 y 4 z 6 +4x 7 y 4 z 6 +10x 8 y 4 z 6 +6x 9 y 4 z 6 +6x 10 y 4 z 6 +9y 5 z 6 +9xy 5 z 6 +3x 2 y 5 z 6 +7x 3 y 5 z 6 +x 4 y 5 z 6 +7x 5 y 5 z 6 +10x 6 y 5 z 6 +4x 7 y 5 z 6 +10x 8 y 5 z 6 +9x 9 y 5 z 6 +8xy 6 z 6 +9x 2 y 6 z 6 +9x 3 y 6 z 6 +7x 4 y 6 z 6 +2x 5 y 6 z 6 +5x 7 y 6 z 6 +5x 8 y 6 z 6 +10x 9 y 6 z 6 +5x 10 y 6 z 6 +6xy 7 z 6 +2x 2 y 7 z 6 +8x 3 y 7 z 6 +3x 4 y 7 z 6 +10x 5 y 7 z 6 +7x 8 y 7 z 6 +2x 9 y 7 z 6 +10xy 8 z 6 +x 2 y 8 z 6 +6x 3 y 8 z 6 +2x 4 y 8 z 6 +6x 5 y 8 z 6 +10x 6 y 8 z 6 +x 7 y 8 z 6 +2x 8 y 8 z 6 +3xy 9 z 6 +8x 2 y 9 z 6 +10x 3 y 9 z 6 +9x 4 y 9 z 6 +5x 5 y 9 z 6 +6x 6 y 9 z 6 +8x 7 y 9 z 6 +3xy 10 z 6 +8x 2 y 10 z 6 +3x 3 y 10 z 6 +8x 4 y 10 z 6 +7x 5 y 10 z 6 +6x 2 z 7 +8x 3 z 7 +6x 4 z 7 +8x 2 yz 7 +7x 3 yz 7 +6x 4 yz 7 +10x 5 yz 7 +10x 6 yz 7 +7x 7 yz 7 +10x 8 yz 7 +10x 9 yz 7 +3x 10 yz 7 +3y 2 z 7 +4xy 2 z 7 +7x 2 y 2 z 7 +2x 3 y 2 z 7 +x 4 y 2 z 7 +4x 5 y 2 z 7 +8x 6 y 2 z 7 +3x 8 y 2 z 7 +x 9 y 2 z 7 +8x 10 y 2 z 7 +2y 3 z 7 +3xy 3 z 7 +8x 2 y 3 z 7 +x 4 y 3 z 7 +3x 5 y 3 z 7 +3x 6 y 3 z 7 +6x 7 y 3 z 7 +6x 8 y 3 z 7 +x 9 y 3 z 7 +7x 10 y 3 z 7 +3y 4 z 7 +3x 2 y 4 z 7 +5x 4 y 4 z 7 +7x 5 y 4 z 7 +8x 6 y 4 z 7 +5x 8 y 4 z 7 +4x 9 y 4 z 7 +6x 10 y 4 z 7 +8xy 5 z 7 +2x 2 y 5 z 7 +9x 3 y 5 z 7 +8x 4 y 5 z 7 +10x 5 y 5 z 7 +7x 6 y 5 z 7 +2x 8 y 5 z 7 +7x 9 y 5 z 7 +7x 10 y 5 z 7 +5xy 6 z 7 +2x 2 y 6 z 7 +5x 4 y 5 z 7 +6x 5 y 6 z 7 +6x 6 y 6 z 7 +10x 7 y 6 z 7 +10x 8 y 6 z 7 +5x 9 y 6 z 7 +10xy 7 z 7 +7x 3 y 7 z 7 +3x 4 y 7 z 7 +x 5 y 7 z 7 +9x 6 y 7 z 7 +5x 7 y 7 z 7 +3x 8 y 7 z 7 +5xy 8 z 7 +9x 2 y 8 z 7 +5x 3 y 8 z 7 +7x 4 y 8 z 7 +5x 5 y 8 z 7 +7x 6 y 8 z 7 +xy 9 z 7 +6x 2 y 9 z 7 +10x 3 y 9 z 7 +6x 4 y 9 z 7 +5x 5 y 9 z 7 +3x 6 y 9 z 7 +7xy 10 z 7 +5x 2 y 10 z 7 +10x 3 y 10 z 7 +8x 4 y 10 z 7 +10x 5 y 10 z 7 +4xz 8 +8x 2 z 8 +8x 3 z 8 +2yz 8 +4xyz 8 +8x 2 yz 8 +7x 3 yz 8 +10x 4 yz 8 +8x 5 yz 8 ++7x 6 yz 8 +7x 7 yz 8 +10x 8 yz 8 +7x 9 yz 8 +9x 10 yz 8 +2y 2 z 8 +5xy 2 z 8 +4x 2 y 2 z 8 +x 3 y 2 z 8 +6x 4 y 2 z 8 +8x 5 y 2 z 8 +7x 6 y 2 z 8 +3x 7 y 2 z 8 +7x 9 y 2 z 8 +8x 10 y 2 z 8 +4y 3 z 8 +3x 2 y 3 z 8 +5x 3 y 3 z 8 +4x 4 y 3 z 8 +8x 5 z 8 +9x 6 y 3 z 8 +5x 7 y 3 z 8 +10x 9 y 3 z 8 +5x 10 y 3 z 8 +
 
8xy 4 z 8 +10x 2 y 4 z 8 +2x 3 y 4 z 8 +7x 4 y 4 z 8 +7x 5 y 4 z 8 +x 6 y 4 z 8 +6x 7 y 4 z 8 +10x 8 y 4 z 8 +9x 10 y 4 z 8 +4xy 5 z 8 +2x 2 y 5 z 8 +7x 3 y 5 z 8 +x 4 y 5 z 8 +4x 5 y 5 z 8 +x 6 y 5 z 8 +7x 7 y 5 z 8 +8x 8 y 5 z 8 +4x 9 y 5 z 8 +10y 6 z 8 +8x 2 y 6 z 8 +8x 3 y 6 z 8 +3x 4 y 6 z 8 +7x 5 y 6 z 8 +4x 6 y 6 z 8 +9x 7 y 6 z 8 +6xy 7 z 8 +9x 2 y 7 z 8 +10x 3 y 7 z 8 +2x 4 y 7 z 8 +2x 5 y 7 z 8 +x 6 y 7 z 8 +8x 7 y 7 z 8 +8xy 8 z 8 +5x 2 y 8 z 8 +8x 3 y 8 z 8 +x 4 y 8 z 8 +7x 5 y 8 z 8 +9x 6 y 8 z 8 +9xy 9 z 8 +7x 3 y 9 z 8 +x 4 y 9 z 8 +10x 5 y 9 z 8 +7xy 10 z 8 +x 2 y 10 z 8 +6x 3 y 10 z 8 +4x 4 y 10 z 8 +8xz 9 +x 2 z 9 +2yz 9 +3xyz 9 +4x 2 yz 9 +10x 3 yz 9 +4x 4 y 9 +7x 5 y 9 +5x 6 yz 9 +10x 7 yz 9 +4x 8 yz 9 +5x 9 yz 9 +8x 10 yz 9 +6y 2 z 9 +xy 2 z 9 +4x 2 y 2 z 9 +7x 3 y 2 z 9 +9x 4 y 2 z 9 +x 5 y 2 z 9 +6x 6 y 2 z 9 +10x 7 y 2 z 9 +9x 8 y 2 z 9 +10x 9 y 2 z 9 +3x 10 y 2 z 9 +8xy 3 z 9 +9x 2 y 3 z 9 +x 3 yz 9 +2x 4 y 3 z 9 +8x 5 y 3 z 9 +7x 6 y 3 z 9 +4x 7 y 3 z 9 +10x 8 y 3 z 9 +2x 9 y 3 z 9 +9x 10 y 3 z 9 +2xy 4 z 9 +6x 2 y 4 z 9 +9x 4 y 4 z 9 +8x 5 y 4 z 9 +10x 6 y 4 z 9 +5x 7 y 4 z 9 +9x 8 y 4 z 9 +10xy 5 z 9 +6x 2 y 5 z 9 +4x 3 y 5 z 9 +2x 4 y 5 z 9 +5x 5 y 5 z 9 +4x 7 y 5 z 9 +7x 8 y 5 z 9 +8xy 6 z 9 +10x 2 y 6 z 9 +6x 3 y 6 z 9 +6x 5 y 6 z 9 +2x 6 y 6 z 9 +6x 7 y 6 z 9 +8xy 7 z 9 +5x 2 y 7 z 9 +6x 3 y 7 z 9 +x 4 y 7 z 9 +9x 5 y 7 z 9 +9x 6 y 7 z 9 +2xy 8 z 9 +x 2 y 8 z 9 +7x 3 y 8 z 9 +6x 5 y 8 z 9 +4xy 9 z 9 +3x 2 y 9 z 9 +8x 3 y 9 z 9 +x 4 y 9 z 9 +4xy 10 z 9 +2x 2 y 10 z 9 +x 3 y 10 z 9 +3z 10 +2xz 10 +6x 10 z 10 +yz 10 +3+yz 10 +4x 2 yz 10 +8x 3 yz 10 +5x 4 yz 10 +10x 5 yz 10 +4x 6 yz 10 +8x 7 yz 10 +2x 8 yz 1 +4x 9 yz 10 +3x 10 yz 10 +7xy 2 z 10 +10x 2 y 2 z 10 +x 3 y 2 z 10 +8x 4 y 2 z 10 +10x 5 y 2 z 10 +5x 6 y 2 z 10 +3x 7 y 2 z 10 +4x 8 y 2 z 10 +3x 9 y 2 z 10 +4xy 3 z 10 +10x 2 y 3 z 10 +8x 3 y 3 z 10 +9x 4 y 3 z 10 +8x 5 y 3 z 10 +4x 6 y 3 z 10 +5x 7 y 3 z 10 +x 8 y 3 z 10 +9y 3 z 10 +6xy 4 z 10 +2x 2 y 4 z 10 +2x 3 y 4 z 10 +6x 4 y 4 z 10 +5x 5 y 4 z 10 +6x 6 y 4 z 10 +2x 8 y 4 z 10 +5xy 5 z 10 +x 2 y 5 z 10 +6x 4 y 5 z 10 +7x 5 y 5 z 10 +6x 6 y 5 z 10 +4x 7 y 5 z 10 +7xy 6 z 10 +2x 2 y 6 z 10 +7x 3 y 6 z 10 +8x 4 y 6 z 10 +10x 5 y 6 z 10 +6x 6 y 6 z 10 +4xy 7 z 10 +8x 2 y 7 z 10 +9x 3 y 7 z 10 +5x 4 y 7 z 10 +3x 5 y 7 z 10 +9xy 8 z 10 +10x 2 y 8 z 10 +4z 3 y 8 z 10 +6x 4 y 8 z 10 +2x 2 y 9 z 10 +2x 2 y 9 z 10 +3x 3 y 9 z 10 +5y 10 z 10 +6xy 10 z 10 +4x 2 y 10 z 10