EMPSI: Efficient multiparty private set intersection (with cardinality)

doi:10.1007/s11704-022-2269-0

Front. Comput. Sci.

2024, Vol. 18

Issue (1) : 181804 https://doi.org/10.1007/s11704-022-2269-0

Information Security

EMPSI: Efficient multiparty private set intersection (with cardinality)

Yunbo YANG^1,², Xiaolei DONG¹(

), Zhenfu CAO¹(

), Jiachen SHEN¹(

), Ruofan LI¹, Yihao YANG¹, Shangmin DOU³

¹. Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, China
². Kunyao Academy of Shanghai Kunyao Network Technology Co., Ltd., Shanghai 201203, China
³. PwC US Advisory Shanghai AC, Shanghai 200233, China

Download: PDF(8243 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Multiparty private set intersection (PSI) allows several parties, each holding a set of elements, to jointly compute the intersection without leaking any additional information. With the development of cloud computing, PSI has a wide range of applications in privacy protection. However, it is complex to build an efficient and reliable scheme to protect user privacy.

To address this issue, we propose EMPSI, an efficient PSI (with cardinality) protocol in a multiparty setting. EMPSI avoids using heavy cryptographic primitives (mainly rely on symmetric-key encryption) to achieve better performance. In addition, both PSI and PSI with the cardinality of EMPSI are secure against semi-honest adversaries and allow any number of colluding clients (at least one honest client). We also do experiments to compare EMPSI with some state-of-the-art works. The experimental results show that proposed EMPSI(-CA) has better performance and is scalable in the number of clients and the set size.

Corresponding Author(s): Xiaolei DONG,Zhenfu CAO,Jiachen SHEN

About author:

Changjian Wang and Zhiying Yang contributed equally to this work.

Just Accepted Date: 15 November 2022 Issue Date: 06 March 2023

Cite this article:

Yunbo YANG,Xiaolei DONG,Zhenfu CAO, et al. EMPSI: Efficient multiparty private set intersection (with cardinality)[J]. Front. Comput. Sci., 2024, 18(1): 181804.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-2269-0
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I1/181804

Fig.1 Add elements into a ZGBF

Notation	Meaning
$P i$	The $i t h$ client
$S$	The cloud server
$λ$	Security parameter
$H$	A set of hash functions
$H 1, H 2$	Collusion-resistance hash function
BF	Bloom filter
ZGBF	Zero-sharing garbled Bloom filter
$z i, j$	The $j t h$ zero-sharing generated by the client $P i$
$m$	The size of ZGBF and BF
$k$	The number of hash functions in $H$
$t$	The number of parties
$n$	The size of set
$X i$	$P i$ ’s set $X i$ with size $n$
$S i m$	Simulator used in security proof

Tab.1 Notations used in EMPSI (-CA)

Fig.2 1-out-of-2 OT Functionality

F O T

Fig.3 Oblivious pseudorandom function

Fig.4 Batch oblivious pseudorandom function

Fig.5 Interaction between the server and client in EMPSI.

Fig.6 Interaction between the server and client

P 1

in EMPSI.

Fig.7 Functionality

F M P S I

Fig.8 Functionality

F M P S I ? C A

Fig.9 Toy example for ZGBF

Fig.10 Batch protocol

π O P R F

Fig.11 Protocol

π P S I

Fig.12 Protocol

π P S I ? C A

Fig.13 Toy example for EMPSI

Set size	ZGBF (EMPSI)	Polynomial ([23])
$28$	0.12	0.016
$212$	1.73	4.04
$216$	26.27	1076.71

Tab.2 Setup time comparison between ZGBF, polynomial in

P 1

[23] (in seconds)

Fig.14 Setup time comparison between ZGBF, polynomial in

P 1

[23] (in seconds)

Set size	Number of parties	EMPSI	[23]
$28$	3	1.69	0.027
	4	2.11	0.028
	5	2.39	0.035
	10	3.40	0.11
	15	4.63	0.11
$212$	3	28.83	8.00
	4	33.14	7.10
	5	39.85	8.82
	10	54.64	17.21
	15	79.90	26.47
$216$	3	447.22	1402.72
	4	506.25	2855.82
	5	544.87	3758.89
	10	895.73	7514.67
	15	1220.75	6407.60

Tab.3 Total time comparison between EMPSI and [23] (in seconds)

Fig.15 Total Time comparison for set size

28

between EMPSI and [23] (in seconds)

Fig.16 Total Time comparison for set size

212

between EMPSI and [23] (in seconds)

Fig.17 Total time comparison for set size

216

between EMPSI and [23] (in seconds)

Set size	ZGBF (EMPSI)	BF+Elgamal([24])
$28$	0.12	0.11
$212$	1.73	1.76
$216$	26.27	28.59

Tab.4 Setup time comparison between ZGBF, BF+Elgamal Encryption [24] (in seconds)

Fig.18 Setup Time comparison between ZGBF, BF+Elgamal Encryption [24] (in seconds)

Set size	Number of parties	EMPSI-CA	[24]
$28$	3	1.69	0.66
	4	2.12	0.92
	5	2.39	1.23
	10	3.40	2.71
	15	4.64	4.49
$212$	3	28.91	165.73
	4	33.21	262.65
	5	39.93	370.42
	10	54.72	852.29
	15	79.98	1283.72
$216$	3	448.38	3151.80
	4	507.42	5454.66
	5	546.03	6928.32
	10	896.89	14646.64
	15	1221.91	20539.52

Tab.5 Total time comparison between EMPSI-CA and [24] (in seconds).

Fig.19 Total time comparison for set size

28

between EMPSI-CA and [24] (in seconds)

Fig.20 Total time comparison for set size

212

between EMPSI-CA and [24] (in seconds)

Fig.21 Total time comparison for set size

216

between EMPSI-CA and [24] (in seconds)

Tab.6 Theoretic comparison with some state-of-the-art works

Protocol	Communication		Computation
Protocol	Server	Client	Server	Client
[9](GBF)	$O (t n λ)$	$O (t n λ)$	$O (t k)$	$O (t k)$
[10](GBF)	$O (t n λ k)$	$O (t n λ k)$	$O (t n λ k)$	$O (t n λ k)$
[24](BF+Elg)	$O (t n λ k)$	$O (t n λ k)$	$O (n) ×$ Elg	$O (n k) ×$ Elg
Ours(ZGBF)	$O (n λ k)$	$O (n λ k)$	$O (t n λ k)$	$O (n λ k)$

Tab.7 Theoretical comparison of MPSI

Protocol	Communication		Computation
Protocol	Server	Client	Server	Client
[24](BF+Elg)	$O (t n λ k)$	$O (t n λ k)$	$O (n) ×$ Elg	$O (n k) ×$ Elg
Ours(ZGBF)	$O (n λ k)$	$O (n λ k)$	$O (t n λ k)$	$O (n λ k)$

Tab.8 Theoretical comparison of MPSI-CA

1	C, Castelluccia N, Bielova A, Boutet M, Cunche C, Lauradoux Métayer D, Le V Roca . DESIRE: a third way for a European exposure notification system leveraging the best of centralized and decentralized systems. 2020, arXiv preprint arXiv: 2008.01621
2	P, Madhusudan L Ren , Venkatakrishnan V N. ConTraIL: privacy-preserving secure contact tracing. 2020
3	J, Chan D, Foster S, Gollakota E, Horvitz J, Jaeger S, Kakade T, Kohno J, Langford J, Larson P, Sharma S, Singanamalla J, Sunshine S Tessaro . PACT: privacy sensitive protocols and mechanisms for mobile contact tracing. 2020, arXiv preprint arXiv: 2004.03544
4	R, Canetti Y T, Kalai A, Lysyanskaya R L, Rivest A, Shamir E, Shen A, Trachtenberg M, Varia D J Weitzner . Privacy-preserving automated exposure notification. Cryptology ePrint Archive, 2020
5	B, Pinkas T, Schneider M Zohner . Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security, 2018, 21( 2): 7
6	B, Pinkas M, Rosulek V, Trieu A Yanai . SpOT-light: lightweight private set intersection from sparse OT extension. In: Proceedings of the 39th Annual International Cryptology Conference. 2019, 401−431
7	M, Chase P Miao . Private set intersection in the internet setting from lightweight oblivious PRF. In: Proceedings of the 40th Annual International Cryptology Conference. 2020, 34−63
8	P, Rindal M Rosulek . Malicious-secure private set intersection via dual execution. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1229−1242
9	V, Kolesnikov N, Matania B, Pinkas M, Rosulek N Trieu . Practical multi-party private set intersection from symmetric-key techniques. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1257−1272
10	R, Inbar E, Omri B Pinkas . Efficient scalable multiparty private set-intersection via garbled bloom filters. In: Proceedings of the 11th International Conference on Security and Cryptography for Networks. 2018, 235−252
11	C, Dong L, Chen Z Wen . When private set intersection meets big data: an efficient and scalable protocol. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 789−800
12	A, Abadi S, Terzis C Dong . Feather: lightweight multi-party updatable delegated private set intersection. Cryptology ePrint Archive, 2020
13	A, Abadi S, Terzis C Dong . O-PSI: delegated private set intersection on outsourced datasets. In: Proceedings of the 30th IFIP International Information Security and Privacy Conference. 2015, 3−17
14	A, Abadi S, Terzis C Dong . VD-PSI: verifiable delegated private set intersection on outsourced private datasets. In: Proceedings of the 20th International Conference on Financial Cryptography and Data Security. 2016, 149−168
15	P, Branco N, Döttling S Pu . Multiparty cardinality testing for threshold private intersection. In: Proceedings of the 24th IACR International Conference on Public-Key Cryptography. 2021, 32−60
16	X, Yang X, Luo X A, Wang S Zhang . Improved outsourced private set intersection protocol based on polynomial interpolation. Concurrency and Computation: Practice and Experience, 2018, 30( 1): e4329
17	Y, Zhao S S M Chow . Can you find the one for me?. In: Proceedings of 2018 Workshop on Privacy in the Electronic Society. 2018, 54−65
18	L, Kissner D Song . Privacy-preserving set operations. In: Proceedings of the 25th Annual International Cryptology Conference. 2005, 241−257
19	T, Duong D H, Phan N Trieu . Catalic: delegated psi cardinality with applications to contact tracing. In: Proceedings of the 26th International Conference on the Theory and Application of Cryptology and Information Security. 2020, 870−899
20	R H Shi . Quantum bloom filter and its applications. IEEE Transactions on Quantum Engineering, 2021, 2: 2100411
21	R H Shi . Quantum multiparty privacy set intersection cardinality. IEEE Transactions on Circuits and Systems II: Express Briefs, 2021, 68( 4): 1203–1207
22	R H, Shi Y F Li . Quantum private set intersection cardinality protocol with application to privacy-preserving condition query. IEEE Transactions on Circuits and Systems I: Regular Papers, 2022, 69( 6): 2399–2411
23	C, Hazay M Venkitasubramaniam . Scalable multi-party private set-intersection. In: Proceedings of the 20th IACR International Workshop on Public Key Cryptography. 2017, 175−203
24	S K, Debnath P, Stǎnicǎ N, Kundu T Choudhury . Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15( 2): 365–386
25	A Shamir . How to share a secret. Communications of the ACM, 1979, 22( 11): 612–613
26	B Schneier . Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, 2007
27	M O Rabin . How to exchange secrets with oblivious transfer. Cryptology ePrint Archive, 2005
28	V, Kolesnikov R Kumaresan . Improved OT extension for transferring short secrets. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 54−70
29	M J, Freedman Y, Ishai B, Pinkas O Reingold . Keyword search and oblivious pseudorandom functions. In: Proceedings of the 2nd Theory of Cryptography Conference. 2005, 303−324
30	V, Kolesnikov R, Kumaresan M, Rosulek N Trieu . Efficient batched oblivious PRF with applications to private set intersection. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 818−829
31	S, Jarecki X Liu . Fast secure computation of set intersection. In: Proceedings of the 7th International Conference on Security and Cryptography for Networks. 2010, 418−435
32	N, Chandran N, Dasgupta D, Gupta S L B, Obbattu S, Sekar A Shah . Efficient linear multiparty PSI and extensions to circuit/quorum PSI. In: Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021, 1182−1204
33	A, Bampoulidis A, Bruni L, Helminger D, Kales C, Rechberger R Walch . Privately connecting mobility to infectious diseases via applied cryptography. Proceedings on Privacy Enhancing Technologies, 2022, 2022( 1): 768–788

[1]

FCS-22269-OF-YY_suppl_1

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed