微信服务号

微信订阅号

2025年4月23日 7:47 星期三
首页 > 过刊浏览>2023年第34卷第7期 >3343-3353. DOI:10.13328/j.cnki.jos.006529
PDF HTML阅读 XML下载 导出引用 引用提醒
集合交集元素之和的保密计算
作者:
作者简介:

李顺东(1963-),男,博士,教授,博士生导师,主要研究领域为公钥密码学,安全多方计算;张凯鑫(1996-),女,硕士生,主要研究领域为密码学与信息安全;杨晨(1996-),女,硕士生,主要研究领域为密码学,信息安全;汪榆淋(1997-),女,硕士生,主要研究领域为应用数学,密码学

通讯作者:

李顺东,E-mail:shundong@snnu.edu.cn

中图分类号:

TP309

基金项目:

国家自然科学基金（61272435）


Secure Intersection-sum Computation
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [35]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    安全多方计算是国际密码学的研究热点之一，保密计算集合交集元素之和问题是安全多方计算比较新的问题之一.该问题在工商业、医疗健康等领域具有重要的理论意义和实用价值.现有解决方案是在有全集情况下设计的，在计算过程中会泄露交集的势且存在一定的误判.在半诚实模型下基于Paillier同态加密算法设计了3个协议，协议1计算共有标识符的数量（即用户标识符交集的势）以及与这些用户相关联的整数值之和，协议2和协议3是在不泄露交集势的情况下计算交集元素关联值之和.整个计算过程不泄露关于协议双方私人输入的任何更多信息.所提协议是在无全集情况下设计的，采用模拟范例证明了所设计协议的安全性，用实验验证协议的高效性.

    Abstract:

    Secure multi-party computation is one of the hot issues in international cryptographic community. The secure computation of intersection-sum is a new problem of secure multi-party computation. The problem has important theoretical significance and practical value in the fields of industry, commerce, and healthcare. The existing solutions are designed under the condition that the private sets are subsets of a universal set and the intersection cardinality will be leaked and there are some false probabilities. This study, based on the Paillier cryptosystem, designs three protocols for the intersection-sum problem. These protocols are secure in the semi-honest model. Protocol 1 privately computes the number of common identifiers (i.e., user identifier intersection cardinality) and the sum of the integer values associated with these users, Protocol 2 and Protocol 3 privately compute the sum of the associated integer values of intersection elements without leaking the intersection cardinality. The whole computation process does not reveal any more information about their private inputs except for the intersection-sum. The protocols do not restrict that the private sets are subsets of a universal set, and they can be applied in more scenarios. It is proved, by using the simulation paradigm, that these protocols are secure in the semi-honest model. The efficiency of the protocols is also tested by experiments.

    参考文献
    [1] Yao AC. Protocols for secure computations. In: Proc. of the 23rd Annual Symp. on Foundations of Computer Science. Chicago: IEEE, 1982. 160–164.
    [2] Ben-Or M, Goldwasser S, Wigfderson A. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. of the 20th Annual ACM Symp. on Theory of Computing. Chicago: Association for Computing Machinery, 1988. 1–10.
    [3] Li SD, Wang DS, Dai YQ. Symmetric cryptographic protocols for extended millionaires’ problem. Science in China Series F: Information Sciences, 2009, 52(6): 974–982. [doi: 10.1007/s11432-009-0109-6]
    [4] Freedman MJ, Nissim K, Pinkas B. Efficient private matching and set intersection. In: Cachin C, Camenisch JL, eds. Advances in Cryptology (EUROCRYPT 2004). Lecture Notes in Computer Science, vol. 3027. Interlaken: Springer, 2004. 1–19.
    [5] Resenede ACD, de Freitas Aranha D. Faster unbalanced Private Set Intersection in the semi-honest setting. Journal of Cryptographic Engineering, 2021, 11: 21–38. [doi: 10.1007/s13389-020-00242-7]
    [6] Falk BH, Noble D, Ostrovsky R. Private set intersection with linear communication from general assumptions. In: Proc. of the 18th ACM Workshop on Privacy in the Electronic Society. London: Association for Computing Machinery, 2019. 14–25.
    [7] Le PH, Ranellucci S, Gordon SD. Two-party private set intersection with an untrusted third party. In: Proc. of the 2019 ACM SIGSAC Conf. on Computer and Communications Security. London: Association for Computing Machinery, 2019. 2403–2420.
    [8] Ciampi M, Orlandi C. Combining private set-intersection with secure two-party computation. In: Catalano D, de Prisco R, eds. Security and Cryptography for Networks (SCN 2018). Lecture Notes in Computer Science, vol. 11035. Amalfi: Springer, 2018. 464–482.
    [9] Wang ZS, Banawan K, Ulukus S. Multi-party private set intersection: An information-theoretic approach. IEEE Journal on Selected Areas in Information Theory, 2021, 2(1): 366–379. [doi: 10.1109/JSAIT.2021.3057597]
    [10] Debnath SK, Sakurai K, Dey K, Kundu N. Secure outsourced private set intersection with linear complexity. In: Proc. of the 2021 IEEE Conf. on Dependable and Secure Computing (DSC). Aizuwakamatsu: IEEE, 2021. 1–8.
    [11] Seo JH, Cheon JH, Katz J. Constant-round multi-party private set union using reversed laurent series. In: Fischlin M, Buchmann J, Manulis M, eds. Public Key Cryptography (PKC 2012). Lecture Notes in Computer Science, vol. 7293. Darmstadt: Springer, 2012. 398–412.
    [12] Blanton M, Aguiar E. Private and oblivious set and multiset operations. International Journal of Information Security, 2016, 15(5): 493–518. [doi: 10.1007/s10207-015-0301-1]
    [13] Chun JY, Hong D, Jeong IR, Lee DH. Privacy-preserving disjunctive normal form operations on distributed sets. Information Sciences, 2013, 231: 113–122. [doi: 10.1016/j.ins.2011.07.003]
    [14] Debnath SK, Stǎnicǎ P, Kundu N, Choudhury T. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15(2): 365–386. [doi: 10.3934/amc.2020071]
    [15] Branco P, Döttling N, Pu SH. Multiparty cardinality testing for threshold private intersection. In: Garay JA, ed. Public-key Cryptography (PKC 2021). Lecture Notes in Computer Science, vol. 12711. Springer, 2021. 32–60.
    [16] Debnath SK, Dutta R. Secure and efficient private set intersection cardinality using bloom filter. In: Lopez J, Mitchell C, eds. Information Security (ISC 2015). Lecture Notes in Computer Science, vol. 9290. Trondheim: Springer, 2015. 209–226.
    [17] Egert R, Fischlin M, Gend D, Jacob S, Senker M, Tillmanns J. Privately computing set-union and set-intersection cardinality via Bloom filters. In: Foo E, Stebila D, eds. Information Security and Privacy (ACISP 2015). Lecture Notes in Computer Science, vol. 9144. Brisbane: Springer, 2015. 413–430.
    [18] 窦家维, 刘旭红, 周素芳, 李顺东. 高效的集合安全多方计算协议及应用. 计算机学报, 2018, 41(8): 1844–1860. [doi: 10.11897/SP.J.1016.2018.01844]
    Dou JW, Liu XH, Zhou SF, Li SD. Efficient secure multiparty set operations protocols and their application. Chinese Journal of Computers, 2018, 41(8): 1844–1860 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2018.01844]
    [19] 窦家维, 陈明艳. 多重集的保密计算及应用. 电子学报, 2020, 48(1): 204–208. [doi: 10.3969/j.issn.0372-2112.2020.01.025]
    Dou JW, Chen MY. Secure multiset operations and their applications. Acta Electronica Sinica, 2020, 48(1): 204–208 (in Chinese with English abstract). [doi: 10.3969/j.issn.0372-2112.2020.01.025]
    [20] 陈振华, 李顺东, 黄琼, 丁勇, 刘娅茹. 非加密方法安全计算两种集合关系. 软件学报, 2018, 29(2): 473–482. http://www.jos.org.cn/1000-9825/5262.htm
    Chen ZH, Li SD, Huang Q, Ding Y, Liu YR. Secure computation of two set-relationships with the unencrypted method. Ruan Jian Xue Bao/Journal of Software, 2018, 29(2): 473–482 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5262.htm
    [21] Zhou SF, Li SD, Dou JW, Geng YL, Liu X. Efficient secure multiparty subset computation. Security and Communication Networks, 2017, 2017: 9717580. [doi: 10.1155/2017/9717580]
    [22] Ion M, Kreuter B, Nergiz E, Patel S, Saxena S, Seth K, Shanahan D, Yung M. Private intersection-sum protocol with applications to attributing aggregate ad conversions. IACR Cryptology ePrint Archive, 2017, 2017: 738–751. (查阅所有网上资料, 请确认修改是否正确)
    [23] Ion M, Kreuter B, Nergiz AE, Patel S, Saxena S, Seth K, Raykova M, Shanahan D, Yung M. On deploying secure computing: Private intersection-sum-with-cardinality. In: Proc. of the 2020 IEEE European Symp. on Security and Privacy (EuroS&P). Genoa: IEEE, 2020. 370–389.
    [24] Miao P, Patel S, Raykova M, Seth K, Yung M. Two-sided malicious security for private intersection-sum with cardinality. In: Micciancio D, Ristenpart T, eds. Advances in Cryptology (CRYPTO 2020). Lecture Notes in Computer Science, vol. 12172. Santa Barbara: Springer, 2020. 3–33.
    [25] Kolesnikov V, Kumaresan R, Rosulek M, Trieu K. Efficient batched oblivious PRF with applications to private set intersection. In: Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security. Vienna: Association for Computing Machinery, 2016. 818–829.
    [26] Pinkas B, Rosulek M, Trieu N, Yanai A. SpOT-light: Lightweight private set intersection from sparse OT extension. In: Boldyreva A, Micciancio D, eds. Advances in Cryptology (CRYPTO 2019). Lecture Notes in Computer Science, vol. 11694. Santa Barbara: Springer, 2019. 401–431.
    [27] Pinkas B, Schneider T, Weinert C, Wieder U. Efficient circuit-based PSI via cuckoo hashing. In: Nielsen J, Rijmen V, eds. Advances in Cryptology (EUROCRYPT 2018). Lecture Notes in Computer Science, vol. 10822. Tel Aviv: Springer, 2018. 125–157.
    [28] Rindal P, Rosulek M. Improved private set intersection against malicious adversaries. In: Coron JS, Nielsen J, eds. Advances in Cryptology (EUROCRYPT 2017). Lecture Notes in Computer Science, vol. 10210. Paris: Springer, 2017. 235–259.
    [29] Goldreich O. Foundations of Cryptography: Vol. 2, Basic Applications. London: Cambridge University Press, 2004. 599–764.
    [30] Lindell Y. How to simulate it—A tutorial on the simulation proof technique. In: Lindell Y, ed. Tutorials on the Foundations of Cryptography. Information Security and Cryptography. Springer, 2017. 277–346.
    [31] Boudot F, Schoenmakers B, Traoré J. A fair and efficient solution to the socialist millionaires’ problem. Discrete Applied Mathematics, 2001, 111(1–2): 23–36. [doi: 10.1016/S0166-218X(00)00342-5]
    [32] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Stern J, ed. Advances in Cryptology (EUROCRYPT 1999). Lecture Notes in Computer Science, vol. 1592. Prague: Springer, 1999. 223–238.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李顺东,张凯鑫,杨晨,汪榆淋.集合交集元素之和的保密计算.软件学报,2023,34(7):3343-3353

复制
分享
文章指标
  • 点击次数:690
  • 下载次数: 2236
  • HTML阅读次数: 1142
  • 引用次数: 0
历史
  • 收稿日期:2021-06-07
  • 最后修改日期:2021-07-25
  • 在线发布日期: 2022-11-30
  • 出版日期: 2023-07-06
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19856710位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号