Efficient and Privacy-Preserving Similarity Query With Access Control in eHealthcare
Yandong Zheng, Rongxing Lu, Yunguo Guan, Songnian Zhang, Jun Shao, Hui Zhu
Abstract
Similarity queries, giving a way to disease diagnosis based on similar patients, have wide applications in eHealthcare and are essentially demanded to be processed under fine-grained access policies due to the high sensitivity of healthcare data. One efficient and flexible way to implement such queries is to outsource healthcare data and the corresponding query services to a powerful cloud. Nevertheless, considering data privacy, healthcare data are usually outsourced in an encrypted form and required to be accessed in a privacy-preserving way. In the past years, many schemes have been proposed for privacy-preserving similarity queries. However, none of them is applicable to achieve data access control and access pattern privacy preservation. Aiming at this challenge, we propose an efficient and access pattern privacy-preserving similarity range query scheme with access control (named EPSim-AC). In our proposed scheme, we first design a novel tree structure, called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree, to index healthcare data and introduce an efficient <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree based similarity query algorithm with access control. Second, to balance the search efficiency and access pattern privacy of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree, we also define a weakened access pattern privacy, called <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree’s <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta $ </tex-math></inline-formula> -access pattern unlinkability. After that, we preserve the privacy of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree based similarity queries with access control through a symmetric homomorphic encryption scheme and present our detailed EPSim-AC scheme. Finally, we analyze the security of our scheme and also conduct extensive experiments to evaluate its performance. The results demonstrate that our scheme can guarantee <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> -d-PB tree’s <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\beta $ </tex-math></inline-formula> -access pattern unlinkability and has high efficiency.