Privacy-Preserving Sorting Scheme Based on Paillier Homomorphic Encryption

doi:10.3969/j.issn.1671-1122.2025.12.012

Abstract

Abstract:

In the era of big data, data sharing has become a key approach to release the potential of data and enhance business value. Financial institutions can enhance their capabilities in precision marketing, fraud detection, and risk management by collaborating with communication operators to jointly compute users’ communication data. However, how to ensuring privacy protection for users in data sharing remains an urgent challenge that needs to be addressed. This paper proposed a privacy-preserving sorting scheme based on Paillier homomorphic encryption, and rigorously proved its correctness and security. The proposed scheme not only enabled weighted summation operations in ciphertext, but also facilitated efficient sorting in ciphertext to achieve availability and invisibility of shared data. Compared with existing schemes, this method is more efficient in ciphertext comparison and suitable for large-scale privacy data protection sorting. Additionally, the paper uses the application scenario of recommending high-quality bank customers as an example, and verifies the correctness and practicability of the proposed scheme through simulation experiments.

Key words: Paillier encryption algorithm, homomorphic encryption, ciphertext sorting, privacy preservation, secure multi-party computation

CLC Number:

TP309

WANG Houzhen, JIANG Haolang, LIU Jichen, TU Hang. Privacy-Preserving Sorting Scheme Based on Paillier Homomorphic Encryption[J]. Netinfo Security, 2025, 25(12): 1975-1989.

Figures/Tables 13

References 25

[1]	BOLDYREVA A, CHENETTE N, LEE Y, et al. Order-Preserving Symmetric Encryption[C]// Springer. The 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2009). Heidelberg: Springer, 2009: 224-241.
[2]	BOLDYREVA A, CHENETTE N, O’NEILL A. Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions[C]// Springer. The 31st Annual Cryptology Conference (CRYPTO 2011). Heidelberg: Springer, 2011: 578-595.
[3]	YUM D H, KIM D S, KIM J S, et al. Order-Preserving Encryption for Non-Uniformly Distributed Plaintexts[C]// Springer. Information Security Applications (WISA 2011). Heidelberg: Springer, 2011: 84-97.
[4]	BONEH D, LEWI K, RAYKOVA M, et al. Semantically Secure Order-Revealing Encryption: Multi-Input Functional Encryption without Obfuscation[C]// Springer. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015). Heidelberg: Springer, 2015: 563-594.
[5]	CHENETTE N, LEWI K, WEIS S A, et al. Practical Order-Revealing Encryption with Limited Leakage[C]// Springer. Fast Software Encryption:The 23rd International Conference. Heidelberg: Springer, 2016: 474-493.
[6]	CASH D, LIU Fenghao, O’NEILL A, et al. Reducing the Leakage in Practical Order-Revealing Encryption[EB/OL]. (2016-06-28)[2024-10-25]. https://eprint.iacr.org/2016/661.
[7]	RIVEST R L, ADLEMAN L, DERTOUZOS M L. On Data Banks and Privacy Homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.
[8]	PAILLIER P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]// Springer. The 18th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 1999). Heidelberg: Springer, 1999: 223-238.
[9]	GENTRY C, HALEVI S. Implementing Gentry’s Fully-Homomorphic Encryption Scheme[C]// Springer. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2011). Heidelberg: Springer, 2011: 129-148.
[10]	CHATTERJEE A, KAUSHAL M, SENGUPTA I. Accelerating Sorting of Fully Homomorphic Encrypted Data[C]// Springer. The 14th International Conference on Cryptology (INDOCRYPT 2013). Heidelberg: Springer, 2013: 262-273.
[11]	LI Shundong, WANG Daoshun. Efficient Secure Multiparty Computation Based on Homomorphic Encryption[J]. Acta Electronica Sinica, 2013, 41(4): 798-803. doi: 10.3969/j.issn.0372-2112.2013.04.029
	李顺东, 王道顺. 基于同态加密的高效多方保密计算[J]. 电子学报, 2013, 41(4): 798-803. doi: 10.3969/j.issn.0372-2112.2013.04.029
[12]	ZUO Xiangjian, LI Shundong, YANG Xiaoli. An Efficient Homomorphic Encryption Based Solution to Millionaires’ Problem[J]. Journal of Chinese Computer Systems. 2017, 38(3): 455-459.
	左祥建, 李顺东, 杨晓莉. 同态加密的百万富翁问题高效解决方案[J]. 小型微型计算机系统, 2017, 38(3): 455-459.
[13]	LI Shundong, ZUO Xiangjian, YANG Xiaoli, et al. Secure Vector Dominance Protocol and Its Applications[J]. Acta Electronica Sinica, 2017, 45(5): 1117-1123. doi: 10.3969/j.issn.0372-2112.2017.05.014
	李顺东, 左祥建, 杨晓莉, 等. 安全向量优势协议及其应用[J]. 电子学报, 2017, 45(5): 1117-1123. doi: 10.3969/j.issn.0372-2112.2017.05.014
[14]	LIU Ximeng, CHOO K R, DENG R H, et al. Efficient and Privacy-Preserving Outsourced Calculation of Rational Numbers[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 15(1): 27-39. doi: 10.1109/TDSC.2016.2536601 URL
[15]	DING Wenxiu, YAN Zheng, DENG R H. Encrypted Data Processing with Homomorphic Re-Encryption[J]. Information Sciences, 2017(409): 35-55.
[16]	ZHENG Yandong, LU Rongxing, YANG Xue, et al. Achieving Efficient and Privacy-Preserving Top-K Query over Vertically Distributed Data Sources[C]// IEEE. 2019 IEEE International Conference on Communications (ICC 2019). New York: IEEE, 2019: 1-6.
[17]	LI Yuxi, ZHOU Fucai, XU Jian, et al. Multiple-Keyword Encrypted Search with Relevance Ranking on Dual-Server Model[J]. Journal of Computer Research and Development, 2018, 55(10): 2149-2163.
	李宇溪, 周福才, 徐剑, 等. 双服务器模型下支持相关度排序的多关键字密文搜索方案[J]. 计算机研究与发展, 2018, 55(10): 2149-2163.
[18]	HUANG Daxin, GAN Qingqing, WANG Xiaoming, et al. Toward Comparable Homomorphic Encryption for Crowd-Sensing Network[EB/OL]. (2020-06-30)[2024-10-25]. https://ia.cr/2020/806.
[19]	JOST C, LAM H, MAXIMOV A, et al. Encryption Performance Improvements of the Paillier Cryptosystem[EB/OL]. (2015-09-08)[2024-10-25]. https://ia.cr/2015/864.
[20]	BARKER E, CHEN Lidong, ROGINSKY A, et al. Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography[R]. Gaithersburg: National Institute of Standards and Technology, SP 800-56B Rev. 2, 2018.
[21]	LIN H Y, TZENG W G. An Efficient Solution to the Millionaires’ Problem Based on Homomorphic Encryption[C]// Springer. Applied Cryptography and Network Security (ACNS 2005). Heidelberg: Springer, 2005: 456-466.
[22]	DESCHAMPS J P. Hardware Implementation of Finite-Field Arithmetic[M]. New York: McGraw-Hill Education, 2009.
[23]	LYU Kewei, CHEN Chi. Research on Proactive Generation Protocol of Beaver Triples[J]. Netinfo Security, 2022, 22(12): 16-24.
	吕克伟, 陈驰. Beaver三元组主动性生成协议研究[J]. 信息网络安全, 2022, 22(12): 16-24.
[24]	DAMGARD I, JURIK M, NIELSEN J B. A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting[J]. International Journal of Information Security, 2010, 9(6): 371-385. doi: 10.1007/s10207-010-0119-9 URL
[25]	LI Liang, ZHANG Yinghui, DENG Kaixin, et al. Privacy-Aware Power Injection in 5G Smart Grid[J]. Netinfo Security, 2018, 18(12): 87-92.
	李梁, 张应辉, 邓恺鑫, 等. 5G智能电网中具有隐私保护的电力注入系统[J]. 信息网络安全, 2018, 18(12): 87-92.

角色	存储信息	存储开销
DO	公钥pk	3l
	明文M	$\frac{nl}{4}$
	排序结果	$k\left\lceil {{\log }_{2}}k \right\rceil $
PO	权重信息W	$\frac{nl}{4}$
	密文	2knl
	排序结果	$k\left\lceil {{\log }_{2}}k \right\rceil $
TA	加权密文	2kl
	私钥sk	l+a
	排序结果	$k\left\lceil {{\log }_{2}}k \right\rceil $

操作	计算开销
加密	$2kn{{T}_{E}}+kn{{T}_{M}}$
加权求和	$k\left( 1+n \right){{T}_{E}}+k\left( 1+n \right){{T}_{M}}$
密文排序	$2k\cdot {{\log }_{2}}k({{T}_{E}}+{{T}_{M}}+{{T}_{in}}+{{T}_{L}})$

传输信息	通信开销/位
TA分发公钥pk	3l
DO传输密文C	2knl
PO传输加权密文CB	2kl
TA传输排序结果	$k\left\lceil {{\log }_{2}}k \right\rceil $

方案	计算开销	加密算法	困难性假设
文献[11]方案	$2(h+1){{\log }_{2}}N+3x$	Paillier	复合剩余类
文献[12]方案	$2(h+1){{\log }_{2}}N+x$	Paillier	复合剩余类
文献[13]方案	$2(h+1){{\log }_{2}}N+1$	Paillier	复合剩余类
文献[15]方案	$10{{\log }_{2}}N+2$	BCP	离散对数困难
本文方案	$\begin{align} & 3.5{{\log }_{2}}N+2{{\log }_{2}}(N+1)+ \\ & 2{{\log }_{2}}\alpha +1 \\ \end{align}$	Paillier	复合剩余类

方案	计算开销/ms		通信轮数/轮
方案	1024 位	2048 位	通信轮数/轮
文献[11]方案	5.35	31.28	3
文献[12]方案	5.02	30.90	3
文献[13]方案	5.10	29.55	3
文献[15]方案	2.41	17.63	4
本文方案	2.02	11.24	4