Secure Low-Complexity k-MCMC for Large-Scale Datasets with Fully Homomorphic Encryption
Shozo Saeki, Minoru Kawahara, Hirohisa Aman · 2025
Outsourcing services and data sharing, such as artificial intelligence services and open science, have been increasing, and so has the importance of data security while keeping availability. One secure method is utilizing Fully Homomorphic Encryption (FHE). In addition, clustering algorithms with FHE have been proposed for outsourcing services. However, these algorithms are difficult to apply to a large-scale dataset due to FHE computations having high computational and space complexities. To address this, we propose secure low complexity k-MCMC (SLC k-MCMC), which approximate k-Means++ initialization and help clustering algorithms to fast convergence. SLC k-MCMC uses data packing with FHE and replaced sampling strategy (RSS), which reduces computational complexity and the amount of network traffic. Finally, we apply SLC k-MCMC to large-scale datasets, including million-scale datasets. As a result, SLC k-MCMC can be approximated to k-Means++ initialization with less than 1 / 1000th computational complexity and network traffic. Fast and high-quality initialization of SLC k-MCMC expands the applicability of the secure clustering algorithms to large-scale datasets.