A method for secure multiparty computation is disclosed. In one embodiment,
participants to a secure computation agree upon a function to be computed
and a representation of the function as a circuit with at least one gate.
Logical tables are then generated for each gate. A logical table includes
all possible input and output values for the gate based on the function.
These input and output values are then encoded and the encoded tables are
passed through a mix network, which generates a blinded table for each
encoded logical table. A blinded table corresponds to the encoded logical
table except that its rows are randomly permuted and entries are
encrypted. After this initial blinding round, participants provide
encryptions of their encoded secret inputs. The participants then jointly
compute the function of interest using the encrypted secret inputs and the
representative circuit. To simulate a gate therein, the participants
compare the encrypted inputs to the gate with each encrypted input entry
in the blinded table until a match is detected. When a match is detected,
the corresponding output entry in the matched row is taken to be the
output of the gate. This method of mixing and matching is performed in an
identical manner for every gate in the circuit, irrespective of the layer
in which it resides or the function being computed, until the output of
the last gate is identified.
