Oblivious map is a cryptographic data structure for programs whose data access patterns exhibit some degree of predictability, which plays a pivot role in constructing high-security searchable encryption schemes that protect both search and access patterns. Typically, oblivious map schemes adopt the combination of an index tree and Oblivious RAM (ORAM) in their construction. However, the round complexity of access operations in these schemes is inherently linked to the height of the index tree, which is logarithmically proportional to the total number of blocks, denoted as$N$. This results in a traditional requirement of$O(\log N)$rounds of interaction per access, which is a significant inefficiency that hampers the practical applicability of oblivious maps. To this end, we design a new fixed-height index tree structure and employ it to construct a new oblivious map scheme, called BOMAP. This scheme features a small number of interaction rounds and does not require the client to store state information beyond the cache. Additionally, BOMAP achieves obliviousness with reduced padding in each access operation. We analyze the theoretical communication size for BOMAP and conclude that BOMAP has obvious advantages when an adaptive height is selected based on$N$(e.g., a 4-level index tree when$N=2^{24}$). Experimental results further demonstrate that the fewer interaction rounds and less padding strategy make BOMAP more efficient than previous oblivious map schemes.

Practical equi-join queries over encrypted databases aim to provide clients with flexible query capabilities while safeguarding data confidentiality. So far, the most promising and practical solution is CHT, which is based on Trusted Execution Environments (TEEs). However, such schemes can only support two-table equi-join queries, which are rather limited compared to Multi-Table Pairwise Equi-Join (MTPEJ). Furthermore, in terms of efficiency, throughput, and access pattern, the join implemented in TEEs is still problematic compared to a practical and secure scheme. In this work, we focus on this important type of equi-join, which facilitates join across any two tables among multiple tables. Specifically, we propose SP$^{2}$Join in this paper, the first MTPEJ framework that supports secure pairwise equi-join among multi-table by leveraging a novel oblivious pipeline join algorithm in TEEs. To validate our approach, we evaluate SP$^{2}$Join in MySQL using the benchmarks and real datasets, and the results demonstrate that SP$^{2}$Join is superior to the state-of-the-art in terms of secure equi-join. Particularly, our pipeline join query time is only 2.68% of CHT, yet throughput can reach up to 16.56 × of CHT. Even for MTPEJ, it is still 14.95% of CHT when implementing pairwise equi-join among 10 tables, with a time cost of approximately 140.30 ms.

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.

To privately publish sensitive multimedia data in an edge network with fog devices, one of the best privacy-preserving solutions is to use differential privacy (DP) mechanisms. However, existing DP data publication mechanisms for the infinite data stream of edge networks mainly focus on publishing data with specific types of data or a set of predetermined queries. This approach is not suitable for multimedia data with numerous features that require a more flexible data publishing mechanism. In this article, we propose EdgeSyn, a novel mechanism for accurately publishing multimedia data over infinite data streams in an edge network. It allocates privacy budgets with a sliding window, adopting data synthesis mechanisms to support dynamic publishing without loss of accuracy. In more detail, EdgeSyn addresses the limitations associated with data types in prior data stream publishing approaches and introduces a privacy budget management strategy that optimally allocates budgets for the implementation of data synthesis mechanisms over an infinite data stream. The experimental results show that EdgeSyn performs well under different privacy budgets and various lengths of active windows.

Secure Multi-party Computation (MPC) provides a promising solution for privacy-preserving multi-source data analytics. However, existing MPC-based collaborative analytics systems (MCASs) have unsatisfying performance for scenarios with dynamic databases. Naively running an MCAS on a dynamic database would lead to significant redundant costs and raise performance concerns, due to the substantial duplicate contents between the pre-updating and post-updating databases.

Abstract Deterministic encryption (DET) allows for fast retrieval of encrypted information, but it would cause significant leakage of frequency information of the underlying data, which results in an array of inference attacks. Simply replacing DET with fully randomized encryption is often undesirable in the scenario of an encrypted database since it incurs a large overhead in query and storage. Frequency Smoothing Encryption (FSE) is a practical encryption scheme to protect frequency information. Current FSE constructions still fall short of efficiency and a reasonable security definition. We revisit FSE and propose two security definitions from both theoretical and practical perspectives. Furthermore, we adopt a novel partitioning strategy to construct a new FSE scheme to improve performance. Experimental results show that compared with others, our scheme achieves excellent query performance while attaining security against inference attacks.

In private data publishing, a promising solution is generating synthetic data that enables any query on the private dataset while satisfying differential privacy. Over the past decade, researchers mainly focused on improving the query accuracy of synthetic data. However, the limitations of existing works restrict them from achieving a better trade-off between accuracy and privacy. In this paper, we propose ABSyn, a novel scheme for differentially private data synthesis. Under the Select-Measure-Generate paradigm, ABSyn has an adaptive mechanism for precisely selecting marginals and follows the batch processes. Our adaptive-batch scheme can provide a well-selected marginal set and the optimal allocation of privacy budget, which makes its synthetic data achieve high accuracy without compromising privacy. We implement an efficient prototype of ABSyn and compare it with existing works by analyzing public datasets. Experimental results show that ABSyn achieves query accuracy on synthetic datasets by a factor of$1.26\times $and efficiency by a factor of$18.60\times $over the state-of-the-art scheme on average.

Order-preserving encryption (OPE) is a cryptographic primitive that preserves the order of plaintexts. In the past few years, many OPE schemes were proposed to solve the problem of executing range queries in encrypted databases. However, OPE leaks some certain information (for example, the order of ciphertext), so it is vulnerable to many attacks. Subsequently, order-revealing encryption (ORE) was proposed by Bonehet al.(Eurocrypt 2015) as a generalization of order-preserving encryption. It breaks through the limitation of the numeric order of OPE plaintext. It implements ciphertext comparison for any specific form of plaintext through a publicly computable comparison function. In this article, we aim to design a new ORE scheme which reduces the leakages and preserves the practicality in terms of ciphertext length and encryption time. We first propose the hybrid model namedHybridORE. Then, we propose an improved scheme namedEncodeOREwhich achieves acceptable security and appropriate ciphertext length. They both explore the encode strategy of encoding plaintext into different parts and apply suitable ORE algorithms to each part according to its security characteristics to reduce leakages. Compared with the typical CLWW scheme (FSE 2016) and Lewi-Wu (CCS 2016) in large domain, they have fewer leakages. The experiment shows that the proposedEncodeOREis very practical.

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.

Searchable symmetric encryption (SSE) has been widely applied in the encrypted database for queries in practice. Although SSE is powerful and feature-rich, it is always plagued by information leaks. Some recent attacks point out that forward privacy which disallows leakage from update operations, now becomes a basic requirement for any newly designed SSE schemes. However, the subsequent search operations can still leak a significant amount of information. To further strengthen security, we extend the definition of forward privacy and propose the notion of “forward search privacy”. Intuitively, it requires search operations over newly added documents do not leak any information about past queries. The enhanced security notion poses new challenges to the design of SSE. We address the challenges by developing the hidden pointer technique (HPT) and propose a new SSE scheme called Khons, which satisfies our security notion (with the original forward privacy notion) and is also efficient. We implemented Khons and our experiment results on large dataset (wikipedia) show that it is more efficient than existing SSE schemes with forward privacy.