Privacy-preserving and verifiable spectral graph analysis in the cloud

Area of Science:

• Computer Science
• Data Science
• Cryptography

Background:

• Cloud computing is increasingly used for large-scale spectral graph analysis.
• Concerns exist regarding data privacy and the potential for cloud services to provide inaccurate results.
• Existing privacy solutions often overlook misbehaving cloud threats and verifiable computation challenges in spectral graph analysis.

Purpose of the Study:

• To develop a holistic solution addressing both privacy and verifiability for spectral graph analytics in the cloud.
• To introduce PVG, a framework designed for secure and accurate eigendecomposition in cloud-based graph analysis.
• To enable users to validate the accuracy of cloud-computed spectral graph analysis results.

Main Methods:

• Designed PVG, a privacy-preserving and verifiable framework for spectral graph analytics.
• Developed an additive publicly verifiable computation (APVC) algorithm to verify matrix multiplication accuracy within eigendecomposition.
• Proposed three secure and verifiable functions for eigendecomposition utilizing APVC and lightweight cryptography.

Main Results:

• PVG provides strong privacy for graph data during cloud-based spectral analysis.
• The framework enables users to effectively validate the accuracy of the eigendecomposition results.
• Experimental results demonstrate PVG's accuracy is consistent with plaintext computations.
• PVG offers practically affordable performance, outperforming existing methods.

Conclusions:

• PVG is the first framework to holistically address privacy and verifiability for cloud-based spectral graph analytics.
• The proposed APVC algorithm and secure functions are effective for verifying eigendecomposition in the cloud.
• PVG offers a practical and secure solution for large-scale spectral graph analysis in cloud environments.