Efficient and Scalable Multi-party Privacy-Preserving k-NN Classification

In recent years, storing data and mining valuable information among multi-party with the help of cloud servers has become popular. However, outsourcing sensitive information and potential information leakage during the process are severe issues. Additionally, the majority of existing privacy-preserving techniques can only be applied to the single-database scene, and as a result of the use of intricate homomorphic encryption, their overall efficiency is quite poor. In this paper, we proposed a Multi-party Privacy-Preserving k-Nearest-Neighbors (MPPkNN) classification scheme based on Multi-key Symmetric Homomorphic Encryption (MSHE). In the specific protocol design process, we innovatively apply the homomorphic encryption property of our MSHE to encrypt the query value in a way similar to public key encryption, which protects the confidentiality of secret keys. For privacy purposes, it is important to limit what a cloud server can infer about the encrypted data records. More particularly, we formally prove that for every single party, our Multi-Key SHE is semantically secure against chosen plaintext attack. As for the computational efficiency, our MPPkNN scheme achieves four orders of magnitude faster than the prior work under the same security parameters. Moreover, our scheme realizes addition and multiplication homomorphic operations under different secret keys, which theoretically supports the collaboration of any number of data owners.