Secure manifold learning on datasets distributed among multiple data owners can benefit or even spawn many applications. For example, multiple service providers can jointly fit low-dimensional embeddings of their users' network behavior data to improve the accuracy of anomaly detection while addressing their privacy concerns about the datasets. In this paper, we focus on a classic manifold learning technique, known as isometric mapping (Isomap), and propose SIsomap, the first secure, distributed manifold learning system. We construct SIsomap based on secret sharing techniques and introduce careful optimizations. In particular, we propose two communication-efficient secure building blocks that focus on top-k and all-pairs shortest paths computation, respectively, and reduce secure operations by leveraging the characteristics of Isomap. Experimental results on both synthetic and real-world datasets demonstrate that our secure top-k and all-pairs shortest paths protocols are respectively up to 13.6× and 1818.5× faster than the state-of-the-art methods, and SIsomap as a whole is 11.1× to 28.8× faster than the baseline solution.

Large language models (LLMs) integrated with retrieval-augmented generation (RAG) systems improve accuracy by leveraging external knowledge sources. However, recent research has revealed RAG's susceptibility to poisoning attacks, where the attacker injects poisoned texts into the knowledge database, leading to attacker-desired responses. Existing defenses, which predominantly focus on inference-time mitigation, have proven insufficient against sophisticated attacks. In this paper, we introduce RAGForensics, the first traceback system for RAG, designed to identify poisoned texts within the knowledge database that are responsible for the attacks. RAGForensics operates iteratively, first retrieving a subset of texts from the database and then utilizing a specially crafted prompt to guide an LLM in detecting potential poisoning texts. Empirical evaluations across multiple datasets demonstrate the effectiveness of RAGForensics against state-of-the-art poisoning attacks. This work pioneers the traceback of poisoned texts in RAG systems, providing a practical and promising defense mechanism to enhance their security.

Dynamic symmetric searchable encryption (SSE) enables clients to perform searches and updates on an encrypted database outsourced to an untrusted server while preserving the privacy of data and queries. For restricting information leakage, it is very important to limit what the server can learn about the deleted data during searches after the deletion, i.e., to satisfy backward privacy. However, previous backward privacy definitions only considered the logical deletion of keywords in documents while ignoring security risks caused by the actual deletion of documents. Moreover, existing SSE schemes often depend on heavy cryptographic primitives for achieving high-level backward privacy, which greatly degrades the end-to-end performance. To this end, we define a new backward privacy notion named BP-DEL, which restricts the information leakage of the actual deletion. Moreover, we design a hybrid index structure that provides BP-DEL for SSE schemes such that they support deletions securely. Based on the hybrid index, we propose a BP-DEL construction named LUNA and design its protocols with a trusted execution environment (TEE) to maintain the index efficiently. Finally, we implement LUNA in the MySQL database by encapsulating it in UDFs. The experimental results show that LUNA has a performance much better than previous works satisfying BP-DEL.

Privacy-preserving collaborative data analysis is a popular research direction in recent years. Among all such analysis tasks, privacy-preserving SQL queries on multi-party databases are of particular industrial interest. Although the privacy concern can be addressed by many cryptographic tools, such as secure multi-party computation (MPC), the efficiency of executing such SQL queries is far from satisfactory, especially for high-volume databases. In particular, existing MPC-based solutions treat each SQL query as an isolated task and launch it from scratch, in spite of the nature that many SQL queries are done regularly and somewhat overlap in their functionalities. In this work, we are motivated to exploit this nature to improve the efficiency of MPC-based, privacy-preserving SQL queries. We introduce a cache-like optimization mechanism. To ensure a higher cache hit rate and reduce redundant MPC operators, we present a cache structure different from that of plain databases and design a set of cache strategies. Our optimization mechanism, SMPCache, can be built upon secret-sharing-based MPC frameworks, which attract much attention from the industry. To demonstrate the utility of SMPCache, we implement it on Rosetta, an open-source MPC library, and use real-world datasets to launch extensive experiments on some basic SQL operators (e.g., Filter, Order-by, Aggregation, and Inner-Join) and some representative composite SQL queries. To give a data point, we note that SMPCache can achieve most up to 3536× efficiency improvement on the TPC-DS dataset and 562× on the TPC-H dataset at a moderate storage cost. We also apply SMPCache to the basic SQL operators (Filter, Order-by, Group-by, Aggregation, and Inner-join) of the Secrecy framework, achieving up to 127.3× efficiency improvement.

Jointly learning from multiple datasets can help building versatile intelligent systems yet may give rise to serious concerns of data privacy and model selection. Specifically, on the one hand, these datasets can be distributed at various local clients, who may not be willing or do not ought to share data with each other. On the other hand, it is unrealistic to choose a model architecture that can well suit the disparate patterns and distributions carried by the various datasets in a priori. Whereas many works in federated learning [1] and neural architecture search [2] have been proposed to address one of the two concerns, very few have attempted the both. To close the gap, in this paper we deliver a framework, termedMulti-Granular Federated Neural Architecture Search(MGFNAS), to enable the automation of model architecture search in a federated and thus privacy-preserved setting. We argue that our MGFNAS framework is general in the sense that it does not impose any restriction on the search space or strategy, such that most existing neural architecture search techniques can be readily implemented in. The main idea of our framework is to search the optimal neural network architecture in two levels of granularity, enabling the neural-operator-basedmicro-levelsearch and the cell-basedmacro-levelsearch. The main challenge of implementing our framework lies in the fact that, due to the decentralized nature, the local architectures searched by multiple clients can differ drastically in order to fit their own datasets, while a general method to form the global model by aggregating the local architectures in both micro and macro levels is missing. To solve the issue, we propose a novel aggregation function, named Network Architecture Probabilistic Aggregation (NAPA). The key idea of our NAPA function is to treat the network architectures as graphs, of which the sub-graph structures being frequently appeared across multiple clients are modeled by probabilistic distributions. At each round, a global model is formed by sampling from those distributions in an exploration-exploitation fashion. Extensive experiments are carried out, and the results substantiate the viability and effectiveness of our proposed framework.

The range query on encrypted databases is usually implemented using the order-preserving encryption (OPE) technique which preserves the order of plaintexts. Since the frequency leakage of plaintexts makes OPE vulnerable to frequency-analyzing attacks, some frequency-hiding order-preserving encryption (FH-OPE) schemes are proposed. However, existing FH-OPE schemes require either the large client storage of size O ( n ) or O (log n ) rounds of interactions for each query, where n is the total number of plaintexts. To this end, we propose a FH-OPE scheme that achieves the small client storage without additional client-server interactions. In detail, our scheme achieves O ( N ) client storage and 1 interaction per query, where N is the number of distinct plaintexts and N ≤ n . Especially, our scheme has a remarkable performance when N ≪ n . Moreover, we design a new coding tree for producing the order-preserving encoding which indicates the order of each ciphertext in the database. The coding strategy of our coding tree ensures that encodings update in the low frequency when inserting new ciphertexts. Experimental results show that the single round interaction and low-frequency encoding updates make our scheme more efficient than previous FH-OPE schemes.

Encryption alone is not enough to protect data privacy, because access pattern leaks some sensitive information. Oblivious RAM (ORAM), the solution to this problem, is still far from practical deployment for heavy storage and communication/computation overhead. To reduce them, an insightful idea was proposed to utilize non-colluding clouds to shift client computation and client-cloud communication to the clouds. The proposed multi-cloud ORAM achieved O(1) client-cloud bandwidth cost and removed most of client computation. In this paper, we exploit “disconnected ORAMoperation” and design “two-layerencryption” to further reduce these overheads. Experiments show that our proposed scheme, NewMCOS, significantly reduces evict cache size from GB/MB to KB level with about 2-3 times lower response time and 20 percent savings in bandwidth for clouds, compared to other schemes. Theoretically speaking, we reduce evict cache size from O(√N) to O(ZK), where N is the number of real data blocks, K is the number of clouds (2 <; K <; <; √N ), and Z is the number of real blocks uploaded from the client for eviction. By employing “lazy eviction operation”, the write frequency is reduced by O(Z), the shuffling bandwidth cost is reduced by Ω(Z log Z). Meanwhile, NewMCOS is proved to be secure.

The rich cloud services in the Internet of Things create certain needs for edge computing, in which devices should be able to handle storage tasks securely, reliably, and efficiently. When processing the storage requests from edge devices, each cloud server is supposed to eliminate duplicate copies of repeating data to reduce the amount of storage space and save on bandwidth. To protect data confidentiality while supporting deduplication, some convergent-encryption-based techniques have been proposed to encrypt the data before uploading. However, all these works cannot meet two requirements while preventing brute-force attacks: (i) power-constrained edge nodes should update encryption keys efficiently when an edge node is abandoned; and (ii) the access privacy of edge nodes should be guaranteed. In this article, we propose a novel encryption scheme for secure chunk-level deduplication. Based on this scheme, we present two constructions of the secure deduplication system that support an efficient key update protocol. The key update protocol does not involve any edge node in computational tasks, so that the deduplication system can adopt an active key update strategy. Moreover, one of our constructions, which is called advance construction, can provide access privacy assurances for edge nodes. The security analysis is given in terms of the proposed threat model. The experimental analysis demonstrates that the proposed deduplication system is practical.