基于Paillier同态加密的隐私保护排序方案

doi:10.3969/j.issn.1671-1122.2025.12.012

信息网络安全 ›› 2025, Vol. 25 ›› Issue (12): 1975-1989.doi: 10.3969/j.issn.1671-1122.2025.12.012

基于Paillier同态加密的隐私保护排序方案

王后珍¹^,²(), 江皓朗¹, 刘继辰¹, 涂航¹

1.武汉大学国家网络安全学院，武汉 430072
2.先进密码技术与系统安全四川省重点实验室，成都 610054

收稿日期:2025-01-24 出版日期:2025-12-10 发布日期:2026-01-06
通讯作者: 王后珍 E-mail:whz@whu.edu.cn
作者简介:王后珍（1981—），男，湖北，副教授，博士，CCF会员，主要研究方向为公钥密码学、抗量子密码|江皓朗（2000—），男，安徽，硕士研究生，主要研究方向为公钥密码学|刘继辰（2000—），男，山东，硕士研究生，主要研究方向为公钥密码学|涂航（1975—），男，湖北，副教授，博士，CCF会员，主要研究方向为物联网安全、嵌入式系统安全、密码学
基金资助:
国家自然科学基金(62272348);国家自然科学基金(62272385);国家自然科学基金(62272389);国家自然科学基金(U19B2021);国家自然科学基金(U20B2064);国家重点研发计划(2022YFB4500800);先进密码技术与系统安全四川省重点实验室开放课题(SKLACSS-202203);中央高校基本科研业务费专项资金(2042022kf002);湖北省重点研发计划(2022BAA041)

Privacy-Preserving Sorting Scheme Based on Paillier Homomorphic Encryption

WANG Houzhen¹^,²(), JIANG Haolang¹, LIU Jichen¹, TU Hang¹

1. School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China
2. Advanced Cryptography and System Security Key Laboratory of Sichuan Province, Chengdu 610054, China

Received:2025-01-24 Online:2025-12-10 Published:2026-01-06
Contact: WANG Houzhen E-mail:whz@whu.edu.cn

摘要/Abstract

摘要：

在大数据时代背景下，数据共享已成为释放数据潜力、提升业务价值的关键途径。金融机构通过与通信运营商合作，对用户的通信数据进行联合建模与分析，可提升其在精准营销、欺诈检测及风险管理方面的能力。然而，如何在数据共享过程中保护用户隐私是一个亟待解决的问题。文章提出一种基于Paillier同态加密的隐私保护排序方案，并对其正确性和安全性进行了证明。该方案不仅支持密文下的加权求和运算，还支持高效的密文排序，从而实现了共享数据的可用不可见。与现有方案相比，该方案在密文排序效率方面更具优势，适用于大规模的隐私数据保护排序场景。此外，文章以银行优质客户推荐应用场景为例，通过仿真实验验证了方案的正确性与可用性。

关键词: Paillier加密算法, 同态加密, 密文排序, 隐私保护, 安全多方计算

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

中图分类号:

TP309

王后珍, 江皓朗, 刘继辰, 涂航. 基于Paillier同态加密的隐私保护排序方案[J]. 信息网络安全, 2025, 25(12): 1975-1989.

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.

图/表 13

图1

表1

表2

表3

图2

表4

表5

表6

图3

图4

图5

图6

表7

参考文献 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

基于Paillier同态加密的隐私保护排序方案

Privacy-Preserving Sorting Scheme Based on Paillier Homomorphic Encryption

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 25

相关文章 15

编辑推荐

Metrics

本文评价

方案对比		HRES方案	本文方案
同态特性		满足加法同态特性	满足加法同态特性
角色		用户、数据服务提供方、安全控制服务器	DO、PO、TA
明文加密	密钥生成	所有角色均生成一对用户公私钥；数据服务提供方和安全控制服务器通过密钥交换协议生成公钥PK	由TA生成算法的公钥和私钥，不需要额外生成新的密钥
明文加密	加密方式	使用PK和用户公钥加密	明文仅能由DO使用公钥加密
密文排序	密文要求	仅能比较使用公钥PK加密的密文	可以比较DO加密的密文，也可以比较PO加权求和
密文排序	实现方式	对密文进行同态减法操作，再由数据服务提供方和安全控制服务器共同判断新密文的正负性，最终由发起密文排序请求的用户判断密文排序结果	由TA使用私钥对两条密文的比值进行解密，根据解密结果判断密文之间的大小关系

参数	数值
客户总人数/万人	50
客户信息数量/万条	1000
客户信息长度/GB	0.30
规则权重长度/B	640
客户信息密文长度/GB	2.38
客户价值密文长度/GB	0.12
时间开销/h	加密	2.52
	价值计算	3.81
	排序	2.92
	总计	9.25

[1]	拾以娟, 周丹平, 范磊, 刘茵. 基于可信执行环境的安全多方计算协议[J]. 信息网络安全, 2025, 25(9): 1439-1446.
[2]	田海博, 李奕彤, 杜育松. 同态加密PIR中查询请求带宽优化的通用构造与实例[J]. 信息网络安全, 2025, 25(7): 1092-1102.
[3]	朱率率, 刘科乾. 基于掩码的选择性联邦蒸馏方案[J]. 信息网络安全, 2025, 25(6): 920-932.
[4]	赵锋, 范淞, 赵艳琦, 陈谦. 基于本地差分隐私的可穿戴医疗设备流数据隐私保护方法[J]. 信息网络安全, 2025, 25(5): 700-712.
[5]	秦金磊, 康毅敏, 李整. 智能电网中轻量级细粒度的多维多子集隐私保护数据聚合[J]. 信息网络安全, 2025, 25(5): 747-757.
[6]	胡宇涵, 杨高, 蔡红叶, 付俊松. 三维分布式无线智能系统数据传输路径隐私保护方案[J]. 信息网络安全, 2025, 25(4): 536-549.
[7]	何可, 王建华, 于丹, 陈永乐. 基于自适应采样的机器遗忘方法[J]. 信息网络安全, 2025, 25(4): 630-639.
[8]	李佳东, 曾海涛, 彭莉, 汪晓丁. 一种保护数据隐私的匿名路由联邦学习框架[J]. 信息网络安全, 2025, 25(3): 494-503.
[9]	张观平, 魏福山, 陈熹, 顾纯祥. 基于区块链的隐私保护跨域认证协议[J]. 信息网络安全, 2025, 25(12): 1948-1960.
[10]	秦思滢, 孙兵, 付绍静, 唐小妹. 基于RLWR的同态加密方案的密钥切换技术[J]. 信息网络安全, 2025, 25(12): 1961-1974.
[11]	陈春玲, 路献辉, 王睿达, 白吉康, 解树兵. 全同态加密中的门自举研究[J]. 信息网络安全, 2025, 25(11): 1691-1706.
[12]	王亚杰, 陆锦标, 李宇航, 范青, 张子剑, 祝烈煌. 基于可信执行环境的联邦学习分层动态防护算法[J]. 信息网络安全, 2025, 25(11): 1762-1773.
[13]	张洋, 魏荣, 尤启迪, 蒋小彤. 基于多密钥同态加密的电子投票协议[J]. 信息网络安全, 2025, 25(1): 88-97.
[14]	温金明, 刘庆, 陈洁, 吴永东. 基于错误学习的全同态加密技术研究现状与挑战[J]. 信息网络安全, 2024, 24(9): 1328-1351.
[15]	林湛航, 向广利, 李祯鹏, 徐子怡. 基于同态加密的前馈神经网络隐私保护方案[J]. 信息网络安全, 2024, 24(9): 1375-1385.