Efficient Privacy-Preserving Similarity Range Query with Quadsector Tree in eHealthcare

The advance of smart eHealthcare has greatly enabled patients to enjoy high-quality healthcare services, e.g., disease prediction. Meanwhile, to support the dramatic increase of healthcare data, healthcare centers often outsource the on-premises data to the cloud. However, since the healthcare data contain some sensitive information and the cloud server is not fully trusted, healthcare centers need to encrypt the data before outsourcing them. Unfortunately, data encryption inevitably hinders some advanced data applications like the similarity range query. Although many studies on similarity range queries over encrypted data have been reported, most of them still have some limitations in security, efficiency, accuracy, and practicality. Aiming at this challenge, in this paper, we propose an efficient, privacy-preserving, and practical similarity range query (EPSim) scheme. Specifically, we first present a modified asymmetric scalar-product-preserving encryption (ASPE) scheme and prove its security. Then, we introduce a Quadsector tree to represent the data and employ a filtration condition to design an algorithm for efficient similarity range queries over the Quadsector tree. Finally, we propose our EPSim scheme by integrating the modified ASPE scheme and Quadsector tree. Detailed security analysis and performance evaluations indicate our scheme is really secure and efficient in similarity range queries.