Symmetric searchable encryption (SSE) for geo-textual data has attracted significant attention. However, existing schemes rely on task-specific, incompatible indices for isolated specific secure queries (e.g., range or k-nearest neighbor spatial-keyword queries), limiting practicality due to prohibitive multi-index overhead. To address this, we propose RISK, a model for rich spatial-keyword queries on encrypted geo-textual data. In a textual-first-then-spatial manner, RISK is built on a novel k-nearest neighbor quadtree (kQ-tree) that embeds representative and regional nearest neighbors, with the kQ-tree further encrypted using standard cryptographic tools (e.g., keyed hash functions and symmetric encryption). Overall, RISK seamlessly supports both secure range and k-nearest neighbor queries, is provably secure under IND-CKA2 model, and extensible to multi-party scenarios and dynamic updates. Experiments on three real-world and one synthetic datasets show that RISK outperforms state-of-the-art methods by at least 0.5 and 4 orders of magnitude in response time for 1% range queries and 10-nearest neighbor queries, respectively.

Abstract This study introduces an innovative framework named scale for processing dynamic skyline queries securely in cloud environments. Unlike previous approaches that require complex operations on encrypted data, scale simplifies dynamic skyline domination to mere comparisons, significantly improving query efficiency. Through empirical evaluations over four datasets, we show that scale accelerates query processing nearly 1000-fold compared to existing state-of-the-art methods. Specifically, scale shows significant efficiency improvements by simplifying query interactions to a single round between the user and the cloud, which is validated through empirical studies on multiple datasets. Moreover, we introduce two distributed versions of scale , dist-scale-s and dist-scale-e , which further optimize performance by facilitating parallel processing. This adaptation showcases a substantial reduction in response times and computational overhead, underpinning the scalability and effectiveness of our framework in handling large-scale, secure cloud-based queries.

Ensuring the ACID properties of transactions is the fundamental functionality of transactional DBMSs. However, through our study on existing solutions on transaction management, we found that transaction implementations in some mainstream databases, such as MySQL, MariaDB and TiDB, may violate what they claim in their documentation, in the form of incorrect database state or query results. Since there is still a lack of efficient and comprehensive testing methods to detect bugs within transaction management implementation for off-the-shelf DBMSs at present, we propose Fucci, a fuzzing framework, to solve the problem. Given a target DBMS, Fucci improves the efficiency of detecting transaction bugs through three key components: Random Conflict Construction (RCC), Multilevel Constraint Solving (MCS), and Experience-driven Automatic Simplification (EAS). RCC addresses the issue of inadequate case validity by ensuring the presence of read-write or write-write conflicts between transactions. MCS enhances the accuracy and efficiency of the transaction oracle by employing an external multi-version control system to solve data visibility. EAS is ultimately adopted to improve the efficiency of simplification and the readability of the identified bug cases. All of the above strategies are tested on commercial databases such as MySQL, MariaDB and TiDB. Accordingly, 6 previously unknown transaction bugs and 14 known duplicate transaction bugs have been newly discovered, most of which have been officially acknowledged.

Proximity graphs (PG) have gained increasing popularity as the state-of-the-art solutions to k -approximate nearest neighbor ( k -ANN) search on high-dimensional data, which serves as a fundamental function in various fields, e.g., retrieval-augmented generation. Although PG-based approaches have the best k -ANN search performance, their index construction cost is superlinear to the number of points. Such superlinear cost substantially limits their scalability in the era of big data. Hence, the goal of this paper is to accelerate the construction of PG-based methods without compromising their k -ANN search performance. To achieve this goal, two mainstream categories of PG are revisited: relative neighborhood graph (RNG) and navigable small world graph (NSWG). By revisiting their construction process, we find the issues of construction efficiency. To address these issues, we propose a new construction framework with a novel pruning strategy for edge selection, which accelerates RNG construction while keeping its k -ANN search performance. Then, we integrate this framework into NSWG construction to enhance both the construction efficiency and k -ANN search performance of NSWG. Extensive experiments are conducted to validate our construction framework for both RNG and NSWG, and that it significantly reduces the PG construction cost, achieving up to 5.6x speedup, while not compromising the k -ANN search performance.

With the extensive usage of convolutional neural networks (CNNs), privacy issues within practical applications have attracted much attention, especially when deep learning services are provided by third-party clouds. Many private inference schemes have been proposed, but their overheads are still too large. In this work, we find that the inference procedure of CNNs can be separated and performed synergistically by many parties. Following this observation, we present a pair of novel notions, namely separable and conditional separable, to tell whether a layer in CNNs can be exactly computed over multiple parties or not. Besides, we also prove that CNNs are conditionally separable. Accordingly, we propose Serpens, a private inference framework under multi-server settings. Serpens reduces the overhead of linear layers to almost zero, and now the computing bottleneck is ReLU. To address that, we design two secure ReLU protocols based on homomorphic encryption and random masks for two- and three-server settings. Experimental results show that Serpens is 78x-105x faster than the state-of-the-art private inference scheme in the two-server setting, and the superiority of Serpens is even larger in the three-server setting, only 11x-64x slower than performing the same inference over plaintext images.