Abstract:

[Objective] In the era of the Internet, graph data, with its rich semantics and structural information, plays a unique role in numerous fields. At the same time, more and more companies are choosing to use "cloud services" as their infrastructure platform, and the protection of personal sensitive data is increasingly attracting people's attention. This poses severe challenges to privacy-preserving graph computing. [Methods] This paper focuses on the crucial subgraph matching problem in graph computing and proposes, for the first time, a privacy-preserving graph query strategy based on secure multi-party computation. The privacy-preserving graph query problem is transformed into a secure join problem for relational tables, and the secure join sub-protocol is improved according to the characteristics of graph data. [Results] Compared with previous works on privacy-preserving graph query, our protocol not only provides lower computation and communication overhead, but also has higher security and credibility.

Key words: secure multi-party computation, cloud services, privacy preserving, graph query, secure join