电子学报2025，Vol.53Issue(8)：2750-2763,14.DOI:10.12263/DZXB.20250389
元组集合子集的保密计算
Secure Computation of Subsets from Tuple Sets
摘要
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 relation-ships 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 sce-narios requiring protection of set intersections and cardinalities),while the amount of information requiring protection in tu-ple 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 partic-ipant 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 de-termination,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 effi-ciency 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 it-self.Specifically,for two-party computations with a universal set,Alice selects from encrypted data sent by Bob,thus avoid-ing complex modular exponentiation and reducing computational costs.For scenarios without a universal set,using polyno-mial 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 experi-mental validation demonstrating the feasibility of the approaches.关键词
密码学/安全多方计算/同态加密/加密选择/多项式Key words
cryptography/secure multi-party computation/homomorphic encryption/encryption selection/polyno-mial分类
信息技术与安全科学引用本文复制引用
李顺东,杜佶欣,余佳桐,吴川宇..元组集合子集的保密计算[J].电子学报,2025,53(8):2750-2763,14.基金项目
国家重点研发计划(No.2022YFB2703001) National Key Research and Development Program of China(No.2022YFB2703001) （No.2022YFB2703001）
