SECURE COMPUTATION USING A SERVER MODULE

Abstract

A server module evaluates a circuit based on concealed inputs provided by respective participant modules, to provide a concealed output. By virtue of this approach, no party to the transaction (including the sever module) discovers any other party's non-concealed inputs. In a first implementation, the server module evaluates a garbled Boolean circuit. This implementation also uses a three-way oblivious transfer technique to provide a concealed input from one of the participant modules to the serer module. In a second implementation, the server module evaluates an arithmetic circuit based on ciphertexts that have been produced using a fully homomorphic encryption technique. This implementation modifies multiplication operations that are performed in the evaluation of the arithmetic circuit by a modifier factor; this removes bounds placed on the number of the multiplication operations that can be performed.

Claims

1-20. (canceled)

21. A computing device comprising: one or more processing devices configured via computer readable instructions to: generate secret keys and corresponding public keys for input wires of a circuit; determine an actual input of the computing device for a computation; send a subset of the secret keys to a second computing device, the subset of the secret keys mapping to a concealed input to the circuit, the concealed input representing the actual input in concealed form; receive a concealed output representing computation performed by the second computing device using the circuit and the concealed input; and map the concealed output to obtain an actual output of the computation.

22. The computing device of claim 21, wherein the one or more processors are configured via the computer readable instructions to: send the public keys to a third computing device, the public keys including first public keys representing a value of 0 for each input wire of the circuit and second public keys representing a value of 1 for each input wire of the circuit.

23. The computing device of claim 22, wherein the one or more processors are configured via the computer readable instructions to: for individual bits of the actual input that have a value of 0 represented by individual first public keys, select first secret keys that correspond to the individual first public keys; and for other individual bits of the actual input that have a value of 1 represented by individual second public keys, select second secret keys that correspond to the individual second public keys, the subset of the secret keys sent to the second computing device comprising the first secret keys and the second secret keys.

24. The computing device of claim 23, wherein the subset of the secret keys excludes secret keys representing 1 for the individual bits of the actual input that have a value of 0 and excludes secret keys representing 0 for the other individual bits of the actual input that have a value of 1.

25. The computing device of claim 21, the circuit comprising a Boolean circuit.

26. The computing device of claim 21, wherein the one or more processors are configured via the computer readable instructions to: obtain a translation table and use the translation table to map the concealed output to the actual output.

27. A method comprising: determining a first key pair representing a selected value and a second key pair representing another value, the first key pair comprising a first secret key and a first public key and the second key pair comprising a second secret key and a second public key; sending, from a second computing device to a first computing device, the first public key and the second public key; and sending the selected value to a third computing device as a concealed input by sending the first secret key to the third computing device.

28. The method of claim 27, further comprising: not the second secret key to the third computing device.

29. The method of claim 28, further comprising: receiving, from the third computing device, a concealed output of a computation performed by the third computing device on the concealed input; and mapping the concealed output to obtain an actual output of the computation.

30. The method of claim 29, the computation being performed by the third computing device using another concealed input provided by the first computing device, the method further comprising: receiving, from the first computing device, a translation table; and using the translation table to map the concealed output to the actual output.

31. The method of claim 30, the first secret key corresponding to a particular wire of a circuit that the third computing device uses to perform the computation.

32. The method of claim 31, the first value being 0 and the second value being 1.

33. The method of claim 32, the computation being a Boolean computation.

34. A computing device comprising: one or more processing devices configured via computer readable instructions to: designate first input wire keys to represent first values for input wires of a circuit; designate second input wire keys to represent second values for the input wires of the circuit; receive, from a second computing device, first public keys corresponding to the first values and second public keys corresponding to the second values; encrypt the first input wire keys with the first public keys to provide first ciphertexts; encrypt the second input wire keys with the second public keys to provide second ciphertexts; and provide the first ciphertexts and the second ciphertexts to a third computing device, the third computing device performing a computation using the circuit.

35. The computing device of claim 34, the first values being 0 and the second values being 1.

36. The computing device of claim 35, wherein the one or more processors are configured via the computer readable instructions to: provide a first concealed input to the computation, the second computing device providing a second concealed input to the computation, the computation being performed by the third computing device on the first concealed input and the second concealed input.

37. The computing device of claim 36, wherein the one or more processors are configured via the computer readable instructions to: determine the first concealed input by mapping a first bit of an actual input to a selected first input wire key for a first input wire of the circuit and mapping a second bit of the actual input to a selected second input wire key for a second input wire of the circuit.

38. The computing device of claim 37, wherein the one or more processors are configured via the computer readable instructions to: provide the circuit to the third computing device in garbled form.

39. The computing device of claim 38, wherein the one or more processors are configured via the computer readable instructions to: garble the circuit by garbling individual gates of the circuit using different permutations of the first input wire keys, the second input wire keys, and output wire keys for one or more output wires of the circuit.

40. The computing device of claim 39, wherein the selected first input wire key allows the third computing device to recover an individual output wire key representing part actual output of the computation, and wherein the one or more processors are configured via the computer readable instructions to: obtain the individual output wire key from the third computing device and map the individual output wire key to a bit of the actual output.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0012] FIG. 1 shows an illustrative system for using a server module to perform a processing task in a secure manner, on behalf of one or more participant modules.

[0013] FIG. 2 is a diagram that shows an illustrative action flow of the system of FIG. 1.

[0014] FIG. 3 is an overview of processing modules used in a first implementation (I) of the system of FIG. 1; in this implementation, the server module evaluates a concealed version of a Boolean circuit based on concealed inputs.

[0015] FIG. 4 is an overview of processing modules used in a second implementation (II) of the system of FIG. 1; in this implementation, the server module evaluates an arithmetic circuit based on concealed inputs, where the concealed inputs are produced by performing encryption using a key produced by a homomorphic encryption technique.

[0016] FIG. 5 shows an illustrative system associated with the first implementation.

[0017] FIGS. 6A, 6B, and 6C together form a diagram that sets forth an illustrative action flow of the system of FIG. 5.

[0018] FIG. 7 depicts features of an illustrative Boolean circuit.

[0019] FIG. 8 illustrates one manner in which a Boolean circuit can be encrypted.

[0020] FIG. 9 illustrates one manner in which a garbled Boolean circuit can be used to evaluate an input to provide an output.

[0021] FIG. 10 shows an illustrative system associated with the second implementation.

[0022] FIG. 11 is a diagram that sets forth an illustrative action flow of the system of FIG. 10.

[0023] FIG. 12 is a diagram that sets forth an action flow of a generation module, pertaining to the second implementation.

[0024] FIG. 13 is a diagram that sets forth an action flow of an encryption module, pertaining to the second implementation.

[0025] FIG. 14 is graph that shows a polynomial function; the polynomial function, in turn, is useful in explaining the operation of an encryption module and decryption module used by the second implementation.

[0026] FIG. 15 is a diagram which illustrates an action flow of a decryption module, pertaining to the second implementation.

[0027] FIG. 16 is a diagram which illustrates action flows of an addition module and a multiplication module, pertaining to the second implementation.

[0028] FIG. 17 shows illustrative processing functionality that can be used to implement any aspect of the features shown in the foregoing drawings.

[0029] The same numbers are used throughout the disclosure and figures to reference like components and features. Series 100 numbers refer to features originally found in FIG. 1, series 200 numbers refer to features originally found in FIG. 2, series 300 numbers refer to features originally found in FIG. 3, and so on.

DETAILED DESCRIPTION

[0030] The disclosure is organized as follows. Section A describes general principles of a system for performing computations in a secure manner using a server module. Section B describes a first implementation of the principles of Section A using a concealed version of a Boolean circuit and a three-way oblivious transfer technique. Section C describes a second implementation of the principles of Section A using an arithmetic circuit in conjunction with a fully homomorphic encryption technique. Section D describes illustrative processing functionality that can be used to implement any aspect of the features described in Sections A-C.

[0031] As a preliminary matter, some of the figures describe concepts in the context of one or more structural components, variously referred to as functionality, modules, features, elements, etc. The various components shown in the figures can be implemented in any manner. In one case, the illustrated separation of various components in the figures into distinct units may reflect the use of corresponding distinct components in an actual implementation. Alternatively, or in addition, any single component illustrated in the figures may be implemented by plural actual components. Alternatively, or in addition, the depiction of any two or more separate components in the figures may reflect different functions performed by a single actual component. FIG. 17, to be discussed in turn, provides additional details regarding one illustrative implementation of the functions shown in the figures.

[0032] Other figures describe the concepts in flowchart form. In this form, certain operations are described as constituting distinct blocks performed in a certain order. Such implementations are illustrative and non-limiting. Certain blocks described herein can be grouped together and performed in a single operation, certain blocks can be broken apart into plural component blocks, and certain blocks can be performed in an order that differs from that which is illustrated herein (including a parallel manner of performing the blocks). The blocks shown in the flowcharts can be implemented in any manner.

[0033] The following explanation may identify one or more features as optional. This type of statement is not to be interpreted as an exhaustive indication of features that may be considered optional; that is, other features can be considered as optional, although not expressly identified in the text. Similarly, the explanation may indicate that one or more features can be implemented in the plural (that is, by providing more than one of the features). This statement is not be interpreted as an exhaustive indication of features that can be duplicated. Finally, the terms exemplary or illustrative refer to one implementation among potentially many implementations.

[0034] A. Overview

[0035] FIG. 1 shows an overview of one illustrative system 100 that includes a server module 102 for performing a processing task on behalf of one or more participant modules. In this example, FIG. 1 shows two participant modules, namely participant module A 104 (referred to below for brevity as P.sub.A) and participant module B 106 (referred to below for brevity as P.sub.B). However, the server module 102 can provide services to any number of participant modules, including one participant module, or more than two participant modules.

[0036] The server module 102 can represent any type of computing functionality. In one case, it corresponds to a computer server that includes processing functionality, input functionality, output functionality, storage functionality, etc. In one scenario, the sever module 102 may represent a processing resource in a cloud computing system, such as a data center that provides a cloud computing service. The server module 102 can represent a single resource provided at a single location or a distributed resource that is distributed over plural locations. For example, the server module 102 can correspond to a single physical machine; alternatively, the server module 102 can represent a virtual server module that maps to corresponding underlying computing hardware in any manner.

[0037] Each participant module 104 can likewise represent any type of functionality that includes processing functionality, input functionality, output functionality, storage functionality, etc. In illustrative concrete examples, any participant module can correspond to a stationary personal computing device, a laptop or net book computing device, a personal digital assistant (PDA) computing device, a stylus-type computing device, a mobile phone device, a game console, a set-top box, and so on. FIG. 17, to be described in turn, sets forth one implementation of any processing component shown in FIG. 1.

[0038] The server module 102 is connected to P.sub.A 104 and P.sub.B 106 via any type of network 108. The network 108 may represent any type of point-to-point or multi-point coupling mechanism. In one implementation, the network 108 can correspond to a wide area network (e.g., the Internet), a local area network, or combination thereof. The network 108 can include any combination of wireless links, wired links, routers, gateways, etc., as governed by any protocol or combination of protocols. The server module 102 can represent a remote or local resource in relation to any of the participant modules.

[0039] In a first scenario, a user or organizational entity may operate P.sub.A 104 to send input data to the server module 102 over the network 108. The server module 102 performs an operation on the input data to generate output data. The server module 102 sends back the output data to P.sub.A 104.

[0040] In a second scenario, an entity associated with P.sub.A 104 and an entity associated with P.sub.B 106 may be interested in performing a processing task that involves input provided by both parties (P.sub.A 104 and P.sub.B 106). For example, consider the case in which P.sub.A 104 is associated with a first hospital and P.sub.B 106 is associated with a second hospital. Assume that both hospitals are located in the same city. These two hospitals may be interested in determining the average cost of care of a certain kind in the city, where that average is formed as function of a city-wide data set to which both hospitals contribute. This operation is an example of a joint computation that depends on the inputs of two separate entities. To perform this function, the first hospital uses P.sub.A 104 to send its patient records to the server module 102, and the second hospital uses P.sub.B 106 to send its patient records to the server module 102. The server module 102 then processes the joint inputs provided by these hospitals, produces an output result, and sends the output result to both hospitals. There are many other practical examples of a similar nature, some involving joint computations, and others involving non-joint (independent) computations.

[0041] It can be appreciated that there are security concerns associated with outsourcing the type of processing task described above. For example, hospital A may not want to divulge the details about individual patient records to either the server module 102 or the hospital B. Similarly, hospital B may not want to divulge the details about individual patient records to either the server module 102 or hospital A.

[0042] In a two-party or multi-party distributed setting (without a server), the above-described challenge is sometimes referred as the millionaire's problem. In this problem, two millionaires want to determine which one of them is richer, but neither wants to disclose his actual net worth to the other. Technology to address this situation in a two-party distributed setting is referred to as two-party computation. Technology which extends these security objectives to more than two participants is referred to as multi-party computation (MPC).

[0043] FIG. 1 graphically illustrates the security concerns outlined above by a series of dashed lines that point to potentially sensitive and confidential data. The dashed lines indicates that entity A associated with P.sub.A 104 does not want others to see its input to the computation in non-concealed form. Similarly, entity B associated with P.sub.B 106 does not want others to see its input to the computation in non-concealed form. A non-concealed form means that the information is readily discoverable. A concealed form means that it is not readily discoverable.

[0044] FIG. 2 shows an overview of an action flow 200 that explains one way in which the system 100 of FIG. 1 can satisfy the above security concerns. Section B describes a first implementation of this basic approach, while Section C describes a second implementation.

[0045] Generally, the server module 102 is treated in a conservative manner as untrustworthy (meaning, for instance, that the server module 102 cannot be trusted to maintain the confidentiality of information provided to the sever module 102). However, in some scenarios, it will be assumed that the server module 102 does not collude with any participant module to circumvent the security provisions described herein. Further, in some scenarios, it will be assumed that the parties to the joint computation are semi-honest entities at worst. This means that the entities can be expected to follow the security protocol (described below). But the entities may try to leverage the information that they discover in the course of this protocol to uncover additional information (to which they are not entitled).

[0046] In action 202, the server module 102 receives a circuit 110 that it uses to process the inputs provided by P.sub.A 104 and P.sub.B 106. At this juncture in the explanation, suffice it to say that the circuit is a collection of interconnected gates that perform the function. The first implementation uses a concealed version of a Boolean circuit, where the Boolean circuit includes a plurality of Boolean-type gates (e.g., any of AND, OR, NAND, NOR, etc.). The second implementation uses an arithmetic circuit that includes a plurality of arithmetic gates (e.g., any of addition, multiplication, etc.).

[0047] The server module 102 can receive the circuit 110 from any source. For example, in the first implementation, the server module 102 receives a garbled version of the circuit 110 from one of the participant modules, e.g., P.sub.A 104.

[0048] In action 204, each of the participant modules provides concealed inputs to the server module 102. In action 206, the server module 102 receives the concealed inputs. The concealed inputs express the inputs of P.sub.A 104 and P.sub.B 106 in a concealed form. Sections B and C will describe two different ways that this concealing operation can be performed.

[0049] In action 208, the server module 102 evaluates the circuit 110 based on the concealed inputs received in action 206. This generates an output which is also expressed in a concealed form (e.g., comprising a concealed output).

[0050] In action 210, the server module 210 sends the concealed output to the participant modules. In a symmetric case, the server module 210 sends the same output result to all of the participating modules. Otherwise, the server module 210 can send a first concealed output result y.sub.A to P.sub.A 104 and a second concealed output result y.sub.B to P.sub.B 106. In action 212, the participant modules (P.sub.A 104 and P.sub.B 106) receive the concealed output result(s). In action 214, the participant modules convert the concealed output to non-concealed form. Sections B and C will describe two ways that can be used to perform this conversion.

[0051] The system 100 thereby maintains the secrecy of sensitive information provided by the participant modules, even though the server module 102 performs a processing task that may be based on the joint inputs provided by plural participant modules. Thus, the system 100 allows the participant modules to proceed as if the server module 102 was a trusted entity, which it is not. According to another potential merit, the system 100 delegates a significant portion of processing burden to the server module 102. This reduces the processing load that is placed on the participant modules. This also reduces resource requirements placed on the participant modules.

[0052] FIG. 3 describes processing modules 302 used by different components in the system 100 of FIG. 1 in the first implementation (I). Together, these processing modules 302 describe a private (symmetric) encryption scheme for generating and operating on keys associated with a Boolean circuit (in a manner to be described below in Section B). The processing modules 302 include a generating module 304 for generating a symmetric encryption key, K. The processing modules 302 also include an encryption module 306 for performing encryption on an n-bit message m using the encryption key K to produce ciphertext c. The processing modules 302 also include a decryption module 308 for performing decryption on the ciphertext c using the encryption key K to reconstruct the message m. This encryption scheme is said to be verifiable, which means that it is possible to efficiently verify whether a ciphertext has been encrypted using a given key.

[0053] The first implementation makes use of another collection of processing modules 310 for handling a three-way oblivious transfer technique (to be described below). Together these processing modules 310 describe a public encryption scheme, e.g., involving the use of a public key (pk) to encrypt a message and a secret key (sk) to decrypt the message. Although not shown, these processing modules 310 can include a key generating module (for generating pk and sk pairs), an encryption module, and a decryption module.

[0054] FIG. 4 describes processing modules 402 that can be used by different components in the system 100 of FIG. 1 in the second implementation (II). Together, these processing modules 402 describe a private (symmetric) encryption scheme. More specifically, these processing modules 402 constitute parts of a fully homomorphic encryption technique (to be described below in detail in Section C). The processing modules 302 include a generating module 304 for generating a symmetric key K.sub.h, together with a modifier factor (where the subscript h indicates that this key is generated as part of the fully homomorphic encryption technique). The processing modules 402 also include an encryption module 406 for performing encryption on a message m (associated with an input to an arithmetic circuit) using the encryption key K.sub.h to produce ciphertext c. The processing modules 302 also include a decryption module 408 for performing decryption on the ciphertext c using the encryption key K.sub.h to reconstruct the message m. The processing modules 402 also include an addition module 410 and a multiplication module 412 for performing addition and multiplication operations in the course of evaluating an arithmetic circuit (again, to be described in detail in Section C).

[0055] B. Implementation I

[0056] FIG. 5 shows a system 500 that represents a first implementation of the system 100 shown in FIG. 1. By way of overview, the server module 502 performs processing tasks using a concealed version of a Boolean circuit. Further, the system 500 uses a three-way oblivious transfer technique to transfer inputs in concealed form from one of the participant modules to the server module 106.

[0057] The server module 502 provides processing resources for use by two parties, participant module A 504 (P.sub.A) and participant module B 506 (P.sub.B). The server module 502 is assumed to be untrustworthy, but non-colluding. In one scenario, all of the entities are assumed to be semi-honest at worst.

[0058] The component modules of the server module 502 can include: a server-participant (SP) module 508 for communicating with P.sub.A 104 and P.sub.B 106; a circuit evaluation module 510 for evaluating the Boolean circuit to generate a concealed output; an input reconstruction module 512 for reconstructing a garbled input (associated with an input from the P.sub.B 506); one or more data stores 514 for retaining information, etc.

[0059] Each participant module can include: a participant-sever (PS) communication module 516 for communicating with the server module 502; a participant-participant (PP) communication module 518 for communicating with other participant modules; a circuit generation module 520 for generating the Boolean circuit (for transfer to the server module 502); a circuit concealment module 522 for garbling the Boolean circuit; an input concealment module 524 for concealing input provided to the server module 502; an output evaluation module 526 for processing concealed output from the server module 502; one or more data stores 528 for retaining information in concealed and/or non-concealed form, etc.

[0060] FIGS. 6A, 6B, and 6C collectively show an illustrative action flow 600 that explains one manner of operation of the system 500 of FIG. 5. In this example, the operations performed by the P.sub.A 504 and the P.sub.B 506 can be reversed, e.g., where P.sub.A 504 performs the operations that are presently delegated to P.sub.B 506.

[0061] Starting with FIG. 6A, this portion of the action flow 600 describes a procedure for creating and garbling a Boolean circuit. This portion of the action flow 600 will be described in conjunction with the examples presented in FIGS. 7, 8, and 9.

[0062] In action 602, the P.sub.A 504 generates the Boolean circuit. In other implementations, other entities can create the Boolean circuit.

[0063] In action 604, the P.sub.A 504 garbles the circuit to produce a garbled circuit, G(Circuit), also more generally referred to herein as a concealed version of the Boolean circuit. Garbling consists of encrypting the contents of the Boolean circuit in a manner to be described below. In action 606, the P.sub.A 504 sends the garbed circuit G(Circuit) to the server module 502. In action 608, the server module 502 receives and stores the garbed circuit G(Circuit).

[0064] In action 610, the P.sub.A 504 produces a translation table. The translation table is used to map a garbled output of the garbled circuit to an actual (non-concealed) output result. In action 612, the P.sub.A 504 sends the translation table to P.sub.B 506 (for its eventual use in interpreting the garbled output produced by the sever module 502). In action 614, the P.sub.B 506 receives and stores the translation table.

[0065] Advancing to FIG. 7, this figure provides additional detail regarding the characteristics of a garbled Boolean circuit 702. Generally, a Boolean circuit comprises a directed acyclic graph that contains n inputs nodes, in output modes, and s gates. The gates perform Boolean operations, e.g., any combination of AND operations, OR operations, NAND operations, NOR operations, etc. Taken together, the gates map an input to an output based on some function. For example, assume that the task assigned the server module 502 is to calculate an average operating cost for two franchise stores. In this case, the Boolean circuit includes an input which receives the sales data (in garbled form) from the two stores, a collection of gates which perform the averaging function, and an output which provides the outcome of the averaging operation (in garbled form).

[0066] More specifically, consider a portion 704 of a particular Boolean circuit 702 that includes three AND gates (where the actual Boolean circuit may include many more gates that are not shown, possibly of different kinds). In one implementation, each gate includes two input wires, each for receiving a binary input (e.g., 0 or 1). Further, each gate includes an output wire for providing a binary output (e.g., 0 or 1) which reflects an output of processing performed by the gate. For example, a first gate (g.sub.1) includes input wires w.sub.11 and w.sub.12, and output wire w.sub.13. A second gate (g.sub.2) includes input wires w.sub.21 and w.sub.22, and output wire w.sub.23. Further, in this case, assume that the first gate and the second gate are members of an input layer of the Boolean circuit that receives input supplied to the Boolean circuit. Hence, the wires w.sub.11, w.sub.12, w.sub.21, and w.sub.22 are referred to as input wires, representing a subset of such input wires provided by the Boolean circuit.

[0067] A third gate (g.sub.3) receives, as its inputs, the output of gates g.sub.1 and g.sub.2. That is, the gate g.sub.3 includes input wires w.sub.13 (the output wire of the first gate g.sub.1) and w.sub.23 (the output wire of the second gate g.sub.2). For this reason, the third gate g.sub.3 is a member of a layer that this is subordinate to the input layer within the Boolean circuit.

[0068] In the garbling action 604, the P.sub.A 504 first assigns keys to each of the wires in the Boolean circuit (a portion 704 of which is shown in FIG. 7). For instance, see FIG. 8. As shown there, the P.sub.A 504 assigns two keys to each wire, a first key corresponding to binary value 0 and a second key corresponding to binary value I. For example, consider the first wire w.sub.11 of the first gate (g.sub.1). The action 604 assigns a first key K.sub.w11.sup.0 for binary value 0 and a second key K.sub.w11.sup.1 for binary value I. The P.sub.A 504 repeats this operation for all wires of all gates. In performing this operation, the P.sub.A 504 can rely on any key generation module 304 to generate random keys, for example, without limitation, the Advanced Encryption Standard (AES) algorithm, using cipher-block chaining (CBC) mode.

[0069] The keys for some wires in lower layers may be defined by the keys already chosen for respective parent layers. For example, consider the keys for gate g.sub.3. Gate g.sub.3 includes input wires which correspond to the output wires of gates g.sub.1 and g. The P.sub.A 504 has already assigned keys K.sub.w13.sup.0 and K.sub.w13.sup.1 to the first input wire and the keys K.sub.w23.sup.0 and K.sub.w23.sup.1 to the second input wire. Hence, these same keys are used as the input wires to gate g.sub.3. However, the P.sub.A 504 assigns new keys (K.sub.w33.sup.0 and K.sub.w33.sup.1) to the output wire w.sub.33 of the third gate.

[0070] In the next phase of action 604, the P.sub.A 504 garbles all of the gates in the Boolean circuit on the basis of the keys that have been assigned. The right-hand portion of FIG. 8 illustrates one way to perform this encryption for gates g.sub.1, g.sub.2, and g.sub.3. To repeat, assume that each of the gates is an AND gate. Each AND gate receives two inputs and generates an output, providing four possible input-output scenarios: inputs (0, 0) yielding an output 0; inputs (0, 1) yielding an output 0; inputs (1, 0) yielding an output 0; and inputs (1, 1) yielding an output 1. The P.sub.A 504 provides an encryption value for each such permutation based on the keys. For example, consider the first input-output permutation for gate g.sub.1. The encrypted value for this permutation is given by the nested encryption: Enc.sub.K.sub.w11.sub.0 (Enc.sub.K.sub.w12.sub.0(K.sub.w13.sup.0)). This means that the P.sub.A 504 uses the key K.sub.w12.sup.0 to encrypt the key K.sub.w13.sup.0. This produces a first result. The P.sub.A 504 then uses the key K.sub.w11.sup.0 to encrypt the first result to produce a second result. The P.sub.A 504 performs this nested encryption four times for each gate in the Boolean circuit, to yield the garbled Boolean circuit, G(Circuit).

[0071] FIGS. 6B and 6C continue by describing how the garbled circuit can be used to provide an output result. Before that more detailed explanation, however, FIG. 9 provides an overview of this operation with respect to a simplified example. Namely, in this simplified example, the server module 502 processes a garbled circuit based on a single garbled input provided by P.sub.A 504. (But in general, the server module 502 can receive and process two inputs provided by separate participant modules, e.g., as supplied by P.sub.A 504 and P.sub.B 506, respectively.)

[0072] In action 902, assume that the P.sub.A 104 identifies a non-concealed input string. Assume that this input string includes, as part thereof, the bit string 1011 to be fed to wires w.sub.11, w.sub.12, w.sub.21, and w.sub.22 of the Boolean circuit. In action 904, the P.sub.A 504 garbles the input string. This operation comprises mapping the input bits to the corresponding keys that have been assigned to these wires. This mapping process produces a garbled input that includes, in part, the keys K.sub.w11.sup.1, K.sub.w12.sup.0, K.sub.w21.sup.1, and K.sub.w22.sup.1. The P.sub.A 504 can then pass the garbled input to the server module 502.

[0073] In action 906, the server module 502 operates on the garbled input to generate a garbled output. For example, consider the isolated case of the input of keys K.sub.w11.sup.1 and K.sub.w12.sup.0 supplied to gate g.sub.1. Possession of these keys allows the server module 502 to decrypt the key for the output wire w.sub.13, namely K.sub.w13.sup.0. Similarly, possession of keys K.sub.w21.sup.1 and K.sub.w22.sup.1 allows the server module 502 to decrypt the key for the output wire w.sub.23, namely K.sub.w23.sup.1. At this point, the server module 502 has extracted the keys for the input wires to gate g.sub.3, which allows it to decrypt the key K.sub.w33.sup.0 for the output wire w.sub.33. This process continues in an iterative manner until the server module 502 extracts a final set of keys for the gates in the last layer. The server module 502 can then pass these keys to the appropriate recipient, e.g., the P.sub.A 504. This output is in concealed form because it does not reveal the actual output values corresponding to the keys. In block 908, the recipient(s) of the concealed output (e.g., P.sub.A 504) uses a translation table to map the keys in the output to associated actual bit values.

[0074] Note that a particular input string selectively empowers the server module 502 to only provide a specific output result. That is, the server module 502 is not in a position to perform computations unless it has keys corresponding to corresponding input values. In practice, the sever module 502 can use its set of received keys to try to decrypt what it can; some of these decryptions will work, while some will not. Thus, the server module 502 can proceed without knowing the meaning that is attached to each key (for example, whether a key is associated with a 0 bit or a 1 bit, etc.).

[0075] With the above introduction, the explanation continues with a description of FIG. 6B. In action 616, P.sub.A 504 garbles its own input (x.sub.A) to produce the garbed input G(x.sub.A), where x.sub.A corresponds to a string of bits. In the terminology developed in Section A, this garbled input constitutes a concealed input. As described in connection with the example of FIG. 9, garbling an input constitutes mapping keys to bits in the input. In action 618, the P.sub.A 504 sends its garbled input G(x.sub.A) to the server module 502. In action 620, the server module 502 receives the garbled input G(x.sub.A).

[0076] The next actions, enclosed by a dashed-line box, correspond to a three-way oblivious transfer technique 622. The three-way oblivious transfer technique 622 operates to handle a cooperative communication among P.sub.A 504, P.sub.B 506, and the server module 502 so as to transfer a garbed input X.sub.B from P.sub.B 506 to the server module 502, where X.sub.B corresponds to a strings of bits).

[0077] This transfer is qualified in the following manner. First, the transfer is performed in such a manner that P.sub.A 504 does not learn the input (X.sub.B) of P.sub.B 506, and vice versa. Second, the server module 502 does not learn of anyone's inputs (in non-concealed form). This task is challenging because P.sub.A 504 is the agent which has generated the encryption keys for the wires. Thus, P.sub.B 506 is asked to conceal its inputs without having knowledge of the keys. The P.sub.A 504 can transfer all the keys to the P.sub.B 506, but this would empower the P.sub.B 506 to examine more information than it is entitled to possess. P.sub.A 504 can transfer a subset of the appropriate keys to P.sub.B 506, but this would inform P.sub.A 504 of the input X.sub.B of P.sub.g 506.

[0078] Stated in another way, P.sub.B 506 seeks to select certain keys from the complete set of keys provided by P.sub.A 504. But P.sub.B 506 does not want P.sub.A 504 to know what keys it has selected. Further, P.sub.A 504 does not want to divulge to P.sub.B 506 the keys that are not being selected.

[0079] In action 624, the P.sub.B 506 begins a process by which it transfers its garbed input to the sever module 502. However, as explained above, the P.sub.B 506 cannot perform this function in as direct a manner as P.sub.A 504, because it does not possess any of the keys to perform the mapping. So, in action 624, the P.sub.B 506 begins by generating secret keys and corresponding public keys for the input wires in the Boolean circuit (using the processing modules 310 associated with a public encryption scheme). That is, for a given input wire, the P.sub.B 506 generates two key pairs. The first pair comprises a secret key sk.sub.0 and a public key pk.sub.0 (associated with bit 0). A second pair (for the same wire) comprises a secret key sk.sub.1 and public key pk.sub.1 (associated with bit 1). In action 626, the P.sub.B 506 sends just the public keys to the P.sub.A 504. In action 626, the P.sub.A 504 receives these public keys.

[0080] In action 620, the P.sub.A 504 uses the received public keys to encrypt corresponding Boolean circuit input keys (that have been previously assigned to the input wires). For example, consider the key K.sub.w11.sup.0 corresponding to input wire w.sub.11, associated with bit 0. The P.sub.A 504 encrypts this key using the corresponding public key provided by P.sub.B 506 to provide a ciphertext c. This produces a plurality of ciphertexts (c's). In action 632, the P.sub.A 504 permutes these ciphertexts into a random order. In action 634, the P.sub.A 504 transfers the permuted ciphertexts to the server module 502. In action 636, the P.sub.A 504 receives the ciphertexts.

[0081] Next, in action 636, the P.sub.B 506 sends appropriate secret keys (sk's) corresponding to its own input (e.g., X.sub.B) to the server module 504. In other words, the P.sub.B 506 does not send all of the secret keys, but just those secret keys that map to the bits of x.sub.B. For example, if a particular wire is fed an input bit of 0 by X.sub.B, then P.sub.B 506 sends the secret key for this particular wire that corresponds to the 0 bit. In action 638, the server module 504 receives the selected secret keys (sk's).

[0082] The three-way oblivious transfer technique concludes in action 642 (of FIG. 6C). Here, the server module 502 reconstructs the garbled input for X.sub.B, e.g., G(x.sub.B), based on the public keys transferred by P.sub.A 504 and the secret keys transferred by P.sub.B 506. This transfer has been performed without P.sub.A 504 or the server module 502 learning about the actual input X.sub.B. And this transfer has been performed without P.sub.B 506 receiving any keys. In practice, the server module 502 need not know how the secret keys pair up with the ciphertexts. It just tries to decrypt the received ciphertexts based on the secret keys that it receives; some attempts will be successful and others will not.

[0083] In action 644, the server module 502 finally can feed the two garbed inputs, G(x.sub.A) and G(x.sub.B) to the garbed Boolean circuit G(Circuit). Upon evaluation, this produces a garbed output G(y), which corresponds to a sequence of output keys produced by the garbled Boolean circuit. (Generally, the symbol x as used in this explanation denotes a vector having plural elements, e.g., x.sub.1, x.sub.2, . . . x.sub.n.) In one scenario, the garbled Boolean circuit produces a symmetric output, meaning that the same garbled output is delivered to each participant module. In another case, the garbled Boolean circuit produces an output that has multiple parts. One part (y.sub.A) represents an output to be sent to P.sub.A 504 and another part (y.sub.B) represents an output to be sent to the P.sub.B 506.

[0084] Accordingly, in action 646, the server module 502 sends garbed output y.sub.A to P.sub.A 504 and garbled output y.sub.B to P.sub.B 506, where y.sub.A may be the same as or different than y.sub.B. In action 648, the P.sub.A 504 receives the garbled input y.sub.A. In action 650, the P.sub.B 506 receives the garbled output y.sub.B.

[0085] In action 652, the P.sub.A 504 uses the translation table to map the garbled output y.sub.A (which comprises a series of keys) to an actual (non-concealed) bit stream. In action 654, the P.sub.B 506 performs a similar function with respect to garbled output y.sub.B.

[0086] C. Implementation II

[0087] FIG. 10 shows a system 1000 that represents a second implementation of the general principles set forth in Section A. In this case, a server module 1002 evaluates an arithmetic circuit based on concealed inputs, rather than a Boolean circuit. An arithmetic circuit includes gates that perform addition, multiplication, etc.

[0088] The server module 1002 communicates with any number of participant modules, such as, without limitation, participant module A 1004 (P.sub.A), participant module B 1006 (P.sub.B), and participant module C 1008 (P.sub.C). In one illustrative scenario, it is assumed that the server module 1002 is potentially untrustworthy, but that it does not collude with any of the participant modules.

[0089] The server module 1002 can include a number of component modules enumerated in FIG. 10. The component modules can include: a server-participant (SP) communication module 1010 for communicating with the participant modules; a circuit evaluation module 1012 for evaluating the arithmetic circuit based on encrypted inputs (e.g., numbers) received from the participant modules (e.g., using the addition module 410 and the multiplication module 412 of FIG. 4); one or more data stores 1014, etc.

[0090] Any of the participant modules can likewise include a number of component modules. The component modules can include: a participant-server (PS) communication module 1016 for communicating with the server module 1002; a participant-participant (PP) module 1018 for communicating with other participant modules; a generating module 1020 (e.g., corresponding to the generating module 404 of FIG. 4) for generating a key (and, optionally, a modifier factor ); an input concealment module 1022 for concealing (e.g., encrypting) an input (e.g., corresponding to the encryption module 406 of FIG. 4); an output evaluation module 1024 for decrypting the output of the arithmetic circuit (e.g., corresponding to the decryption module 408 of FIG. 4); one or more data stores 1026, etc.

[0091] FIG. 11 shows an illustrative action flow 1100 that describes one manner of operation of the system 1000 of FIG. 1. To facilitate explanation, FIG. 11 shows the operation of system 1000 with respect to only P.sub.A 1004 and P.sub.B 1006. However, the same principles described herein can be extended for the case in which there is more than three participant modules, or the case in which there is only one participant module.

[0092] In actions 1102 and 1104, each of the participant modules (P.sub.A 1004 and P.sub.B 1006) can run a distributed coin tossing protocol. This result in each participant module generating the same random string r.

[0093] In actions 1106 and 1108, each of the participant modules (P.sub.A 1004 and P.sub.B 1006) uses the random string r and a security parameter k to generate a key K.sub.h. This key is produced using the generating module 404 of FIG. 4 of the fully homomorphic encryption technique; as stated above, this key is assigned the subscript h to distinguish it from the key described in Section A. More specifically, each participant module generates the same key because each participant module applies the same inputs to the generating process (i.e., r and k). P.sub.A 1004 and P.sub.B 1006 also generate the same modifier factor ().

[0094] A fully homomorphic encryption technique has the following properties, defined with respect to an add (Add) operation and a multiplication (Mult) operation. To simplify, the explanation will first omit the role of the modifier factor (). The add operation, Add(c.sub.1, c.sub.2,), is a deterministic algorithm that takes as input two ciphertexts (c.sub.1, c.sub.2) and outputs a ciphertext c.sub.3 such that m.sub.1+m.sub.2 equals the decryption of c.sub.3 (using K.sub.h), where m.sub.1 is the decryption of c.sub.1 (using K.sub.h) and m.sub.2 is the decryption of c.sub.2 (using K.sub.h). The multiplication operation, Mult(c.sub.1, c.sub.2,), is a deterministic algorithm that takes as input two ciphertexts (c.sub.1, c.sub.2) and outputs a ciphertext c.sub.3 such that m.sub.1m.sub.2 equals the decryption of c.sub.3 (using K.sub.h), where, again, m.sub.1 is the decryption of c.sub.1 (using K.sub.h) and m.sub.2 is the decryption of c.sub.2 (using K.sub.h). The system 1000 can leverage this property in the manner described below. Additional information regarding the modifier factor () is provided below.

[0095] In action 1110, the P.sub.A 1004 encrypts its input x.sub.A using the key K.sub.h to produce ciphertext c.sub.A. In action 1112, the P.sub.B 1006 encrypts its input x.sub.B using the key K.sub.h to produce ciphertext c.sub.B. In actions 1114 and 1116, the P.sub.A 1004 and P.sub.B 1006 send the ciphertexts (c.sub.A, c.sub.B) to the server module 1002. The P.sub.A 1004 and P.sub.B 1006 also send the modifier factor () to the server module 1002 (although, in another embodiment, only one of the participant modules sends the modifier factor to the server module 1002, since each participant module produces the same modifier factor). In action 1118, the server module 1002 receives these ciphertexts and modifier factor(s).

[0096] In action 1120, the server module 1002 evaluates the arithmetic circuit based on the encrypted inputs received in action 1116. This produces an encrypted output, y. In action 1122, the server module 1002 sends the encrypted output y to the P.sub.A 1004 and the P.sub.B 1006. In actions 1124 and 1126, the P.sub.A 1004 and P.sub.B 1006 receive the encrypted output y.

[0097] In action 1128, the P.sub.A 1004 decrypts the encrypted output y using the key K.sub.h. Likewise, in action 1130, the P.sub.B 1006 decrypts the encrypted output using the key K.sub.h. This is possible because of the characteristics of the fully homomorphic encryption technique described above. Namely, even though the original encrypted inputs may have been transformed using several addition and multiplication operations, the same key can be used to decrypt the final output result.

[0098] Recall, based on the introduction provided with respect to FIG. 4, that the encryption scheme of the second implementation is defined with respect to five processing modules that make up the fully homomorphic encryption technique: a generating module 404; an encryption module 406; a decryption module 408; an addition module 410; and a multiplication module 412. The remaining figures in this section provide additional details regarding each of these modules, and, in doing so, further clarify the nature of the key and use thereof.

[0099] Beginning with FIG. 12, this figure describes an operation 1202 that generates a key, as performed by the generating module 404. The generating operation 1202 can be used in conjunction with the system 1000 of FIG. 10; but it can also be used in other encryption-related environments, including those environments which do not involve two-party or multi-party computation.

[0100] In action 1204, the generating module 404 provides a plurality of a values. These values correspond to locations along the x-axis of a polynomial function to be created in the encryption process. Note FIG. 14 for a graphical depiction of the a values in relation to an illustrative polynomial function. The encryption process (to be described below) will evaluate the polynomial function at these values to produce a plurality of polynomial values, e.g., p(.sub.1), p(.sub.2), p(.sub.3), etc. The generating module 404 provides the set of a values by uniformly sampling from a field , e.g., , where k is a security parameter.

[0101] In action 1206, the generating module 406 provides a set of noise indices (N). These indices identify random locations of noise values (where the noise values will be added, during encryption, to a ciphertext based on the random locations in the key K.sub.h). In one implementation, the generating module 406 can uniformly select n of these noise indices at random from a range (2k+1+n).

[0102] In action 1208, the generating module 406 forms the key K.sub.h based on a combination of a and N. In other words, the key K.sub.h(, N) includes a plurality of x-axis locations (e.g., comprising the elements of ), along with a plurality of noise indices that describe the placement of noise values (e.g., comprising the elements of N).

[0103] In action 1210, the generating module 406 generates a modifier factor Tr. The modifier factor is a parameter that is produced by at least one of the participant modules (or some other entity), and provided to the server module 1002; thus the modifier factor is considered a public parameter. As will be described in greater detail below, the server module 1002 uses the modifier factor each time it multiplies two ciphertexts together using component-wise multiplication (for reasons described below).

[0104] FIG. 13 shows operations performed by the encryption module 406. Generally, as indicated in action 1302, the encryption module 406 uses the key K.sub.h to encrypt a message m (where the message here refers to a value within some range, not an individual bit). In action 1304, the encryption module 406 begins by generating a random univariate polynomial p such that p(0)=m. In other words, the polynomial p is chosen such that the value at =0 is equal to the message to be encrypted, m. Note FIG. 14 for a graphical illustration of this concept.

[0105] In action 1306, the encryption module 406 generates the ciphertext c using the key as follows. In particular, consider the generation of an element c.sub.i of the ciphertext c. If this element corresponds to a non-noise location (e.g., i.Math.N), then c.sub.i=p(.sub.i). This means that c.sub.i equals the value of the polynomial p evaluated at .sub.i, where .sub.i is one of the elements of . If c.sub.i corresponds to a noise location (e.g., iN), then c.sub.i is set to some random noise value, s.sub.i.

[0106] FIG. 15 shows a decryption operation 1502 performed by the decryption module 408. In action 1504, the decryption module 408 is provided with a ciphertext e that includes a plurality of polynomial values at non-noise locations, interspersed with noise values. The key K.sub.h identifies the location of noise values in ciphertext c, which implicitly also identifies the locations of the p(.sub.i) values. Based on this information (namely, the and the p(.sub.i) values), the decryption module 408 performs interpolation to reconstruct the polynomial function, e.g., as shown in FIG. 14.

[0107] In action 1506, the decryption module 408 then evaluates the reconstructed polynomial function at =0 to extract the original message, e.g., p(0)=m.

[0108] FIG. 16 shows an addition operation 1602 performed by the addition module 410 and a multiplication operation 1604 performed by the multiplication module 412. The server module 1002 calls on the addition module 410 when evaluating a gate that performs addition in the arithmetic circuit. The server module 1002 calls on the multiplication module 412 when evaluating a gate that performs multiplication in the arithmetic circuit. The addition operation 1602 produces a result that can be decrypted using the same key used to produce the encrypted input values (e.g., c.sub.1 and c.sub.2). Similarly, the multiplication operation 1604 produces a result that can be decrypted using the same key used to produce the encrypted input values. These addition and multiplication operations can be performed on a component-by-component basis. For example, if each of the ciphertexts (c.sub.1 and c.sub.2) includes plural components, the addition operation involves adding components of c.sub.1 with corresponding components of c.sub.2 to produce a result. Similarly, multiplication involves multiplying components of c.sub.1 with corresponding components of c.sub.2 to produce a result, and then multiplying that result by the modifier factor .

[0109] More specifically, in the course of evaluating the arithmetic circuit, the multiplication operation 1604 modifies each multiplication result (e.g., produced by the component-wise multiplication c.sub.1c.sub.2) by the modifier factor, . The multiplication module 412 performs this task to reduce the degree of an underlying polynomial function associated with the result of multiplication. A large degree for a polynomial function is undesirable because this increases the number of samples needed to perform effective interpolation of the polynomial function (in the decryption process). This, in turn, requires the use of a large key, K.sub.h. By modifying each product of multiplication by , the sever module 1002 can keep the degree in check, e.g., without it growing in linear proportion with the number of multiplications that are performed. As a consequence, the server module 1002 need not place any a-priori bounds on the number of multiplications that can be performed in the course of evaluating the arithmetic circuit. And thus, the approach described herein overcomes limitations of a version of fully homomorphic encryption described, for example, in F. Armknecht and A. R. Sadeghi, A New Approach for Algebraically Homomorphic Encryption, Technical Report 2008/422, IACR ePrint Cryptography Archive, 2008.

[0110] There are different ways to generate the modifier factor . Generally, the modifier factor is designed to satisfy two aims. First, the modifier factor is designed to reduce the degree of an underlying polynomial function that is associated with a product of a multiplication operation. Second, the modifier factor is designed so as not to disclose any information about the construction of the key K.sub.h. More specifically, it is designed so as not to disclose the location of the noise elements in a ciphertext (as governed by N in the key K.sub.h).

[0111] One algorithm for generating the modifier factor is given by: =V.sup.N().Math.R.Math.P.Math.V.sub.N().sup.1.

[0112] 1. In this equation, let V.sub.N().sup.1 be the (2k+1)(2k+1+n) matrix that results from augmenting the inverse of the Vandermonde matrix V(d) with 0-columns at locations jN. A Vandermonde matrix is a matrix having rows that provide elements associated with a geometric progression.

[0113] 2. Let P be the projection matrix that maps (2k+1)-dimensional vectors v to (k+1)-dimensional vectors v=(v.sub.1, . . . , v.sub.2k+1, 0, . . . , 0). The (2k+1)(2k+1) matrix P is obtained by extending the (k+1)(k+1) identity matrix with k 0-columns and 0-rows.

[0114] 3. Let R be the (2k+1)(2k+1) matrix obtained by replacing the 1's in rows 2 thrown k+1 of the (2k+1)(2k+1) identity matrix with random values in F.

[0115] 4. Let V.sup.N() be the (2k+1+n)(2k+1) matrix obtained by adding random rows to the Vandermonde matrix V() at locations iN.

[0116] D. Representative Processing Functionality

[0117] FIG. 17 sets forth illustrative electrical data processing functionality 1700 that can be used to implement any aspect of the functions described above. With reference to FIGS. 1, 5, and 10, for instance, the type of processing functionality 1700 shown in FIG. 17 can be used to implement any aspect of a server module, and/or any aspect of a participant module. In one case, the processing functionality 1700 may correspond to any type of computing device that includes one or more processing devices.

[0118] The processing functionality 1700 can include volatile and non-volatile memory, such as RAM 1702 and ROM 1704, as well as one or more processing devices 1706. The processing functionality 1700 also optionally includes various media devices 1708, such as a hard disk module, an optical disk module, and so forth. The processing functionality 1700 can perform various operations identified above when the processing device(s) 1706 executes instructions that are maintained by memory (e.g., RAM 1702, ROM 1704, or elsewhere). More generally, instructions and other information can be stored on any computer readable medium 1710, including, but not limited to, static memory storage devices, magnetic storage devices, optical storage devices, and so on. The term computer readable medium also encompasses plural storage devices.

[0119] The processing functionality 1700 also includes an input/output module 1712 for receiving various inputs from a user (via input modules 1714), and for providing various outputs to the user (via output modules). One particular output mechanism may include a presentation module 1716 and an associated graphical user interface (GUI) 1718. The processing functionality 1700 can also include one or more network interfaces 1720 for exchanging data with other devices via one or more communication conduits 1722. One or more communication buses 1724 communicatively couple the above-described components together.

[0120] In closing, the description may have described various concepts in the context of illustrative challenges or problems. This manner of explication does not constitute an admission that others have appreciated and/or articulated the challenges or problems in the manner specified herein.

[0121] More generally, although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.