Structure-preserving subgraph queries

Patent metadata

Field	Value
Publication number	US-10061715-B2
Application number	US-201514835747-A
Country	US
Kind code	B2
Filing date	Aug 26, 2015
Priority date	Jun 2, 2015
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

The present invention relates to solving the issues related to subgraph query services with tunable preservation of privacy of structural information. More particularly, it relates to a novel cyclic group based encryption (CGBE) method for private matrix operations.

First claim

What is claimed is:

1. A method executed in a computer system that minimizes eavesdropping by a service provider (SP) on a query graph Q to a database from a client computer or graph data G in the database from a data owner in a structure-preserving subgraph query processing (SPQP), the method comprising:
encrypting the graph data G, by the data owner, and delivering the encrypted graph data in the database to the SP that is accessible to the client computer with the query graph Q that execute through the SP;
minimizing the eavesdropping on the query graph Q to the database from the client computer or the graph data G from the data owner by:
delivering, by the data owner, private keys to the client computer for encryption of the query graph Q and decryption of an encrypted result;
encrypting the query graph Q, by the client computer, using the private keys, and submitting the encrypted query to SP, wherein the encrypting of the query graph Q is based on a cyclic group based private key encryption and comprises:
enumerating all possible subgraph isomorphism mappings M i s from the query graph Q to the data graph G by matching for creating a structure-preserving structure;
verifying if the mapping M i is valid or not;
reducing search space of the M i s by degree constraints and neighborhood constraints;
performing query evaluation between the query graph Q and the graph data G using adjacency matrices; and
using the cyclic group based private key encryption to encrypt M Q and M G as encrypted matrices of query M Qk and encrypted matrices of graph M G k respectively for verifying the validity of M i ;

checking the validity of each mapping M i by the SP under the cyclic group based private key encryption;
aggregating computational results under the cyclic group based private key encryption by the SP for reducing communication overheads between the client computer and the SP as the query graph Q has a bounded size; and
determining, by the SP, subgraph structure with a number of possible mappings reduced.

2. The method according to claim 1 , wherein the performing of the query evaluation comprises:
transforming the structure-preserving structure into a series of mathematical computations via operations comprising:
enumerating all possible subgraph isomorphism mappings M i s;
verifying validity of the M i by additions and multiplications using adjacency matrices of query M Q and M G , where the M G is complement of adjacency matrices of graph M G ; and
reducing search space of the M i s by inner products using static indexes SI Q and SI G of the query graph Q and the data graph G respectively, wherein SI Q is an ensemble of h-hop information of each vertex of the query graph Q, and SI G is an ensemble of h-hop information of each vertex of the data graph G, both represented by a bit vector.

3. A computer system comprising:
a computer device hosting graph data G operated by a data owner;
a client computer executing a query graph Q; and
a service provider (SP) with computing infrastructures for evaluating the query graph Q and returning to the client computer with an encrypted result, wherein the data owner owns and encrypts the graph data G and outsources the encrypted graph data G in a database to SP; and the client computer and the SP are configured to execute processes for minimizing eavesdropping in a structure-preserving subgraph query processing (SPQP) according to the method of claim 2 .

4. A non-transitory computer-readable medium whose contents cause a computing system to perform the method of claim 2 for minimizing eavesdropping by a service provider (SP) on a query graph Q to a database from a client computer or graph data G in the database from a data owner in a structure-preserving subgraph query processing (SPQP).

5. The method according to claim 1 , wherein the determining of the subgraph structure comprises:
obtaining a feedback from the client computer on useless enumerations;
exploiting private inner products on static indexes to derive a refinement that reduces the number of possible mappings;
computing and encrypting the static indexes of graphs offline; and
computing the static indexes of the query graph Q once by the client computer online.

6. The method according to claim 5 , wherein the feedback from the client computer is a protocol between the SP and the client computer for pruning the useless partial mappings by the client computer.

7. A computer system comprising:
a computer device hosting graph data G operated by a data owner;
a client computer executing a query graph Q; and
a service provider (SP) with computing infrastructures for evaluating the query graph Q and returning to the client computer with an encrypted result, wherein the data owner owns and encrypts the graph data G and outsources the encrypted graph data G in a database; and the client computer and the SP are configured to execute processes for minimizing eavesdropping in a structure-preserving subgraph query processing (SPQP) according to the method of claim 5 .

8. A non-transitory computer-readable medium whose contents cause a computing system to perform the method of claim 5 for minimizing eavesdropping by a service provider (SP) on a query graph Q to a database from a client computer or graph data G in the database from a data owner in a structure-preserving subgraph query processing (SPQP).

9. A computer system comprising:
a computer device hosting graph data G operated by a data owner;
a client computer executing a query graph Q; and
a service provider (SP) with computing infrastructures for evaluating the query graph Q and returning to the client computer with an encrypted result, wherein the data owner owns and encrypts the graph data G and outsources the encrypted graph data G in a database; and the client computer and the SP are configured to execute processes for minimizing eavesdropping in a structure-preserving subgraph query processing (SPQP) according to the method of claim 6 .

10. A non-transitory computer-readable medium whose contents cause a computing system to perform the method of claim 6 for minimizing eavesdropping by a service provider (SP) on a query graph Q to a database from a client computer or graph data G in the database from a data owner in a structure-preserving subgraph query processing (SPQP).

11. The method according to claim 1 , wherein the checking of the validity of each mapping M i by the SP under the cyclic group based private key encryption comprises applying SPMatch with additions and multiplications to the cyclic group based private key encryption for efficient encryption and decryption.

12. A computer system comprising:
a computer device hosting graph data G operated by a data owner;
a client computer executing a query graph Q; and
a service provider (SP) with computing infrastructures for evaluating the query graph Q and returning to the client computer with an encrypted result, wherein the data owner owns and encrypts the graph data G and outsources the encrypted graph data G in a database; and the client computer and the SP are configured to execute processes for minimizing eavesdropping in a structure-preserving subgraph query processing (SPQP) according to the method of claim 11 .

13. A non-transitory computer-readable medium whose contents cause a computing system to perform the method of claim 11 for minimizing eavesdropping by a service provider (SP) on a query graph Q to a database from a client computer or graph data G in the database from a data owner in a structure-preserving subgraph query processing (SPQP).

14. A computer

Assignees

• Univ Hong Kong Baptist Univ

Inventors

• Choi Koon Kau
• Fan Zhe

Classifications

• G06F17/30442

  Physics · mapped topic

• G06F12/1408 Primary

  by using cryptography (for digital transmission H04L9/00) · CPC title

• G06F2212/1052

  Security improvement · CPC title

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• H04L9/3066

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title