Abstract
As a significant basis for privacy-preserving applications of Secure Multiparty Computation (MPC), Private Set Intersection (PSI) has long been a question of great interest in a wide range of field, such as ad conversion rates and private contact tracing. Threshold PSI (\(t\)-\(\mathsf {PSI}\)), a variant of PSI, allows two parties to learn the intersection of two sets only if the cardinality of intersection is larger (or lesser) than a threshold t. In this paper, we give a generic \(t\)-\(\mathsf {PSI}\) construction that relies heavily on Oblivious Transfer (OT). Without resorting to the relatively expensive homomorphic calculation approaches from public-key mechanism, two kinds of \(t\)-\(\mathsf {PSI}\) protocols could be efficiently implemented based on our proposed construction, i.e., \(t^{\scriptscriptstyle {\le }}\mathsf {PSI}\) and \(t^{\scriptscriptstyle {>}}\text {-}\mathsf {PSI}\). Specially, we construct two efficient protocols named secret-sharing private equality test and membership text , which enable PSI to scale to a wide range of practical applications. The experimental simulation results show that our protocols are efficient and computation friendly.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Yao, A.C.: Protocols for secure computations. In: 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pp. 160–164. IEEE (1982)
Zhao, C., et al.: Secure multi-party computation: theory, practice and applications. Inf. Sci. 476, 357–372 (2019)
Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 818–829 (2016)
Chase, M., Miao, P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 34–63. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_2
Song, X., Gai, M., Zhao, S., Jiang, H.: Privacy-preserving statistics protocol for set-based computation. J. Comput. Res. Dev. 57(10), 2221 (2020). (in Chinese)
Zhao, C., Jiang, H., Wei, X., Xu, Q., Zhao, M.: Cut-and-choose bilateral oblivious transfer and its application. In: 2015 IEEE Trustcom/BigDataSE/ISPA, vol. 1, pp. 384–391. IEEE (2015)
Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., Trieu, N.: Practical multi-party private set intersection from symmetric-key techniques. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1257–1272 (2017)
Kolesnikov, V., Rosulek, M., Trieu, N., Wang, X.: Scalable private set union from symmetric-key techniques. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11922, pp. 636–666. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34621-8_23
Pinkas, B., Schneider, T., Tkachenko, O., Yanai, A.: Efficient circuit-based PSI with linear communication. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 122–153. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_5
Karakoç, F., Küpçü, A.: Linear complexity private set intersection for secure two-party protocols. Cryptology ePrint Archive, Report 2020/864 (2020). https://eprint.iacr.org/2020/864
Zhao, Y., Chow, S.S.M.: Are you the one to share? Secret transfer with access structure. In: Proceedings on Privacy Enhancing Technologies 2017, no. 1, pp. 149–169 (2017)
Zhao, Y., Chow, S.S.M.: Can you find the one for me? In: Proceedings of the 2018 Workshop on Privacy in the Electronic Society, pp. 54–65 (2018)
Ghosh, S., Simkin, M.: The communication complexity of threshold private set intersection. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 3–29. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_1
Badrinarayanan, S., Miao, P., Rindal, P.: Multi-party threshold private set intersection with sublinear communication. IACR Cryptology ePrint Archive 2020:600 (2020)
Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, Cambridge (2009)
Acknowledgements
We thank the anonymous reviewers. This work was supported by the National Natural Science Foundation of China under Grant 61632020, and the Special Project of Science and Technology Innovation Base of Key Laboratory of Software Engineering of Shandong Province under Grant 11480004042015.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhao, S., Ma, M., Song, X., Jiang, H., Yan, Y., Xu, Q. (2021). Lightweight Threshold Private Set Intersection via Oblivious Transfer. In: Liu, Z., Wu, F., Das, S.K. (eds) Wireless Algorithms, Systems, and Applications. WASA 2021. Lecture Notes in Computer Science(), vol 12939. Springer, Cham. https://doi.org/10.1007/978-3-030-86137-7_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-86137-7_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86136-0
Online ISBN: 978-3-030-86137-7
eBook Packages: Computer ScienceComputer Science (R0)