Cloud-Assisted Privacy-Preserving Spectral Clustering Algorithm Within a Multi-User Setting

Abstract

Spectral clustering, a powerful algorithm in the field of AI, holds a significant role despite its inherent high time complexity. For data owners grappling with limitations such as small datasets and restricted computational resources, harnessing the computational capabilities of cloud computing and aggregating data from multiple sources can yield precise spectral clustering results. However, explicit data uploading to cloud servers poses privacy risks. In response to this challenge, we explore the outsourcing dilemma of spectral clustering in a cloud and multi-user environment and propose a quantum-secure and efficient solution. Specifically, by employing the CKKS homomorphic encryption algorithm within a dual non-collusive server model, we formulate a comprehensive and multi-user spectral clustering outsourcing scheme. Our approach addresses privacy concerns by introducing secure computation protocols for $L_{2}$ norm, exponential function, and negative half power function. We elaborate on efficient computational algorithms for each stage of spectral clustering, ensuring accurate clustering outcomes without compromising dataset privacy. Moreover, in our scheme, users only need to upload their encrypted dataset without requiring direct interaction with each other or the cloud server until obtaining clustering results. Finally, we argue the IND- $\mathcal {CPA}$ security of our design and substantiate its accuracy and efficiency through theoretical comparison analysis and experimental evaluations.

Keywords

• CKKS
• computation outsourcing
• homomorphic encryption
• privacy-preserving
• spectral clustering