微信服务号

微信订阅号

2025-4-24- 16
Home > Archive>Volume 34, Issue 11, 2023 >5442-5456. DOI:10.13328/j.cnki.jos.006747
PDF HTML XML Export Cite reminder
Two Cloud-assisted Over-threshold Multi-party Private Set Intersection Calculation Protocol
Author:
Affiliation:

Clc Number:

TP309

  • Article
    • | |
  • Metrics
    • |
  • Reference [43]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The over-threshold multi-party private set intersection (OT-MP-PSI) protocol is a variant of the conventional PSI protocol. This protocol allows m participants to jointly compute the OT intersection for which at least t (t≤m) participants have the common element and ensures that only the participant with the OT element knows whether the element belongs to the OT intersection and nothing else. The OT-MP-PSI protocol extends the practical application scenarios of the PSI protocol. As the existing schemes are all constructed on the basis of expensive public key-based cryptography, their heavy computational burden results in long runtime. This study designs a novel cryptographic component, the oblivious programmable pseudo-random secret-sharing (OPPR-SS) component based on symmetric cryptography. Furthermore, a two cloud-assisted OT-MP-PSI protocol is designed on the basis of the OPPR-SS component, and it assigns the tasks of secret sharing and reconstructing to untrusted cloud servers, respectively, so that they can assist in the completion of those tasks. As a result, participants with weak computation capability can complete the OT-MP-PSI protocol as well. Furthermore, the study proves that the proposed protocol is secure in the semi-honest model. Compared with the existing OT-MP-PSI protocols, the proposed protocol achieves the optimal runtime and communication overhead at both the secret sharing stage and the secret reconstructing stage. The communication complexities of the participants, the secret sharing cloud, and reconstructing cloud are no longer related to the threshold t. The number of communication rounds for the participants is constant, and the communication complexity is merely O(n). The computational complexities of the secret sharing cloud and the secret reconstructing cloud are only related to the number of symmetric cryptographic operations.

    Reference
    [1] Kolesnikov V, Kumaresan R, Rosulek M, Trieu N. Efficient batched oblivious PRF with applications to private set intersection. In: Proc. of the 23rd ACM SIGSAC Conf. on Computer and Communications Security. Vienna: ACM, 2016. 818–829.
    [2] Chase M, Miao PH. Private set intersection in the internet setting from lightweight oblivious PRF. In: Proc. of the 40th Annual Int’l Cryptology Conf. on Advances in Cryptology. Santa Barbara: Springer, 2020. 34–63.
    [3] Dong CY, Chen LQ, Wen ZK. When private set intersection meets big data: An efficient and scalable protocol. In: Proc. of the 20th ACM SIGSAC Conf. on Computer & Communications Security. Berlin: ACM, 2013. 789–800.
    [4] 窦家维, 刘旭红, 王文丽. 有理数域上两方集合的高效保密计算. 计算机学报, 2020, 43(8): 1397–1413.
    Dou JW, Liu XH, Wang WL. Privacy preserving two-party rational set computation. Chinese Journal of Computers, 2020, 43(8): 1397–1413 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2020.01397]
    [5] Debnath SK, Dutta R. Towards fair mutual private set intersection with linear complexity. Security and Communication Networks, 2016, 9(11): 1589–1612. [doi: 10.1002/sec.1450]
    [6] Mohassel P, Rindal P, Rosulek M. Fast database joins and PSI for secret shared data. In: Proc. of the 27th ACM SIGSAC Conf. on Computer and Communications Security. Virtual Event: ACM, 2020. 1271–1287.
    [7] 宋祥福, 盖敏, 赵圣楠, 蒋瀚. 面向集合计算的隐私保护统计协议. 计算机研究与发展, 2020, 57(10): 2221–2231.
    Song XF, Gai M, Zhao SN, Jiang H. Privacy-preserving statistics protocol for set-based computation. Journal of Computer Research and Development, 2020, 57(10): 2221–2231 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2020.20200444]
    [8] 魏立斐, 刘纪海, 张蕾, 王勤, 贺崇德. 面向隐私保护的集合交集计算综述. 计算机研究与发展, 2020, 59(8): 1782–1799.
    Wei LF, Liu JH, Zhang L, Wang Q, He CD. Survey of privacy preserving oriented set intersection computation. Journal of Computer Research and Development, 2020, 59(8): 1782–1799 (in Chinese with English abstract).
    [9] Demmler D, Rindal P, Rosulek M, Trieu N. PIR-PSI: Scaling private contact discovery. Proceedings on Privacy Enhancing Technologies, 2018, 2018(4): 159–178. [doi: 10.1515/popets-2018-0037]
    [10] Lv SY, Ye JH, Yin SJ, Cheng XC, Feng C, Liu XY, Li R, Li ZH, Liu ZL, Zhou L. Unbalanced private set intersection cardinality protocol with low communication cost. Future Generation Computer Systems, 2020, 102: 1054–1061. [doi: 10.1016/j.future.2019.09.022]
    [11] Duong T, Phan DH, Trieu N. Catalic: Delegated PSI cardinality with applications to contact tracing. In: Proc. of the 26th Int’l Conf. on the Theory and Application of Cryptology and Information Security. Daejeon: Springer, 2020. 870–899.
    [12] Hazay C, Venkitasubramaniam M. Scalable multi-party private set-intersection. In: Proc. of the 20th IACR Int’l Conf. on Practice and Theory in Public-key Cryptography. Amsterdam: Springer, 2017. 175–203.
    [13] Kolesnikov V, Matania N, Pinkas B, Rosulek M, Trieu N. Practical multi-party private set intersection from symmetric-key techniques. In: Proc. of the 2017 ACM SIGSAC Conf. on Computer and Communications Security. Dallas: ACM, 2017. 1257–1272.
    [14] Kavousi A, Mohajeri J, Salmasizadeh M. Efficient scalable multi-party private set intersection using oblivious PRF. IACR Cryptology ePrint Archive, 2021. https://eprint.iacr.org/2021/484
    [15] Badrinarayanan S, Miao PH, Srinivasan R, Rindal P. Multi-party threshold private set intersection with sublinear communication. In: Proc. of the 24th IACR Int’l Conf. on Practice and Theory of Public Key Cryptography. Virtual Event: Springer, 2021. 349–379.
    [16] Wagner C, Dulaunoy A, Wagener G, Iklody A. MISP: The design and implementation of a collaborative threat intelligence sharing platform. In: Proc. of the 2016 ACM on Workshop on Information Sharing and Collaborative Security. Vienna: ACM, 2016. 49–56.
    [17] Kissner L, Song D. Private and Threshold Set-intersection. Pittsburgh: Carnegie Mellon University, 2004.
    [18] Mahdavi RA, Humphries T, Kacsmar B, Krastnikov S, Lukas N, Premkumar JA, Shafieinejad M, Oya S, Kerschbaum F, Blass EO. Practical over-threshold multi-party private set intersection. In: Proc. of the 2020 Annual Computer Security Applications Conf. Austin: ACM, 2020. 772–783.
    [19] Rosulek M, Trieu N. Compact and malicious private set intersection for small sets. In: Proc. of the 2021 ACM SIGSAC Conf. on Computer and Communications Security. Virtual Event: ACM, 2021. 1166–1181.
    [20] Chandran N, Gupta D, Shah A. Circuit-PSI with linear complexity via relaxed batch OPPRF. IACR Cryptology ePrint Archive. 2021. https://eprint.iacr.org/2021/034
    [21] Pinkas B, Rosulek M, Trieu N, Yanai A. SpOT-light: Lightweight private set intersection from sparse OT extension. In: Proc. of the 39th Annual Int’l Cryptology Conf. on Advances in Cryptology. Santa Barbara: Springer, 2019. 401–431.
    [22] 周素芳, 李顺东, 郭奕旻, 窦家维, 陈振华. 保密集合相交问题的高效计算. 计算机学报, 2018, 41(2): 464–480. [doi: 10.11897/SP.J.1016.2018.00464]
    Zhou SF, Li SD, Guo YM, Dou JW, Chen ZH. Efficient secure set intersection problem computation. Chinese Journal of Computers, 2018, 41(2): 464–480 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2018.00464]
    [23] Pinkas B, Rosulek M, Trieu N, Yanai A. PSI from PaXoS: Fast, malicious private set intersection. In: Proc. of the 39th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Zagreb: Springer, 2020. 739–767.
    [24] Pinkas B, Schneider T, Segev G, Zoher M. Phasing: Private set intersection using permutation-based hashing. In: Proc. of the 24th USENIX Conf. Security Symp. Washington: USENIX Association, 2015. 515–530.
    [25] Pinkas B, Schneider T, Weinert C, Wieder U. Efficient circuit-based PSI via cuckoo hashing. In: Proc. of the 37th Annual Int’l Conf. on the Theory and Applications of Cryptographic Techniques. Tel Aviv: Springer, 2018. 125–157.
    [26] Abdelrahaman A, Marcel K, Dragos R, Peter S, Nigel PS, Tim W. SCALE-MAMBA software. 2021. https://homes.esat.kuleuven.be/~nsmart/SCALE/
    [27] Chandran N, Dasgupta N, Gupta D, Obbattu SLB, Sekar S, Shah A. Efficient linear multiparty PSI and extensions to Circuit/Quorum PSI. In: Proc. of the 2021 ACM SIGSAC Conf. on Computer and Communications Security. Virtual Event: ACM, 2021. 1182–1204.
    [28] Bay A, Erkin Z, Hoepman JH, Samardjiska S, Vos J. Practical multi-party private set intersection protocols. IEEE Transactions on Information Forensics and Security, 2022, 17: 1–15. [doi: 10.1109/TIFS.2021.3118879]
    [29] Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation. Foundations and Trends® in Privacy and Security, 2018, 2(2–3): 70–246.
    [30] Garimella G, Pinkas B, Rosulek M, Trieu N, Yanai A. Oblivious key-value stores and amplification for private set intersection. In: Proc. of the 41st Annual Int’l Cryptology Conf. on Advances in Cryptology. Springer, 2021. 395–425.
    [31] Inbar R, Omri E, Pinkas B. Efficient scalable multiparty private set-intersection via garbled Bloom filters. In: Proc. of the 11th Int’l Conf. on Security and Cryptography for Networks. Amalfi: Springer, 2018. 235–252.
    [32] 魏立斐, 王勤, 张蕾, 陈聪聪, 陈玉娇, 宁建廷. 半可信云服务器辅助的高效隐私交集计算协议. 软件学报, 2023, 34(2): 932–944. http://www.jos.org.cn/1000-9825/6397.htm
    Wei LF, Wang Q, Zhang L, Chen CC, Chen YJ, Ning JT. Efficient private set intersection protocols with semi-trusted cloud server aided. Ruan Jian Xue Bao/Journal of Software, 2023, 34(2): 932–944 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6397.htm
    [33] Rindal P, Schoppmann P. VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE. IACR Cryptology ePrint Archive, 2021. https://eprint.iacr.org/2021/266
    [34] De Cristofaro E, Tsudik G. Experimenting with fast private set intersection. In: Proc. of the 5th Int’l Conf. on Trust and Trustworthy Computing. Vienna: Springer, 2012. 55–73.
    [35] Kolesnikov V, Kumaresan R. Improved OT extension for transferring short secrets. In: Proc. of the 33rd Annual Cryptology Conf. on Advances in Cryptology. Santa Barbara: Springer, 2013. 54–70.
    [36] Schoppmann P, Gascón A, Reichert L, Raykova M. Distributed vector-OLE: Improved constructions and implementation. In: Proc. of the 2019 ACM SIGSAC Conf. on Computer and Communications Security. London: ACM, 2019. 1055–1072.
    [37] Yao AC. Protocols for secure computations. In: Proc. of the 23rd Annual Symp. on Foundations of Computer Science (SFCS 1982). Chicago: IEEE, 1982. 160–164.
    [38] Shamir A. How to share a secret. Communications of the ACM, 1979, 22(11): 612–613. [doi: 10.1145/359168.359176]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

魏立斐,刘纪海,张蕾,宁建廷.双云辅助的超阈值多方隐私集合交集计算协议.软件学报,2023,34(11):5442-5456

Copy
Share
Article Metrics
  • Abstract:610
  • PDF: 2326
  • HTML: 1417
  • Cited by: 0
History
  • Received:March 16,2022
  • Revised:June 02,2022
  • Online: June 16,2023
  • Published: November 06,2023
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038149Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063