Page 1 of 2
THIS COPY WAS MADE FROM AN INTERNAL IBM DOCUMENT AND NOT FROM THE PUBLISHED BOOK
JP820020750 Koichiro Kato/Japan/IBM Akira K Okada
Method to implement a multiparty protocol which allows parties to join or leave dynamically
Disclosed is a system for multiparty protocols which allow parties to join or leave dynamically without requiring re-configuration or re-evaluation of Boolean functions.
The multiparty protocol enables the evaluation of Boolean functions based on input values which each party secretly holds. While the protocol proceeds, a party cannot gain any knowledge about the input values of other parties. When the protocol completes, the final result (the output of the Boolean function) can be shared among parties. The detailed algorithm for the multiparty protocol is found in reference [1]. Fig 1 shows the configuration of a multiparty protocol known so far where the number of parties is m and each party hold n bits.
Party 1 Party m
Output
1 n
Boolean Function
1n 1 n
Fig 1. Configuration of Multiparty Protocol
This configuration does not allow the parties to be dynamically changed during the execution of the protocol: if some parties leave or join the protocol, the Boolean function needs to be re-configured and re-evaluated. By restricting the type of Boolean functions only to the repeatable ones (e.g. addition or successive comparison), this disclosure proposes the system shown in Fig 2, where the adder can be replaced with any repeatable operation. The multiparty protocol using this system proceeds as follows. Note that operations such as summation are performed over GF(2).
Input : The number of the parties is m. Each party secretly holds n bits denoted by x(i,j) where i = 1,...,m and j = 1,...,n. A1 Initialization of the accumulator: Let i = 1. Party i (= 1) randomly selects and sends n bits to each of the other (m-1) parties. Party i modifies its n bits so that the sum of m parties is equal to the origi...