System and method for proving membership of subset from given set and linear operation therefor
A method for providing a zero-knowledge membership proof is provided. The method comprises defining public parameters to be used for computing and verification of proof by a prover and a verifier, respectively. The method comprises computing, by the prover, a commitment to a given ordered set X using the public parameters, and sending it to the verifier. The method further comprises receiving, by the prover, a query from the verifier for proving membership of a subset S sampled from the given ordered set X. The method further comprises computing, by the prover, a proof of membership, including an inner product, commitments of polynomials defining the inner product and a proof of the inner product being correctly computed, and sending the proof of membership to the verifier. The method further comprises verifying, by the verifier, the proof of membership based on the defined public parameters.
1. A method for providing a zero-knowledge membership proof, the method comprising:
defining, in a setup phase, public parameters to be used for computing and verification of proof by a prover and a verifier, respectively;
computing, by the prover, a commitment using the public parameters to a given ordered set X;
sending, by the prover, the commitment to the given ordered set X to the verifier;
receiving, by the prover, a query from the verifier for proving membership of a subset S sampled from the given ordered set X;
computing, by the prover, a proof of membership providing that elements in the subset S represented by a vector {right arrow over (s)} are present in the given ordered set X represented by a vector {right arrow over (x)}, with the vector {right arrow over (s)} and the vector {right arrow over (x)}being of same length and the vector {right arrow over (s)} containing two or more components of the vector {right arrow over (x)} that are selected in same position as in the vector {right arrow over (x)}, and 0 in non-selected positions, based, at least in part, on the defined public parameters;
sending, by the prover, the proof of membership to the verifier; and
verifying, by the verifier, the proof of membership based on the defined public parameters.
2. The method of claim 1 , wherein the prover, using the commitment, further claims to have computed a correct result for each of one or more linear operations performed over elements of the subset S.
3. The method of claim 2 , wherein the query, received by the prover, from the verifier, further comprises a request for value Y resultant of a given linear operation performed over elements of the subset S.
4. The method of claim 3 further comprising:
adding, by the prover, a matrix representative of the given linear operation to be performed over elements of the subset S to modify polynomials used to compute an inner product; and
checking, by the verifier, for the modified polynomials while verifying the inner product.
5. The method of claim 1 further comprising updating, by the prover, the commitment, using the public parameters, in case of addition of new elements to the given ordered set X.
6. The method of claim 1 , wherein the proof of membership is defined over an elliptic curve group.
7. The method of claim 1 , wherein the commitment is a Pedersen commitment.
8. A system for performing data analysis on private data by implementing a zero-knowledge membership proof, the system comprising:
a data provider device comprising a database configured to store private data therein;
a data owner device, acting as a prover, configured to access and process the private data from the database; and
a client device, acting as a verifier, configured to provide a query related to a group of elements of the private data for performing data analysis therefor,
wherein public parameters to be used for computing and verification of proof by the prover and the verifier, respectively, are defined in a setup phase and shared therewith,
wherein the prover is configured to:
compute a commitment using the public parameters to elements of the private data, defined as a given ordered set X, and
send the commitment to the given ordered set X to the verifier, wherein the verifier is configured to:
send the query, to the prover, for proving membership of the group of elements defined as a subset S sampled from the given ordered set X, wherein the prover is further configured to:
compute a proof of membership providing that the group of elements in the subset S represented by a vector {right arrow over (s)} are present in the given ordered set X represented by a vector {right arrow over (x)}, with the vector {right arrow over (s)} and the vector {right arrow over (x)} being of same length and the vector {right arrow over (s)} containing two or more components of the vector {right arrow over (x)} that are selected in same position as in the vector {right arrow over (x)}, and 0 in non-selected positions, based, at least in part, on the defined public parameters, and
send the proof of membership to the verifier, and wherein the verifier is further configured to:
verify the proof of membership based on the defined public parameters.
9. The system of claim 8 , wherein the prover, using the commitment, further claims to have computed a correct result for each of one or more linear operations performed over elements of the subset S.
10. The system of claim 9 , wherein the query, received by the prover, from the verifier, further comprises a request for value Y resultant of a given linear operation performed over elements of the subset S.
11. The system of claim 10 , wherein:
the prover is configured to add a matrix representative of the given linear operation to be performed over elements of the subset S to modify polynomials used to compute an inner product; and
the verifier is configured to check for the modified polynomials while verifying the inner product.
12. The system of claim 8 , wherein the prover is further configured to update the commitment, using the public parameters, in case of addition of new elements to the private data.
13. The system of claim 8 , wherein the proof of membership is defined over an elliptic curve group.
14. The system of claim 8 , wherein the commitment is a Pedersen commitment.
15. A system for performing identification of a customer by implementing a zero-knowledge membership proof, the system comprising:
a data owner device, acting as a prover, comprising a database to store identification data containing identities of a plurality of customers therein; and
a client device, acting as a verifier, configured to provide a query to confirm identities of one or more given customers, from the plurality of customers, from the identification data,
wherein public parameters to be used for computing and verification of proof by the prover and the verifier, respectively, are defined in a setup phase and shared therewith,
wherein the prover is configured to:
compute a commitment using the public parameters for the identities of the plurality of customers, defined as a given ordered set X, and
send the commitment to the given ordered set X to the verifier, wherein the verifier is configured to:
send the query, to the prover, for proving membership of identities of the one or more given customers defined as a subset S sampled from the given ordered set X, wherein the prover is further configured to:
compute a proof of membership providing that the identities of the one or more given customers defined in the subset S represented by a vector {right arrow over (s)} are present in the given ordered set X represented by a vector {right arrow over (x)}, with the vector {right arrow over (s)} and the vector {right arrow over (x)} being of same length and the vector {right arrow over (s)} containing two or more components of the vector {right arrow over (x)} that are selected in same position as in the vector {right arrow over (x)}, and 0 in non-selected positions, based, at least in part, on the defined public parameters, and
send the proof of membership to the verifier, and
wherein the verifier is further configured to:
verify the proof of membership based on the defined public parameters.
16. The system of claim 15 , wherein the prover is further configured to update the commitment, using the public parameters, in case of addition of identities of new customers to the identification data.
17. The system of claim 15 , wherein the proof of membership is defined over an elliptic curve group.
18. The system of claim 15 , wherein the commitment is a Pedersen commitment.