With the widespread adoption of cloud storage, time-series databases have become indispensable for managing and analyzing sequential data generated on the user side over time (i.e., time-series data), thereby alleviating the computational and storage burden on resource-constrained users. However, critical security and privacy challenges-such as query privacy leakage, data exposure, and threats to storage integrity-remain inadequately addressed by existing solutions. To this end, we propose VMPQ, an efficient protocol for privacy-preserving and verifiable multi-predicate queries over time-series databases. Specifically, we introduce a new cryptographic primitive, verifiable offline/online private information retrieval (V-OO-PIR), which supports sublinear retrieval complexity while simultaneously ensuring both query privacy and result verifiability against untrusted servers. Building on V-OO-PIR, we design a dual-layer security framework that integrates replicated secret sharing (RSS) and secure multiparty computation (MPC): (1) RSS splits time-series data into two shares stored across two non-colluding servers, ensuring data confidentiality and mitigating exposure risks, and (2) MPC performs secure multiplication directly on these shares, enabling efficient evaluation of multi-predicate queries without reconstructing the original data. As a result, VMPQ ensures query privacy by preventing servers from inferring user interests across multiple predicates, while simultaneously guaranteeing data confidentiality and the verifiability of query results. Theoretical analysis confirms the security of VMPQ against malicious adversaries. Experimental results demonstrate that VMPQ reduces query latency by up to 5× compared to the state-of-the-art solution Waldo, while also enhancing throughput and preserving high storage efficiency through optimized database encoding.

Paging and exit overheads have been proven to be the performance bottlenecks when adopting Searchable Symmetric Encryption (SSE) with trusted hardware such as Intel SGX for keyword search. This problem becomes more serious when incorporating ORAM and SGX to design oblivious SSE schemes such as POSUP [1] and Oblidb [2] which can defend against inference attacks. The main reason comes from high round communication complexity of ORAM and constrained trusted memory created by SGX. To overcome this performance bottleneck, we propose a set of novel SSE constructions with realistic security/performance trade-offs. Our core idea is to encode the keyword-identifier pairs into a bloom filter to reduce the number of ORAM operations during the search procedure. Specifically, Construction 1 loads the bloom filter into the enclave sequentially, which outperforms about$1.7\times$when the dataset is large compared with the performance of the baseline that directly combines ORAM and SGX. To further improve the performance of Construction 1, Construction 2 classifies keywords into groups and stores these groups in different bloom filters. By additionally leaking the keywords in search token belonging to which groups, Construction 2 outperforms Construction 1 by$16.5\sim 36.8\times$and provides an improvement of at least one order over state-of-the-art oblivious protocols.

Volume-hiding encrypted multi-map (EMM) allows the client to efficiently search on encrypted data while concealing the real volume of values for the queried key, thereby mitigating privacy-compromising attacks that depend on volume knowledge. However, most of the volume-hiding EMMs focus on single keyword queries, leaving the design of a volume-hiding conjunctive-keyword EMM a significant challenge. In this paper, we first propose a performance-optimized volume-hiding single-keyword EMM by adopting binary fuse filter,$\mathsf {BF^{2}MM}$, which serves as the crucial component for volume-hiding conjunctive-keyword EMM. We then introduce a generic construction dubbed$\mathsf {vCMM}$for volume-hiding conjunctive query, relying on a novel index structure from merely symmetric-key cryptographic tools. We further instantiate it to a practical volume-hiding conjunctive-keyword EMM,$\mathsf {BF^{2}CMM}$, which features nearly optimal query communication complexity and storage overhead. In addition, we extend our proposals to non-interactive DP-variants$\mathsf {DP\textrm {-}BF^{2}MM}$and$\mathsf {DP\textrm {-}BF^{2}CMM}$to provide tunable trade-offs between performance and privacy. Finally, we provide a thorough comparison with the existing volume-hiding conjunctive-keyword EMM$\mathsf {OXTMM}$. Experimental results show a significant performance improvement of$\mathsf {BF^{2}CMM}$, with over a$2\times$storage saving, a$90\times$increase in setup efficiency, and roughly$180\times$speedup in search latency compared to$\mathsf {OXTMM}$, respectively.

Symmetric Searchable Encryption (SSE) enables querying over encrypted data stored on servers, protecting the privacy of both client queries and the data. However, the response results of the query can leak certain statistical information, allowing an active attacker to inject files and exploit these leakages to recover the queried keyword. Recently, Zhang et al. (USENIX Security 2023) proposed a volumetric injection attack, called BVMA, based on response volume patterns. This attack requires larger file injections and has a moderate recovery rate. In this work, we propose a powerful volumetric injection attack,$\mathsf {Violin}$, that utilizes response length and size patterns, achieving a higher recovery rate and smaller injection size. Specifically,$\mathsf {Violin}$requires$\mathcal {O}(\log n)$injection files with a total size of$\mathcal {O}(n\log n)$, where$n$is the number of keywords. Furthermore, we propose a file injection method with optimal injection amount (i.e., injected files number and size) based on Pascal’s triangle rule under threshold countermeasure. We implement$\mathsf {Violin}$and compare it with the existing injection attacks. Experimental results indicate that$\mathsf {Violin}$achieves a recovery rate approaching 100%, surpassing the state-of-the-art BVMA while requiring smaller file sizes. Under threshold countermeasure,$\mathsf {Violin}$achieves a saving of 22% in injection file size and a remarkable 95% decrease in injected file number compared to BVMA.

Secure join schemes, an important class of queries over encrypted databases, have attracted increasing attention. While efficient querying is paramount, data owners also emphasize the significance of privacy preservation. The state-of-the-art JXT (Jutla and Patranabis ASIACRYPT 2022) enables efficient join queries over encrypted tables with a symmetric-key solution. However, we observe that JXT inadvertently leaks undesirable query results as the number of queries increases. In this paper, we propose a novel equi-join scheme, One-Time Join Cross-Tags (OTJXT), which can avoid additional result leakage in multiple queries and extend to equi-join as opposed to natural join in JXT. Specifically, we design a new data encoding method using nonlinear transformations that reveals only the union of results for each query without extra leakage observed in JXT. Moreover, OTJXT addresses the linear search complexity issue (Shafieinejad et al. ICDE 2022) while preventing multiple query leakage. Finally, we implement OTJXT and compare its performance with JXT and Shafieinejad et al.'s scheme on the TPC-H dataset. The results show that OTJXT outperforms in search and storage efficiency, achieving a$\mathbf {98.5\times }$(resp.,$\mathbf {10^{6}\times }$) speedup in search latency and reducing storage cost by 62.5% (resp., 78.5%), compared to JXT (resp., Shafieinejad et al.'s scheme). Using OTJXT, a TPC-H query on a 40 MB database only takes 21 ms.

Secure join queries over encrypted databases, the most expressive class of SQL queries, have attracted extensive attention recently. The state-of-the-art JXT (Jutla et al. ASIACRYPT 2022) enables join queries on encrypted relational databases without pre-computing all possible joins. However, JXT can merely support join queries over two tables (in encrypted databases) with some high-entropy join attributes. In this paper, we propose an equi-join query protocol over two tables dubbed JXT+, that allows the join attributes with arbitrary names instead of JXT requiring the identical name for join attributes. JXT+ reduces the query complexity from O(\ell_1 \cdot \ell_2) to O(\ell_1) as compared to JXT, where \ell_1 and \ell_2 denote the numbers of matching records in two tables respectively. Furthermore, we present JXT++, the first equi-join queries across three or more tables over encrypted databases without pre-computation. Specifically, JXT++ supports joins of arbitrary attributes, i.e., all attributes (even low-entropy) can be candidates for join, while JXT requires high-entropy join attributes. In addition, JXT++ can alleviate sub-query leakage on three or more tables, which hides the leakage from the matching records of two-table join. Finally, we implement and compare our proposed schemes with the state-of-the-art JXT. The experimental results demonstrate that both of our schemes are superior to JXT in search and storage costs. In particular, JXT+ (resp., JXT++) brings a saving of 49% (resp., 68%) in server storage cost and achieves a speedup of 51.7× (resp., 54.3×) in search latency.

Encrypted conjunctive search enables server to perform efficient conjunctive query over encrypted data while guaranteeing data and query privacy. The well-known Oblivious Cross-Tags (OXT) protocol (by Cash et al. in CRYPTO 2013) is the first to realize efficient conjunctive search with some well-defined leakage, such as the keyword pair result pattern (KPRP) leakage and the cross-query intersection result pattern (IP) leakage. To mitigate the potential threats brought by the leakage, much effort has been made to reduce the information leaked by OXT. However, it is still open to achieve encrypted conjunctive search without revealing both KPRP and IP, while preserving high-efficiency.

Order-revealing encryption (ORE) enables the untrusted server to perform greater-than-comparison over ciphertext without compromising data privacy, which allows anyone to evaluate the lexicographic ordering of two arbitrary ciphertexts with a public comparison algorithm. However, most ORE constructions merely support ciphertext comparison for single-user. Recently, a variant of ORE named delegatable ORE has been introduced, which achieves cross-user ciphertext comparison by employing token mutual authorization technique at the cost of weak security, i.e., reveals the most significant differing bit of underlying plaintexts. To tackle this problem, we first present a deterministic property-preserving hash called DPPH with short-size hash value, and then propose a novel multi-client ORE scheme (m-ORE) from DPPH that supports ciphertext comparison among multiple users while hiding the most significant differing bits. Furthermore, we present an enhanced construction dubbed m-H-ORE by introducing a two-phase comparison method, which can achieve supper-efficient comparison in some cases, i.e., two ciphertexts with different bit-length. Finally, we provide formal security proofs of the proposed schemes and run extensive experiments to evaluate their performance on real-world and synthetic datasets. The results demonstrate that both of the proposed schemes can achieve a speedup of 47× and 138× in comparison cost to that of parameter-hiding ORE, respectively.

Data deduplication is of vital importance for mobile cloud computing to cope with the explosive growth of outsourced mobile data. In order to ensure the privacy of sensitive mobile data against an untrusted cloud, Message-Locked Encryption (MLE) has been proposed to enable deduplication over ciphertext. However, MLE prohibits data access control since it uses deterministic content-derived encryption keys. Recently, a lightweight rekeying-aware encrypted deduplication system (REED) has been proposed to achieve dynamic access control for secure data deduplication. However, REED is vulnerable to key-retaining attack and stub-retaining attack, which leads to insecure access revocation, and thus cannot support secure dynamic access control. In response, we present AC-Dedup, an encrypted deduplication storage system that supportssecure dynamic access controlfor mobile cloud storage. At the core of AC-Dedup are two novel encryption techniques namedmixed message locked encryptionandrandom stub re-encryptionto resist the two types of attacks, respectively. To the best of our knowledge, AC-Dedup is the first practical system that achieves secure data deduplication and secure dynamic access control simultaneously. We conduct security analysis and experimental evaluation on mobile device and cloud platform with real-world IoT datasets. The results show that AC-Dedup enables secure and efficient dynamic access control while preserving deduplication effectiveness.

Blockchain databases have been exploited in many applications to construct trust and share data among multiple participants. However, maintaining the entire blockchain locally will cause heavy communication and storage overhead for users with limited resources. Alternatively, the user could act as a light node that stores block headers only and delegates queries to full nodes that maintain the entire blockchain. However, introducing a light node raises several concerns about query integrity and privacy. In this paper, we propose EPPVChain, the first scheme that simultaneously achieves efficient, privacy-preserving and verifiable conjunctive query for blockchain databases. EPPVChain resorts to a novel symmetric cryptographic primitive named Symmetric Hidden Vector Encryption (SHVE), and deploys several new techniques to achieve the desired goals. In specific, we design a new SHVE-based authenticated data structure to support privacy-preserving verifiable conjunctive queries. We further propose two improved schemes to aggregate data records to optimize query performance. Finally, we propose a dual-chain key escrow protocol to securely escrow the symmetric key of SHVE without relying on any trusted third party. The security analysis and evaluation confirm EPPVChain’s ability to achieve query privacy and integrity with high efficiency.

Verifiable data streaming (VDS) protocols enable end users with limited storage space to continuously stream data items to an untrusted cloud server, while preserving the capacity of verifying the integrity of those retrieved data items for downstream tasks. Although there has been plenty of research around the construction of VDS, we observe that they all focus on the scenario of single-user. When deploying these VDS protocols into more common applications that involve multiple users’ data (e.g., network data monitoring and stock trends analysis), the size of the proof used to prove the integrity of retrieved data items grows linearly with the number of involved users. This would bring tremendous communication overhead, especially for lightweight users. To this end, we initiate the study of VDS protocols that are suitable for multi-user (or cross-user) setting. Specifically, we first introduce a new primitive called aggregatable chameleon vector commitment (ACVC) that allows to aggregate multiple proofs from different commitments into a single proof. Then, based on ACVC, we present a communication-efficient VDS protocol for the multi-user setting. That is, when querying data items from multiple users, the size of corresponding proof is constant and independent of the number of involved users. Theoretical analysis indicates that the proposed VDS protocol outperforms previous VDS protocols in terms of communication overhead. We also implement the proposed ACVC, and conduct extensive experiments to demonstrate its practicability.

Encryption and compression are two critical techniques to ensure data confidentiality and efficiency for a cloud-based data storage system, respectively. However, directly combing encryption and compression incurs substantial performance degradation. We propose TinyEnc, an encrypted data storage system for cloud-based key-value store, which supports encryption and compression simultaneously with rich query support. To reconcile encryption and compression without compromising performance, we first propose a new encrypted compression data structure to enable fine-grained access to compressed and encrypted key-value data. We then propose two new transforming mechanisms, namely orthogonal data dividing and hierarchical data padding, to transform a plaintext key-value table into the encrypted compression data structure in a privacy-preserving way. Finally, we craft order-revealing encryption (ORE) and symmetric searchable encryption (SSE) to design a new encrypted search index over the encrypted compression data structure to support rich types of data queries. We implement a prototype of TinyEnc on top of Cassandra. Besides, the evaluation result shows that TinyEnc increases the throughput by up to 7 times and compression ratio by up to 1.3 times with respect to previous works.

The wide use of internet-connected services makes massive personal data collected by service providers without the need of our consent. Although the archived data may enable them to provide better service experiences for users, it also presents serious risks to individual privacy, especially when active or unexpected data breaches have become commonplace. To mitigate this issue, several acts and regulations (e.g., the European Union general data protection regulation) have been issued and specified a lot of security requirements for personal data management. Among these various requirements, we mainly focus on the requirement of giving back the access control of personal data to data owners themselves and the right to be forgotten for data erasure. In this article, we provide a cryptographic solution of achieving these two requirements in the setting of outsourced storage. Specifically, we introduce a personal data management framework built upon a novel cryptographic primitive dubbed as forward-secure attribute-based puncturable encryption (FS-DABPE). This primitive simultaneously features of system-wide forward secrecy and practical key management as well as fine-grained access control of the encrypted personal data. Consequently, by locally puncturing, updating and erasing system-wide secret keys, it securely realizes fine-grained personal data sharing and data erasure without interactions. Furthermore, to instantiate the proposed framework, we present a concrete FS-DABPE construction, and prove its security under a well-studied complexity assumption. In addition, we provide a prototype implementation of the concrete construction, and present extensive experimental results that illustrate its feasibility and practicability.

Encrypted multi-map (EMM), as a special case of structured encryption, has attracted extensive attention recently. However, most of EMM constructions reveal the real volumes of queried keys, which can be leveraged to launch leakage-abuse attacks, as demonstrated by Kellaris et al. in CCS 2016 and Kornaropoulos et al. in S&P 2021.

With the widespread use of cloud emails and frequent reports on large-scale email leakage events, a security property so-called forward secrecy becomes desirable and indispensable for both individuals and cloud email service providers to strengthen the security of cloud email systems. Specifically, forward secrecy can guarantee the confidentiality of those previously encrypted emails even if the user’s secret key gets exposed. However, due to the failure to meet the security and practicality requirements of email systems simultaneously, typical methods of achieving forward secrecy, such as Diffie-Hellman key exchange and forward-secure public-key encryption, have not been widely approved and adopted. In this article, to capture forward secrecy of encrypted cloud email systems without sacrificing the practicability, we introduce a new cryptographic primitive named forward-secure puncturable identity-based encryption (fs-PIBE), which enables an email user to perform fine-grained revocation of decryption capacity. In more detail, the user is allowed to preserve the decryption capacity of unreceived encrypted emails, while abolishing that of those received ones. Thus, it provides more practical forward secrecy than typical manners, in which the decryption capacity of received and unreceived encrypted emails is revoked simultaneously. Based on such a primitive, we build a framework of encrypted cloud email systems, and instantiate it with a concrete fs-PIBE construction that has constant size of ciphertext and provable security in the standard model. Furthermore, to improve the security and efficiency of the presented framework, we extend the proposed fs-PIBE scheme to support end-to-end encryption and outsourced decryption, respectively. In addition, as a proof-of-concept of the proposed fs-PIBE scheme, we implement it and produce various experiments to demonstrate its practicability and correctness.

Deploying data storage and query service in an untrusted cloud server raises critical privacy and security concerns. This paper focuses on the fundamental problem of processing conjunctive keyword queries over an untrusted cloud in a privacy-preserving manner. Previous tree-based searchable symmetric encryption (SSE) schemes, such asIBTreeandVBTree, can process conjunctive keyword queries in a secure and efficient way. However, these schemes cannot address “Result Pattern (RP)” leakage, which can be used to recover the keywords contained in a conjunctive keyword query. To combat this challenging problem, we propose a result pattern hiding conjunctive query scheme namedRphxusing Intel SGX. In particular, we first propose a new “SGX-aware” compressed index namedVIBTby combining variable-length bloom filter tree, matryoshka filter and online cipher. To achieveRPhiding, we then introduce a new tree-based SSE scheme namedRphxby deployingVIBTto Intel SGX. Security analysis shows thatRphxcan enhance the security requirements by hidingRPleakage under the IND-CKA2 security model. Experimental results show thatVIBTgains at least$30\times $improvement in storage efficiency andRphxcan achieve comparable search efficiency comparing with previous works.

Searchable Encryption (SE) enables a data owner to outsource encrypted data to an untrusted server while preserving the keyword search functionality. Typically, the server learns whether or not a query has been performed more than once, which is usually called the search pattern. However, such kind of information leakage might be leveraged to break query privacy. To further reduce such type of leakage and provide strong privacy guarantee, Wanget al.proposed a novel SE scheme based on the Paillier encryption scheme in INFOCOM’15. Unfortunately, their scheme cannot perform keyword search successfully, because the additive homomorphic property is not sufficient for their construction. In this article, we first show that why their scheme fails to return the correct search result, and then propose a new SE scheme by adopting a special additive homomorphic encryption scheme to achieve the multiplicative homomorphic property efficiently. Furthermore, we enhance the security on the user side. Specifically, we use random polynomials with an appropriate degree to guarantee that the user cannot learn anything other than the desired search result. Finally, we present a formal security analysis and implement our scheme on a real-world database, which demonstrates that our construction can achieve the desired security properties with good performance.

Data deduplication technique has been widely adopted by commercial cloud storage providers, which is both important and necessary in coping with the explosive growth of data. To further protect the security of users’ sensitive data in the outsourced storage mode, many secure data deduplication schemes have been designed and applied in various scenarios. Among these schemes, secure and efficient re-encryption for encrypted data deduplication attracted the attention of many scholars, and many solutions have been designed to support dynamic ownership management. In this paper, we focus on the re-encryption deduplication storage system and show that the recently designed lightweight rekeying-aware encrypted deduplication scheme (REED) is vulnerable to an attack which we call it stub-reserved attack. Furthermore, we propose a secure data deduplication scheme with efficient re-encryption based on the convergent all-or-nothing transform (CAONT) and randomly sampled bits from the Bloom filter. Due to the intrinsic property of one-way hash function, our scheme can resist the stub-reserved attack and guarantee the data privacy of data owners’ sensitive data. Moreover, instead of re-encrypting the entire package, data owners are only required to re-encrypt a small part of it through the CAONT, thereby effectively reducing the computation overhead of the system. Finally, security analysis and experimental results show that our scheme is secure and efficient in re-encryption.

With the advent of artificial intelligence, machine learning has been well explored and extensively applied into numerous fields, such as pattern recognition, image processing and cloud computing. Very recently, machine learning hosted in a cloud service has gained more attentions due to the benefits from the outsourcing paradigm. Based on cloud-aided computation techniques, the heavy computation tasks involved in machine learning process can be off-loaded into the cloud server in a pay-per-use manner, whereas outsourcing large-scale collection of sensitive data risks privacy leakage since the cloud server is semi-honest. Therefore, privacy preservation for the client and verification for the returned results become two challenges to be dealt with. In this paper, we focus on designing a novel privacy-preserving single-layer perceptron training scheme which supports batch patterns training and verification for the training results on the client side. In addition, adopting classical secure two-party computation method, we design a novel lightweight privacy-preserving predictive algorithm. Both two participants learns nothing about other’s inputs, and the calculation result is only known by one party. Detailed security analysis shows that the proposed scheme can achieve the desired security properties. We also demonstrate the efficiency of our scheme by providing the experimental evaluation on two different real datasets.

With the growing popularity of cloud computing, more and more enterprises and individuals tend to store their sensitive data on the cloud in order to reduce the cost of data management. However, new security and privacy challenges arise when the data stored in the cloud due to the loss of data control by the data owner. This paper focuses on the techniques of verifiable data storage and secure data deduplication. We firstly summarize and classify the state-of-the-art research on cloud data storage mechanism. Then, we present some potential research directions for secure data outsourcing.

The notion of database outsourcing enables the data owner to delegate the database management to a cloud service provider (CSP) that provides various database services to different users. Recently, plenty of research work has been done on the primitive of outsourced database. However, it seems that no existing solutions can perfectly support the properties of both correctness and completeness for the query results, especially in the case when the dishonest CSP intentionally returns an empty set for the query request of the user. In this paper, we propose a new verifiable auditing scheme for outsourced database, which can simultaneously achieve the correctness and completeness of search results even if the dishonest CSP purposely returns an empty set. Furthermore, we can prove that our construction can achieve the desired security properties even in the encrypted outsourced database. Besides, the proposed scheme can be extended to support the dynamic database setting by incorporating the notion of verifiable database with updates.