元组集合子集的保密计算
Secure Computation of Subsets from Tuple Sets
- 电子学报 2025年53卷第8期 页码：2750-2763
- 作者机构：
陕西师范大学计算机科学学院，陕西西安 710062
- 作者简介：
[ "李顺东 男，1963年12月出生于河南省平顶山市.现为陕西师范大学计算机科学学院教授、博士生导师.主要研究方向为密码学与信息安全.E-mail: shundong@snnu.edu.cn" ]
[ "杜佶欣 女，1999年12月出生于山西省太原市.现为陕西师范大学计算机科学学院硕士研究生.主要研究方向为密码学与信息安全.E-mail: djixin@snnu.edu.cn" ]
[ "余佳桐 女，2000年6月出生于四川省资阳市.现为陕西师范大学计算机科学学院硕士研究生.主要研究方向为密码学与信息安全.E-mail: yujiatong@snnu.edu.cn" ]
[ "吴川宇 女，2000年1月出生于河南省驻马店市.现为陕西师范大学计算机科学学院硕士研究生.主要研究方向为密码学与信息安全.E-mail: wuchuanyu@snnu.edu.cn" ]
- 基金信息：国家重点研发计划(2022YFB2703001)
DOI：10.12263/DZXB.20250389
中图分类号： TP309;收稿：2025-05-17，
录用：2025-07-29，
纸质出版：2025-08-25
- 稿件说明：
移动端阅览
李顺东, 杜佶欣, 余佳桐, 等. 元组集合子集的保密计算[J]. 电子学报, 2025, 53(08): 2750-2763.
LI Shun-dong, DU Ji-xin, YU Jia-tong, et al. Secure Computation of Subsets from Tuple Sets[J]. Acta Electronica Sinica, 2025, 53(08): 2750-2763.
李顺东, 杜佶欣, 余佳桐, 等. 元组集合子集的保密计算[J]. 电子学报, 2025, 53(08): 2750-2763. DOI：10.12263/DZXB.20250389
LI Shun-dong, DU Ji-xin, YU Jia-tong, et al. Secure Computation of Subsets from Tuple Sets[J]. Acta Electronica Sinica, 2025, 53(08): 2750-2763. DOI：10.12263/DZXB.20250389
摘要
安全多方计算是现代密码学的一个重要研究分支，它能够有效保护数据，防止隐私数据被不当获取或利用，同时确保参与者在共享数据时仍能保持数据隐私和完整性.其中，集合子集的保密计算是支撑保密数据查询、保密数据外包、相似文档检索以及其他隐私数据安全共享的关键技术.现有方案主要聚焦于单一元素集合的子集判定，对元组集合缺乏有效支持，且在实用性、安全性与效率层面存在以下挑战：需对元组集合进行两次独立子集判定，导致计算效率低下，且中间结果可能暴露非子集关系的敏感数据；难以有效保护单一元素集合的隐私（尤其在需要保护集合交集与势的场景下），而元组集合所需保护的信息量更大，隐私泄露风险显著加剧；现有单一元素子集协议可能存在误判；同时，现有方案缺乏对某一参与方持有多个元组集合的高效批量判定.针对上述挑战，本文首次提出某个参与方有多个集合，且集合元素是元组情况下的集合子集的保密计算协议，针对参与方有无全集设计了不同的协议.所提协议通过单次执行即可同步判定一个元组集合是否为其他多个元组集合的子集，避免分步计算导致的中间结果泄露风险.本文协议可显著提升效率，并具备广泛的适用性，同时本文所提协议不仅保护了参与双方元组集合的势，也保护了元组集合子集的势与具体元素.在解决有全集的两方计算时，Alice只需从Bob发送的加密数据中进行选择，避免了复杂的模指数运算，从而降低了计算成本；在解决无全集的两方计算时，结合集合的多项式表示，Bob只需将自己的数据代入Alice发送的加密多项式中，即可计算集合的子集.最后，本文使用公认的模拟范式证明了两个协议是安全的，且实验表明了方案是可行的.
Abstract
Secure multi-party computation is an important research branch of modern cryptography. It can effectively protect data
prevent privacy data from being improperly acquired or exploited
and simultaneously ensure that participants maintain data privacy and integrity while sharing data. Among its applications
secure computation for set subset relationships is a key technology underpinning private data queries
confidential data outsourcing
similar document retrieval
and other secure sharing of private data. Existing schemes primarily focus on subset determination for sets composed of single elements and lack effective support for complex sets composed of tuples. Furthermore
they face the following challenges in terms of practicality
security
and efficiency: existing schemes require performing two independent subset determinations on the tuple set
resulting in low computational efficiency
and intermediate results may expose sensitive data unrelated to the subset relationship; Existing schemes struggle to effectively protect the privacy of single-element sets (especially in scenarios requiring protection of set intersections and cardinalities)
while the amount of information requiring protection in tuple sets is larger
significantly exacerbating privacy leakage risks; Existing subset protocols for single-element sets may yield erroneous judgments; Simultaneously
existing schemes lack support for efficient batch determination when one participant holds multiple tuple sets. To address the above challenges
this paper proposes
for the first time
secure computation protocols for set subsets where one participant holds multiple sets and the set elements are tuples
designing distinct schemes for scenarios where participants possess or lack a universal set. The proposed protocols enable the synchronous determination
through a single execution
of whether one tuple set is a subset of multiple other tuple sets
avoiding the privacy leakage risk of intermediate results inherent in stepwise computation. The protocols in this paper significantly enhance efficiency and possess broad applicability. Furthermore
the protocols proposed in this paper not only protect the cardinality of the tuple sets held by both participating parties but also protect the cardinality and specific elements of the tuple subset itself. Specifically
for two-party computations with a universal set
Alice selects from encrypted data sent by Bob
thus avoiding complex modular exponentiation and reducing computational costs. For scenarios without a universal set
using polynomial representations of sets
Bob simply substitutes his data into the encrypted polynomial sent by Alice to compute subset confidentiality. Finally
using established simulation paradigms
this paper proves the security of the protocols
with experimental validation demonstrating the feasibility of the approaches.
关键词
Keywords
references
YAO A C . Protocols for secure computations [C ] // 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) . Piscataway : IEEE , 2008 : 160 - 164 .
FREEDMAN M J , HAZAY C , NISSIM K , et al . Efficient set intersection with simulation-based security [J ] . Journal of Cryptology , 2016 , 29 ( 1 ): 115 - 155 .
GOLDREICH O . Cryptography and cryptographic protocols [J ] . Distributed Computing , 2003 , 16 ( 2 ): 177 - 199 .
KUMAR S N . Review on network security and cryptography [J ] . International Transaction of Electrical and Computer Engineers System , 2015 , 3 ( 1 ): 1 - 11 .
ZHAO C , ZHAO S N , ZHAO M H , et al . Secure multi-party computation: Theory, practice and applications [J ] . Information Sciences , 2019 , 476 : 357 - 372 .
GOLDWASSER S . Multi party computations: Past and present [C ] // Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing - PODC’97 . New York : ACM , 1997 : 1 - 6 .
BEN-OR M , WIGDERSON A . Completeness theorems for non-cryptographic fault-tolerant distributed computation [C ] // Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing - STOC’88 . New York : ACM , 1988 : 1 - 10 .
TEO S G , CAO J N , LEE V C S . DAG: A general model for privacy-preserving data mining [J ] . IEEE Transactions on Knowledge and Data Engineering , 2020 , 32 ( 1 ): 40 - 53 .
WANG F W , ZHU H , LIU X M , et al . Privacy-preserving collaborative model learning scheme for E-healthcare [J ] . IEEE Access , 2019 , 7 : 166054 - 166065 .
DUONG T , PHAN D H , TRIEU N . Catalic: Delegated PSI cardinality with applications to contact tracing [M ] // Advances in Cryptology - ASIACRYPT 2020 . Cham : Springer International Publishing , 2020 : 870 - 899 .
FREEDMAN M J , NISSIM K , PINKAS B . Efficient private matching and set intersection [M ] // Advances in Cryptology - EUROCRYPT 2004 . Berlin, Heidelberg : Springer , 2004 : 1 - 19 .
KISSNER L , SONG D . Privacy-preserving set operations [M ] // Advances in Cryptology - CRYPTO 2005 . Berlin, Heidelberg : Springer , 2005 : 241 - 257 .
窦家维 , 陈明艳 . 多重集的保密计算及应用 [J ] . 电子学报 , 2020 , 48 ( 1 ): 204 - 208 .
DOU J W , CHEN M Y . Secure multiset operations and their applications [J ] . Acta Electronica Sinica , 2020 , 48 ( 1 ): 204 - 208 . (in Chinese)
赵雪玲 , 家珠亮 , 李顺东 . 集合交集问题的安全计算 [J ] . 密码学报 , 2022 , 9 ( 2 ): 294 - 307 .
ZHAO X L , JIA Z L , LI S D . A secure multiparty intersection computation [J ] . Journal of Cryptologic Research , 2022 , 9 ( 2 ): 294 - 307 . (in Chinese)
WANG W L , LI S D , DOU J W , et al . Privacy-preserving mixed set operation [J ] . Information Sciences , 2020 , 525 ( 7 ): 67 - 81 .
窦家维 , 刘旭红 , 王文丽 . 有理数域上两方集合的高效保密计算 [J ] . 计算机学报 , 2020 , 43 ( 8 ): 1397 - 1413 .
DOU J W , LIU X H , WANG W L . Privacy preserving two-party rational set computation [J ] . Chinese Journal of Computers , 2020 , 43 ( 8 ): 1397 - 1413 . (in Chinese)
张朋飞 , 翟睿辰 , 程祥 , 等 . 满足地理不可区分性的偏好感知多对多任务分配算法 [J ] . 电子学报 , 2025 , 53 ( 3 ): 878 - 894 .
ZHANG P F , ZHAI R C , CHENG X , et al . A preference-aware many-to-many task allocation algorithm under geo-indistinguishability [J ] . Acta Electronica Sinica , 2025 , 53 ( 3 ): 878 - 894 . (in Chinese)
HU J W , ZHAO Y J , HONG MENG TAN B , et al . Enabling threshold functionality for private set intersection protocols in cloud computing [J ] . IEEE Transactions on Information Forensics and Security , 2024 , 19 : 6184 - 6196 .
WU A X , XIN X J , ZHU J H , et al . Cloud-assisted laconic private set intersection cardinality [J ] . IEEE Transactions on Cloud Computing , 2024 , 12 ( 1 ): 295 - 305 .
周素芳 . 集合相关问题的保密计算研究 [D ] . 西安 : 陕西师范大学 , 2019 .
ZHOU S F . Research on Secure Multiparty Computation of Set-Related Problems [D ] . Xi’an : Shaanxi Normal University , 2019 . (in Chinese)
窦家维 , 王颖囡 , 葛雪 . 区间关系保密计算若干问题研究 [J ] . 电子学报 , 2021 , 49 ( 1 ): 50 - 57 .
DOU J W , WANG Y N , GE X . Some research on secure interval relation computation [J ] . Acta Electronica Sinica , 2021 , 49 ( 1 ): 50 - 57 . (in Chinese)
袁水莲 , 皮德常 , 胥萌 . 基于差分隐私的轨迹隐私保护方法 [J ] . 电子学报 , 2021 , 49 ( 7 ): 1266 - 1273 .
YUAN S L , PI D C , XU M . Trajectory privacy protection method based on differential privacy [J ] . Acta Electronica Sinica , 2021 , 49 ( 7 ): 1266 - 1273 . (in Chinese)
康海燕 , 冀源蕊 . 基于本地化差分隐私的时序位置发布方案研究 [J ] . 电子学报 , 2022 , 50 ( 9 ): 2222 - 2232 .
KANG H Y , JI Y R . Research on time-serial location data publication based on local differential privacy [J ] . Acta Electronica Sinica , 2022 , 50 ( 9 ): 2222 - 2232 . (in Chinese)
朱伊波 , 方贤进 , 张朋飞 , 等 . 本地差分隐私下面向离群点的真值发现算法研究 [J ] . 电子学报 , 2025 , 53 ( 5 ): 1541 - 1558 .
ZHU Y B , FANG X J , ZHANG P F , et al . A study of truth discovery algorithms for forward outliers under local differential privacy [J ] . Acta Electronica Sinica , 2025 , 53 ( 5 ): 1541 - 1558 . (in Chinese)
XIONG L , JIANG Z L , HUANG Y , et al . Efficient private set intersection based on functional encryption [C ] // The 2022 4th International Conference on Data Intelligence and Security . Piscataway : IEEE , 2022 : 9 - 15 .
BANAWAN K , ARASLI B , WEI Y P , et al . The capacity of private information retrieval from heterogeneous uncoded caching databases [J ] . IEEE Transactions on Information Theory , 2020 , 66 ( 6 ): 3407 - 3416 .
WANG N , HEIDARZADEH A , SPRINTSON A , et al . A new approach to harnessing side information in multi-server private information retrieval [C ] // The IEEE International Symposium on Information Theory (ISIT) . Piscataway : IEEE , 2024 : 2646 - 2651 .
CHEN Z , WANG Z Y , JAFAR S ALI . The capacity of T-private information retrieval with private side information [J ] . IEEE Transactions on Information Theory , 2020 , 66 ( 8 ): 4761 - 4773 .
ERHILI L , HEIDARZADEH A . Achieving capacity of PIR with private side information with low sub-packetization and without MDS codes [C ] // 2024 IEEE International Symposium on Information Theory . Piscataway : IEEE , 2024 : 2652 - 2657 .
SIAVOSHANI M J , SHARIATPANAHI S P , MADDAH-ALI M A . Private information retrieval for a multi-message scenario with private side informationin [J ] . IEEE Transactions on Communications , 2021 , 69 ( 5 ): 3235 - 3244 .
LU Y X , JAFAR S A . On single server private information retrieval with private coded side information [J ] . IEEE Transactions on Information Theory , 2023 , 69 ( 5 ): 3263 - 3284 .
HEIDARZADEH A , SPRINTSON A . The linear capacity of single-server individually-private information retrieval with side information [C ] // The IEEE International Symposium on Information Theory (ISIT) . Piscataway : IEEE , 2022 : 2833 - 2838 .
HSU H C , LIU Z Y , TSO R , et al . Multi-value private information retrieval using homomorphic encryption [C ] // 2020 15th Asia Joint Conference on Information Security . Piscataway : IEEE , 2020 : 82 - 88 .
LING G W , TANG F , CAI C C , et al . P²FRPSI: Privacy-preserving feature retrieved private set intersection [J ] . IEEE Transactions on Information Forensics and Security , 2024 , 19 : 2201 - 2216 .
LING G W , TANG P , SHAN J Y , et al . More efficient, privacy-enhanced, and powerful privacy-preserving feature retrieval private set intersection [J ] . IEEE Transactions on Information Forensics and Security , 2025 , 20 : 4815 - 4827 .
WANG Z S , BANAWAN K , ULUKUS S . Private set intersection: A multi-message symmetric private information retrieval perspective [J ] . IEEE Transactions on Information Theory , 2022 , 68 ( 3 ): 2001 - 2019 .
CHEN Y C , HUANG K C . JEDI: Joint and effective privacy preserving outsourced set intersection and data integration protocols [J ] . IEEE Transactions on Information Forensics and Security , 2023 , 18 : 4504 - 4514 .
赵昊 . 两种隐私集合交集计算协议研究 [D ] . 成都 : 电子科技大学 , 2024 .
ZHAO H . Research on Two Types of Private Set Intersection Computation Protocols [D ] . Chengdu : University of Electronic Science and Technology of China , 2024 . (in Chinese)
徐银 . 隐私保护下集合运算研究 [D ] . 济南 : 山东大学 , 2023 .
XU Y . Research on Privacy-Preserving Set Operations [D ] . Jinan : Shandong University , 2023 . (in Chinese)
罗磊 . 基于云辅助的隐私集合交集计算协议的研究 [D ] . 上海 : 华东师范大学 , 2023 .
LUO L . Researches on Private Set Intersection Computation Protocols Under the Cloud Environments [D ] . Shanghai : East China Normal University , 2023 . (in Chinese)
马立驹 . 隐私保护的集合运算研究 [D ] . 济南 : 山东师范大学 , 2024 .
MA L J . Research on Privacy-Preserving Set Operations [D ] . Jinan : Shandong Normal University , 2024 . (in Chinese)
苏代钊 . 面向隐私保护的集合求交计算及其应用研究 [D ] . 成都 : 西华大学 , 2024 .
SU D Z . Research on Privacy-Preserving Set Intersection Computation and Its Applications [D ] . Chengdu : Xihua University , 2024 . (in Chinese)
李婷 . 基于大数据平台支持任意计算和模糊匹配的隐私保护集合交集方案 [D ] . 西安 : 西安电子科技大学 , 2024 .
LI T . Privacy Protection Set Intersection Scheme Based on Big Data Platform Supporting Arbitrary Computing and Fuzzy Matching [D ] . Xi’an : Xidian University , 2024 . (in Chinese)
李顺东 , 赵雪玲 , 家珠亮 . 集合交集元素和的保密计算 [J ] . 电子学报 , 2023 , 51 ( 1 ): 86 - 92 .
LI S D , ZHAO X L , JIA Z L . Private intersection-sum computation [J ] . Acta Electronica Sinica , 2023 , 51 ( 1 ): 86 - 92 . (in Chinese)
马秀莲 , 张倦倦 , 李顺东 . 保密计算交集对应元素和的最大值 [J ] . 电子学报 , 2023 , 51 ( 7 ): 1835 - 1841 .
MA X L , ZHANG J J , LI S D . Maximum value of sum of intersection elements of secret calculation [J ] . Acta Electronica Sinica , 2023 , 51 ( 7 ): 1835 - 1841 . (in Chinese)
LIU Q , GUO X J , YANG K , et al . Labeled private set intersection from distributed point function [J ] . IEEE Transactions on Information Forensics and Security , 2025 , 20 : 2970 - 2983 .
YANG Y B , HU Y W , LI R F , et al . LSE: Efficient symmetric searchable encryption based on labeled PSI [J ] . IEEE Transactions on Services Computing , 2024 , 17 ( 2 ): 563 - 574 .
GOLDREICH O , MICALI S , WIGDERSON A . How to play ANY mental game [C ] // Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing - STOC’87 . New York : ACM , 1987 : 218 - 229 .
GOLDREICH O . Foundations of Cryptography Volume II Basic Applications [M ] . Cambridge, UK : Cambridge University Press , 2004 .
0
浏览量
5
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies