Privacy-Preserving and Robust Skyline Querying over Incomplete Data in Sharded Blockchain Networks

Decentralised applications (DApps) in Web 3.0 increasingly need multi-criteria queries such as location-based skylines. These queries return the records near a user that are not dominated on any criterion, for example rentals that are close, cheap and well reviewed. In a sharded blockchain, supporting such queries is hard for three reasons: records contributed by many parties have missing attribute values, records and queries are sensitive, and results must be assembled across shards. This paper proposes a framework that addresses all three challenges. First, the Dimensional Imputation and Enhancement network (DIME) repairs missing values before encryption. It is a mask-aware denoising autoencoder trained only on observed values and enhanced with positional encodings and neighbourhood statistics of the records' locations. Second, the data owner builds an Encrypted Shard-Tree for every shard, a padded R-tree whose entries are Paillier ciphertexts. On this index, a secure shard-based dominance protocol and a secure branch-and-bound search compute each shard's skyline with the help of a key-holding full node that only sees blinded, shuffled values. A constant-round protocol then merges the shards' results. We prove the protocols correct, characterise their leakage and evaluate a full implementation with real cryptography on two real and three synthetic datasets. With 30% missing values, DIME reduces the imputation error by up to 15% relative to MissForest on real data, whereas skyline semantics for incomplete data attain F1 scores as low as 0.02. Every secure query returned the exact skyline. The secure search was up to 7.5 times faster than an index-free secure scan and 25 times faster than a fully oblivious protocol, and its latency grew only 5.7-fold when the data grew 25-fold.

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-19
DOI
https://doi.org/10.21203/rs.3.rs-11615078/v1
Primary Topic
Data Management and Algorithms
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Privacy-Preserving and Robust Skyline Querying over Incomplete Data in Sharded Blockchain Networks

Kening Zhang, Yung Po Tsang, C.K.M. Lee
Research Square
Data Management and Algorithms
preprint

Privacy-Preserving and Robust Skyline Querying over Incomplete Data in Sharded Blockchain Networks

Kening Zhang, Yung Po Tsang, C.K.M. Lee
preprint en

Abstract

Decentralised applications (DApps) in Web 3.0 increasingly need multi-criteria queries such as location-based skylines. These queries return the records near a user that are not dominated on any criterion, for example rentals that are close, cheap and well reviewed. In a sharded blockchain, supporting such queries is hard for three reasons: records contributed by many parties have missing attribute values, records and queries are sensitive, and results must be assembled across shards. This paper proposes a framework that addresses all three challenges. First, the Dimensional Imputation and Enhancement network (DIME) repairs missing values before encryption. It is a mask-aware denoising autoencoder trained only on observed values and enhanced with positional encodings and neighbourhood statistics of the records' locations. Second, the data owner builds an Encrypted Shard-Tree for every shard, a padded R-tree whose entries are Paillier ciphertexts. On this index, a secure shard-based dominance protocol and a secure branch-and-bound search compute each shard's skyline with the help of a key-holding full node that only sees blinded, shuffled values. A constant-round protocol then merges the shards' results. We prove the protocols correct, characterise their leakage and evaluate a full implementation with real cryptography on two real and three synthetic datasets. With 30% missing values, DIME reduces the imputation error by up to 15% relative to MissForest on real data, whereas skyline semantics for incomplete data attain F1 scores as low as 0.02. Every secure query returned the exact skyline. The secure search was up to 7.5 times faster than an index-free secure scan and 25 times faster than a fully oblivious protocol, and its latency grew only 5.7-fold when the data grew 25-fold.

Research Square
Hong Kong Polytechnic University (HK)
Data Management and Algorithms
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon