Pinocchio/Trinocchio on authenticated data

Abstract

According to an aspect, there is provided a first node for use in a system, the system comprising one or more trusted source nodes, one or more worker nodes and a verifier node, wherein the first node is configured to determine a trusted input commitment key for a trusted input to be input into a computation that is to be evaluated by the one or more worker nodes, wherein the trusted input commitment key is for use by the one or more trusted source nodes in forming a trusted input commitment of one or more trusted inputs; determine a computation evaluation key for use by the one or more worker nodes in determining a proof that a computation on one or more trusted inputs is correct and that the one or more trusted inputs were used in the computation, wherein the computation evaluation key comprises key material for one or more trusted input wires that are for inputting the one or more trusted inputs into the computation, wherein the key material is derived from a trapdoor value, one or more polynomials evaluated in a point corresponding to the trapdoor value that are independent of polynomials representing the computation, and one or more polynomials evaluated in a point corresponding to the trapdoor value that represent the computation; determine a computation verification key for use by the verifier node in verifying the result of the computation by the one or more worker nodes; and publish the trusted input commitment key, the computation evaluation key and the computation verification key. A corresponding method of operating a first node is provided. Other aspects also provide a trusted source node, a worker node and a verifier node, and methods of operating the same.

The invention claimed is: 
     
       1. A first node for use in a communication network system, the system comprising one or more trusted source nodes, the one or more worker nodes and a verifier node, wherein the first node, the one or more trusted sources nodes, one or more worker nodes and the verifier node are electronic devices, wherein the first node is configured to:
 determine a trusted input commitment key for a trusted input to be input into a computation that is evaluated by the one or more worker nodes, wherein the trusted input commitment key is for use by the one or more trusted source nodes in forming a trusted input commitment of one or more trusted inputs; 
 determine a computation evaluation key for use by the one or more worker nodes in determining a proof that a computation on one or more trusted inputs is correct and that the one or more trusted inputs were used in the computation, wherein the computation evaluation key comprises key material for one or more trusted input wires that are for inputting the one or more trusted inputs into the computation, wherein the key material is derived from a trapdoor value, one or more polynomials evaluated in a point corresponding to the trapdoor value that are independent of polynomials representing the computation, and one or more polynomials evaluated in a point corresponding to the trapdoor value that represent the computation; 
 determine a computation verification key for use by the verifier node in verifying the result of the computation by the one or more worker nodes; and 
 publish the trusted input commitment key, the computation evaluation key and the computation verification key to make the keys available for nodes within the system. 
 
     
     
       2. A first node as claimed in  claim 1 , wherein the key material for each trusted input wire includes an encoding of the product of a secret value and the combination of a computation-independent polynomial evaluated in a point corresponding to the trapdoor value representing the trusted input wire and one or more computation-dependent polynomials evaluated in a point corresponding to the trapdoor value that represent how the wire is used in the computation. 
     
     
       3. A method of operating a first node in a system, the system comprising one or more trusted source nodes, one or more worker nodes and a verifier node, wherein the method comprises:
 determining a trusted input commitment key for a trusted input to be input into a computation that is to be evaluated by the one or more worker nodes, wherein the trusted input commitment key is for use by the one or more trusted source nodes in forming a trusted input commitment of one or more trusted inputs; 
 determining a computation evaluation key for use by the one or more worker nodes in determining a proof that a computation on one or more trusted inputs is correct and that the one or more trusted inputs were used in the computation, wherein the computation evaluation key comprises key material for one or more trusted input wires that are for inputting the one or more trusted inputs into the computation, wherein the key material is derived from a trapdoor value, one or more polynomials evaluated in a point corresponding to the trapdoor value that are independent of polynomials representing the computation, and one or more polynomials evaluated in a point corresponding to the trapdoor value that represent the computation; 
 determining a computation verification key for use by the verifier node in verifying the result of the computation by the one or more worker nodes; and 
 publishing the trusted input commitment key, the computation evaluation key and the computation verification key. 
 
     
     
       4. A non-transitory 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 of  claim 3 . 
     
     
       5. A worker node for use in a communication network system, the system comprising a first node, one or more trusted source nodes and a verifier node, wherein the worker node, the first node, the one or more trusted sources nodes, and the verifier node are electronic devices wherein the worker node is configured to:
 obtain a computation evaluation key for a computation to be performed by the worker node, wherein the computation evaluation key comprises key material for one or more trusted input wires that are for inputting the one or more trusted inputs into the computation, wherein the key material is derived from a trapdoor value, one or more polynomials evaluated in a point corresponding to the trapdoor value that are independent of polynomials representing the computation, and one or more polynomials evaluated in a point corresponding to the trapdoor value that are dependent on polynomials representing the computation; 
 receive one or more trusted inputs for the computation; 
 evaluate the computation using the received one or more trusted inputs to determine values for one or more internal wires of the computation and one or more output wires of the computation; 
 and determine a proof that the computation on the one or more trusted inputs is correct and that the one or more trusted inputs were used in the computation using the computation evaluation key, wherein the determined proof is sent to the verifier node. 
 
     
     
       6. A worker node as claimed in  claim 5 , wherein the key material for each trusted input wire includes an encoding of the product of a secret value and the combination of a computation-independent polynomial evaluated in a point corresponding to the trapdoor value representing the trusted input wire and one or more computation-dependent polynomials evaluated in a point corresponding to the trapdoor value that represent how the wire is used in the computation. 
     
     
       7. A worker node as claimed in  claim 5 , wherein the key material for the one or more trusted input wires comprises:
     β·( s   k   +r   v   v   k   +r   w   w   k   +r   y   y   k     1  
 
 
       where k is a label representing each trusted input wire, s is the trapdoor value, β, r v  and r w  are random values and r y =(r v ·r w ) for each trusted input, v k , w k  and y k  are polynomials evaluated at s that represent the computation, with v k  representing the way that the respective trusted input wire is used in the left factor, w k  representing the way that the respective trusted input wire is used in the right factor, and y k  representing the way that the respective trusted input wire is used in the product of the set of multiplications that make up the computation,  ·   1  is an additively homomorphic encoding, and  f   1  for polynomial f represents the additively homomorphic encoding of ring element f(s). 
     
     
       8. A method of operating a worker node in a system, the system comprising a first node, one or more trusted source nodes and a verifier node, wherein the method comprises:
 obtaining a computation evaluation key for a computation to be performed by the worker node, wherein the computation evaluation key comprises key material for one or more trusted input wires that are for inputting the one or more trusted inputs into the computation, wherein the key material is derived from a trapdoor value, one or more polynomials evaluated in a point corresponding to the trapdoor value that are independent of polynomials representing the computation, and one or more polynomials evaluated in a point corresponding to the trapdoor value that are dependent on polynomials representing the computation; 
 receiving one or more trusted inputs for the computation; 
 evaluating the computation using the received one or more trusted inputs to determine values for one or more internal wires of the computation and one or more output wires of the computation; and 
 determining a proof that the computation on the one or more trusted inputs is correct and that the one or more trusted inputs were used in the computation using the computation evaluation key. 
 
     
     
       9. A non-transitory 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 of  claim 8 . 
     
     
       10. A verifier node for use in a communication network system, the system comprising a first node, one or more trusted source nodes and one or more worker nodes, wherein the verifier, the first node, the one or more trusted sources nodes, and one or more worker nodes are electronic devices, wherein the verifier node is configured to:
 obtain a trusted input verification key and computation verification key; 
 obtain, from the one or more trusted source nodes, a trusted input commitment, the trusted input commitment comprising a representation of one or more trusted inputs that have been input by the one or more trusted source nodes to a computation; 
 obtain, from one or more worker nodes, an output of the computation and a proof that the computation on the one or more trusted inputs by the one or more worker nodes is correct and that the one or more trusted inputs were used in the computation; 
 and determine whether the computation on the one or more trusted inputs is correct and whether the trusted inputs were used in the computation using the obtained trusted input verification key, obtained computation verification key, obtained trusted input commitment and obtained proof, wherein the verifier node determines whether the computation on the one or more trusted inputs is correct and whether the trusted inputs were used in the computation by verifying that a plurality of encodings are consistent with each other and that the plurality of encodings are consistent with the trusted input commitment for the computation. 
 
     
     
       11. A verifier node as claimed in  claim 10 , wherein the computation comprises zero or more non-trusted input wires, one or more computation output wires, one or more trusted input wires and one or more internal wires, and wherein the proof comprises encodings representing the contributions of a set of input wires including the trusted input wires to left factors, right factors and products of the multiplications that form the computation. 
     
     
       12. A verifier node as claimed in  claim 11 , wherein the proof comprises an element Z that is for use in verifying that the plurality of encodings are consistent with each other and that the plurality of encodings are consistent with the trusted input commitment for the computation. 
     
     
       13. A verifier node as claimed in  claim 12 , wherein the verifier node is configured to determine whether the computation on the one or more trusted inputs is correct and whether the trusted inputs were used in the computation by verifying that the plurality of encodings are consistent with each other and that the plurality of encodings are consistent with the trusted input commitment for the computation. 
     
     
       14. A method of operating a verifier in a system, the system comprising a first node, one or more trusted source nodes and one or more worker nodes, wherein the method comprises:
 obtaining a trusted input verification key and computation verification key; 
 obtaining, from the one or more trusted source nodes, a trusted input commitment, the trusted input commitment comprising a representation of one or more trusted inputs that have been input by the one or more trusted source nodes to a computation; 
 obtaining, from one or more worker nodes, an output of the computation and a proof that the computation on the one or more trusted inputs by the one or more worker nodes is correct and that the one or more trusted inputs were used in the computation; and 
 determining whether the computation on the one or more trusted inputs is correct and whether the trusted inputs were used in the computation using the obtained trusted input verification key, obtained computation verification key, obtained trusted input commitment and obtained proof. 
 
     
     
       15. A non-transitory 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 of  claim 14 .