Method and system for mediated secure computation

Techniques are described for mediated secure computation. A unique identifier value may be assigned to each one of a plurality of nodes included in a network. An encrypted portion of a logical circuit may be received at a server from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. A result may be obtained based on executing the logical circuit, based on combining the encrypted portions of the logical circuit received at the server.

TECHNICAL FIELD

This description relates to techniques for mediated secure computation.

BACKGROUND

With the growth of activity involving transactions among large numbers of parties via large networks such as the Internet, many applications have developed in which a large number of clients may wish to obtain a result based on inputs provided by each of the clients. For example, an online auction may be set up in which a large number of users may submit bids for individual items, such that none of the bidding users has any knowledge of any others of the bidding users. Each bidding user may have an interest in winning the auction for the lowest possible bid that exceeds all other bidding users' bids. All bidding users may receive a result indicating the winning bid at the end of the auction. As an example, at the end of an auction, a bidding user may wish to contest the result, as the bidding user may know that their bid was higher than the result provided to them. However, all bidding users may wish to remain anonymous to all other bidding users, and may wish to withhold certain information from a service provider that may process the auction.

Secure multiparty computation (SMC) generally may involve a cryptographic computation of functions, such that the input of the parties may remain private (i.e., confidential with that party). Only the result (or results) may be revealed to the parties and what may be inferred from one party's input and output may be implicitly revealed. Conventional SMC may assume that a subset (e.g., a majority) of the parties are honest and complete the protocol whereas the other parties may be malicious and may eventually drop out of the protocol.

Distributed algorithmic mechanism design (DAMD) may involve computing functions, such that a result may be compatible with the utility of the collaborating agents and the computation may be efficient in computation and communication complexity. In some applications, it may be desirable for agents to keep their input private, i.e., it may be in their best interest to not reveal their input.

However, it may be difficult to prevent collusion among agents that may lead to invalid results of certain types of computations. Thus, it may be desirable to provide techniques for multiparty secure computation.

SUMMARY

According to one general aspect, a system includes a mediated secure computation manager including a unique identifier manager configured to assign a unique identifier value to each one of a plurality of nodes included in a network. The mediated secure computation manager further includes a node input receiving manager configured to receive, at a server, an encrypted portion of a logical circuit from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. The mediated secure computation manager further includes a portion combining engine configured to combine the encrypted portions of the logical circuit received at the server, and a logical circuit execution manager configured to obtain a result based on executing the logical circuit, based on one or more operations of the portion combining engine.

According to another aspect, a system includes a network node processing engine including a node identifier manager configured to receive, at a node included in a plurality of nodes associated with a network, a unique identifier value assigned to the node by a server. The network node processing engine further includes a portion encryption manager configured to encrypt a portion of a logical circuit, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. The network node processing engine further includes a node portion manager configured to send, to the server, the encrypted portion of the logical circuit, and a result receiving manager configured to receive a result from the server based on execution of the logical circuit, based on combining the encrypted portion with one or more other encrypted portions of the logical circuit received at the server from one or more other nodes included in the plurality of nodes associated with the network.

According to another aspect, a method includes assigning a unique identifier value to each one of a plurality of nodes included in a network. An encrypted portion of a logical circuit may be received at a server from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. A result may be obtained based on executing the logical circuit, based on combining the encrypted portions of the logical circuit received at the server.

According to another aspect, a method includes receiving, at a node included in a plurality of nodes associated with a network, a unique identifier value assigned to the node by a server. An encrypted portion of a logical circuit may be sent to the server, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. A result may be received from the server based on execution of the logical circuit, based on combining the encrypted portion with other encrypted portions of the logical circuit received at the server from one or more other nodes included in the plurality of nodes associated with the network.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a system100for mediated secure computation. In the example ofFIG. 1, a mediated secure computation manager102includes various processing engines that obtain and process logical circuits and inputs from a plurality of nodes such as network nodes104a,104b. According to an example embodiment, the mediated secure computation manager102may include a server106for receiving inputs from the plurality of nodes, and may process the inputs based on a logical circuit108, to provide a result110that has been requested by the network nodes104a,104b. For example, the server106may include a service provider, and the network nodes104a,104bmay include clients of the service provider, who may communicate with the server106via a network such as the Internet. Although not explicitly shown inFIG. 1, there may be a large number of such nodes, for example, communicating with the server106via a network such as a local area network (LAN) or a wide area network such as the Internet.

The mediated secure computation manager102may include a unique identifier manager112configured to assign a unique identifier value114a,114bto each one of a plurality of nodes included in a network. For example, if there are n network nodes included in the network, the unique identifier manager112may assign the integers 1, 2, 3, . . . , n uniquely to each of the network nodes. For example, each of the network nodes may be informed of its unique identifier value114a,114b, and may not be informed of other network nodes' unique identifier values; however, each network node may be informed of the total number of network nodes included in the network, or the total number of network nodes that may be included in a computation of a logical circuit such as the logical circuit108. According to an example embodiment, the server106may not collude with any one or more of the nodes, such as network nodes104a,104b.

According to an example embodiment, the unique identifier manager112may be configured to assign a unique identifier value114a,114bto each one of the plurality of nodes included in the network, based on counting values associated with a number of the plurality of nodes. For example, the unique identifier manager112may assign the unique identifier value114aof 1 to the network node104a, and the unique identifier value114bof 2 to the network node104b. For example, if there are n nodes included in the network, then the unique identifier manager112may assign a unique identifier value114a,114b, . . . of 1, 2, . . . , n individually to each of the n nodes.

According to an example embodiment, the mediated secure computation manager102may include a node input receiving manager116configured to receive, at the server106, an encrypted portion118a,118bof a logical circuit108from each of the nodes, the logical circuit108including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit108associated with a function, wherein each encrypted portion is encrypted based on a random number value120that is common to the plurality of nodes and unknown at the server106. For example, the gates may include AND gates, OR gates, exclusive-OR (XOR) gates, NOT OR (NOR), or NOT AND (NAND) gates which may include input wires and output wires configured to carry binary values (e.g., values of either 0 or 1). For example, the gates may be hard-wired, or may be represented by logic based on truth table representations of the gates, or combinations of any number of representations.

For example, the node input receiving manager116may receive an encrypted portion118aof the logical circuit108from the network node104a, and may receive encrypted portion118bof the logical circuit108from the network node104b. For example, the node input receiving manager116may receive an encrypted portion of the logical circuit108from the each one of n network nodes included in the network. All of the network nodes may agree on a value of the random number value120, and the random number value120may be unknown at the server106(e.g., may be kept as a secret from the server106), as discussed further below.

According to an example embodiment, the node input receiving manager116may be configured to receive, at the server106, from each one of the nodes, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit108, and one or more representations of remaining encrypted portions122a,122bof the logical circuit108, the one or more representations of remaining encrypted portions encrypted based on a hash function. For example, at each one of the nodes included in the network, the hash function may be applied to encrypt the one or more remaining portions122a,122bof the logical circuit108via hash function logic124, wherein the one or more remaining portions122a,122bmay include one or more portions of the logical circuit108other than the encrypted portion of the logical circuit108associated with the individual node, as discussed further below.

According to an example embodiment, the mediated secure computation manager102may include a portion combining engine126configured to combine the encrypted portions118a,118bof the logical circuit108received at the server106.

According to an example embodiment, the mediated secure computation manager102may include a logical circuit execution manager128configured to obtain the result110based on executing the logical circuit108, based on one or more operations of the portion combining engine126.

According to an example embodiment, the logical circuit execution manager128may be configured to obtain the result110based on verifying a correctness of each encrypted portion118a,118bof the logical circuit108and executing the logical circuit108, based on combining input values associated with the logical input wires associated with each one of the gates, based on truth tables associated with the encrypted portions118a,118bof the logical circuit108received at the server106, as discussed further below.

According to an example embodiment, the mediated secure computation manager102may include a challenge manager130configured to receive, from each one of the nodes, a timestamp value and the unique identifier value114a,114b, encrypted based on a signature associated with the node104a,104b, as discussed further below.

According to an example embodiment, the mediated secure computation manager102may include a verification manager132configured to verify the representations associated with the one or more gates based on comparing the one or more representations of the remaining encrypted portions122a,122breceived from the nodes, as discussed further below.

According to an example embodiment, the mediated secure computation manager102may include an execution result handler134configured to send the result to each of the nodes.

According to an example embodiment, the mediated secure computation manager102may include a logical circuit determination manager136configured to obtain the logical circuit108based on logic associated with a function that is configured to generate the result110based on one or more input values. For example, one or more users may determine a function that is desired to be executed on multiple inputs received from multiple parties. The logic of the function may be determined, for example, by designing a hardwired logical circuit for executing the function. As another example, program code (e.g., high level language code, assembly language code, or machine language code) may be generated that is configured to perform the function, and the program code may be compiled or assembled by a compiler or assembler to obtain a logical circuit for performing the function. For example, the logical circuit may include multiple logical gates that may include binary input wires and binary output wires.

According to an example embodiment, the mediated secure computation manager102may include a logical circuit determination manager136configured to obtain the logical circuit108based on logic associated with a function that is configured to generate the result110based on one or more input values associated with one or more of an auction, a fraud detection system, a game, a credit card clearing house system, or a competitive transaction system. For example, a credit card clearing house system may include a server that may detect fraudulent credit card transactions based on logic associated with a function configured to detect fraudulent transactions without the server receiving the actual credit card numbers for which fraudulent transactions are being made.

According to an example embodiment, the mediated secure computation manager102may include a logical circuit determination manager136configured to obtain the logical circuit108based on logic associated with a function that is configured to generate the result based on one or more input values, wherein the logical circuit108includes one or more binary gates, each binary gate configured to receive binary input values. For example, the binary gates may include logical gates such as AND, OR, XOR, NOT OR (NOR), or NAND gates.

According to an example embodiment, the system100may include the node104athat may include a network node processing engine138that may be in communication with the server106. For example, the connection may be via a local area network (LAN) or a wide area network (WAN) such as the Internet. Although not explicitly shown inFIG. 1, the network node104bmay also include a network node processing engine138that may include components similar to those discussed herein with regard to the network node104a. Similarly, the system100may include a large number of network nodes configured similarly to the network node104adiscussed herein.

According to an example embodiment, the network node processing engine138may include a node identifier manager140configured to receive, at a node included in a plurality of nodes associated with a network, a unique identifier value114a,114bassigned to the node by a server. For example, the server may include the server106discussed previously.

According to an example embodiment, the node identifier manager140may be configured to receive, at a node included in a plurality of nodes associated with a network, the unique identifier value114a,114bassigned to the node by the server106, wherein the unique identifier114a,114bis assigned based on counting values associated with a number of the plurality of nodes. According to an example embodiment, the unique identifier value114amay be assigned to the node104aby the unique identifier manager112, as discussed previously.

According to an example embodiment, the network node processing engine138may include a portion encryption manager142configured to encrypt a portion of a logical circuit108, the logical circuit108including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit108associated with a function, wherein the encrypted portion118a,118bis encrypted based on a random number value120that is common to the plurality of nodes and unknown at the server106. For example, the logical circuit may include the logical circuit108discussed previously with regard to the server106included in the mediated secure computation manager102.

According to an example embodiment, the network node processing engine138may include a node portion manager144configured to send, to the server106, the encrypted portion118a,118bof the logical circuit108. For example, a node portion manager144included in the node104amay send the encrypted portion118ato the server106, and a node portion manager144(not shown inFIG. 1) included in the node104bmay send the encrypted portion118bto the server106.

According to an example embodiment, the node portion manager144may be configured to send, to the server106, the encrypted portion118a,118b, based on one or more representations associated with one or more gates included in the logical circuit108, and one or more representations of remaining encrypted portions122a,122bof the logical circuit108, the one or more representations of remaining encrypted portions122a,122bencrypted based on a hash function, wherein the encrypted portion is encrypted based on a random number value120that is common to the plurality of nodes and unknown at the server106. For example, the random number value120may include the random number120discussed previously.

According to an example embodiment, the node portion manager144may be configured to send, to the server106, an encrypted portion118a,118bof the logical circuit108, the logical circuit including one or more gates, each gate associated with the one or more logical input wires and the one or more logical output wires, each gate represented by one or more truth tables associated with the encrypted portion118a,118bof the logical circuit108, wherein the logical circuit108is associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server.

According to an example embodiment, the network node processing engine138may include a result receiving manager146configured to receive a result from the server106based on execution of the logical circuit108, based on combining the encrypted portion118a,118bwith one or more other encrypted portions of the logical circuit108received at the server106from one or more other nodes associated with the network.

According to an example embodiment, the network node processing engine138may include a node challenge manager148configured to send, to the server106, a timestamp value and the unique identifier value114a,114b, encrypted based on a signature associated with the node104a,104b.

According to an example embodiment, the network node processing engine138may include a node logical circuit determination manager150configured to obtain the logical circuit108based on logic associated with a function that is configured to generate the result110based on one or more input values.

FIG. 2is a flowchart illustrating an example operation of the system ofFIG. 1. At202, a unique identifier value may be assigned to each one of a plurality of nodes included in a network. For example, the unique identifier value114a,114bmay be assigned to the network nodes104a,104bby the unique identifier manager112, as discussed previously.

At204, an encrypted portion of a logical circuit may be received at a server from each of the nodes, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein each encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. For example, the node input receiving manager116may receive an encrypted portion of the logical circuit108from the each one of n network nodes included in the network, as discussed previously.

At206, a result may be obtained based on executing the logical circuit, based on combining the encrypted portions of the logical circuit received at the server. For example, the logical circuit execution manager128may obtain the result110based on executing the logical circuit108, based on one or more operations of the portion combining engine126, as discussed previously.

According to an example embodiment, obtaining a result may include obtaining a result based on verifying a correctness of each encrypted portion of the logical circuit and executing the logical circuit, based on combining input values associated with the logical input wires associated with each one of the gates, based on truth tables associated with the encrypted portions of the logical circuit received at the server. For example, the logical circuit execution manager128may obtain the result110based on verifying a correctness of each encrypted portion118a,118bof the logical circuit108and executing the logical circuit108, based on combining input values associated with the logical input wires associated with each one of the gates, based on truth tables associated with the encrypted portions118a,118bof the logical circuit108received at the server106, as discussed previously.

According to an example embodiment, assigning a unique identifier value may include assigning a unique identifier value to each one of a plurality of nodes included in a network, based on counting values associated with a number of the plurality of nodes. According to an example embodiment, the method may further include receiving, from each one of the nodes, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node. For example, the server106may challenge each one of the plurality of nodes. For example, the challenge manager130may receive, from each one of the nodes, a timestamp value and the unique identifier value114a,114b, encrypted based on a signature associated with the node104a,104b, as discussed previously.

According to an example embodiment, receiving, at a server, an encrypted portion of a logical circuit may include receiving, at the server, from each one of the nodes, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the one or more representations of remaining encrypted portions encrypted based on a hash function. According to an example embodiment, the method may further include verifying the representations associated with the one or more gates based on comparing the representations of the remaining encrypted portions received from the nodes. For example, the verification manager132may verify the representations associated with the one or more gates based on comparing the one or more representations of the remaining encrypted portions122a,122breceived from the nodes, as discussed previously.

According to an example embodiment, the method may further include sending the result to each of the nodes. For example, the execution result handler134may send the result to each of the nodes.

According to an example embodiment, the method may further include obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values. For example, the logical circuit determination manager136may obtain the logical circuit108, as discussed previously.

According to an example embodiment, the method may further include obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values associated with one or more of an auction, a fraud detection system, a game, a credit card clearing house system, or a competitive transaction system.

According to an example embodiment, the method may further include obtaining the logical circuit based on logic associated with a function that is configured to generate the result based on one or more input values, wherein the logical circuit includes one or more binary gates, each binary gate configured to receive binary input values.

FIG. 3is a flowchart illustrating an example operation of the system ofFIG. 1. For example,FIG. 3may illustrate operation of the network node104aor104b. At302, a unique identifier value assigned to a node by a server may be received at the node included in a plurality of nodes associated with a network. For example, the node identifier manager140may receive the unique identifier value114aassigned to the node104aby the server106.

According to an example embodiment, the unique identifier value may be assigned based on counting values associated with a number of the plurality of nodes. For example, the unique identifier value114amay be assigned to the node104aby the unique identifier manager112, as discussed previously.

At304, an encrypted portion of a logical circuit may be sent to the server, the logical circuit including one or more gates, each gate associated with one or more logical input wires and one or more logical output wires, the logical circuit associated with a function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. For example, the portion encryption manager142discussed previously may encrypt a portion of a logical circuit108.

According to an example embodiment, sending, to the server, an encrypted portion of a logical circuit may include sending, to the server, the encrypted portion, based on one or more representations associated with one or more gates included in the logical circuit, and one or more representations of remaining encrypted portions of the logical circuit, the one or more representations of remaining encrypted portions encrypted based on a hash function, wherein the encrypted portion is encrypted based on a random number value that is common to the plurality of nodes and unknown at the server. For example, the portion encryption manager142may encrypt a portion of the logical circuit108, and a respective node portion manager144, as discussed previously, may send, to the server106, the encrypted portion118a,118bof the logical circuit108.

At306, a result may be received from the server based on execution of the logical circuit, based on combining the encrypted portion with one or more other encrypted portions of the logical circuit received at the server from the one or more other nodes associated with the network. For example, the result receiving manager146may receive a result from the server106based on execution of the logical circuit108, as discussed previously.

According to an example embodiment, the method may further include sending, to the server, a timestamp value and the unique identifier value, encrypted based on a signature associated with the node. For example, the node challenge manager148may send, to the server106, a timestamp value and the unique identifier value114a,114b, encrypted based on a signature associated with the node104a,104b.

FIG. 4depicts an example encrypted gate400associated with a logical circuit represented via a truth table according to an example embodiment. As shown in the example ofFIG. 4, binary input values402may be input via logical input wires to the gate. Encrypted output values404as shown inFIG. 4represent an encrypted output of a result generated as a result of an operation performed by the logical gate depicted byFIG. 4. For example, a value406as shown inFIG. 4may represent an encrypted version of a result of an operation on input value pairs “0, 0” that may be input to the logical gate. Similarly, values408,410, and412as shown inFIG. 4may represent encrypted versions of results of the operation performed on input value pairs “0, 1”, “1, 0” and “1,1” that may respectively be input to the logical gate.

According to an example embodiment, a protocol for generating an encrypted version of a desired logical circuit may include generating component gates associated with the logical circuit, and encrypting portions of the gates as discussed below. For example, a binary circuit C may include gates G={g1, . . . , gα} and wires W={w1, . . . ,wβ}. For example, logical input wires associated with the gates may be denoted as I={i1, . . . ,iγ} ⊂ W and logical output wires may be denoted as O={o1, . . . ,oδ} ⊂ W. For example, if the gates are binary gates (i.e., the gates have inputs that may only have one of two possible values) having two inputs, then the two input wires of each binary gate gimay be denoted as ini1and ini2and an output wire may be denoted as outi.

According to an example embodiment, for each wire wia random bit rwimay be selected, as well as two random keys kwi,0and kwi,1, such that the last bit of a binary representation of kwi,0has a value of 0 and the last bit of a binary representation of kwi,1has a value of 1. According to an example embodiment, each gate gimay be represented as a truth table. For example, opi,a,bmay denote a result of the gate gi's operation on example inputs a and b, as shown in the encrypted truth table ofFIG. 4, which depicts example encrypted results of an based on an example gate gi. One skilled in the art of data processing may appreciate that there may exist many representations of the gates other than truth tables, any of which may be utilized without departing from the spirit of the techniques discussed herein.

According to an example embodiment, a logical circuit for which each gate is encrypted as discussed above may be executed, if a user or entity that wishes to execute the logical circuit, has access to one key per input wire. The executing user or entity may thus decrypt one entry in the truth table and may then have access to one key of the output wire. Furthermore, if the executing user or entity (i.e., executing party) has access to only one key per input wire, the executing party also may only have access to one key for each other wire including the output wires, and the executing party may not be able to obtain more information.

According to an example embodiment, a secure multiparty computation (SMC) protocol may run at the application layer of a network stack. For example, the protocol may implement a specific or generic application. For example, there may exist multiple layers below in an example Transmission Control Protocol/ Internet Protocol (TCP/IP) embodiment. According to an example embodiment, techniques discussed herein may run over the Transmission Control Protocol (TCP) with point-to-point links between example systems. Thus, a “link” may be similar to a “connection” and a TCP connection may considered a point-to-point link. In contrast, for example, distributed algorithmic mechanism design (DAMD) protocols may run on the network layer.

According to an example embodiment, parties included in a computation may be identified by Internet Protocol (IP) addresses. Thus, each party may have a unique global identifier, which may be revealed during communication, and may thus break anonymity in direct (e.g., point-to-point) communication.

According to an example embodiment, techniques discussed herein may be provided in a web services environment. Further, web services may additionally provide an ability to establish secure channels via web services (WS)-Security.

According to an example embodiment, example techniques discussed herein may include an example protocol which may be divided into three example sub-protocols which may be referred to as collaborative anonymous identification, collaborative coin-flipping and collaborative computation protocols. According to an example embodiment, the collaborative anonymous identification protocol may include assigning each client or party to the computation (e.g., a network node) a unique identifier or identification number. For example, the unique identifier manager112ofFIG. 1, which may be included in the server106, may assign unique identifiers to network nodes, as discussed previously.

According to an example embodiment, the collaborative coin-flipping protocol may include selecting random numbers for garbling or encrypting the circuit for use in the collaborative computation. For example, as discussed with regard toFIG. 1, the portion encryption manager142, included in a network node, may encrypt a portion of the logical circuit108, wherein the encrypted portion118a,118bmay be encrypted based on a random number value120that is common to the plurality of nodes and unknown at the server106. For example, the node portion manager144may send, to the server106, the encrypted portion118a,118b, based on one or more representations associated with one or more gates included in the logical circuit108, and one or more representations of remaining encrypted portions122a,122bof the logical circuit108, the one or more representations of remaining encrypted portions122a,122bencrypted based on a hash function.

According to an example embodiment, the collaborative computation may include evaluating the garbled or encrypted circuit and distributing the result(s) to the clients or parties to the computation (e.g., network nodes). For example, as discussed with regard toFIG. 1, the logical circuit execution manager128may obtain the result110based on executing the logical circuit108, based on one or more operations of the portion combining engine126.

As discussed previously, the collaborative anonymous identification protocol may include assigning, by the server, to each client Ci(e.g., network nodes) a unique identifier i consecutively selected from 1 to n (e.g., for n clients or network nodes). These identifiers may be freshly assigned for each run of the example mediated SMC protocol, since the composition of clients or network nodes may change frequently. For example, new customers of the server may sign up, or old customers may leave. As a further example, not all customers may wish to be included in each run of the example mediated SMC protocol. For example, groups of customers bidding on auction items may change from one auction item to the next.

In a non-anonymous protocol the identification protocol may be unnecessary, since each client or network node could compute its identifier locally. In such a non-anonymous setting, each client could sort the static identities of all participants lexicographically and assign itself as identifier the rank of its static identifier.

According to an example embodiment, in a server model, the server may assign all identifiers to clients or network nodes, with no two clients or network nodes being assigned the same identifier (i.e., the network nodes are assigned unique identifiers, and all such identifiers are assigned). According to an example embodiment, the network setup may include loosely synchronized clocks between all clients.

Thus, according to an example embodiment, the server106may rank all static identifiers and compute the identifiers i, since the server106knows all clients (e.g., network nodes104a,104b). According to an example embodiment, the server106(referred to as server S below) may assign the unique identifiers to the clients or network nodes as follows:

Setup: Each client Cihas a constant s and the clients' clocks are loosely synchronized. The server S does not know s.

1. The server S sends i=1 and n to client C1.

2. Client C1produces a random challenge c, a timestamp timestamp and its signature (message authentication code) MAC(timestamp.c, s). Client C1also signs its identifier sig=MAC(c.1, s) and sends this signature sig and c, timestamp, MAC(timestamp.c, s) to the server S.

3. The server S sends the identifier i, n, c, timestamp, and MAC(timestamp.c, s) to each client Ci(i ∈ [2, n]) other than C1.

4. Each client Ci(except C1) verifies thatthe timestamp timestamp is freshthe signature MAC(timestamp.c, s) is correct
Then the client Cireturns MAC(c.i, s) to the server S.

According to an example embodiment, the client Cimay compute the signature locally.

According to an example embodiment, the identification protocol may have constant communication complexity (O(1)) over linearly many links (O(n)). The example protocol may be considered “network efficient.”

In the collaborative coin-flipping protocol the clients Cior network nodes may agree on a random number, such that the selection is fair, i.e., one client or network node may not dominate the selection. Furthermore, the selected r remains unknown, or secret from the server S.

One example collaborative coin-flipping protocol may be performed as follows:1. Each client Cimay commit to its input xiusing a cryptographic hash function H(x) and may send that commitment to all other clients Ci.2. After receiving all commitments each client Cimay reveal xito each other client.3. The clients Cimay set the result to the exclusive-or of all inputs:
r=⊕i=1nxi.

However, such an example protocol may use quadratically many links and have an overall communication cost that is O(n2). If the communication is channeled through the server, the messages may need to be encrypted, so that the server cannot read them. Even if a common key is used among all clients, unknown to the server, the server may still reply with a message that includes all inputs that has linear communication cost O(n) over linearly many links. Thus, a different scheme may be more efficient, at least in terms of communication cost. However, since the server is not involved in the coin-flipping, fairness may be ensured, and the commitment protocols may become unnecessary.

According to an example embodiment, a shared secret s and a common key associated with a homomorphic encryption technique may be provided. For example, if p is a large odd prime number and de mod p−1=1 with e>1, then each remod p may provide an example encryption associated with an encryption technique associated with Pohlig-Hellman. Thus, (re)dmod p=r.

Such an example encryption technique may, for example, be homomorphic in the multiplication operation
r1er2e=(r1r2)e

According to an example embodiment, a secret key (e, p) of a Pohlig-Hellman encryption scheme may be made known to all clients Ci, wherein the server S only knows p, as knowledge of p may not break the security of the example encryption.

According to an example embodiment, an example pseudo-random number generator may generate PRNGi(s) as an i-th random number, given seed s. According to an example embodiment, the example collaborative coin-flipping protocol may be performed as follows:Setup: The clients Cior network nodes may run the example collaborative anonymous identification protocol, and may be assigned unique identifiers numbered from 1 to n. Each client Cior network node has constant values s, e, p and a randomly chosen input xi. The server S has the value p.1. Each client Cimay send ci=(PRNGi(s)xi)emod p to the server S (0<xi<p).2. Upon receiving all encrypted inputs ci(0<ci<p), the server S may send to each client Cj

cj′=∏i=1j-1⁢ci⁢∏i=j+1n⁢ci⁢⁢mod⁢⁢p3. Each client Cimay set

According to an example embodiment, upon sending the values c′jthe server S may exclude all clients or network nodes from this and subsequent protocols, if they do not deliver the encrypted input, for example, within a predetermined time interval. According to an example embodiment, such an example protocol may be fair even against a server S that tries to dominate the outcome. For example, neither can the server S replay a previous encrypted value, since each client Cimay decrypt and multiply the received value with its own input, nor can the server compute the inverse of each client's encrypted input, return it and force the clients to decrypt to r=1 (or any other chosen cipher text), since each client Cimay divide the result by a different constant derived from the shared secret s, and unknown to the server S. However, if the server were able to force clients to the same identifier in the collaborative anonymous identification protocol, this assumption may not hold. Additionally, the server may refuse any ci=0 and the clients may refuse any c′j=0 resulting in r=0, as this may not provide a valid result with the constraint (xi>1).

Such an example technique may provide constant O(1) communication cost (i.e., linear in a security parameter k=O(log p)) over linearly many links (O(n)), and may thus be considered “network efficient.”

According to an example embodiment, the server S may execute the logical circuit encrypted by the clients Cior network nodes in accordance with the example collaborative computation protocol. According to an example embodiment, the collaborative computation protocol may be performed as follows:Setup: The clients Cior network nodes may execute the example collaborative coin-flipping protocol and agree on a random number r unknown to the server S.1. Using r (e.g., as a seed in a pseudo-random number generator), each client Cior network node may select random bits riand keys ki,0, ki,1and may generate the encrypted circuit. The clients Cimay set roto 0 for o ∈ O (i.e., the result may not be garbled).2. If α denotes the number of gates G={g1, . . . , gα} in the logical circuit (w log it may be possible that α mod n=0), and if

Gi={gα⁡(i-1)n+1,K,gα⁢⁢in}denote client Ci's fraction, or portion, of the logical circuit C, and xi,jdenotes the bit of Ci's input on wire j(j ∈ Ii⊂ I), then each client Cimay send Gi, H(G\ Gi) and kj,rj⊕xi,jfor j ∈ Ii⊂ I to the server S (e.g., similarly as shown in the example truth table representing an example gate giofFIG. 4).3. The server S may verify the correctness of each hash H(G\ Gi) after receiving the logical circuit portions Gi. If they all match, the technique may continue; otherwise, an example technique for detecting malicious clients may be initiated, as discussed below. Thus, the server S may execute the circuit C and directly obtain the result f. The server S may then send or distribute f to each client Ci. If an entry of a gate cannot be decrypted, the example technique for detecting malicious clients may be initiated, as discussed below.

According to an example embodiment, such an example technique may provide a network complexity of

O⁡(αn)
communication over linearly many (O(n)) links. For example practical problems associated with e-commerce providers, such as auctions (best-price, second-price, etc.) or benchmarking, the circuit size a may be linear in the number of participants: α=O(n). Then the example technique may be considered “network efficient” with a constant communication cost over linearly many links.

According to an example embodiment, maliciously modified logical circuits may be detected as discussed below. Each client Cior network node may send a hash of the logical circuit, excluding the client's fraction or portion, to the server S. The server S may verify, by recomputing the hashes, that every client did send the correct fraction or portion of G. If a client maliciously modifies its fraction (and all other clients do not collude with that client), the hashes of all other clients will be incorrect.

According to an example embodiment, in order to detect which client Cior network node misbehaved, and exclude that client from future computations, the server S may request that all clients reveal G to the server S. The server S may then exclude the malicious client (or clients) by comparing the submitted Gis to the majority. This example technique may succeed if only a minority

t<n2
of n clients is malicious.

According to an example embodiment, if a decryption of a gate entry fails (e.g., because a client Cisends a false key for its input), the server S may request that asks all clients Cireveal all ki,0. The server S may then compare the inputs to the majority again and exclude false submitters. However, a majority of malicious clients Cimay force the server to exclude an honest minority using this technique. However, at this point in the example technique no random bits rihave been revealed, and privacy against t=n−1 clients is still maintained.

According to an example embodiment, such an example procedure may be effective against rational attackers. For example, a rational attacker may be interested in obtaining the result and withholding the result from other clients Ci. Such an attacker may modify the random bits rofor all output wires wo(wo∈ O) in its fraction or portion wo∈ Gi. The attacker may obtain the correct result, since it knows ro, but all other clients (and the server S) may be oblivious to the correct result (or a fraction or portion of the correct result). In accordance with the example technique, such an attacker may be excluded if it attempts this attack, and thus its rational behavior may be expected to change to complying with the example protocol.

According to an example embodiment, revealing G in order to detect malicious clients may be avoided. For example, if each client Cisends n−1 hashes H(G1), . . . , H(Gi−1), H(Gi+1), . . . , H(Gn) to the server S, the server S may determine the malicious clients from the majority of the corresponding hashes for its fraction of G. Such an example technique may provide communication complexity O(max(alpha/n, n)) over linearly many links, which may have a lower bound of O(n) over linearly many links, and thus, may not be considered “network efficient.” However, in practice, due to the small size of the cryptographic hashes, this example technique may still be efficient.

Security may be divided into security against semi-honest and malicious attackers. For example, semi-honest attackers may follow the example techniques as described, but may keep a record of the interaction. They may then try to infer as much information as possible about the other parties' input from this record. A malicious attacker may be allowed to deviate in arbitrary ways from the example techniques. Certain attacks, such as input substitution and early abort, may not be prevented in the presence of malicious attackers.

According to an example embodiment, the example collaborative coin-flipping protocol as a secure building block may be replaced, for example, by an ideal oracle functionality.

No information regarding the parties' input other than the logical circuit and keys is revealed to any party other than the server S. According to an example embodiment, in a semi-honest model, given an n-ary function f, the example mediated SMC protocol may n−1-privately compute f in the semi-honest model if the server S is honest. For example, as all clients Cimay receive only one message in the collaboration protocol, which is the result of f, they may not infer any more information, since the result may be always revealed. Thus, no collusion of up to n−1 clients may be able to infer anything about any other client's input.

According to an example embodiment, in a semi-honest model, given an n-ary function f, the example mediated SMC protocol may 1-privately compute f. Thus, the server S may not receive any information about the inputs as well (as long as the server S does not collude with any of the clients Cior network nodes). Further, the example protocol may be secure against malicious clients as well, as discussed previously.

According to an example embodiment, given an n-ary function f, the example mediated SMC protocol may securely compute f, if t<n/2 clients are malicious and the server S is semi-honest. For example, if a minority t<n/2 of clients maliciously submit false input, an example detection technique as discussed previously may exclude the clients from the protocol. The majority may complete the protocol. Thus, a minority of clients may fail arbitrarily.

According to an example embodiment, malicious behavior by the server S may be prevented as well. The server's only chance to maliciously (and undetectably) influence the protocol may occur when sending the result. If the server S sends, with the result, a proof that indicates that the result has been computed according to the logical circuit C, the clients may be able to verify the server's honesty. Such a proof may be provided by the server sending the keys kofor the output wires (o ∈ O) to the clients Ci. According to an example embodiment, given an n-ary function f, the example mediated SMC protocol (augmented with an additional proof by the server) may 1-securely compute f in the malicious model.

As discussed below, protocol-compliant behavior (as may be included for semi-honest security) may be rational for the server. The discussion below regards situations that may involve rational behavior of the clients, i.e., each client acting in its own best interest. Thus, each client Cimay be interested in learning the correct result of the computation, and as a second preference the client may be interested in withholding the result from other clients. According to an example embodiment, the server S may acts as a mediator (e.g., providing mediated secure computation) in the protocol. For example, if the server is being paid for its services, then it may be in its best interest to deliver the correct result to the paying clients.

In the field of game theory, a strategy for client Cior server S may be considered a (possibly randomized) function of local information to actions. A joint strategy {right arrow over (σ)}=(σ1,K,σn+1) may include a tuple of strategies, one for each client Ci(σi) and one for the server S (σn+1). For example, Ui({right arrow over (σ)}) may denote player i's (server or client) expected utility, if {right arrow over (σ)} is played.

For example, {right arrow over (σ)}−imay denote a tuple that incoudes each player's strategy in {right arrow over (σ)} other than player i's. A Nash equilibrium may refer to a joint strategy, such that no player has any incentive to do anything different (given what the other players are doing). Thus, {right arrow over (σ)} may denote a Nash equilibrium, if for all players i and strategies
σ′i:Ui({right arrow over (σ)}−i, σi)≧Ui({right arrow over (σ)}−i,σ′i).

A game may have many Nash equilibria, some of which may be unrealistic in practice, and thus, game theory may provide improvements of the Nash equilibrium. As an example, in DAMD, a weakly dominant strategy may refer to a strategy that, regardless of what any other players do, earns a player a payoff at least as high as any other strategy, and, that earns a strictly higher payoff for some other players' strategies. Thus, for example, a strategy σimay be considered weakly dominant, if there exists a tuple of strategies of other players {right arrow over (σ)}′−i, such that Ui({right arrow over (σ)}−i, σi)>Ui({right arrow over (σ)}′−i, σi), and for all tuples of strategies of other players {right arrow over (σ)}′−iand all strategies τ there is a result that Ui({right arrow over (σ)}′−i, σi)≧Ui({right arrow over (σ)}′−i, τ).

According to an example embodiment, a function f may be referred to as non-cooperatively computable if there exists a dominant strategy, such that clients Cimay compute f using a trusted third party. Further, f may be considered (deterministically) non-cooperatively computable, if for any client Ci, every strategy σiand every input xiof i, either there exists an outcome of f, such that σidoes not compute that outcome, or else the outcome is oblivious to σi.

For example, r and r′ may be runs in the game tree, info(r) may be a tuple (s1, . . . , sn) where siis 1 if client Cireceives the correct result from the server, and is 0 otherwise, and if infoi(r)=si, then it may be true that:C1. ui(r)=ui(r′) if info(r)=info(r′)C2. If info(r)=1 and info(r′)=0, then ui(r)>ui(r′)C3. If infoi(r)=infoi(r′), infoj(r)≦infoj(r′) for all j≠i, and there exists some j, such that infoj(r)<infoj(r′), then ui(r)>ui(r′).

For example, compute(r) may be a tuple (s1, . . . , sn) where si=1 if client Ci's input is included in the computation, and is 0 otherwise. Further,compute(r) may denote the element-wise negation of compute(r). An example assumption on the utility function of the server may include:S1. uS(r)>uS(r′) if Σi=1ncompute(r)^inf o(r)>Σi=1ncompute(r′)^inf o(r′)S2. uS(r)<uS(r′) if Σi=1ncompute(r)^inf o(r)>Σi=1ncompute(r′)^inf o(r′)

According to an example embodiment, the rational security of the mediated SMC protocol may lead to the following: If the clients' utilities satisfy C1-C3 and the server's utility satisfies S1-S2, then example protocol compliant behavior in the example mediated SMC protocol for non-cooperatively computable functions f may be a weakly dominant strategy. For example, considering the alternative choices for a client, and assuming that a client submits false input or no input (e.g., deviating from the protocol in the malicious model), the client may then always receive a lower pay-off (no matter what the server does), since infoi(r)=0. According to an example embodiment, the server delivering the computed result to all not excluded clients only has a higher pay-off than all other strategies if all not excluded clients submit the correct input. No strategy may have a higher utility, since the maximum number of not excluded clients and the minimum number of excluded clients may learn the result.

For example, if the server S does not exclude malicious clients, the server may reduce his pay-off, since the number of clients that will learn the correct result is reduced. Consequently, excluding malicious clients may maximize the number of clients that may receive the correct result.

According to an example embodiment, if assumption S2 is omitted, then it may be rational for the server to deliver the result to all clients (even excluded ones), yet still exclude malicious clients from the computation. According to an example embodiment, this business case may be extended to interested third parties who purchase only the result. However, it may be desired for the server to punish misbehaving clients to reduce the computational cost, i.e., reduce the number of necessary reruns of the protocol.

According to an example embodiment, anonymity may be important from the perspective of the clients, server or application. For example, clients may not want to reveal their participation in the protocol. For example, the server may benefit economically from not having to reveal its customers to every client. For example, certain applications may only be possible with anonymity, e.g., multi-group benchmarking.

Anonymity may be broken by any static identifier, e.g., IP addresses or public keys. A static identifier may include a piece of information specific to an entity that does not change between multiple runs of an example protocol. Even pseudonymous identifiers such as public keys may reveal the composition of the clients by comparison of multiple runs.

An example mediated SMC protocol may efficiently provide a certain form of anonymity. The clients in the protocol may remain anonymous among each other, but the server may be known to every client. This may thus achieve all three privacy goals: clients, server, and application.The clients may not reveal their participation in the protocol (except to the server).The server does not have to reveal its customers to any client.The participants in the application (clients) remain anonymous.

Furthermore, the server may charge the clients for the service as an economic motivation. The server may know the identity of each client and may charge them, but does not have to reveal them. Thus, according to an example embodiment, the clients of the example mediated SMC protocol may remain anonymous among each other. For example, the communication in all the involved example protocols may be only between a client and the server, i.e., no clients may exchange messages directly. Thus, the communication does not break anonymity among the clients (e.g., by IP addresses). According to an example embodiment, the clients' only identifying information in the example protocol is the identifier i chosen by the server in the example collaborative anonymous identification protocol. This identifier may be known only to the client and the server and may not be shared explicitly or implicitly. All key information may be shared among all clients. Therefore the example protocols discussed previously may not break anonymity among the clients.

As an example deployment consideration, in considering auctions, it may be desirable to defend the outcome of the auction against potential claims of competitors. Privacy-preserving auctions may prevent an auctioneer from knowing the bids before (and possibly after) the protocol runs. According to an example embodiment, accusations that individual bids may have been leaked to competitors before auction closing may be avoided by use of the example techniques discussed herein. Nevertheless bidders may require confirmation of their bids, especially since in privacy-preserving auctions there may be a delay between submitting a bid and executing the protocol. For example, such a confirmation may act as a proof that the client has submitted a certain bid in case the auction shows a different result. For example, the client may not have been able to participate in the collaborative computation protocol and may have been excluded after timeout. Such a situation may not even be the client's fault, and may be due to a network problem.

As another example, the confirmation may not be abused to proof a bid that has never been submitted. A client may not be able to claim bids after the auction the client never has submitted or intended to submit. As discussed previously, collusion of a client with the server may be excluded, and the confirmation may include an example protocol between one client and the server only.

According to an example embodiment, the confirmation may include an example bit-commitment protocol, which may include two phases: First, the committer may send a commitment commit(m) to a message m. This commitment may not reveal any information about m. Second, the committer may open the commitment by sending m. The committer may not be able to open its commitment for any other message m′≠m.

According to an example embodiment, an overall example mediated SMC protocol for auctions may be performed as follows:1. All potential clients and the server S may engage in the example collaborative anonymous identification and coin-flipping protocols.2. Potential clients may submit their bids, receive confirmation and become full clients.3. All full clients may engage in the example collaborative computation protocol, setting all inputs of potential, but not full clients to 0.

According to an example embodiment, an example confirmation that a client may receive for submitting a bid may be received as follows:1. Client Cimay submit commit(kj,xi,j⊕rj), and commit(rj) for each j ∈ Ii⊂ I of its input wires Ii.2. The server S may send a timestamp timestamp and signature DS(timestamp.commit(kj,xi,j⊕rj).commit(rj)) of the commitments to the client Ci. For example, in the case of auctions, the server S may also include an auction identifier and a (static) identity of the client Ci.Upon starting the example collaborative computation protocols after the client Cihas opened the commitment to kj,xi,j⊕rj(e.g., between steps 2 and 3 shown above), the server may perform a verification of the commitment.2a. The server may verify the commitment commit(kj,xi,j⊕rj) of each client Ci. On a false commitment, the server S may exclude the client from the computation similarly as discussed previously.

In case of a dispute, the client Cimay claim its bid to a trusted third party. The clients Cimay show the two commitments (for the client's input and for the random garble bits) commit(kj,xi,j⊕rj) and commit(rj), the timestamp timestamp and their signature by the server S (DS(timestamp.commit(kj,xi,j⊕rj). commit(rj))). This may convince the trusted third party that the commitments have been made to the server S.

The client Cimay then open the commitments and the combination of kj,xi,j⊕rjand rjmay provide a means to reconstruct xi,jfor j ∈ Iiand finally xiwhich is the bid submitted in plain text. The trusted third party may then be able to verify the bid as submitted and resolve the dispute.

In a conventional common random string (CRS) model for cryptographic protocols, all parties may have access to a common random string at the start of the protocol. The example techniques discussed herein, however, may at least provide that the server may not have access to the common secret “keys” (s and e), and that the example techniques may be run multiple times with the same keys (e.g., “random string”). The example collaborative coin-flipping protocol discussed herein may select a new random number for each run of the computation protocol.

According to an example embodiment, an example key distribution technique may be provided similar to the public-key infrastructure (PKI) model. In the PKI model all parties may share the public key of a trusted root. The trusted root may then issue certificates to each party certifying their public key (by signing it with their secret key). Such certificates may be issued indirectly via chains.

The PKI model has been commonly adopted throughout the Internet, due in part, to a widespread use of the Secure Socket Layer (SSL) protocol. The SSL protocol may establish secure and authenticated channels based on PKI protocols.

According to an example embodiment, a key distribution for the example techniques discussed herein may uses a certificate authority (CA) as a dealer of the secret keys. Thus, the CA may act as a trusted third party and may not collude with the server S. One skilled in the art of data processing may appreciate that there may exist many established CAs whose business model relies on their trustworthiness and ability to keep data confidential (such as their private key).

According to an example embodiment, a client may register for a service at the server S as discussed below. For example, the server S may act (e.g., in accordance with rationality assumptions) as a service provider offering a privacy-preserving service to its clients. According to an example embodiment, each client Cimay first contact the server, and they may perform the following:1. Client Cimay obtain the certificate of the server S that includes its public key ES(·).2. Client Cimay send to the server S its identity Cialong with the registration information, e.g., its intended username, password and credit card information, encrypted with the public key of the server: ES(Ci, info).3. The server S may verify the registration information (e.g., charges the credit card) and may return over a secure channel an encrypted and signed token with timestamp:
ECA(Ci, timestamp, DS(Ci, timestamp)).

Once the client Cihas received the token, the client Cimay contact the CA and engage in the following protocol. According to an example embodiment, the server S may assist and offer a link to the CA that may forward the token automatically.1. Client Cimay send its public key ECi(·) and the token, i.e., ECA(ECi(·), ECA(Ci, timestamp, DS(Ci, timestamp))) to the CA.2. The CA may verify the freshness and signature of the token and the identity information (e.g., a supplied e-mail address). It may then issue a certificate to the client Cifor its public key: CertCA(Ci)=(Ci, ECi(·), DCA(Ci, ECi(·))). According to an example embodiment, the CA may return the certificate CertCA(Ci), and the secret keys of the protocol ECi(s, e) to Ci.

According to an example embodiment, the client Cimay now engage in the example mediated SMC protocol with the server S, as the client Cihas obtained a certificate from a common trusted root to establish a secure and authenticated channel and the secret keys (s and e) for use in the protocol. According to an example embodiment, depending on the method used to establish secure channels, the client Cimay first need to forward the certificate to the server in a separate step.

According to an example embodiment, this certificate procurement may only be performed once, when the client signs up for the service.

According to an example embodiment, an example SMC protocol may use a central server to mediate the protocol. The central server may provide a more practical and efficient network coordination of the protocol.

According to an example embodiment, such a protocol may provide security against rational players that want to obtain the correct result and as a second preference withhold it from as many other players as possible. According to an example embodiment, the server may want to deliver the correct result to as many cooperating clients as possible, for example, because the owner of the server may be paid for delivering such a correct result.

According to an example embodiment, a simple protocol for secure multi-party computation of any function may provide anonymity of the clients or parties of the computation among themselves, which may be advantageous, for example, in environments in which a service provider model may be desired. For example, the service provider may not have to reveal the identity of its customers to each other.

According to an example embodiment, a simple protocol for secure multi-party computation of any function may be based on an example single server SMC protocol.

According to an example embodiment, a simple protocol for secure multi-party computation of any function may be based on an example technique using garbled logical circuits. According to an example embodiment, a network including a plurality of network nodes may use one server to compute the function securely and privately and distribute the results to all of the network nodes. According to an example embodiment, the protocol may not protect against collusion with the server; however, it may resolve one or more dilemmas of distributed algorithmic mechanism design. For example, the “network complexity” may be low (i.e., the communication complexity of each participant may be constant for many practical problems). For example, the protocol may be completed in a fixed, constant number of rounds in the presence of rational parties or users. As another example, the clients or users of the computation may remain anonymous and unknown among each other. As yet another example, the computation may be completed with only one server.