Encrypted Skyline Queries Promise Safer Online Medical Diagnosis

Online medical diagnosis has quietly become one of the most consequential applications of the digital age. For patients in rural or under-resourced regions, the ability to submit symptoms and receive diagnostic guidance from a remote service can mean the difference between timely treatment and prolonged illness. Yet behind every such interaction lies a delicate transaction: highly sensitive medical data must travel to servers that the patient does not control, be processed by algorithms the patient cannot inspect, and return a result whose quality depends on how well the system can sift through vast stores of case records. A new study published in the Journal of Big Data argues that this trade-off between usefulness and privacy has been solved too narrowly in the past, and it proposes a cryptographic architecture that lets patients define their own search criteria without ever exposing the underlying data.

The research, led by Yong Wang of Wannan Medical University together with colleagues at Anhui Normal University, Bengbu University and Zhejiang University, introduces a scheme called UDSQ, short for user-defined dynamic skyline secure query. At its heart lies a classic problem from multi-criteria database theory known as the skyline query. Given a collection of data points, each described by several attributes, a skyline query returns the set of points that are not dominated by any other point. A point dominates another if it is at least as good in every attribute and strictly better in at least one. In a medical context, imagine searching a database of patient cases for records that minimize both treatment cost and symptom severity while maximizing treatment success. The skyline consists of all cases that no other case beats across that entire combination of criteria, giving clinicians a shortlist of genuinely compelling matches rather than an arbitrary ranking.

What makes the new work distinctive is the word dynamic in its title. In conventional skyline systems, the attributes used for comparison are fixed in advance by the database designer. A patient consulting an online diagnosis service, however, may care about very different things: one might prioritize the experience level of the treating physician, another the proximity of the clinic, a third the cost of medication. UDSQ allows the user to define the region of interest, the set of dimensions and the thresholds that matter to them at query time. The system then restricts the skyline computation to that user-defined region, which has a welcome side effect: by shrinking the search space, it reduces the computational burden and the amount of data that must travel back and forth between the server and the client.

The central obstacle, of course, is that the medical records on the server are supposed to be encrypted. A skyline query appears to require exactly what encryption forbids: comparing values to determine which point dominates which. The authors resolve this tension by combining two cryptographic primitives. The first is order-revealing encryption, a technique that allows a server to compare the relative order of two ciphertexts without being able to decrypt either one. With order-revealing encryption, the server can evaluate dominance relationships among encrypted records, determining whether one encrypted case is better than another across the user’s chosen attributes, while learning nothing about the actual values of cost, severity or success rate.

The second primitive is proxy re-encryption, which addresses a different problem: how a single untrusted server can process queries from many users without each user having to share a secret key with the server. In a proxy re-encryption scheme, a data owner can generate a special transformation key that lets the server convert ciphertexts encrypted under one key into ciphertexts readable under another, without the server ever seeing the plaintext or the original key. In UDSQ, this mechanism allows the diagnosis platform to re-encrypt results so that only the querying patient can read them. Crucially, the authors show that combining proxy re-encryption with a single-server model defends against collusion attacks, scenarios in which a malicious server and a compromised user pool their information in an attempt to reconstruct other patients’ data. Because the transformation keys are structured to prevent any coalition from inverting the encryption, the scheme maintains its privacy guarantees even under this stronger adversary model.

To make the encrypted skyline computation efficient, the researchers designed two dedicated algorithms. The Rectangles Intersection Determination Algorithm, or RIDA, represents the user-defined query region geometrically and determines which candidate data points fall within its boundaries by computing intersections between rectangular regions in the attribute space. Rather than testing every record against every dimension individually, RIDA prunes the candidate set using rectangle intersection tests performed directly on encrypted representations. The Skyline Point Determination Algorithm, or SPDA, then takes the surviving candidates and establishes their dominance relationships in ciphertext, identifying which points belong to the final skyline. The division of labor matters: by separating spatial pruning from dominance testing, the pipeline avoids the quadratic comparisons that plague naive skyline implementations, and the authors report that the combination yields measurable advantages in both communication and computation overhead compared with existing approaches.

The experimental evaluation, conducted on publicly available benchmark datasets rather than real patient records, supports the efficiency claims. Because the study did not involve human participants or new human subject data, the authors note that ethics approval was not applicable, and the use of public benchmarks means the performance figures reflect the algorithms themselves rather than any particular clinical deployment. The reported results indicate that UDSQ reduces the communication cost between client and server, a critical factor for patients in areas with limited bandwidth, while also lowering the computational load on the server. In encrypted-query research, where cryptographic operations typically impose orders-of-magnitude slowdowns, achieving both security and competitive overhead is the benchmark of a practical design.

The implications extend beyond medicine. Skyline queries arise wherever users must choose among multi-attribute alternatives: hotel bookings balancing price, location and rating; investment portfolios balancing risk and return; sensor networks balancing energy consumption and data fidelity. Any of these domains could adopt the user-defined, encrypted paradigm that UDSQ demonstrates. But medicine is the most urgent case, because the stakes of disclosure are highest. A patient’s diagnostic history, once leaked, cannot be changed the way a compromised password can. Regulatory frameworks around the world increasingly demand that health data be protected not only in transit but also during computation, and techniques like order-revealing encryption represent one of the few viable paths to computing on data that remains sealed throughout the process.

Still, the scheme is not a panacea, and honest reporting requires acknowledging the boundaries of what the study demonstrates. Order-revealing encryption, while powerful, leaks the ordering of values by design, and the cryptographic community continues to study what auxiliary information an adversarial server might infer from such leakage when combined with background knowledge. The single-server model simplifies deployment but concentrates trust in one infrastructure provider, even if that provider cannot read the data. And the user-defined nature of the query, while empowering, means that the privacy profile can shift with each new query configuration, a dynamic that future work will need to characterize formally. The authors’ contribution is best understood as a well-engineered point in the design space, one that balances these tensions more favorably than prior schemes while leaving open questions that the field is actively pursuing.

What the study ultimately signals is a maturing of privacy-preserving computation from theoretical curiosity toward deployable infrastructure. The researchers, funded by the doctoral research foundation of Wannan Medical College and the Anhui Province Intelligent Robot Information Fusion and Control Engineering Research Center, have published their work open access, allowing clinicians, cryptographers and system builders to scrutinize and extend it. As online diagnosis platforms expand into regions where they can do the most good, the demand for systems that never force patients to choose between accurate answers and protected data will only grow. UDSQ offers a concrete demonstration that this choice is not inevitable: with the right combination of user control, geometric pruning and modern encryption, the skyline of the best possible medical matches can be computed entirely in the dark, and delivered intact to the one person who holds the key.

Subject of Research: Secure user-defined dynamic skyline queries for privacy-preserving online medical diagnosis

Article Title: UDSQ: a secure and efficient user-defined dynamic skyline query in online medical diagnosis

Article References: Wang, Y., Xu, X., Nie, X., & Peng, G. (2026). UDSQ: a secure and efficient user-defined dynamic skyline query in online medical diagnosis. Journal of Big Data. https://doi.org/10.1186/s40537-026-01581-8

Image Credits: AI Generated

DOI: 10.1186/s40537-026-01581-8

Keywords: skyline query, data security, privacy protection, online medical diagnosis, order-revealing encryption, proxy re-encryption, encrypted queries, cloud computing, database management, collusion attacks, health informatics, cryptography