According to an aspect, there is provided a first node for use in a system, wherein the first node is configured to determine a plurality of keys for enabling a computation by a plurality of worker nodes in the system, wherein the computation comprises a plurality of computation parts, wherein the plurality of computation parts comprises one or more types of computation part, and wherein an output from one computation part to another computation part is a shared block; and publish the determined plurality of keys for access by at least one input node in the system, the plurality of worker nodes, and at least one recipient node in the system; wherein the plurality of keys comprises a computation part prove key for each part of the computation; a computation part verification key for each part of the computation; a shared block commitment generation key for each shared block; an input commitment generation key for each input node and computation part combination; and an output commitment generation key for each recipient node and computation part combination. A corresponding method of operating a first node is also provided.

TECHNICAL FIELD

The techniques described herein relate to computations on input data, and in particular to computations that can be performed on input data in a distributed, privacy-preserving and verifiable manner.

BACKGROUND

Existing systems for outsourcing a computation to workers in the cloud can be divided among the following three axes:Distributed: If the function to be computed as part of the computation consists of multiple parts that can be easily decoupled (i.e. they can be computed independently without much overlap in data), does the system enable the computing of these different parts independently from each other by different (committees of) workers?Privacy-Preserving: Can the function be computed without the need for workers to learn the sensitive data that they are computing on?Verifiable: Does the recipient of the computation result receive a cryptographic proof that the computation was correct (that is valid even if all workers try to disrupt the computation)? Is this auditable, i.e. can producing this proof be optional and performed after the computation, with little overhead during the computation itself?

Table 1 below shows selected existing systems/algorithms and their compliance with the above three criteria.

TABLE 1Selected Systems in Outsourcing ComputationSystemDistributed?Verifiable?Privacy?Multiparty ComputationnoNoyesPinocchionoYesnoGepettoyesYesnoTrinocchionoYesyes

Multiparty computation (MPC) refers to typical MPC algorithms, Pinocchio is as described in “Pinocchio: Nearly Practical Verifiable Computation” by B. Parno, J. Howell, C. Gentry, and M. Raykova, in Security and Privacy, 2013 IEEE Symposium on, pages 238-252, 2013, Gepetto is as described in “Geppetto: Versatile verifiable computation” by Craig Costello, Cedric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur, in 2015 IEEE Symposium on Security and Privacy, S P 2015, San Jose, Calif., USA, May 17-21, 2015, pages 253-270, 2015, and Trinocchio is as described in “Trinocchio: Privacy-Friendly Outsourcing by Distributed Verifiable Computation” by Berry Schoenmakers, Meilof Veeningen, and Niels de Vreede, in Cryptology ePrint Archive, Report 2015/480, 2015.

Traditional multiparty computation (MPC) allows the performance of a computation in a committee of multiple workers in such a way that no individual worker learns the sensitive data in the computation. Although multiple workers are involved, it is not distributed in the sense that the workers all participate to compute the same function, as opposed to computing different parts of the computation independently.

An appealing feature of some systems, is when it is “auditable”, meaning that the privacy-preserving computation can be separate in time from the production of the correctness proof. In other words, the computation can take place at one point in time, with little additional overhead relating to the proof; and only if needed later, the (computationally much heavier) task of producing a correctness proof can be undertaken. In some cases, producing the proof can even be done without any interaction between the workers.

SUMMARY

It would be beneficial to provide a system that allows the performance of a distributed privacy-preserving computation that has correctness guarantees. Moreover, performing privacy-preserving computations usually incurs a large performance overhead, particularly when also combined with correctness. Hence, it is important to enable distribution in order to reduce the computational burden on single devices and bring latency down.

Various embodiments disclosed herein present a system, methods and nodes that achieve, for the first time, verifiable, privacy-preserving and distributed computations. This allows the performance gains of distributed computing to be leveraged in settings where verifiability and privacy are useful.

According to a first specific aspect, there is provided a first node for use in a system, wherein the first node is configured to determine a plurality of keys for enabling a computation by a plurality of worker nodes in the system, wherein the computation comprises a plurality of computation parts, wherein the plurality of computation parts comprises one or more types of computation part, and wherein an output from one computation part to another computation part is a shared block; and publish the determined plurality of keys for access by at least one input node in the system, the plurality of worker nodes, and at least one recipient node in the system; wherein the plurality of keys comprises a computation part prove key for each part of the computation; a computation part verification key for each part of the computation; a shared block commitment generation key for each shared block; an input commitment generation key for each input node and computation part combination; and an output commitment generation key for each recipient node and computation part combination.

According to a second aspect, there is provided a method of operating a first node in a system, the method comprising determining a plurality of keys for enabling a computation by a plurality of worker nodes in the system, the computation comprising a plurality of computation parts, wherein the plurality of computation parts comprises one or more types of computation part, and wherein an output from one computation part to another computation part is a shared block; and publishing the determined plurality of keys for access by at least one input node in the system, the plurality of worker nodes, and at least one recipient node in the system; wherein the plurality of keys comprises a computation part prove key for each part of the computation; a computation part verification key for each part of the computation; a shared block commitment generation key for each shared block; an input commitment generation key for each input node and computation part combination; and an output commitment generation key for each recipient node and computation part combination.

According to a third aspect, there is provided an input node for use in a system, wherein the input node has one or more inputs for a computation and the computation comprises a plurality of parts, wherein the input node is configured to obtain one or more input commitment generation keys for the input node, wherein the input commitment scheme used to generate the input commitment generation keys supports reuse of input commitments in multiple computation parts; determine, using the obtained one or more input commitment generation keys, an input commitment and an input commitment opening for each of the one or more inputs; output the one or more determined input commitments; and send, to each worker node in the system that is to perform a computation part on an input, a respective secret share of the determined input commitment opening for that input.

According to a fourth aspect, there is provided a method of operating an input node in a system, wherein the input node has one or more inputs for a computation and the computation comprises a plurality of parts, wherein the method comprises obtaining one or more input commitment generation keys for the input node, wherein the input commitment scheme used to generate the input commitment generation keys supports reuse of input commitments in multiple computation parts; determining, using the obtained one or more input commitment generation keys, an input commitment and an input commitment opening for each of the one or more inputs; outputting the one or more determined input commitments; and sending, to each worker node in the system that is to perform a computation part on an input, a respective secret share of the determined input commitment opening for that input.

According to a fifth aspect, there is provided a worker node for use in a system, wherein the worker node is configured to receive, from one or more other nodes in the system, a respective secret share of one or more input commitment openings for one or more inputs to a computation part of a computation to be performed by the worker node; obtain one or more output commitment generation keys; obtain a computation part prove key for the computation part to be performed by the worker node; wherein the computation part proving scheme used to generate the computation part prove key supports reuse of commitments in multiple computation part proofs of different types of computation; compute the result of the computation part using the received respective secret share of the one or more input commitment openings, wherein the result of the computation part is computed as a privacy-preserving computation by the worker node and the one or more other worker nodes, wherein the worker node and the one or more other worker nodes form a first committee of worker nodes; determine, using the obtained one or more output commitment generation keys, an output commitment or a secret share of an output commitment and a secret share of an output commitment opening for the result of the computation part; generate, using the computation part prove key, a computation part proof or a secret share of a computation part proof for use in proving that the worker node performed the computation part correctly with respect to the one or more input commitment openings and the determined output commitment openings; and output the computation part proof or the secret share of the computation part proof.

According to a sixth aspect, there is provided a method of operating a worker node in a system, wherein the method comprises receiving, from one or more other nodes in the system, a respective secret share of one or more input commitment openings for one or more inputs to a computation part of a computation to be performed by the worker node; obtaining one or more output commitment generation keys; obtaining a computation part prove key for the computation part to be performed by the worker node; wherein the computation part proving scheme used to generate the computation part prove key supports reuse of commitments in multiple computation part proofs of different types of computation; computing the result of the computation part using the received respective secret share of the one or more input commitment openings, wherein the result of the computation part is computed as a privacy-preserving computation by the worker node and the one or more other worker nodes, wherein the worker node and the one or more other worker nodes form a first committee of worker nodes; determining, using the obtained one or more output commitment generation keys, an output commitment or a secret share of an output commitment and a secret share of an output commitment opening for the result of the computation part; generating, using the computation part prove key, a computation part proof or a secret share of a computation part proof for use in proving that the worker node performed the computation part correctly with respect to the one or more input commitment openings and the determined output commitment openings; and outputting the computation part proof or the secret share of the computation part proof.

According to a seventh aspect, there is provided a recipient node for use in a system, wherein the recipient node is configured to receive, from one or more worker nodes in the system, secret shares of one or more output commitment openings for outputs of one or more computation parts of a computation performed by the one or more worker nodes, wherein an output from one computation part to another computation part is a shared block; obtain one or more published input commitments for one or more inputs to the computation provided by one or more input nodes in the system; obtain one or more shared block commitments for one or more shared blocks provided from a first committee of worker nodes to a second committee of worker nodes; form an output of the computation from the received secret shares of the one or more output commitment openings; obtain a computation part proof or secret shares of a computation part proof for each part of the computation; obtain a computation part verification key for each part of the computation; and use the computation part proof or secret shares of the computation part proof for each part of the computation and the one or more computation part verification keys to verify that the worker nodes in each committee performed the respective computation part correctly with respect to the one or more input commitments, the one or more shared block commitments and the output commitment openings or the output commitments.

According to an eighth aspect, there is provided a method of operating a recipient node in a system, wherein the method comprises receiving, from one or more worker nodes in the system, secret shares of one or more output commitment openings for outputs of one or more computation parts of a computation performed by the one or more worker nodes, wherein an output from one computation part to another computation part is a shared block; obtaining one or more published input commitments for one or more inputs to the computation provided by one or more input nodes in the system; obtaining one or more shared block commitments for one or more shared blocks provided from a first committee of worker nodes to a second committee of worker nodes; forming an output of the computation from the received secret shares of the one or more output commitment openings; obtaining a computation part proof or secret shares of a computation part proof for each part of the computation; obtaining a computation part verification key for each part of the computation; and using the computation part proof or secret shares of the computation part proof for each part of the computation and the one or more computation part verification keys to verify that the worker nodes in each committee performed the respective computation part correctly with respect to the one or more input commitments, the one or more shared block commitments and the output commitment openings or the output commitments.

According to a ninth aspect, there is provided a computer program product comprising a computer readable medium having computer readable code embodied therein, the computer readable code being configured such that, on execution by a suitable computer or processor, the computer or processor is caused to perform the method according to the second, fourth, sixth or eighth aspects.

DETAILED DESCRIPTION OF EMBODIMENTS

FIG. 1is a block diagram of a system2in which the techniques and principles described herein may be implemented. The system2comprises a first node4(which is also referred to herein as a central authority or central authority node4), one or more input nodes6(which is also referred to herein as an ‘inputter’), a plurality of worker nodes8and one or more recipient nodes10(which is also referred to herein as a ‘verifier node’).

Broadly, the system2, particularly the central authority node4and the plurality of worker nodes8, are provided to perform a computation on one or more items of input data provided by one or more of the input nodes6. The output of the computation is provided to the one or more recipient nodes10. A verifier node (which may be the recipient node10or a different recipient node10) can confirm that the output of the computation is correct.

In some embodiments, the recipient node10may request that the computation is performed on private data owned or stored by one or more input nodes6, and the input node(s)6can provide the private data as an input to the computation without the worker nodes8or recipient node10learning the content of the data.

In some embodiments, the recipient node10may request that the computation is performed on data owned or stored by the recipient node10, in which case a particular recipient node10can operate both as an input node6and a recipient node10with respect to the computation. In these embodiments, input data may also be provided by one or more other input nodes6.

In the techniques described herein, the computation comprises two or more computation parts that can be computed separately from each other by the worker nodes8. The computation parts may be sequential (i.e. one computation part makes use of the output of the previous computation part), parallel (i.e. each computation part makes use of the input data to compute their own output), or any combination (e.g. a computation part could take an output of the previous computation part and the input data as inputs). In cases where a computation part provides its output as an input to another computation part, this output is referred to as a ‘shared block’.

Each computation part is computed in a privacy-preserving manner by a respective group of worker nodes8(referred to as a ‘committee’).FIG. 1shows two committees of worker nodes8, a first committee12comprising two or more worker nodes8that is for computing a first computation part and a second committee14comprising two or more worker nodes8that is for computing a second computation part. In some embodiments, a worker node8may be part of just one committee12,14, or a worker node8may be part of two or more committees12,14.

The plurality of computation parts that make up the computation can comprise computation parts that each relate to a different function, operation or calculation, or two or more of the computation parts can be of the same type (i.e. they relate to the same function, operation or calculation). For example, a computation could require the evaluation of ƒ(ƒ(x)), where x is the input data and ƒ is a function to be computed by a computation part. Here, both computation parts are of the same type (i.e. function ƒ). In another example a computation could require the evaluation of g(ƒ(x)), where x is the input data and ƒ and g are different functions to be computed by respective computation parts. Here, the computation parts are of different types (i.e. function f and function g).

Each of the nodes4,6,8,10are interconnected to enable data and information exchange therebetween, for example via a network, such as the Internet, although one or more of any of the nodes4,6,8,10may be co-located or otherwise interconnected via a local area network.

Each of the nodes4,6,8,10can be in the form of any type of computing device or electronic device, such as a computer, a server, a laptop, a tablet, a smartphone, etc.

FIG. 2is a block diagram illustrating the components of a node according to various embodiments of the techniques described herein. Any of the central authority node4, the input node(s)6, the worker node(s)8and the recipient node(s)10can be implemented as shown inFIG. 2

According toFIG. 2, the node includes interface circuitry20for enabling a data connection to and/or data exchange with other nodes, such as other nodes in the system2. In particular the interface circuitry20can enable a connection between the node4,6,8,10and a network, such as the Internet, via any desirable wired or wireless communication protocol. For example, the interface circuitry20can operate using WiFi, Bluetooth, Zigbee, or any cellular communication protocol (including but not limited to Global System for Mobile Communications (GSM), Universal Mobile Telecommunications System (UMTS), Long Term Evolution (LTE), LTE-Advanced, etc.).

The node further includes a processing unit22for performing operations on data and for generally controlling the operation of the node. The interface circuitry20may be connected to the processing unit22. The node further includes a memory unit24for storing any data required for the execution of the techniques described herein and for storing computer program code for causing the processing unit22to perform method steps as described in more detail below and as appropriate for the role that the node4;6;8;10has in the system2. The memory unit24may be connected to the processing unit22.

The processing unit22can be implemented in numerous ways, with software and/or hardware, to perform the various functions described herein. The processing unit22may comprise one or more microprocessors or digital signal processor (DSPs) that may be programmed using software or computer program code to perform the required functions and/or to control components of the processing unit22to effect the required functions. The processing unit22may be implemented as a combination of dedicated hardware to perform some functions (e.g. amplifiers, pre-amplifiers, analog-to-digital convertors (ADCs) and/or digital-to-analog convertors (DACs)) and a processor (e.g., one or more programmed microprocessors, controllers, DSPs and associated circuitry) to perform other functions. Examples of components that may be employed in various embodiments of the present disclosure include, but are not limited to, conventional microprocessors, DSPs, application specific integrated circuits (ASICs), and field-programmable gate arrays (FPGAs).

The memory unit24can comprise any type of non-transitory machine-readable medium, such as cache or system memory including volatile and non-volatile computer memory such as random access memory (RAM) static RAM (SRAM), dynamic RAM (DRAM), read-only memory (ROM), programmable ROM (PROM), erasable PROM (EPROM), and electrically erasable PROM (EEPROM).

It will be appreciated that a practical implementation of any of the central authority node4, input node6, worker node8and recipient node10may include additional components to those shown inFIG. 2. For example the node can include a power supply, such as a battery, or components for enabling the node to be connected to a mains power supply. As another example, the node can comprise a user interface that includes one or more components that enables a user of the node to input information, data and/or commands into the node (as appropriate), and/or enables the node to output information or data to the user of the node. The user interface can comprise any suitable input component(s), including but not limited to a keyboard, keypad, one or more buttons, switches or dials, a mouse, a track pad, a touchscreen, a stylus, a camera, a microphone, etc., and the user interface can comprise any suitable output component(s), including but not limited to a display screen, one or more lights or light elements, one or more loudspeakers, a vibrating element, etc.

According to some aspects of the techniques presented herein, verifiable computations can be made distributed. According to other aspects of the techniques presented herein, verifiable computations, can be made privacy-preserving (while also supporting multiple, mutually distrusting inputters and recipients).

FIGS. 3-6are flow charts that illustrate exemplary methods of operating a central authority node4, input node6, worker node8and recipient node10respectively to provide a verifiable, distributed and privacy-preserving computation according to the techniques presented herein.

Thus,FIG. 3is a flow chart that illustrates the steps in the method or steps in the operation of the central authority node4. The steps can be performed by the processing unit22and/or the interface circuitry20as appropriate. In some embodiments, the processing unit22can perform the steps as a result of executing suitable program code stored in the memory unit24.

In general, the central authority node4is responsible for setting up the computation system to enable the distributed, privacy-preserving and verifiable computation.

Thus, in step101, the central authority node4determines a plurality of keys for enabling a computation by the plurality of worker nodes8in the system2. The plurality of keys also enables an input node6to provide a privacy-preserving representation to an input that subsequent proofs can refer to, and enables a recipient node10to verify that the output of the computation is correct given the privacy preserving representation(s) to the input(s) and that the computation was performed correctly.

In step103, the central authority node4publishes the determined plurality of keys. Thus the central authority node4makes the plurality of keys available for any node6,8,10in the system2to access. Publishing the keys can mean storing them in a location that is accessible by the other nodes6,8,10, for example in memory unit24if that is accessible by the other nodes6,8,10, or storing them on a server or other computer that is accessible via the Internet or other network.

As described in more detail below with reference to the methods shown inFIGS. 4-6, the input node(s)6, worker node(s)8and recipient node(s)10obtain one or more of these published keys as required for their operation as part of the distributed, privacy-preserving and verifiable computation. The transfer of these (or the relevant) key(s) to the input node(s)6from the central authority node4is illustrated by signal30, the transfer of these (or the relevant) key(s) to the worker node(s)8from the central authority node4is illustrated by signal32, and the transfer of these (or the relevant) key(s) to the recipient node(s)10from the central authority node4is illustrated by signal34. In each case, it will be appreciated that in practice the key(s) may not directly pass from the central authority node4to the relevant destination node(s)6,8,10, but they may be obtained by those node(s)6,8,10from an intermediate storage node, depending on the way in which the central authority node4publishes the key(s).

The plurality of keys includes several different types of key.

The plurality of keys can include a computation part prove key for each part of the computation, and a computation part verification key for each part of the computation. The computation part prove key is to be used by a worker node8to generate a proof that a computation part performed by the worker node8was computed correctly. The computation part verification key can be used by a recipient node10along with the proof generated by the worker nodes8to verify that the computation part was performed correctly.

In some embodiments, each type of computation part has a respective computation part prove key and a respective computation part verification key (i.e. the computation part prove key and computation part verification key are different for each type of computation part). Thus, different computation parts that are of the same type (e.g. they both apply a function ƒ) can have the same computation part prove key and computation part verification key.

In some embodiments, the computation part proving scheme that the central authority node4uses to generate the computation part prove key supports reuse or sharing of commitments (a private state) in multiple computation part proofs of different types of computation. Those skilled in the art will be aware of various computation part proving schemes that satisfy this property, including, for example, the schemes described in “Geppetto: Versatile verifiable computation” and “Prover-efficient commit-and-prove zero-knowledge snarks” by Helger Lipmaa, in Cryptology ePrint Archive, Report 2014/396, 2014. Further details are not otherwise provided in this part of the description.

The plurality of keys can also include one or more commitment generation keys. In some embodiments, the plurality of keys can also include one or more corresponding commitment verification keys. The commitment generation keys are used to generate commitments for a data element, and commitment openings for the data element. As is known, a commitment is a secret statement by a party as to the value of a data element (e.g. an input, a shared block, an output), and the commitment opening is the value that was originally committed to and information that enables a party that receives the commitment and commitment opening to verify that the value of the data element is correct (i.e. it corresponds to the value that was originally committed to). It will be appreciated that in some embodiments of the present disclosure, a data element (input/shared block/output) can be a vector.

The commitment generation keys can be divided into commitment generation keys (which are also referred to herein as ‘commitment evaluation keys’) for inputs (i.e. data elements) from input node(s)6, commitment generation keys for shared blocks that are output from one computation part and input into another computation part, and commitment generation keys for output(s) from the computation to a recipient node10. Likewise for the commitment verification keys.

For the purposes of the discussion of the techniques described herein, the central authority node4can be considered to determine a shared block commitment generation key for each shared block in the computation, a shared block commitment verification key for each shared block, an input commitment generation key for each computation part that an input node6is to provide an input to, a corresponding input commitment verification key for each input commitment generation key, an output commitment generation key for each computation part that a recipient node10is to receive an output from, and a corresponding output commitment verification key for each output commitment generation key.

In some embodiments, the input commitment scheme used to generate the input commitment generation keys supports reuse of input commitments in multiple computation parts. That is, input commitments generated by an input node6using the input commitment generation keys are not dependent on the computation part that the input is to be provided to. Those skilled in the art will be aware of various commitment schemes that satisfy this property, including, for example, “Prover-efficient commit-and-prove zero-knowledge snarks”, and “ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data” by Michael Backes, Manuel Barbosa, Dario Fiore and Raphael M. Reischuk in Cryptology ePrint Archive: Report 2014/617. Further details are not otherwise provided in this part of the description.

In some embodiments, the output commitment scheme used to generate the output commitment generation keys supports reuse of output commitments in multiple computation parts. That is, output commitments generated by a worker node8using the output commitment generation keys are not dependent on the computation part that the output (i.e. shared block) is output from. Those skilled in the art will be aware of various commitment schemes that satisfy this property, including, for example, “Prover-efficient commit-and-prove zero-knowledge snarks”. Further details are not provided in this part of the description.

In some embodiments, the commitment generation keys can be the same for each type of node6,8,10, and the commitment verification keys can be the same for each type of node6,8,10. In other embodiments, the commitment generation keys and the corresponding commitment verification keys can be different for each type of node6,8,10. In other embodiments, the commitment generation keys and the corresponding commitment verification keys can be different for each node6,8,10in the system (i.e. different for each of the worker nodes8, etc.). In yet other embodiments, for each input node6, there can be a respective commitment generation key (and corresponding commitment verification key) for each computation part that the input node6is to provide an input to in the computation.

In some embodiments, the computation requires or include one or more public parameters (i.e. parameters that are not private). Examples of public parameters include a minimally desired accuracy for an estimator, or a maximum number of spelling mistakes for an exact search query. In these embodiments, the central authority node4can determine the values of these public parameters, and publish them for access by any of the nodes6,8,10in the system2.

Turning now toFIG. 4,FIG. 4is a flow chart that illustrates the steps in the method or steps in the operation of an input node6. The steps can be performed by the processing unit22and/or the interface circuitry20as appropriate. In some embodiments, the processing unit22can perform the steps as a result of executing suitable program code stored in the memory unit24.

The input node6has one or more inputs for a computation that is to be performed. An input may comprise any data that is required for a computation. The input may be private to the input node6(e.g. the data may be secret), or the input node6may not otherwise wish to reveal the input that it has provided to the computation (e.g. the input node6may select a subset of its available data for the computation, but does not want to reveal which data was selected).

As noted above, the computation comprises a plurality of parts. The computation parts may each be of a different type, of the same type or a combination (e.g. some computation parts are of the same type and other computation parts are of a different type). The input node6may provide an input to more than one computation part in the computation. In that case, the input provided by the input node6may be the same or different for each computation part. In embodiments where the system2comprises a plurality of input nodes6that each provide one or more inputs to a particular computation, multiple input nodes6may provide an input to any particular computation part.

In a first step, step201, the input node6obtains one or more input commitment generation keys for the input node6. As described above with reference to the central authority node4, the central authority node4generates the input commitment generation keys and publishes them. Thus, in step201, the input node6accesses the published input commitment generation keys (indicated or represented by signal30inFIG. 1).

Where the input node has a plurality of inputs for the computation, the input node6may obtain a respective input commitment generation key for each of the inputs (i.e. the central authority node4has generated a respective input commitment generation key for each of the inputs), or alternatively the input node6may obtain a single input commitment generation key for use with each of the plurality of inputs (i.e. the central authority node4has generated a single input commitment generation key for use with any input). As another alternative, the input node6may use a particular input commitment generation key for two or more inputs, and another input commitment generation key for one or more other inputs.

In embodiments where the input node6is to provide an input to two or more computation parts, the input node6may obtain a respective input commitment generation key for each of the two or more computation parts (i.e. the central authority node4has generated a respective input commitment generation key for each of the computation parts that the input node6is to provide an input to).

When the input node6is to provide an input to the computation, in step203, the input node6determines an input commitment and an input commitment opening for each of the one or more inputs using the obtained one or more input commitment generation keys.

In some embodiments, the input commitment scheme used to generate the input commitment generation keys supports reuse of input commitments in multiple computation parts. That is, input commitments generated by an input node6using the input commitment generation keys are not dependent on the computation part that the input is to be provided to.

In step205, the input node6outputs the one or more determined input commitments. In particular, the input node6makes the one or more input commitments available for at least the recipient node(s)10in the system2. Where there are multiple recipient nodes10, the input node6can publish the one or more input commitments. Where there is a single recipient node10, the input node6can send the one or more input commitments to the recipient node10. Publishing the one or more input commitments can mean storing them in a location that is accessible by the recipient (and potentially other) nodes4,6,8,10, for example in memory unit24if that is accessible by the other nodes4,6,8,10, or storing them on a server or other computer that is accessible via the Internet or other network.

In step207(which can happen before, at the same time, or after step205), for a particular input to the computation, the input node6sends a respective secret share of the input commitment opening for that input to each of the worker nodes8in the system2that are to perform a computation part on that input. Thus, if the first committee12of worker nodes8are to perform a computation part on the input, the input node6sends a respective secret share of the input commitment opening for that input to each of the worker nodes8in the first committee12. This is indicated inFIG. 1by signal36from the input node(s)6to the first committee12.

Thus, after determining the input commitment opening(s) in step203, the input node6determines a plurality of secret shares of each input commitment opening, with a respective secret share being generated for each worker node8in the committee that is to use the input in a computation part. Thus, the worker nodes8in the committee are able to reconstruct the input commitment opening as part of the computation part (using MPC techniques so that no individual worker node8is able to find out the input commitment opening directly).

In the event that the input node6is to provide the input (or another input) to another computation part (e.g. performed by the second committee14inFIG. 1), the input node6can provide respective secret shares of the input commitment opening to each of the worker nodes8in that second committee14, which is indicated by signal36from input node6to second committee14inFIG. 1. In that case, the input commitment opening provided to the first committee12can be the same as the input commitment opening provided to the second committee14.

As noted below, the worker nodes8can also make use of the input commitment(s), and signal36inFIG. 1also represents the transfer of the input commitment(s) to the worker nodes8.

Also as noted below, the recipient node(s)10make use of the input commitment(s), and signal37inFIG. 1represents the transfer of the input commitment(s) to the recipient node(s)10.

Turning now toFIG. 5,FIG. 5is a flow chart that illustrates the steps in the method or steps in the operation of a worker node8that is part of a committee with one or more other worker nodes8, and that is to perform a computation part of the computation. In general (and unless otherwise indicated below)FIG. 5applies the operation of a worker node8in performing a computation part on an input from an input node6and to the operation of a worker node8in performing a computation part on a shared block output from another committee that performed a different computation part, or to any combination thereof (e.g. to the operation of a worker node8in performing a computation part on an input from an input node6and a shared block output from another committee, etc.). Also as unless otherwise indicated below,FIG. 5applies the operation of a worker node8in performing a computation part to generate an output for a recipient node10and to the operation of a worker node8in performing a computation part to generate a shared block for use by another committee that is to perform a different computation part on the shared block, or to any combination thereof (e.g. to the operation of a worker node8in performing a computation part to generate an output for both a recipient node10and another committee that is to perform a different computation part on the output (shared block)).

It will be appreciated that each worker node8in a committee will operate as shown inFIG. 5and described below. The steps can be performed by the processing unit22and/or the interface circuitry20as appropriate. In some embodiments, the processing unit22can perform the steps as a result of executing suitable program code stored in the memory unit24.

In a first step, step401, the worker node8receives a respective secret share of one or more input commitment openings for one or more inputs to a computation part of a computation to be performed by the worker node. As indicated above, the input commitment opening may be a commitment opening from an input node6relating to an input by the input node6(indicated by signal36inFIG. 1), or it may be a commitment opening of a shared block commitment from another committee of worker nodes8(indicated by signal38inFIG. 1).

The worker node8also obtains one or more output commitment generation keys (step403). As described above with reference to the central authority node4, the central authority node4generates one or more shared block commitment generation keys and one or more output commitment generation keys and publishes them. Thus, in step403, the worker node8accesses the published commitment generation keys (indicated or represented by signal32inFIG. 1). Where the worker node8is to provide the output of the computation part to a recipient node10, the worker node8obtains the output commitment generation key(s) relevant to that computation part/recipient node10, and where the worker node8is to provide the output of the computation part to another committee of worker nodes8, the worker node8obtains the shared block commitment generation key(s) relevant to that computation part/next committee of worker nodes8.

As described above, in some embodiments, the output commitment scheme the central authority node4used to generate the output commitment generation keys supports reuse of output commitments in multiple computation parts.

The worker node8also obtains a computation part prove key for the computation part to be performed by the worker node8(step405). As noted above, the computation part proving scheme used by the central authority node4to generate the computation part prove key supports reuse of commitments in multiple computation part proofs of different types of computation. Thus, in step405, the worker node8accesses the published computation part prove key(s) (indicated or represented by signal32inFIG. 1).

Next, the worker node8computes the result of the computation part using the received respective secret share of the one or more input commitment openings (step407). The worker node8computes the result of the computation part as a privacy-preserving computation with the one or more other worker nodes in the committee for that computation part. Those skilled in the art will be aware of various type of privacy-preserving computation techniques that can be used to perform the computation part, and further details are not provided herein.

Performing the computation part results in one or more outputs (which as noted above may be or include an output for a recipient node10and/or a shared block for another committee of worker nodes8), and the worker node8determines a secret share of an output commitment (or the output commitment itself) and a secret share of an output commitment opening for the result of the computation part (step409). These are generated using the one or more output commitment generation keys obtained in step403.

In some embodiments, the worker node8can output the output commitment or the secret share of the output commitment and/or the secret share of the output commitment opening. These can be output to another committee of worker nodes8(as indicated by signal38inFIG. 1) and/or a recipient node10(as indicated by signal42from the second committee14inFIG. 1) as appropriate. In particular, in the case where the output of the computation part is a shared block to be input to another computation part, the output commitment or secret share of the output commitment is sent to the recipient node(s)10, and the secret share of the output commitment opening can be sent to the next committee of worker nodes8. In the case where the output of the computation part is an output of the overall computation, the output commitment or secret share of the output commitment and the secret share of the output commitment opening is sent to the recipient node(s)10. The outputting can include publishing the secret share of the output commitment.

In some embodiments, the worker node8can determine the output commitment by cooperating with the other worker nodes8in the committee to determine the output commitment (e.g. by combining their respective secret shares of the output commitment), and the worker node8can output the determined output commitment. In this case, the determined output commitment can be published by the worker node8(with publishing being as described above) or sent to the recipient node(s)10.

Next, in step411, the worker node8generates, using the computation part prove key, a computation part proof or a secret share of a computation part proof for use in proving that the worker node8(or committee of worker nodes8) performed the computation part correctly with respect to the one or more input commitment openings used in the computation part and the output commitment openings that were determined as a result of the computation part.

Finally, in step413, the worker node8can output the computation part proof or the secret share of the computation part proof. The computation part proof or the secret share of the computation part proof can be output to the recipient node(s)10, as indicated by signal40inFIG. 1for the first committee12and signal42inFIG. 1for the second committee14. The determined computation part proof or the secret share of the computation part proof can be published by the worker node8(with publishing being as described above) or sent to the recipient node(s)10.

In some embodiments, in step411the worker node8can determine a secret share of the computation part proof and cooperate with the other worker nodes8in the committee to determine the computation part proof (e.g. by combining their respective secret shares of the computation part proof), and the worker node8can output the determined computation part proof in step413.

It will be appreciated that step411may be performed when (or around the same time as) steps407and409are performed. Alternatively, step411(and indeed optionally step409) may be performed when a computation proof is required (which may be any time after the computation has been performed, e.g. days or weeks after), and thus step411can be performed in response to a request for a proof to be provided.

In some embodiments, the worker node8also performs the following steps relating to commitments to the input(s) to the computation part, before proceeding with the computation of the result of the computation part in step407.

Firstly, the worker node8can obtain one or more input commitments for the one or more inputs. The input commitments are either published by the input node(s)6or provided from another committee, either as a published (shared block) commitment or in the form of respective secret shares of the (shared block) commitment sent by the worker nodes8in the other committee.

The worker node8performs a check with the one or more other worker nodes8in the committee that the secret shares of the one or more input commitment openings received in step401correspond to the one or more input commitments. The worker node8performs this check interactively in a privacy-preserving way with the other worker nodes8in the committee. In some embodiments, this check makes use of the input commitment generation key (in which case the worker node8obtains this key from the central authority node4in a similar way to the other keys described above), and essentially the input commitment is rebuilt from respective secret shares of the input commitment openings as part of a multiparty computation and the worker nodes8check that the rebuilt input commitment matches the published input commitment.

If the check is passed (i.e. if the rebuilt input commitment(s) correspond to the one or more input commitments), then worker node8can proceed with step407. If the check is failed, the worker node8/committee can output an error to any of the nodes4,6,8,10in the system indicating that the check has failed.

Turning now toFIG. 6,FIG. 6is a flow chart that illustrates the steps in the method or steps in the operation of a recipient node10that is to receive the output of the computation (or an output of the computation if there are multiple outputs that are provided to different recipient nodes10).

The steps inFIG. 6can be performed by the processing unit22and/or the interface circuitry20as appropriate. In some embodiments, the processing unit22can perform the steps as a result of executing suitable program code stored in the memory unit24.

In step501, the recipient node10receives secret shares of one or more output commitment openings for outputs of one or more computation parts in the computation (e.g. as shown by signal42inFIG. 1).

The recipient node10obtains one or more published input commitments for one or more inputs that were provided by one or more input nodes6(step503). The provision of the input commitments from the input node(s)6to the recipient node(s)10is shown by signal37inFIG. 1and as described above.

The recipient node10also obtains one or more shared block commitments for one or more shared blocks provided from a first committee12of worker nodes8to a second committee14of worker nodes8(step505). The provision of the shared block commitments to the recipient node(s)10is shown by signal40inFIG. 1.

It will be appreciated that steps501,503and505can occur at generally the same time and/or in any order. Alternatively, step505can occur at the same time as step509below.

In step507, the recipient node10forms an output of the computation from the received secret share of the one or more output commitment openings. This step comprises reconstructing the one or more output commitment openings from the received secret shares.

When the recipient node10is to verify that the computation has been performed correctly, the recipient node10obtains a computation part proof or secret shares of a computation part proof for each part of the computation from the worker nodes8in the system2(step509). As noted above,FIG. 1shows these computation part proofs or secret shares of a computation part proof being provided to the recipient node10in signals40and42.

As part of the verification, the recipient node10obtains a computation part verification key for each part of the computation (step511). As described above, the computation part verification key(s) are determined and published by the central authority node4and signal34inFIG. 1represents the computation part verification key(s) being provided to the recipient node10. In some embodiments, there is a single computation part verification key for all parts of the computation (or, put another way, the computation part verification keys for the computation parts are the same). In alternative embodiments, there is a respective computation part verification key for each type of computation part (e.g. there is a shared or common verification key that is used by all computation parts that execute the same function).

In step513, the recipient node10then uses the computation part proof or secret shares of the computation part proof for each part of the computation and the one or more computation part verification keys to verify that the worker nodes8in each committee performed the respective computation part correctly with respect to the one or more input commitments, the one or more shared block commitments and the output commitment openings or the output commitments.

Thus, the recipient node10is able to verify whether or not the computation has been performed correctly.

In some embodiments, the computation provides outputs to one or more other recipient nodes10. In that case, as part of the verification of the computation, the recipient node10obtains one or more published output commitments for one or more outputs from the computation that are provided to those other recipient nodes. These output commitments were published by the relevant committees of worker nodes8, and so can be accessed by the recipient node10.

In some embodiments, the recipient node10checks the correctness of the various commitments generated through the computation before forming (or trusting) the output of the computation.

Thus, the recipient node10obtains a shared block commitment verification key for each shared block commitment, an input commitment verification key for each published input commitment and an output commitment generation key for each received output commitment opening. As noted above, these keys are determined and distributed (e.g. published) by the central authority node4, and the recipient node10obtaining these keys is represented by signal34inFIG. 1.

The recipient node10then checks the correctness of the published input commitments and the shared block commitments using the input commitment verification key and the shared block commitment verification key, respectively.

If the check is passed, then the recipient node10can proceed with step507and form the output of the computation.

In embodiments where the computation provides outputs to one or more other recipient nodes10, before forming the output in step507, the recipient node10can obtain one or more published output commitments for the one or more outputs provided to the other recipient node(s)10, obtain an output commitment verification key for each of the one or more published output commitments (e.g. obtain from the central authority node4), and check the correctness of the published output commitment(s) using the output commitment verification key(s). If the correctness check is passed, the recipient node10can proceed with forming the output of the computation in step507.

As another check before forming the output in step507, the recipient node10can check that the one or more output commitment openings from the computation correspond to the one or more published output commitments. If the check is passed, the recipient node10can proceed with forming the output of the computation in step507.

If any of the above checks are failed, then the recipient node10can output an error indication.

As noted above, the methods inFIGS. 3-6are exemplary methods of providing a verifiable, distributed and privacy-preserving computation. Some more detailed implementations are provided below. In particular, the following description provides an embodiment, implementation or instantiation based on Trinocchio/Geppetto, and an embodiment, implementation or instantiation based on a commit-and-prove scheme.

Various embodiments may be realised as an extension to Trinocchio. The Trinocchio system may include the following entities performing the following tasks. It will be appreciated that in various embodiments, any party (node) may arbitrarily combine the tasks of inputter (input node6), worker (worker node8), and recipient (recipient node10). As discussed, the computation proof may be built after-the-fact to achieve auditability of the computation. Below, some operations are annotated that may be performed after-the-fact when a proof is desired.

The central authority—This performs a one-time set-up of the computation system. This results in: public parameters; a computation prove key and computation verification key; for each inputter, an input commitment generation key and an input commitment verification key; and for each recipient, an output commitment evaluation key and an output commitment verification key. All keys are published. In various cases, “published” may mean disclosed (e.g., on a website) so that all parties in the system can access the information.

Inputter—The inputter provides input to the computation. An inputter uses the input commitment generation key to generate an input commitment and an input commitment opening. The input commitment is published and the input commitment opening is provided as input to the workers.

Worker—The worker performs the computation. Using multiparty computation, the workers perform the following tasks in a privacy-preserving way: (i) checking that the input commitment openings provided by the inputters correspond to the published input commitments; (ii) computing the result of the computation; (iii) using the output commitment evaluation key to generate output commitments and commitment openings for each recipient; (iv) publishing the output commitments, and disclosing the output commitment openings to the relevant recipients. When a proof is desired, the computation prove key is used to generate a computation proof showing that the computation was performed correctly. The proof is published.

Recipient—The recipient receives the computation output. The recipient receives output commitment opening from the workers, checks that it corresponds to the published output commitment, and checks correctness of all input commitments and output commitments using the input/output commitment verification keys. When a proof is desired, the recipient checks correctness of the computation proof with respect to these commitments and the computation verification key. If all checks pass, the recipient accepts the received output commitment opening as the computation result.

The following adaptation of Trinocchio to distributed computations according to the techniques described herein is discussed with reference toFIG. 7.FIG. 7shows an exemplary system similar to that shown inFIG. 1, and comprises a central authority4, an inputter6, a worker8and a recipient10.FIG. 7also shows some of the information/data exchanged between the nodes4,6,8,10.

As noted above, in a distributed computation, a computation is split into different parts, with outputs of some parts used as inputs of other parts. This is referred to as “shared block” between computation parts.

Central authority4inFIG. 7—Central authority4performs a one-time set-up of the computation system (e.g. as shown in step101above). This results in: public parameters; for each computation part, a computation part prove key; a (common) computation verification key; for each shared block, a shared block commitment generation key and a shared block commitment verification key; for each inputter/computation part combination, an input commitment generation key and an input commitment verification key; and for each recipient/computation part combination, an output commitment generation key and an output commitment verification key. All keys are published (e.g. as in step103above).

Inputter6inFIG. 7—The inputter6provides input to the computation parts. An inputter6uses the input commitment generation keys to generate input commitments and input commitment openings (e.g. as in step203above). The input commitments are published (e.g. as in step205above) and the input commitment openings are provided as input to the relevant workers8(e.g. as in step207above).

Worker8inFIG. 7—The worker8performs a computation part. Using multi-party computation in a committee12,14, the workers8perform the following tasks in a privacy-preserving way:

Checking that the input commitment openings provided by the inputters6correspond to the published input commitments;

Computing the result of the computation part (e.g. as in step407above)

Using the output commitment generation key to generate output commitments and commitment openings for each recipient10(e.g. as in step409above). The output commitments are published, and the output commitment openings are disclosed to the relevant recipients10(although this only applies if the output goes to the recipient10).

Using the shared block commitment evaluation key to generate shared block commitments and commitment openings for each recipient. The shared block commitments are published, and the shared block commitment openings are disclosed to the relevant recipients (although this only applies if the output is processed further by another computation part).

When a proof is desired: using the computation part prove key to generate a computation part proof showing that the computation part was performed correctly (e.g. as in step411above). The proof is published (e.g. as in step413above).

Recipient10inFIG. 7—The recipient10receives the computation output. The recipient10receives output commitment openings from the workers8(e.g. as in step501above); checks that they correspond to the published output commitments; and checks correctness of all input commitments, shared block commitments, and output commitments using the input/shared block/output commitment verification keys. When a proof is desired: the recipient10checks correctness of the computation part proofs with respect to the relevant commitments and the computation verification key (e.g. as in step513above). If all checks pass, the recipient10accepts the received output commitment openings as the computation result.

Detailed Implementation of a Trinocchio/Geppetto-Based Implementation

In the following numbered sections, a protocol for verifiable computation is discussed that is based on quadratic arithmetic programs (QAPs) from “Pinocchio: Nearly Practical Verifiable Computation” (referred to below as [PHGR13]), “Trinocchio: Privacy-Friendly Outsourcing by Distributed Verifiable Computation” (referred to below as [SVdV15]) and “Geppetto: Versatile verifiable computation” (referred to below as [CFH15]).

1.1 Modelling Computations as Quadratic Arithmetic Programs

A quadratic arithmetic program (QAP) over a field F is a triple (V, W, Y)∈Fd×k, where d is called the degree of the QAP and k is called the size. A vector {right arrow over (x)}∈Fkis said to be a solution to the QAP if (V·{right arrow over (x)})×(W·{right arrow over (x)})=Y·{right arrow over (x)}, where x denotes the pairwise product.

Fix k. Let S⊂{1, . . . , k}. The span of S is defined, denoted FSto be the set of vectors {right arrow over (x)} with nonzero entries only in the indices of S. I.e. FS={{right arrow over (x)}∈Fk|{right arrow over (x)}i=0∀i∉S}.

Fix a QAP Q. A commit-and-prove scheme is defined that allows pairwise addition, and proofs that: 1) given a set S, a commitment is valid with respect to S, i.e. it is a valid commitment to a vector {right arrow over (x)} and {right arrow over (x)} is in the span of S; 2) a commitment is to a vector {right arrow over (x)} that is a solution to Q.

Assume discrete logarithm groups G1, G2, G3with a pairing e: G1×G2→G3for which the (4d+4)-PDH, d-PKE and (8d+8)-SDH assumptions [PHGR13] hold, with d the degree of the QAP. Proofs are the CRS model, where parts of the CRS are needed for proving statements and other parts are needed for verifying statements, but both may be seen by all parties. Fix d distinct, public ω1, . . . , ωd∈F. Let t=(x−ω1)· . . . ·(x−ωd)∈F[x]. Fix random, secret s, αv, αw, αy, rv, rw, ry=rv·rw∈F. Given generators g1of G1and g2of G2(written additively) and polynomial ƒ∈F[x],ƒ1is written for ƒ(s)·g1andƒ2for ƒ(s)·g2.

The commitment scheme is as follows. Let v1(x), . . . , vk(x)∈F[x] be the unique polynomials of degree <d, obtained by Lagrange interpolation, such that vi(ωj)=Vj,i, and similarly wi(ωj)=Wj,i,yi(ωj)=Yj,i. A commitment to {right arrow over (x)}∈Fkwith randomness (δv, δw, δy) is given by (V1,W2,Y1) with:

To prove that a commitment is a valid commitment in the span of a set S, i.e.V1,W1,Y1all use the same {right arrow over (x)} and this {right arrow over (x)} is in the span of S, a prover provides values (αvV1,αwW2,αyY1,Z1) with:

To verify that the commitment is valid, a verifier checks that:
e(V1,αv2)=e(αvV1,12);
e(αw1,W2)=e(αwW1,12);
e(Y1,αy2)=e(αyY1,12);
e(V1+Y1,S2)·e(βS1,W2)=e(Z1,12).  (1)
Proving that a commitmentV1,W2,Y1to vector {right arrow over (x)} with randomness (δv, δw, δy) is a solution to QAP Q is equivalent to proving that target polynomial t(x) divides the polynomial p(x)=(Σixi·vi(x))·(Σixi·wi(x))−(Σixi·yi(x)).V1,W2andY1represent evaluations “in the exponent” of Σixi·vi(x), Σixi·wi(x), and Σixi·yi(x) in secret point s. (With randomness added that needs to be compensated for.) The idea to prove that t(x) divides p(x) is to compute quotient polynomial h(x)=p(x)/t(x) and also provide an evaluation “in the exponent” of h(x), such that the equation h(x)·t(x)=p(x) can be verified using the pairing. More precisely, let h(x)=p(x)/t(x)+Σi=1kδvxi·wi(x)+Σi=1kδwxi·vi(x)+δvδw·t(x)−δy, and write h(x)=Σi=0d−1hi·xi. The proof that {right arrow over (x)} is a solution to QAP Q is simply

Given function ƒ:Fl→Fm, QAP Q of size n≥l+m is said to encode ƒ if it is true that {right arrow over (y)}=ƒ({right arrow over (x)}) iff there exists {right arrow over (z)} such that ({right arrow over (x)},{right arrow over (y)},{right arrow over (z)}) is a solution to Q. Clearly, every function can be encoded by a QAP: write the function as an arithmetic circuit, let {right arrow over (z)} represent internal wires of the circuit and let each row of the matrices V, W, Y denote a multiplication gate. However, note that not all natural QAPs are arithmetic circuits. For instance, consider the function ƒ:F→Fksuch that y0, . . . , yk-1=ƒ(x) is the k-bit bit decomposition of 0≤x<2k. A simple QAP for this consists of equations yi·(1−yi)=0, x=y0+2y1+ ⋅ ⋅ ⋅ +2k−1yk-1[PHGR13]; but this QAP is not an arithmetic circuit starting from x. Fixing a QAP that encodes ƒ, ƒ′ denotes the (any) function that returns {right arrow over (z)} in addition to {right arrow over (y)}.

Pinocchio uses a QAP that computes ƒ to allow efficient outsourcing of computations {right arrow over (y)}=ƒ({right arrow over (x)}). The client provides {right arrow over (x)} to the server. The server computes ƒ′({right arrow over (x)}), i.e., {right arrow over (y)}=ƒ({right arrow over (x)}) and {right arrow over (z)} such that ({right arrow over (x)},{right arrow over (y)},{right arrow over (z)}) is a solution to Q. Let S={l+m+1, . . . , n} be the variables of {right arrow over (x)} that do not belong to {right arrow over (x)} or {right arrow over (y)}. The server generates a commitment Cz=(Vz1,Wz1,Yz1) to {right arrow over (z)} and a proof that it is valid with respect to S. Moreover, let Cxy=(Vxy1,Wxy2,xy1) denote a commitment to {right arrow over (x)}+{right arrow over (y)} without any randomness. The server then generates a proof that Cxy+G=(Vxy1+Vz1,Wxy2+Wz2,xy1+Yz1) is a solution to Q. The server provides {right arrow over (y)} and the commitments and proofs to the client. The client reconstructs Cxy+Czfrom {right arrow over (x)}, {right arrow over (y)}, and Czand checks that Cxyis valid with respect to s and that Cxy+Czrepresents a solution to Q.

QAPs represent equations v·w=y where v, w, y are linear combinations in the variables. In many natural cases, it is desired to use constants in proofs, e.g., v=Σici·xi+c0. This is achieved by having the client append a one to its input vector at location l′=l+1 and writing c0as c0·xl′.

1.4 Trinocchio: Multiple Inputs and Distributed Proving

Trinocchio [SVdV15] improves Pinocchio in two main ways. First, [SVdV15] performs computations in a privacy-preserving way using multi-party computation in a committee of multiple servers (workers). Specifically, ƒ′ is computed using passively secure MPC based on Shamir secret sharing; from the secret shares of {right arrow over (y)}, {right arrow over (z)} that this gives, the Pinocchio proof can be computed locally by each of the servers. Essentially, the computation of the Pinocchio proof has multiplicative depth one (the only multiplication occurring when computing v(x)·w(x) for the quotient polynomial), so each server can simply compute the Pinocchio proof as above on Shamir secret shares; the result is an additive sharing of the Pinocchio proof that the client can reconstruct and verify.

In the single-server case, ƒ can be computed as follows. First, all clients i announce commitments Cito their inputs {right arrow over (xi)} (embedded in Fn) and prove correctness of their inputs with respect to Si. Then, they provide their inputs and commitment randomness to the server. The server computes {right arrow over (y)}, {right arrow over (z)} such that {right arrow over (x1)}, . . . , {right arrow over (xp)}, {right arrow over (y)}, {right arrow over (z)} is a solution to the QAP. It computes commitment Czto Z and a proof that it is correct with respect to S0. Let Cydenote a commitment to {right arrow over (y)} without randomness. The server finally proves that C1+ . . . +Cp+Cy+Cz(which is a commitment to {right arrow over (x1)}, . . . , {right arrow over (xp)}, {right arrow over (y)}, {right arrow over (z)} with randomness the sum of the client and server randomness) is a solution to the QAP, and publishes the Cz, {right arrow over (y)} and the proofs. The clients check correctness of all commitments, reconstruct C1+ . . . +Cp+Cy+Czusing C1, . . . , Cp, Czand {right arrow over (y)} and accept {right arrow over (y)} if the commitments and proof are correct.

As in the single-inputter case, the server's work can be performed in a privacy-preserving way by multiple servers using multi-party computation based on Shamir secret sharing. In this case, to make sure that the additive sharing of the Pinocchio proof does not leak anything about its inputs, this sharing is re-randomised with an additive sharing of 0 before being opened to the client.

The central observation of Geppetto [CFH15] is that it is possible to combine multiple QAPs into a single QAP with controlled overlap between the wires. This allows multiple independent proofs on a common set of values.

For instance, suppose there is a function ƒ and QAP Q1=(V1; W1; Y1) such that y=ƒ(x) if there exists {right arrow over (u )}such that (x, y, {right arrow over (u)}) is a solution to Q1. Similarly, suppose that b=g(a) if there exists {right arrow over (v)} such that (a, b, {right arrow over (v)}) is a solution to Q2=(V2,W2,Y2). Using Geppetto, a proof can be made that g ∘ ƒ was computed correctly by first creating a proof that ƒ was computed correctly, then creating a proof that g was computed correctly on the output of ƒ. Alternatively a circuit for function g ∘ ƒ could be created directly. Compared to this, the Geppetto approach allows different parties to provide the proofs for ƒ and g, and it allows more flexibility, e.g. it allows verifying iterative algorithms where the number of iterations is not known beforehand.

To build a QAP for g ∘ ƒ, consider the QAP Q=(V1|V2, W1|W2, Y1|Y2), where A|B denotes placing the two matrices next to each other, adding rows with zeros to A or B to make them the same height. Observe that if (x, y, {right arrow over (u)}) is a solution to Q1, then (x, y, {right arrow over (u)}, 0, . . . , 0) is a solution to Q; and if (a,b,{right arrow over (v)}) is a solution to Q2, then (0, . . . , 0, a, b, {right arrow over (v)}) is a solution to Q as well. Hence we can use Q both to prove that ƒ was computed correctly and that g was computed correctly. Now, we still need to guarantee that the output of ƒ is used as the input of g. To this end, a glue variable G is introduced, and rows added to Q representing equation y+a−G=0, i.e., row (0, . . . , 0) to V, (0, . . . , 0) to W, and (0, 1, 0, . . . , 0, 1, 0, . . . , 0, −1) to Y. Note that, when a=0 (e.g., when verifying a proof on a set S of variable indices that does not include a), this equation is y=G; and when y=0, it is a=G. Hence including G in proofs on the variables of Q1and Q2guarantees that indeed y=a.

As proof that b=g(ƒ(x)), the server provides commitments Cƒto (y, {right arrow over (u)}), Cgto (a, {right arrow over (v)}), and CGto G; and proofs that they are correct with respect to the appropriate sets of indices; the output value b; and proofs that Cx+Cƒ+CGand Cg+CG+Cbare solutions to Q. Here, Cxand Cbare commitments without randominess to values x and b that the client recomputes.

1.6 Flexible Gluing in Geppetto

Above, to “glue” variable y from a QAP Q1and variable a from a QAP Q2, a variable G is introduced and equation y+a−G. Now suppose it is desired to glue two variables x, y from Q1to the same variable a from two different instances of QAP Q2. This occurs naturally, for example, if a function ƒ calls a function g twice with different parameters.

Solution 1: Selector variable inside QAP—The solution to this problem that is probably adopted in the MapRedude example from [CFH15] is to glue x and y to different copies a1, a2of a, and introduce an additional selection variable s: if s=1 then a is equated to a1and if s=2 then a is equated to a2. In more detail, in the above scenario there are variables {x, y} in Q1, variables {M1, M2, a, a′, a1, a2} in Q2, and glue variables G1, G2. Glue equations x+a1=G1, x+a2=G2are added. In Q2, a is set to a1or a2depending on the value of s with the following equations (generalizing the “zero-equality gate” from [PHGR13]):

It is verified that these equations hold if and only if a′=δs,1·a1, M1=(a′−a1)(s−1)−1, M2=(a−a′−a2)(s−2)−1, and finally a=δs,1·a1+δs,2·a2as intended. If Q2is glued together at most M times to any other QAP, then this solution involves introducing M glue equations and M glue variables. Moreover, it involves adding 2M variables and 2M equations to Q2; however, note that these equations do not involve glue so when combining QAPs Q1and Q2, they can be put next to equations from Q1so they do not necessarily increase the QAP's degree.

Solution 2: Dynamically enabling glue equations—An alternative solution to this problem is to introduce additional variables that can be used to dynamically enable or disable glue equations. In the above setting, two variables α1, α2can be introduced and the following glue equations:
0=α1·(x+a−G1)
0=α2·(y+a−G2)

The verifier sets (α1, α2)=(1, 0) for the first instance of Q2to enable equation x+a=G1; (α1, α2)=(0, 1) for the second instance of Q2to enable equation y+a=G2; and (α1, α2)=(1, 1) for QAP Q1to enable both equations. This solution involves adding M glue variables and M glue equations, and M global “enable/disable” variables. Hence, this solution is slightly more efficient (and arguably less complicated) than the previous one.

Alternatives: Replicating or Phantom Functions—The easiest solution to this problem is simply to replicate QAP Q2M times. However, this means that all variables from Q2need to be replicated, increasing the (effort needed to produce the) evaluation key significantly, and a different verification key is needed for each invocation.

A final, conceptually simple solution is to introduce “phantom functions”. Conceptually, with replication, copies ƒ1, . . . , ƒMof ƒ are used when it is called different times from the same function. Here, instead of letting ƒ2, . . . , ƒMbeing copies of ƒ, ƒ2(x) is defined to be the function that directly calls ƒ and returns whatever it returns. The advantage is that it is not necessary to replicate all variables, resulting in a smaller evaluation key. However, this solution is less efficient, in particular for the verifier, because the number of function calls increases: e.g., for the second invocation of ƒ proofs need to be built and verified both for ƒ2and for its call to ƒ.

Remark: All Glue can be in Same Commitment—Note that in each of the above solutions, if a QAP Q1shares variables with at most M instances of QAP Q2, then each glue variable is replicated M many times. Note that all of these glue variables can be in the same commitment, i.e., different commitments for each instance of Q2are not needed. E.g. if Q1shares a set of variables with two instances of Q2, then there are four commitments: C1for Q1's variables, C2and C′2for Q2's variables and G for all glue variables. It is only needed to verify once that G is correct with respect to the set of all glue variables.
2 Distributed Privacy-Preserving Verifiable Computation

This section describes how to adapt Geppetto to the distributed privacy-preserving setting described above with reference toFIGS. 3-6.

A distributed computation can be outsourced to several committees of ≥3 parties that each perform a part of the computation using multi-party computation protocols based on secret sharing. The idea is that the computation takes place on secret shares, and the parties of the previous committee pass on their shares to the parties of the next committee. There are two ways of doing this: either n parties copy their shares as-is, or t parties copy their shares and then re-share them among the n new computation parties.

When deploying Geppetto, the idea is that the multi-party computation takes place (almost) as before, but certain information is saved. When a proof is requested, this information is then used by each of the workers that participated at some stage in the computation, to produce a separate proof that its actions were performed correctly. The proofs of all of these individual workers are then combined to obtain an overall proof of correctness of the computation outcome.

Specifically, when using the above technique for performing a distributed computation without Geppetto, each worker in a committee12,14gets as input secret shares of the inputs to the committee's computation part, as shown inFIG. 8. These shares may come from inputters6to the computation, from other committees12,14, or from a combination thereof. Similarly, the recipients10may also include the recipient of the overall computation result, in which the output is not shared among a committee but instead a single party gets all shares (this corresponds to step501inFIG. 6).

When deploying Geppetto (e.g. as shown inFIG. 9) during the computation the committee12,14gets, in addition to the secret-shared inputs {right arrow over (x)}1of each inputter, also secret-shared randomness {right arrow over (δ)}i=(δi,v, δi,w, δi,y) (this corresponds to step401inFIG. 5). Instead of computing ({right arrow over (y)}1, . . . , {right arrow over (y)}m)=ƒ({right arrow over (x)}1, . . . , {right arrow over (x)}n) (where ƒ is the part of the distributed computation assigned to the committee), the committee12,14now computes ({right arrow over (y)}1, . . . , {right arrow over (y)}m, {right arrow over (z)})=ƒ({right arrow over (x)}1, . . . , {right arrow over (x)}n) such that ({right arrow over (x)}1, . . . , {right arrow over (y)}1, . . . , {right arrow over (z)}) is a solution to the QAP for function ƒ (this corresponds to step407inFIG. 5). In addition, the committee12,14generates randomness [[{right arrow over (δ)}ƒ]], [[{right arrow over (δ)}′1]], . . . to be used in the commitment to its internal wires and to the wires it shares with the various recipients10(this corresponds to determining the secret share of the output commitment opening in step409inFIG. 5). The workers8in the committee12,14provide {right arrow over (y)}iand {right arrow over (δι′)} to recipient m—in secret shared form if the recipient10is another committee, or opened if it is an actual recipient10. Finally, the committee generates 8+7 m additive sharings [0] of zero used to randomise its proof elements. They store all of these secret shares until they are requested to produce a proof. It will be noted that it suffices to store [[Σ{right arrow over (δ)}i]] instead of the individual [[{right arrow over (δ)}1]].

When requested to produce a proof, the workers8in the committee12,14build secret shares of the commitments Cƒto their internal wires, and C1, . . . , Cmto the wires they shares with the recipients10(this corresponds to determining a secret share of an output commitment in step409ofFIG. 5). It should be noted that outputs for different recipients10can be combined into a single commitment as long as outlined above, as long as this does not conflict with wire values from other parties that the recipients10might receive. They use the additive zero sharings [0] to re-randomise these proof elements. Finally, they produce shares of their proof that ƒ was computed correctly with respect to these commitments and the commitments shared with the inputters6(this corresponds to step411inFIG. 5). Concerning the commitments from the inputters6, this proof is made based on [[Σ{right arrow over (δ)}i]]; and so knowing the actual commitments is not necessary. To build the proof and commitments, the workers8use a global key and specific keys for each commitment block provided by a trusted third party, TTP (e.g. central authority node4). The workers8provide the values to the verifier10(this corresponds to step413ofFIG. 5).

A verifier10collects from all inputters6commitments to their inputs (this corresponds to step503ofFIG. 6), and from all workers8in the committee12,14shares of their proofs (this corresponds to step509ofFIG. 6) and commitments (this corresponds to step505ofFIG. 6). Recombining these shares, the verifier10now verifies that the computation was correctly carried out with respect to the committed inputs and outputs (this corresponds to step513ofFIG. 6). Verification is with respect to a verification key provided by the trusted third party (TTP) (this corresponds to step511ofFIG. 6). Any inputter or outputter, who (as only party) knows the randomness of its commitment, can verify the correctness of the commitments used (this corresponds to step507ofFIG. 6), or prove knowledge and/or properties of the underlying values to others.

Implementations Based on Commit-and-Prove

Various alternative embodiments may be based on “commit-and-prove” schemes. A commit-and-prove scheme can be as described in “Prover-efficient commit-and-prove zero-knowledge snarks” by Helger Lipmaa, in Cryptology ePrint Archive, Report 2014/396, 2014. At a conceptual level, these embodiments would at least involve the following differences with the Trinocchio-based embodiments above:All commitment generation and verification keys would be the same, e.g., they would correspond to commitments using the “Interpolating Commitment Scheme” from Definition 1 of “Prover-efficient commit-and-prove zero-knowledge snarks”;The computation part prove keys (e.g., the prover parts crspof the common reference strings for the various SNARKs presented in “Prover-efficient commit-and-prove zero-knowledge snarks”) and verification keys (e.g., the verifier parts crsvof the common reference strings for the various SNARKs presented in “Prover-efficient commit-and-prove zero-knowledge snarks”) no longer need to be generated at the same time as the commitment keys, and in particular, different computations can use the same set of commitment keys and new computations can be performed on already committed data (i.e. inputs);In some commit-and-prove schemes, the computation part prove keys no longer need to be generated by the central authority4.

An implementation of a commit-and-prove scheme can be based on the technique described in the patent entitled “PINOCCHIO/TRINOCCHIO ON AUTHENTICATED DATA” having application No. 62/608,650, filed on Dec. 21, 2017 in the name of KONINKLIJKE PHILIPS, N.V., the content of which is hereby incorporated by reference. In that technique, Pinocchio is turned into a commit-and-proof scheme with computation-independent commitments by representing external committed data (i.e. inputs or outputs) for a computation as:

The point is that, if the ith value contained in the input or output (seen as a vector, and where i is in the range l+1 to m defined above) is to correspond to the jth wire of a computation, then thervβSvj+rwβSwj+ryβSyj1contribution in the internal wire commitment to the computation's wire is turned intorvβSvj+rwβSwj+ryβSyj+si1; where βS, rvand rware random values and ry=(rv·rw) for each trusted input value, vi, wiand yiare polynomials evaluated at s that represent the computation, with vkrepresenting the way that the respective internal wire is used in the left factor, wkrepresenting the way that the respective internal wire is used in the right factor, and ykrepresenting the way that the respective internal wire is used in the product of the set of multiplications that make up the computation.

When verifying equation (1) above in section 1.2, instead of takingV1+Y1, one takesV1+Y1+I1.

As discussed in “PINOCCHIO/TRINOCCHIO ON AUTHENTICATED DATA”, the above technique can be generalised to multiple shared inputs or outputs. As discussed above, the wires for the first shared input or output are included in the commitment to the internal wires that do not correspond to an input or output. For each additional input or output, a separate commitment
Vi1,αvVi1,Wi2,αwWi1,Yi1,αyYi1,Zi1
is included analogously to the commitment to the internal wires that do not correspond to an input or output or to the first input or output, but representing just the internal wires corresponding to that particular input or output, with a fresh value for β. The recipient node10repeats the checks in equation (1) for each of these commitments, and the check in equation (2) is adjusted so that valuesV1,W2,Y1include the commitments.

In this case, elements11,si1,γ1,γ·si1used to construct input-independent commitments form the input commitment generation keys used in steps101,201and203and output commitment generation keys used in steps101,403and409. The description above of input-independent commitments would be used to construct the input commitments used in steps203,205,503and513and the output commitments in steps409,505and513. The information that needs to be shared between the workers in the committee and the parties they exchange values with in steps207,401,409and501are the secret-shared values and the randomness δi, δi′ used in the commitments, i.e. the values xiand randomness x0in the description of the computation-independent commitmentsI1,γI1above.

The methods and systems described herein may be useful in many settings. For example, by allowing the distribution of computations between multiple committees of servers (workers8), the techniques described herein increase performance and hence make application of the techniques to these applications more practical:A wearable biosensor measures data of a customer and thereby acts as trusted source; an insurance company wants to have statistics on this data to evaluate a premium for the customer. The biosensor cannot compute the data on its own so the data needs to be outsourced, but the insurer wants to be convinced of the correctness. Here, a party providing the systems herein can be the central authority and producer of the biosensor; the processing of the data can then be outsourced to multiple external workers without needing to share data with them, while correctness is still guaranteed.Governments periodically publish health statistics to inform the public. These statistics can be authenticated with respect to the data by the hospitals and other medical organizations so that the public is sure they are correct. In this case, the party providing the systems disclosed herein could act as trusted party independent from both the trusted sources (medical organizations) and worker (different parties instructed by the government to compute the statistics in a distributed, privacy-preserving fashion).A smart meter produces readings but does not have the computational power to compute an aggregate report on this, or the aggregate report format may change over time. Hence this is outsourced to the owner of the smart meter. But the energy company wants to be sure that the aggregate report has not been manipulated by the owner to reduce her electricity bill. Here, the bill can be computed by multiple external cloud parties without needing to share the readings with those workers and without having to rely on them for correctness.Similarly, the scheme can be used for pay-as-you-drive insurance.A bookkeeper authenticates financial data of an organization; based on proofs an auditor can check that certain processes were followed correctly.The system could be deployed for consumers to get loyalty discounts based on payment information provided by sales terminals, without the shop knowing details about the consumer's purchases (assuming the shop cannot see what happens inside the sales terminals).

Another potential use case is that of privacy-preserving medical research. Here, researchers from multiple institutions can perform research on joint datasets while only seeing aggregate data. Using privacy-preserving verifiable computation, a researcher can build a proof that certain claimed results (e.g., a statistically significant correlation between a treatment and a medical outcome) are true, without seeing the data himself or needing to share it with peer reviewers. As above, the techniques described herein increase practicality by allowing these proofs to be constructed in a distributed way.

There is therefore provided a system, methods and nodes that achieve verifiable, privacy-preserving and distributed computations.