安全高效的MDS外包方案

Secure and Efficient Outsourcing Protocol of MDS

多维尺度分析(Multi-Dimensional Scaling,MDS)作为一种传统有效的降维方法,利用样本的成对相似性,构建一个低维空间,满足每对样本在高维空间的距离与在构建的低维空间中的样本相似性尽可能维持一致的条件,其在数据分析和数据降维都有着广泛的应用前景。由于本地资源受限,MDS算法有时无法在本地实现。云服务器拥有强大计算能力和存储能力,能够为人们解决这样的问题。而这样的计算方式也带来了许多挑战,尤其是安全性。针对高复杂度的MDS算法首次提出了外包方案,将MDS算法交给云服务器以降低用户本地的复杂度。在提出的方案中,用户的隐私得到了很好的保护,本地资源也得到了大量的节约。另外,用户也可以验证返回结果的正确性。从理论和实验两方面对提出的方案进行了可行性的阐述。

Multi-dimensional scaling(MDS),as a traditional effective dimensionality reduction method,uses the pairwise similarity of samples to construct a low-dimensional space,making the distance between each pair of samples in the highdimensional space be consistent with the sample similarity of the low-dimensional space as soon as possible.It has broad application prospects in data analysis and data dimensionality reduction.However,due to the limited local resources,the MDS algorithm sometimes cannot be implemented locally.Clouds with powerful computing and storage capabilities can solve such problems for people.This promising computing method also brings many challenges,especially security issues.This paper proposes an outsourcing scheme for the high-complexity MDS algorithm for the first time.The MDS algorithm is handed over to the cloud server to reduce the user’s local complexity.In the proposed scheme, user privacy has been well protected,and local resources have also been greatly saved.In addition,users can also verify the correctness of the returned results.This paper expounds the feasibility of the proposed scheme from both theoretical and experimental aspects.