System and method for enforcement of correctness of inputs of multi-party computations

Abstract

A method of performing a Multi-Party Computation (MPC) process between two parties and a server, the parties generating initial garbled labels to an initial garbled circuit and sending the initial garbled labels corresponding to an input to the server, the parties generating a fresh garbled circuit and generating multiple bridge gates for translating the initial garbled labels to garbled values for the inputs to the fresh garbled circuit, where each of the bridge gates is associated with a specific input wire of the fresh garbled circuit and maps a value of the initial garbled labels to a value of garbled labels of the fresh garbled circuit, where the server computes fresh garbled values for the fresh garbled circuit using the bridge gates and the initial garbled values and evaluates the fresh garbled circuit using the fresh garbled labels.

Claims

1. A method of performing a Multi-Party Computation (MPC) process between two parties and a server, the method comprising an initialization phase comprising: the two parties generating initial garbled labels to an initial garbled circuit; each of the two parties sending the initial garbled labels corresponding to an input from each of the two parties to the server; the method also comprises an evaluation phase comprising: the two parties generating a fresh garbled circuit; the two parties generating multiple bridge gates for translating the initial garbled labels to garbled values for the inputs to the fresh garbled circuit; wherein each bridge gate of the multiple bridge gates is associated with a specific input wire of the fresh garbled circuit; wherein each bridge gate of the multiple bridge gates maps a value of the initial garbled labels to a value of garbled labels of the fresh garbled circuit; the two parties sending the garbled circuit and bridge gates to the server; the server computing fresh garbled values for the fresh garbled circuit using the bridge gates and the initial garbled values; the server evaluating the fresh garbled circuit using the fresh garbled labels.

2. The method of claim 1, wherein the bridge gates encrypt a garbled value representing 0 on a wire with a garbled value representing 0 in the initial garbled values, and like encrypt a garbled value representing 1 on a wire with a garbled value representing 1 in the initial garbled values.

3. The method of claim 1, wherein the initialization phase further comprises of the server storing the initial garbled labels corresponding to the inputs of the first party and the second party.

4. The method of claim 1, wherein the initialization phase further comprises: the first party sending a commitment of its initial garbled labels to the second party without revealing the garbled labels; the second party sending a commitment of its initial garbled labels to the first party without revealing the garbled labels; and the evaluation phase further comprises: the first party sending the server the commitment to the second party's initial garbled labels and the commitment opening to its own garbled labels; the second party sending the server the commitment to the first party's initial garbled labels and the commitment opening to its own garbled labels; the server using the commitment openings to open the commitments and obtain the initial garbled values of the first party and second party.

5. The method of claim 4, wherein the commitment to the initial garbled labels is the result of a hash function applied to the initial garbled labels.

6. The method of claim 1, wherein the initialization phase comprising: the first party generating an initialization seed for a pseudorandom generator; the first party sending the initialization seed to the second party; each of the two parties computing initial garbled labels based on the same initialization seed.

7. The method of claim 6, wherein the evaluation phase comprising: the first party generating a fresh seed for the pseudorandom generator; the first party sending the fresh seed to the second party; each of the two parties computing a garbled circuit based on the fresh seed.

8. The method of claim 1, further comprising the server sending the output to the first party.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention may be more clearly understood upon reading of the following detailed description of non-limiting exemplary embodiments thereof, with reference to the following drawings, in which:

(2) FIG. 1 discloses an initialization phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention;

(3) FIG. 2 discloses an evaluation phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention;

(4) FIG. 3 discloses usage of commitments during an evaluation phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention.

(5) The following detailed description of embodiments of the invention refers to the accompanying drawings referred to above. Dimensions of components and features shown in the figures are chosen for convenience or clarity of presentation and are not necessarily shown to scale. Wherever possible, the same reference numbers will be used throughout the drawings and the following description to refer to the same and like parts.

DETAILED DESCRIPTION

(6) Illustrative embodiments of the invention are described below. In the interest of clarity, not all features/components of an actual implementation are necessarily described.

(7) The invention, in embodiments thereof, discloses a method for verifying correctness of inputs of a Multi-Party Computation (MPC) process between two parties. The verification is performed using a third party, such as a server communicating with the two parties. The third party can verify that it received the correct garbled circuit by checking that it received the same garbled circuit from both parties.

(8) Each of the parties comprises a memory storage configured to store a share of the secret and a set of instructions utilized to implement the methods elaborated below. Each of the parties also comprises a communication module configured to exchange information with at least one of the other parties. each of the parties also comprises a processing module for processing information based on the set of instructions stored in the memory storage.

(9) FIG. 1 discloses an initialization phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention.

(10) Step 110 discloses the first party generating an initialization seed for a pseudorandom generator. The initialization seed may be a string having a predefined length. The string may be generated using a random process.

(11) Step 120 discloses the first party sending the initialization seed to the second party. Sending the initialization seed may be performed by sending a message over the internet, via a wired cable or via a cellular modem. The initialization seed may be stored in a predefined memory address in the memory of the second party.

(12) Step 130 discloses each of the two parties computing initial garbled labels based on the initialization seed. The garbled circuit may be computed as disclosed in U.S. patent Ser. No. 10/178,090. The initial garbled labels may be computed using an MPC process. The garbled labels of both parties should be identical.

(13) Step 140 discloses each of the two parties sending the initial garbled labels corresponding to its own input to the server. Sending the seed may be performed by sending a message over the internet, via a wired cable or via a cellular modem. The memory of the server, also denoted as the third party, may have one memory address allocated for the initial garbled labels received from the first party and a second memory address allocated for the initial garbled labels received from the second party. The server stores the initial garbled labels, and uses them every time that the correctness of the MPC input is enforced.

(14) FIG. 2 discloses an evaluation phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention.

(15) Step 210 discloses the first party generating a fresh seed for the pseudorandom generator. The fresh seed may be a string having a predefined length. The string may be generated using a random process. The fresh seed may be generated after or prior to generation of the seed of step 110.

(16) Step 220 discloses the first party sending the fresh seed to the second party. Sending the seed may be performed by sending a message over the internet, via a wired cable or via a cellular modem.

(17) Step 230 discloses each of the two parties computing a fresh garbled circuit based on the fresh seed. Computing the fresh garbled circuit may be performed in the same manner as the initial garbled circuit is computed in step 130. The fresh Garbled circuit need new inputs from the parties each time a fresh Garbled circuit is used.

(18) Step 240 discloses the two parties generating bridge gates for translating the initial garbled labels to garbled values for the inputs to the garbled circuit. In some exemplary cases, each bridge gate of the multiple bridge gates is associated with a specific input wire of the fresh garbled circuit. Each input wire of the fresh garbled circuit is associated with a specific bridge gate of the multiple bridge gates, and the specific bridge gate comprises a ciphertext of the bit representing the input wire, either 0 or 1.

(19) In some exemplary cases, each bridge gate of the multiple bridge gates maps a value of the initial garbled labels to a value of garbled labels of the fresh garbled circuit. The multiple bridge gates may be generated based on a predefined set of computerized instructions. The predefined set of instructions may consider properties of the fresh garbled circuit, such as number of input wires of the fresh garbled circuit.

(20) In some exemplary cases, the multiple bridge gates encrypt the garbled value representing 0 on a wire with a garbled value representing 0 in the initial input garbled values, and encrypt the garbled value representing 1 on a wire with a garbled value representing 1 in the initial input garbled values.

(21) Step 250 discloses the two parties sending the garbled circuit and multiple bridge gates to the server. Sending the garbled circuit and multiple bridge gates may be performed by sending a message over the internet, via a wired cable or via a cellular modem. The garbled circuit and multiple bridge gates may be stored in a predefined memory address in the memory of the server.

(22) Step 260 discloses the server generating garbled labels as input for the garbled circuit based on the initial garbled values and the bridge gates.

(23) Step 270 discloses the server evaluating the garbled circuit using the initial garbled labels, bridge gates and garbled circuit. evaluating the garbled circuit may be performed by methods known to persons skilled in the art, for example as elaborated in U.S. patent Ser. No. 10/178,090.

(24) Step 280 discloses the server sending the output to the first party. Sending the output may be performed by sending a message over the internet, via a wired cable or via a cellular modem. The output may be stored in a predefined memory address in the memory of the first party.

(25) FIG. 3 discloses usage of commitments during an evaluation phase of a method for performing a Multi-Party Computation (MPC) process between two parties and a server, according to exemplary embodiments of the invention.

(26) Step 310 discloses the first party sending a commitment of its initial garbled labels to the second party without revealing the garbled labels. The commitment is defined as a value that bounds the node to the value but does not reveal it. The commitment may be computed, for example, by choosing a random r.sub.i of length 128 bits and computing c.sub.i=SHA256(Q.sub.i,r.sub.i). Then, the nodes exchange the value c.sub.i.

(27) Step 320 discloses the second party sending a commitment of its initial garbled labels to the first party without revealing the garbled labels. Exchange of the commitments, commitment openings and additional messages between the nodes may be performed via a wired or wireless channel.

(28) Step 330 discloses the first party sending the server the commitment to the second party's initial garbled labels and the commitment opening to its own garbled labels. The commitment openings may be the commitment message before the hash function is applied thereto. For example, the commitment opening is (Q.sub.i, r.sub.i) while the commitment message is c.sub.i=SHA256(Q.sub.i, r.sub.i).

(29) Step 340 discloses the second party sending the server the commitment to the first party's initial garbled labels and the commitment opening to its own garbled labels.

(30) Step 350 discloses the server using the commitment openings to open the commitments and obtain the initial garbled values of the first party and second party.

(31) While the disclosure has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings without departing from the essential scope thereof. Therefore, it is intended that the disclosed invention not be limited to the particular embodiments disclosed herein.