计算机科学
汉明距离
密码学
安全多方计算
架空(工程)
欧几里德距离
方案(数学)
数学证明
计算
理论计算机科学
秘密分享
汉明码
数据挖掘
算法
人工智能
数学
操作系统
数学分析
几何学
解码方法
区块代码
作者
Zhi Li,Hao Wang,Songnian Zhang,Wenying Zhang,Rongxing Lu
标识
DOI:10.1109/tifs.2023.3337940
摘要
As a practical machine learning method, the K-nearest neighbors (KNN) classification has received widespread attention. The achievement of the KNN classification relies heavily on a large amount of labeled data. However, in the real world, data is often held by different data owners. How to realize efficient joint computing among multiple data owners under the premise of protecting data security and privacy is an urgent problem to be solved. In this paper, we construct a secure multi-party KNN classification scheme (SecKNN) based on function secret sharing (FSS) technology, which is a novel cryptographic primitive and can achieve cheap communication and computation costs for secure computation. Compared with the existing works, our scheme dramatically reduces computational overhead and runs roughly 50.8 times faster than the state-of-the-art approach. Furthermore, our scheme supports the secure KNN classification under general distance functions such as Euclidean distance, Manhattan distance, and Hamming distance. To implement our SecKNN scheme, we design two efficient FSS schemes for Hamming distance function, which implements secure two-party and multi-party Hamming distance computation in a single round. They can be considered as independent research results. Finally, we give formal security proofs for the proposed protocols and validate the effectiveness and efficiency of our protocols through experiments.
科研通智能强力驱动
Strongly Powered by AbleSci AI