System and method for privacy preserving query verification

• US 7,979,711 B2
• Filed: 08/08/2007
• Issued: 07/12/2011
• Est. Priority Date: 08/08/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Hong, Hsu, Windsor Wee Sun, Ma, Xiaonan
• Primary Examiner(s): Hoffman; Brandon S
• Application Number:
  US11/835,646
• Publication Number:
  US 20090041253A1
• Time in Patent Office: 1,434 Days
• Field of Search: None
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

The present invention relates to a method for proving the correctness of a query result produced by a data publisher while preserving the privacy of the query result. The method comprises delivering a public key of a public key/private key pair from a data owner to a client and delivering data and cryptographic metadata to at least one data publisher, wherein the metadata is associated both with the data and the public key of the public key/private key pair. The method further comprises receiving a query from the client, returning a query result and a verification object from the data publisher to the client in response to the query, and verifying the correctness of the query result, wherein the correctness of the query result is verified utilizing the verification object and the public key.

Claims

1. A method for proving the correctness of a query result produced by a data publisher while preserving data privacy, the method comprising:

delivering a public key of a public key/private key pair from a data owner to a client;

delivering data and cryptographic metadata to at least one data publisher, wherein the metadata is associated both with the data and the public key of the public key/private key pair;

receiving a query from the client;

returning a query result and a verification object from the data publisher to the client in response to the query; and

verifying the correctness of the query result, wherein the correctness of the query result is verified utilizing the verification object and the public key.

2. The method of claim 1, wherein the client is assigned an accessible space in which to perform query searches in accordance with a determined access control policy.

3. The method of claim 2, wherein the verification object is generated in accordance with the determined access control policy that is assigned to the client and the query results that are comprised within the accessible space of the client.

4. The method of claim 3, wherein the data owner provides a digital signature stating that there are nac data points comprised within the accessible space (ac) that is assigned to a client.

5. The method of claim 4, wherein a verification object comprises a data point authentication data structure, a signature from the data owner stating the number of data points nac within an accessible space (ac), and additional verification data stating that ac-q comprises at least nac-nq data points.

6. The method of claim 5, wherein verifying the correctness of a query result comprises verifying the authenticity and completeness of query result data.

7. The method of claim 6, wherein a valid query space (q) is comprised of a subspace of the client'"'"'s accessible space (ac).

8. The method of claim 7, wherein a client does not have access to information in regard to data points outside of the accessible space (ac) that has been assigned to the client.

9. The method of claim 8, wherein a client does not have access to information in regard to the access control polices of additional clients of the data publisher.

10. The method of claim 9, wherein a dataset, an access control policy, and a query are multi-dimensional.

11. A computer program product that includes a computer readable device useable by a processor, the medium having stored thereon a sequence of instructions which, when executed by the processor, causes the processor to verify the correctness of a query result while preserving data privacy by:

receiving data and cryptographic metadata that is associated with the data and the public key of a public key/private key pair from a data owner;

receiving a query from a client;

returning a query result and a verification object from at least one data publisher to the client in response to the query; and

verifying the correctness of the query result, wherein the correctness of the query result is verified utilizing the verification object and the public key.

12. The computer program product of claim 11, wherein the client is assigned an accessible space in which to perform query searches in accordance with a determined access control policy.

13. The computer program product of claim 12, wherein the verification object is generated in accordance with the determined access control policy that is assigned to the client and the query results that are comprised within the accessible space of the client.

14. The computer program product of claim 13, wherein a digital signature is received from the data owner stating that there are nac data points comprised within an accessible space (ac) that is assigned to a client.

15. The computer program product of claim 14, wherein a verification object comprises a data point authentication data structure, a signature from the data owner stating the number of data points nac within an accessible space (ac), and additional verification data stating that ac-q comprises at least nac-nq data points.

16. The computer program product of claim 15, wherein verifying the correctness of a query result comprises verifying the authenticity and completeness of query result data.

17. The computer program product of claim 16, wherein a valid query space (q) is comprised of a subspace of the client'"'"'s accessible space (ac).

18. The computer program product of claim 17, wherein a client is not permitted to have access to information in regard to data points outside of the accessible space (ac) that has been assigned to the client.

19. The computer program product of claim 18, wherein a client is not permitted to have access to information in regard to the access control polices of additional clients of the data publisher.

20. The computer program product of claim 19, wherein a dataset, an access control policy, and a query are multi-dimensional.