nach oben

Designs, Codes and Cryptography

Erschienen in:

24.05.2023

Hiding the input-size in multi-party private set intersection

verfasst von: Yu Zhan, Ziqian Zhang, Qian Liu, Baocang Wang

Erschienen in: Designs, Codes and Cryptography | Ausgabe 9/2023

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Ateniese et al. (PKC 2011) introduced the concept of size-hiding private set intersection (SHI-PSI) and proposed a construction for two parties. The SHI-PSI protocol protects the privacy of input set content and better guarantees the privacy of the client set size. However, more practical protocols in multi-party scenarios have remained a research gap. In this paper, we propose a secure and feasible protocol named size-hiding multi-party private set intersection. Based on the Bloom filter, threshold homomorphic encryption and marking technique, the proposed protocol supports the private set intersection among multiple participants. Meanwhile, the set size privacy of the designated participant is preserved. The proposed protocol is proved to be secure against semi-honest participants under the decisional composite residuosity assumption. Finally, the efficiency of our protocol is illustrated through both performance analyses and comparisons of related work.

Vorheriger Artikel The proportion of non-degenerate complementary subspaces in classical spaces

Nächster Artikel (Compact) Adaptively secure FE for attribute-weighted sums from k-Lin

Abadi A., Terzis S., Metere R., Dong C.: Efficient delegated private set intersection on outsourced private datasets. IEEE Trans. Depend. Secure Comput. 16(4), 608–624 (2019). https://doi.org/10.1109/TDSC.2017.2708710.CrossRef

Abadi A., Murdoch S.J., Zacharias T.: Polynomial representation is tricky: maliciously secure private set intersection revisited. In: Bertino E., Shulman H., Waidner M. (eds.) Computer Security–ESORICS 2021, vol. 12973, pp. 721–742. Springer, Darmstadt (2021).CrossRef

Abadi A., Dong C., Murdoch S.J., Terzis S.: Multi-party updatable delegated private set intersection. In: Eyal I., Garay J.A. (eds.) Financial Cryptography and Data Security—FC 2022, Grenada, vol. 13411, pp. 100–119. Springer, Grenada (2022).

Alamati N., Branco P., Döttling N., Garg S., Hajiabadi M., Pu S.: Laconic private set intersection and applications. In: Nissim K., Waters B. (eds.) Theory of Cryptography, TCC 2021, vol. 13044, pp. 94–125. Springer, Raleigh (2021).

Ateniese G., De Cristofaro E., Tsudik G.: (if) size matters: Size-hiding private set intersection. In: Catalano D., Fazio N., Gennaro R., Nicolosi A. (eds.) Public Key Cryptography—PKC 2011, pp. 156–173. Springer, Berlin (2011).CrossRef

Aydin T.S., Metere R., Dong C.: Efficient delegated private set intersection on outsourced private datasets. IEEE Trans. Depend. Secure Comput. 16(4), 608–624 (2019). https://doi.org/10.1109/TDSC.2017.2708710.CrossRef

Badrinarayanan S., Miao P., Raghuraman S., Rindal P.: Multi-party threshold private set intersection with sublinear communication. In: Garay J.A. (ed.) Public-Key Cryptography—PKC 2021, pp. 349–379. Springer, Cham (2021).CrossRef

Badrinarayanan S., Miao P., Xie T.: Updatable private set intersection. Proc. Privacy Enhanc. Technol. 2022(2), 378–406 (2022). https://doi.org/10.2478/popets-2022-0051.CrossRef

Bay A., Erkin Z., Hoepman J.-H., Samardjiska S., Vos J.: Practical multi-party private set intersection protocols. IEEE Trans. Inf. Forensics Secur. 17, 1–15 (2022). https://doi.org/10.1109/TIFS.2021.3118879.CrossRef

10.

Bhowmick A., Boneh D., Myers S., Talwar K., Tarbe K.: The Apple PSI system (2021). https://www.apple.com/child-safety/pdf/Apple_PSI_System_Security_Protocol_and_Analysis.pdf.

11.

Bloom B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970). https://doi.org/10.1145/362686.362692.CrossRefMATH

12.

Bose P., Guo H., Kranakis E., Maheshwari A., Morin P., Morrison J., Smid M., Tang Y.: On the false-positive rate of bloom filters. Inf. Process. Lett. 108(4), 210–213 (2008). https://doi.org/10.1016/j.ipl.2008.05.018.MathSciNetCrossRefMATH

13.

Bradley T., Faber S., Tsudik G.: Bounded size-hiding private set intersection. In: Zikas V., De Prisco R. (eds.) Security and Cryptography for Networks, pp. 449–467. Springer, Cham (2016).

14.

Branco P., Döttling N., Pu S.: Multiparty cardinality testing for threshold private intersection. In: Garay J.A. (ed.) Public-Key Cryptography—PKC 2021, vol. 12711, pp. 32–60. Springer, New York (2021).CrossRef

15.

Cerulli A., De Cristofaro E., Soriente C.: Nothing refreshes like a RePSI: reactive private set intersection. In: Preneel B., Vercauteren F. (eds.) Applied Cryptography and Network Security, pp. 280–300. Springer, Cham (2018).CrossRef

16.

Chase M., Miao P.: Private set intersection in the internet setting from lightweight oblivious PRF. In: Micciancio D., Ristenpart T. (eds.) Advances in Cryptology—CRYPTO 2020, pp. 34–63. Springer, Cham (2020).CrossRef

17.

Chase M., Ostrovsky R., Visconti I.: Executable proofs, input-size hiding secure computation and a new ideal world. In: Oswald E., Fischlin M. (eds.) Advances in Cryptology—EUROCRYPT 2015, pp. 532–560. Springer, Berlin (2015).CrossRef

18.

Chen H., Laine K., Rindal P.: Fast private set intersection from homomorphic encryption. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17), pp. 1243–1255. Association for Computing Machinery, New York (2017).

19.

Chen H., Huang Z., Laine K., Rindal P.: Labeled psi from fully homomorphic encryption with malicious security. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (CCS ’18), pp. 1223–1237. Association for Computing Machinery, New York (2018).

20.

D’Arco P., González Vasco M.I., Pérez del Pozo A.L., Soriente C.: Size-hiding in private set intersection: existential results and constructions. In: Mitrokotsa, A., Vaudenay, S. (eds.) Progress in Cryptology—AFRICACRYPT 2012, pp. 378–394. Springer, Berlin (2012)

21.

Davidson A., Cid C.: An efficient toolkit for computing private set operations. In: Pieprzyk J., Suriadi S. (eds.) Information Security and Privacy, pp. 261–278. Springer, Cham (2017).CrossRef

22.

Debnath S.K., Stǎnicǎ P., Kundu N., Choudhury T.: Secure and efficient multiparty private set intersection cardinality. Adv. Math. Commun. 15(2), 365–386 (2021).MathSciNetCrossRefMATH

23.

Dong C., Chen L., Wen Z.: When private set intersection meets big data: An efficient and scalable protocol. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security (CCS ’13), pp. 789–800. Association for Computing Machinery, New York, NY, USA (2013).

24.

Fouque P.-A., Poupard G., Stern J.: Sharing decryption in the context of voting or lotteries. In: Frankel Y. (ed.) Financial Cryptography, pp. 90–104. Springer, Berlin (2001).CrossRef

25.

Freedman M.J., Nissim K., Pinkas B.: Efficient private matching and set intersection. In: Cachin C., Camenisch J.L. (eds.) Advances in Cryptology—EUROCRYPT 2004, pp. 1–19. Springer, Berlin (2004).

26.

Garimella G., Pinkas B., Rosulek M., Trieu N., Yanai A.: Oblivious key-value stores and amplification for private set intersection. In: Malkin T., Peikert C. (eds.) Advances in Cryptology—CRYPTO 2021, pp. 395–425. Springer, Cham (2021).CrossRef

27.

Ghosh S., Nilges T.: An algebraic approach to maliciously secure private set intersection. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019, pp. 154–185. Springer, Cham (2019).CrossRef

28.

Ghosh S., Simkin M.: The communication complexity of threshold private set intersection. In: Boldyreva A., Micciancio D. (eds.) Advances in Cryptology—CRYPTO 2019, pp. 3–29. Springer, Cham (2019).CrossRef

29.

Goldreich O.: Foundations of Cryptography, vol. 2. Cambridge University Press, Cambridge (2004) https://doi.org/10.1017/CBO9780511721656.CrossRefMATH

30.

Hazay C., Venkitasubramaniam M.: Scalable multi-party private set-intersection. In: Fehr S. (ed.) Public-Key Cryptography—PKC 2017, pp. 175–203. Springer, Berlin (2017).CrossRef

31.

Ion M., Kreuter B., Nergiz A.E., Patel S., Saxena S., Seth K., Raykova M., Shanahan D., Yung M.: On deploying secure computing: private intersection-sum-with-cardinality. In: 2020 IEEE European Symposium on Security and Privacy (EuroS P), pp. 370–389 (2020)

32.

Kiss Á., Liu J., Schneider T., Asokan N., Pinkas B.: Private set intersection for unequal set sizes with mobile applications. Proceedings on Privacy Enhancing Technologies 2017(4), 177–197 (2017). https://doi.org/10.1515/popets-2017-0044.CrossRef

33.

Kissner L., Song D.: Privacy-preserving set operations. In: Shoup V. (ed.) Advances in Cryptology—CRYPTO 2005, pp. 241–257. Springer, Berlin (2005).CrossRef

34.

Kolesnikov V., Kumaresan R., Rosulek M., Trieu N.: Efficient batched oblivious PRF with applications to private set intersection. In: Weippl E.R., Katzenbeisser S., Kruegel C., Myers A.C., Halevi S. (eds.) Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24–28, 2016, pp. 818–829. ACM, New York (2016).

35.

Le P.H., Ranellucci S., Gordon S.D.: Two-party private set intersection with an untrusted third party. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS ’19), pp. 2403–2420. Association for Computing Machinery, New York (2019).

36.

Lindell Y., Nissim K., Orlandi C.: Hiding the input-size in secure two-party computation. In: Sako K., Sarkar P. (eds.) Advances in Cryptology—ASIACRYPT 2013, pp. 421–440. Springer, Berlin (2013).CrossRefMATH

37.

Meadows C.: A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In: 1986 IEEE Symposium on Security and Privacy, pp. 134–134 (1986).

38.

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, pp. 3–33. Springer, Cham (2020).CrossRef

39.

Paillier P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern J. (ed.) Advances in Cryptology—EUROCRYPT ’99, pp. 223–238. Springer, Berlin, Heidelberg (1999).CrossRef

40.

Pinkas B., Schneider T., Tkachenko O., Yanai A.: Efficient circuit-based psi with linear communication. In: Ishai Y., Rijmen V. (eds.) Advances in Cryptology—EUROCRYPT 2019, pp. 122–153. Springer, Cham (2019).CrossRef

41.

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, pp. 401–431. Springer, Cham (2019).CrossRef

42.

Pinkas B., Rosulek M., Trieu N., Yanai A.: Psi from Paxos: fast, malicious private set intersection. In: Canteaut A., Ishai Y. (eds.) Advances in Cryptology—EUROCRYPT 2020, pp. 739–767. Springer, Cham (2020).CrossRef

43.

Quach W., Wee H., Wichs D.: Laconic function evaluation and applications. In: Thorup M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pp. 859–870. IEEE Computer Society, Paris, France (2018).

44.

Rindal P., Rosulek M.: Improved private set intersection against malicious adversaries. In: Coron J.-S., Nielsen J.B. (eds.) Advances in Cryptology—EUROCRYPT 2017, pp. 235–259. Springer, Cham (2017).CrossRef

45.

Rindal P., Schoppmann P.: Vole-psi: fast OPRF and circuit-psi from vector-ole. In: Canteaut A., Standaert F.-X. (eds.) Advances in Cryptology—EUROCRYPT 2021, pp. 901–930. Springer, Cham (2021).CrossRef

46.

Ruan O., Wang Z., Mi J., Zhang M.: New approach to set representation and practical private set-intersection protocols. IEEE Access 7, 64897–64906 (2019). https://doi.org/10.1109/ACCESS.2019.2917057.CrossRef

47.

Ruan O., Huang X., Mao H.: An efficient private set intersection protocol for the cloud computing environments. In: 2020 IEEE 6th International Conference on Big Data Security on Cloud (BigDataSecurity), IEEE International Conference on High Performance and Smart Computing, (HPSC) and IEEE International Conference on Intelligent Data and Security (IDS), pp. 254–259 (2020).

48.

Shinagawa K., Nuida K., Nishide T., Hanaoka G., Okamoto E.: Size-hiding computation for multiple parties. In: Cheon J.H., Takagi T. (eds.) Advances in Cryptology—ASIACRYPT 2016, pp. 937–966. Springer, Berlin, Heidelberg (2016).CrossRef

49.

Shoup V., et al.: NTL: a library for doing number theory (2001). https://www.shoup.net/ntl/.

50.

Wang Y., Huang Q., Li H., Xiao M., Ma S., Susilo W.: Private set intersection with authorization over outsourced encrypted datasets. IEEE Trans. Inf. Forensics Secur. 16, 4050–4062 (2021). https://doi.org/10.1109/TIFS.2021.3101059.CrossRef

51.

Zhang E., Liu F.-H., Lai Q., Jin G., Li Y.: Efficient multi-party private set intersection against malicious adversaries. In: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, pp. 93–104. Association for Computing Machinery, New York (2019).

52.

Zhang E., Chang J., Li Y.: Efficient threshold private set intersection. IEEE Access 9, 6560–6570 (2021). https://doi.org/10.1109/ACCESS.2020.3048743.CrossRef

Titel: Hiding the input-size in multi-party private set intersection
verfasst von: Yu Zhan
Ziqian Zhang
Qian Liu
Baocang Wang
Publikationsdatum: 24.05.2023
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 9/2023
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-023-01238-0

Springer Professional

Hiding the input-size in multi-party private set intersection

Abstract

Premium Partner

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 9/2023

Meet-in-the-middle attack with splice-and-cut technique and a general automatic framework

Characterizing subgroup perfect codes by 2-subgroups

Obituary of Professor Zhexian Wan

On the security of functional encryption in the generic group model

Several families of irreducible constacyclic and cyclic codes

(Compact) Adaptively secure FE for attribute-weighted sums from k-Lin

Premium Partner