Privacy-preserving and verifiable spectral graph analysis in the cloud

Resorting to cloud computing for spectral graph analysis on large-scale graph data is becoming increasingly popular. However, given the intrusive and opaque natures of cloud services, privacy, and misbehaving cloud that returns incorrect results have raised serious concerns. Current schemes are proposed for privacy alone under the semi-honest model, while disregarding the realistic threat posed by the misbehaving cloud that might skip computationally intensive operations for economic gain. Additionally, existing verifiable computation techniques prove inadequate for the specialized requirements of spectral graph analysis, either due to compatibility issues with privacy-preserving protocols or the excessive computational burden they impose on resource-constrained users. To tackle the above two issues in a holistic solution, we present, tailor, and evaluate PVG, a privacy-preserving and verifiable framework for spectral graph analytics in the cloud for the first time. PVG concentrates on the eigendecomposition process, and provides strong privacy for graph data while enabling users to validate the accuracy of the outcomes yielded by the cloud. For this, we first design a new additive publicly verifiable computation algorithm, APVC, that can verify the accuracy of the result of the core operation (matrix multiplication) in eigendecomposition returned by cloud servers. We then propose three secure and verifiable functions for eigendecomposition based on APVC and lightweight cryptography. Extensive experiments on three manually generated and two real-world social graph datasets indicate that PVG's accuracy is consistent with plaintext, with practically affordable performance superior to prior art.