Card-Based Protocols for Private Set Intersection and Union
Authors: 
Anastasiia Doi, Tomoki Ono, Yoshiki Abe, Takeshi Nakai, Kazumasa Shinagawa, Yohei Watanabe, Koji Nuida, Mitsugu IwamotoAuthors Info & Claims
Pages 359 - 380
Abstract
Card-based cryptography aims to realize secure multiparty computation with physical cards. This paper is the first to address Private Set Intersection (PSI) and Private Set Union (PSU) in card-based cryptography. PSI and PSU are well-studied secure computation protocols to compute the set intersection and the set union, respectively. We show two-party PSI and PSU protocols in each of the two operation models: one is the shuffle-based model in which parties perform all operations publicly, and the other is the private-permutation-based model that allows parties to perform some operations privately. In the shuffle-based model, we show PSI and PSU protocols can be realized with existing secure AND and OR protocols, respectively. However, these protocols have an issue of increasing the number of shuffles depending on the size of the universal set. To resolve the issue, we further propose PSI and PSU protocols with only one shuffle at the cost of increasing the number of cards. In the private-permutation-based model, we show PSI and PSU protocols can be achieved with existing secure AND and OR protocols, respectively, as in the shuffle-based protocols. These protocols have an advantage of requiring only one private permutation and one communication. We further show that the number of cards of these protocols can be reduced at the cost of increasing the number of private permutations and communications.
References
[1]
Abe, Y., Hayashi, Y., Mizuki, T., Sone, H.: Five-card AND protocol in committed format using only practical shuffles. In: Emura, K., Seo, J.H., Watanabe, Y. (eds.) Proceedings of the 5th ACM on ASIA Public-Key Cryptography Workshop, APKC@AsiaCCS, Incheon, Republic of Korea, June 4, 2018, pp. 3–8. ACM (2018)
[2]
Crépeau, C., Kilian, J.: Discreet solitary games. In: Stinson, D.R. (eds.) Advances in Cryptology—CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pp. 319–330. Springer (1993)
[3]
den Boer, B.: More efficient match-making and satisfiability: the Five Card Trick. In: Quisquater, J., Vandewalle, J. (eds.) Advances in Cryptology—EUROCRYPT ’89, Volume 434 of LNCS, pp. 208–217. Springer, Berlin(1989)
[4]
Doi, A., Ono, T., Nakai, T., Shinagawa, K., Watanabe, Y., Nuida, K., Iwamoto, M.: Card-based cryptographic protocols for private set intersection. In: ISITA 2022. IEEE (2022) (to appear)
[5]
Dong, C., Chen, L., Wen, Z.: When private set intersection meets big data: an efficient and scalable protocol. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) 2013 ACM SIGSAC Conference on Computer and Communications Security, CCS’13, Berlin, Germany, November 4–8, 2013, pp. 789–800. ACM (2013)
[6]
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Advances in Cryptology—EUROCRYPT 2004, pp. 1–19. Springer, Berlin (2004)
[7]
Frikken, K.B.: Privacy-preserving set union. In: Katz, J., Yung, M. (eds.) Applied Cryptography and Network Security, 5th International Conference, ACNS 2007, Zhuhai, China, June 5–8, 2007, Proceedings, Volume 4521 of Lecture Notes in Computer Science, pp. 237–252. Springer, Berlin (2007)
[8]
Haga, R., Toyoda, K., Shinoda, Y., Miyahara, D., Shinagawa, K., Hayashi, Y., Mizuki, T.: Card-based secure sorting protocol. In: Cheng, C., Akiyama, M. (eds.) Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Tokyo, Japan, August 31–September 2, 2022, Proceedings, volume 13504 of Lecture Notes in Computer Science, pp. 224–240. Springer, Berlin (2022)
[9]
Hashimoto, Y., Shinagawa, K., Nuida, K., Inamura, M., Hanaoka, G.: Secure grouping protocol using a deck of cards. In: Shikata, J. (ed.) Information Theoretic Security—10th International Conference, ICITS 2017, Hong Kong, China, November 29–December 2, 2017, Proceedings, volume 10681 of Lecture Notes in Computer Science, pp. 135–152. Springer, Berlin (2017)
[10]
Jia, Y., Sun, S., Zhou, H., Du, J., Gu, D.: Shuffle-based private set union: faster and more secure. In: Butler, K.R.B., Thomas, K. (eds.) 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, pp. 2947–2964. USENIX Association (2022)
[11]
Koch, A., Walzer, S., Härtel, K.: Card-based cryptographic protocols using a minimal number of cards. In: Iwata, T., Cheon, J.H. (eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29–December 3, 2015, Proceedings, Part I, Volume 9452 of Lecture Notes in Computer Science, pp. 783–807. Springer (2015)
[12]
Koch, A., Walzer, S.: Foundations for actively secure card-based cryptography. In: Farach-Colton, M., Prencipe, G., Uehara, R. (eds.) 10th International Conference on Fun with Algorithms, FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy, volume 157 of LIPIcs, pp. 17:1–17:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
[13]
Marcedone, A., Wen, Z., Shi, E.: Secure dating with four or fewer cards. Cryptology ePrint Archive, Report 2015/1031 (2015)
[14]
Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) Frontiers in Algorithmics, Third International Workshop, FAW 2009, Hefei, China, June 20-23, 2009. Proceedings, Volume 5598 of Lecture Notes in Computer Science, pp. 358–369. Springer (2009)
[15]
Mizuki, T., Kumamoto, M., Sone, H.: The five-card trick can be done with four cards. In: Wang, X., Sako, K. (eds.) Advances in Cryptology—ASIACRYPT 2012—18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2–6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pp. 598–606. Springer (2012)
[16]
Nakai, T., Tokushige, Y., Misawa, Y., Iwamoto, M., Ohta, K.: Efficient card-based cryptographic protocols for millionaires’ problem utilizing private permutations. In: Foresti, S., Persiano, G. (eds.) Cryptology and Network Security—15th International Conference, CANS 2016, Milan, Italy, November 14–16, 2016, Proceedings, Volume 10052 of Lecture Notes in Computer Science, pp. 500–517 (2016)
[17]
Nakai T, Shirouchi S, Tokushige Y, Iwamoto M, and Ohta K Secure computation for threshold functions with physical cards: power of private permutations New Gener. Comput. 2022 40 1 95-113
[18]
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—39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pp. 401–431. Springer (2019)
[19]
Pinkas, B., Schneider, T., Zohner, M.: Faster private set intersection based on OT extension. In: Fu, K., Jung, J., (eds.) Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20–22, 2014, pp. 797–812. USENIX Association (2014)
[20]
Pinkas B, Schneider T, and Zohner M Scalable private set intersection based on OT extension ACM Trans. Priv. Secur. 2018 21 2 7:1-7:35
[21]
Ramanathan, S., Mirkovic, J., Yu, M.: BLAG: improving the accuracy of blacklists. In: 27th Annual Network and Distributed System Security Symposium, NDSS. The Internet Society (2020)
[22]
Takashima, K., Abe, Y., Sasaki, T., Miyahara, D., Shinagawa, K., Mizuki, T., Sone, H.: Card-based secure ranking computations. In: Li, Y., Cardei, M., Huang, Y. (eds.) Combinatorial Optimization and Applications—13th International Conference, COCOA 2019, Xiamen, China, December 13–15, 2019, Proceedings, Volume 11949 of Lecture Notes in Computer Science, pp. 461–472. Springer (2019)
[23]
Thomas, K., Pullman, J., Yeo, K., Raghunathan, A., Kelley, P.G., Invernizzi, L., Benko, B., Pietraszek, T., Patel, S., Boneh, D., Bursztein, E.: Protecting accounts from credential stuffing with password breach alerting. In: 28th USENIX Security Symposium (USENIX Security 19), pp. 1556–1571. USENIX Association (2019)
[24]
Yao, A.C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, pp. 162–167. IEEE Computer Society (1986)
Index Terms
- Card-Based Protocols for Private Set Intersection and Union
Index terms have been assigned to the content through auto-classification.
Recommendations
Linear Complexity Private Set Intersection for Secure Two-Party Protocols
Cryptology and Network SecurityAbstractIn this paper, we propose a new private set intersection (PSI) protocol with bi-oblivious data transfer that computes the following functionality. The two parties ( and ) input two sets of items (X and Y, respectively) and one of the parties (
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications SecurityWe describe a lightweight protocol for oblivious evaluation of a pseudorandom function (OPRF) in the presence of semihonest adversaries. In an OPRF protocol a receiver has an input r; the sender gets output s and the receiver gets output F(s; r), where ...
Scalable Multi-party Private Set Union from Multi-query Secret-Shared Private Membership Test
Advances in Cryptology – ASIACRYPT 2023AbstractMulti-party private set union (MPSU) allows parties, each holding a dataset of known size, to compute the union of their sets without revealing any additional information. Although two-party PSU has made rapid progress in recent years, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2024.
Publisher
Ohmsha
Japan
Publication History
Published: 22 June 2024
Accepted: 03 June 2024
Received: 07 December 2023
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in