Heapsort-Based Secure Top-K Query Scheme for E-Healthcare Systems

In the e-Healthcare ecosystem, medical institutions increasingly rely on cloud computing platforms to outsource data storage and query processing, aiming to optimize service delivery efficiency. A critical component of such services is the top-<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> query, which identifies the <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> most relevant or highest-ranked records within datasets. However, since medical data contain sensitive patient information and require privacy-preserving outsourcing, traditional top-<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> query schemes are no longer suitable, while existing privacy-preserving solutions suffer from high computational overhead in practice. To address these issues, we introduce a lightweight privacy-preserving secure top-<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> query scheme. Specifically, our proposed scheme utilizes lightweight cryptographic tools, additive secret sharing and Function Secret Sharing (FSS) techniques, as the foundation of the underlying distributed secure computation. These techniques significantly reduce computational overhead while ensuring the privacy of medical data. Furthermore, we propose a Secure Max Heap Sorting (MH) protocol, which helps us to rapidly implement the top-<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> query functionality in our scheme. Additionally, we design a set of fundamental secure protocols based on FSS, including the Secure Minimum Value (MinV) protocol, Secure Maximum Value (MaxV) protocol and Secure Heap Adjustment (HA) protocol. By integrating our cryptographic protocols with a secure squared Euclidean distance protocol, we construct a secure top-<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> query scheme for e-Healthcare scenarios. Finally, we present formal security proofs under the semi-honest adversary model, which theoretically establish the security of the proposed scheme. Thanks to the adoption of secret sharing techniques, our scheme requires the client to only split the data into secret shares, a process that incurs nearly zero computational cost. The superior efficiency of our solution is further demonstrated through theoretical analysis and experimental evaluations.