Verifiable Strong Privacy-Preserving Any-Hop Reachability Query on Blockchain-Assisted Cloud

Any-hop (k-hop) reachability query is one fundamental operation in graph data analysis and its performance affects the efficiency of various tasks in Social Internet of Things. As graph data scale increases, data is often outsourced to cloud servers. To protect the privacy of graph data, it is necessary to encrypt the data before outsourcing. Existing schemes can only support privacy-preserving 2-hop reachability queries. Only one scheme can support privacy-preserving k-hop reachability queries, but it discloses topological information and the query results is not verifiable. Most serious deficiency is that its efficiency is not practical. To address these issues, we propose a verifiable strong privacy-preserving k-hop reachability query on encrypted data. This scheme not only supports efficient privacy-preserving k-hop reachability queries without leaking any network topological information but also uses blockchain to achieve verifiability of query results. The security analysis shows that our scheme is secure. Compared to existing k-hop reachability query scheme, our scheme greatly improves query efficiency (at least <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$6.4\cdot 10^{5}\times $ </tex-math></inline-formula> faster when the number of nodes <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \geq 100$ </tex-math></inline-formula> ).