Abstract: Skyline query is designed to select a set of suitable points from a large number of data points, which provides a key technique for multiobjective optimization of locationoriented objects. Plaintext Skyline query will cause data leakage. Homomorphic encryption Paillier is adopted to protect data and implement ciphertext Skyline query. To address the low efficiency of the Paillier encryption and decryption the MPGPaillier (multiple primegenerator Paillier) algorithm, which is combined with multiple primes and common modules, is proposed to prove the correctness and security of the algorithm. Experimental comparison and analysis show that MPGPaillier has significant improvement over Paillier and MPPaillier (multiple primePaillier) algorithms in terms of encryption and decryption efficiency.

Key words: Skyline query, homomorphic encryption, Paillier, multiple prime, public modulus

摘要： Skyline查询旨在大量数据点中选择出一组符合要求的点集合，为面向位置对象的多目标优化问题提供了关键技术.明文的Skyline查询会引发数据泄露，采取同态加密Paillier对数据进行保护，实现密文上的Skyline查询.针对Paillier加解密效率低的问题,提出了多素数和公共模数联合的MPGPaillier(multiple primegenerator Paillier)算法，对算法的正确性和安全性进行证明.实验对比分析表明，在加解密效率方面，MPGPaillier比Paillier和MPPaillier(multiple primePaillier)算法有显著提升.

关键词: Skyline查询, 同态加密, Paillier, 多素数, 公共模数