IXT: Improved searchable encryption for multi-word queries based on PSI

doi:10.1007/s11704-022-2236-9

Frontiers of Computer Science

2023, Vol. 17

Issue (5): 175811 https://doi.org/10.1007/s11704-022-2236-9

本期目录

IXT: Improved searchable encryption for multi-word queries based on PSI

Yunbo YANG^1,², Xiaolei DONG¹(

), Zhenfu CAO¹(

), Jiachen SHEN¹(

), 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 200233, China
³. PwC US Advisory Shanghai AC, Shanghai 201203, China

全文: PDF(6166 KB) HTML

Abstract：

Oblivious Cross-Tags (OXT) [1] is the first efficient searchable encryption (SE) protocol for conjunctive queries in a single-writer single-reader framework. However, it also has a trade-off between security and efficiency by leaking partial database information to the server. Recent attacks on these SE schemes show that the leakages from these SE schemes can be used to recover the content of queried keywords. To solve this problem, Lai et al. [2] propose Hidden Cross-Tags (HXT), which reduces the access pattern leakage from Keyword Pair Result Pattern (KPRP) to Whole Result Pattern (WRP). However, the WRP leakage can also be used to recover some additional contents of queried keywords. This paper proposes Improved Cross-Tags (IXT), an efficient searchable encryption protocol that achieves access and searches pattern hiding based on the labeled private set intersection. We also prove the proposed labeled private set intersection (PSI) protocol is secure against semi-honest adversaries, and IXT is $L ′$ -semi-honest secure ( $L ′$ is leakage function). Finally, we do experiments to compare IXT with HXT. The experimental results show that the storage overhead and computation overhead of the search phase at the client-side in IXT is much lower than those in HXT. Meanwhile, the experimental results also show that IXT is scalable and can be applied to various sizes of datasets.

Key words： searchable encryption private set intersection

收稿日期: 2022-04-20 出版日期: 2023-03-22

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

引用本文:

. [J]. Frontiers of Computer Science, 2023, 17(5): 175811.
Yunbo YANG, Xiaolei DONG, Zhenfu CAO, Jiachen SHEN, Shangmin DOU. IXT: Improved searchable encryption for multi-word queries based on PSI. Front. Comput. Sci., 2023, 17(5): 175811.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-022-2236-9
https://academic.hep.com.cn/fcs/CN/Y2023/V17/I5/175811

Tab.1

Notation	Meaning
$λ$	Security parameter
$κ$	Statistical parameter
$H 1, H 2$	Collusion-resistance hash function
$C$	Linear correcting code
$∧$	Bit-wise AND
$⊕$	Bit-wise XOR
$d$	Number of documents in database
Sym	An indistinguishability under chosen-plaintext attack (IND-CPA) secure encryption scheme
$i d i$	The document identifier of the $i t h$ document
$w$	A keyword
$D B$	Database $(i d i, W i) i = 1 d$
$D B (w)$	inverted-index
$\| D B (w) \|$	Number of identifiers corresponding to keyword $w$
$E D B$	Encrypted database
$W$	The set of all keywords
$D, Q, R$	PaXoS structure
$L [y]$	All corresponding labels of $y$
$[n]$	The set of integers $1, 2, . . ., n$
$n$	Max number of keywords per query
$R$	Result set at client side
negl $(λ)$	A negligible function in $λ$
$N$	Number of $(w, i d)$ pairs
$n$	Number of queried keywords
$T P R F$	Time to perform PRF computation
$T h a s h$	Time to perform hash computation of BF
$T X O R$	Time to perform bitwise XOR computation over $λ$
$T E n c$	Time to perform symmetric-key encryption computation
$T D e c$	Time to perform symmetric-key decryption computation
$T T S e t$	Time to perform TSet computation
$k$	Number of hash used in BF
$p, e$	Number of pairings and exponentiations
$m, m ′$	Number of multiplications over $G$ and elements in BF
$e p r e$	Number of preprocessed exponentiations
$\| t \|$	Number of retrieved elements in TSet

Tab.2

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

id	Keywords
1	$w 1, w 2, w 6, w 7, w 8$
2	$w 2, w 3, w 4, w 5$
3	$w 4, w 5, w 6, w 7$
4	$w 1, w 2, w 3$
5	$w 1, w 3, w 6$
6	$w 2, w 3, w 7$

Tab.3

Scheme	Access pattern leakage entries	Search pattern leakage entries
HXT	$(i d 4, w 2), (i d 4, w 3)$	$w 1 . w 2, w 3$
IXT	None	None

Tab.4

Fig.6

Fig.7

		OXT[1]	HXT[2]	IXT
Comp.	Set-up comp. cost	$N (T T S e t + e p r e + K T h a s h)$	$N (T T S e t + e p r e + K T h a s h) + (m) T P R F$	$O (n λ)$
	Common cost (server) xtag & BF match	$\| D B (w 1) \| ((n ? 1) (k T h a s h + e))$		N/A
	Additional cost (server) HVE Queries	N/A	$\| D B (w 1) \| ((m ′) T X O R + T D e c)$	N/A
	Common cost (server) labeled PSI	N/A	N/A	$O (N λ)$
	Common cost (client) stag, xtoken & index recover	$\| D B (w 1) \| ((m ′) T P R F + (m ′) T X O R + T E n c)$		N/A
	Additional cost (client) HVE KeyGen	N/A	$\| D B (w 1) \| ((m ′) T P R F + (m ′) T X O R + T E n c)$	N/A
	Common cost (client) labeled PSI	N/A	N/A	$O (n λ)$
Storage	Storage size (server)	$N λ + m$	$N λ + m λ$	$N λ$
Comm.	Common comm.	$\| t \| + \| D B (w 1) \| (n ? 1) G + \| ? \| O (λ)$		$O (N λ)$
Comm.	Additional comm. token_c transmission	N/A	$\| D B (w 1) \| (O (m ′ + 2 λ))$	N/A

Tab.5

Number of databases	Distinct (id,w) pairs
1	$101$
2	$102$
3	$103$
4	$104$
5	$105$
6	$106$
7	$107$

Tab.6

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

1	D, Cash S, Jarecki C, Jutla H, Krawczyk M C, Roşu M Steiner . Highly-scalable searchable symmetric encryption with support for Boolean queries. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 353–373
2	S, Lai S, Patranabis A, Sakzad J K, Liu D, Mukhopadhyay R, Steinfeld S F, Sun D, Liu C Zuo . Result pattern hiding searchable encryption for conjunctive queries. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 745–762
3	R, Curtmola J, Garay S, Kamara R Ostrovsky . Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19( 5): 895–934
4	M J, Freedman K, Nissim B Pinkas . Efficient private matching and set intersection. In: Proceedings of 2004 International Conference on the Theory and Applications of Cryptographic Techniques on Cryptology. 2004, 1–19
5	K, Lee M Seo . Functional encryption for set intersection in the multi-client setting. Designs, Codes and Cryptography, 2022, 90( 1): 17–47
6	Y, Huang D, Evans J Katz . Private set intersection: are garbled circuits better than custom protocols? In: Proceedings of the 19th Network and Distributed Security Symposium. 2012
7	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
8	H, Chen K, Laine P Rindal . Fast private set intersection from homomorphic encryption. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 1243–1255
9	H, Chen Z, Huang K, Laine P Rindal . Labeled PSI from fully homomorphic encryption with malicious security. In: Proceedings of 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018, 1223–1237
10	J, Wang X, Chen S F, Sun J K, Liu M H, Au Z H Zhan . Towards efficient verifiable conjunctive keyword search for large encrypted database. In: Proceedings of the 23rd European Symposium on Research in Computer Security. 2018, 83–100
11	C, Liu L, Zhu M, Wang Y A Tan . Search pattern leakage in searchable encryption: attacks and new construction. Information Sciences, 2014, 265: 176–188
12	A, Peter E, Tews S Katzenbeisser . Efficiently outsourcing multiparty computation under multiple keys. IEEE Transactions on Information Forensics and Security, 2013, 8( 12): 2046–2058
13	M S, Islam M, Kuzu M Kantarcioglu . Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: Proceedings of the 19th Annual Network and Distributed System Security Symposium. 2012, 12
14	S, Garg P, Mohassel C Papamanthou . TWORAM: efficient oblivious ram in two rounds with applications to searchable encryption. In: Proceedings of the 36th Annual International Cryptology Conference. 2016, 563–592
15	B, Wang W, Song W, Lou Y T Hou . Inverted index based multi-keyword public-key searchable encryption with strong privacy guarantee. In: Proceedings of 2015 IEEE Conference on Computer Communications (INFOCOM). 2015, 2092–2100
16	Y, Wang S F, Sun J, Wang J K, Liu X Chen . Achieving searchable encryption scheme with search pattern hidden. IEEE Transactions on Services Computing, 2022, 15( 2): 1012–1025
17	B, Pinkas M, Rosulek N, Trieu A Yanai . PSI from PaXoS: fast, malicious private set intersection. In: Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2020, 739–767
18	M O Rabin . How to exchange secrets with oblivious transfer. Paper 2005/187. Cryptology ePrint Archive, 2005
19	V, Kolesnikov R Kumaresan . Improved OT extension for transferring short secrets. In: Proceedings of the 33rd Annual Cryptology Conference. 2013, 54–70
20	M, Orrù E, Orsini P Scholl . Actively secure 1-out-of-N OT extension with application to private set intersection. In: Proceedings of 2017 Cryptographers’ Track at the RSA Conference on Topics in Cryptology. 2017, 381–396
21	O Goldreich . Foundations of Cryptography: Vol. 2, Basic Applications. Cambridge: Cambridge University Press, 2004
22	Apache Lucene. See Lucene.apache website

[1]

FCS-22236-OF-YY_suppl_1

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed