A Content Delivery Network (CDN) is a distributed system composed of a large number of nodes that allows users to request objects from nearby nodes. CDN not only reduces end-toend latency on the user side but also offloads Content Providers (CPs), providing resilience against Distributed Denial of Service (DDoS) attacks. However, by caching objects and processing user requests, CDN providers could infer user preferences and the popularity of objects, thus resulting in information leakage. Unfortunately, such information leakage may result in loss of user privacy and reveal business-specific information to untrusted or compromised CDN providers. State-of-the-art solutions can protect the content of sensitive objects but cannot prevent CDN providers from inferring user preferences and the popularity of objects.
1 November 2024 in Information Processing & Management
Searchable Encryption (SE) is a technique that allows Cloud Service Providers to search over encrypted datasets without learning the content of queries and records. In recent years, many SE schemes have been proposed to protect outsourced data. However, most of them leak sensitive information, from which attackers could still infer the content of queries and records by mounting leakage-based inference attacks, such as the count attack and file-injection attack . In this work, first we define the leakage in searchable encrypted databases and analyse how the leakage is leveraged in existing leakage-based attacks. Second, we propose a Privacy-preserving Multi-cloud based dynamic symmetric SE scheme for relational Database ( P-McDb ). P-McDb has minimal leakage, which not only ensures confidentiality of queries and records but also protects the search, intersection, and size patterns. Moreover, P-McDb ensures both forward and backward privacy of the database. Thus, P-McDb could resist existing leakage-based attacks, e.g., active file/record-injection attacks. We give security definition and analysis to show how P-McDb hides the aforementioned patterns. Finally, we implemented a prototype of P-McDb and tested it using the TPC-H benchmark dataset. Our evaluation results show that users can get the required records in 2.16 s when searching over 4.1 million records.
1 January 2025 in Proceedings on Privacy Enhancing Technologies
Recent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most DSSE schemes with forward and backward privacy schemes only support single keyword queries, which impedes its prevalence in practice. Although some forward and backward private DSSE schemes with expressive queries (e.g., conjunctive queries) have been introduced, their backward privacy either essentially corresponds to single keyword queries or forward privacy is not comprehensive. In addition, the deletion of many DSSE schemes is achieved by addition paired with a deletion mark (i.e., lazy deletion). To address these problems, we present two novel DSSE schemes with conjunctive queries (termed SDSSE-CQ and SDSSE-CQ-S), which achieve both forward and backward privacy. To analyze their security, we present two new levels of backward privacy (named Type-O and Type-O-, more and more secure), which give a more comprehensive understanding of the leakages of conjunctive queries in the OXT framework. Eventually, the security analysis and experimental evaluations show that the proposed schemes achieve better security with reasonable computation and communication increase.
A private decision tree evaluation (PDTE) protocol allows a feature vector owner (FO) to classify its data using a tree model from a model owner (MO) and only reveals an inference result to the FO. This paper proposes Mostree, a PDTE protocol secure in the presence of malicious parties with sublinear communication. We design Mostree in the three-party honest-majority setting, where an (untrusted) computing party (CP) assists the FO and MO in the secure computation. We propose two low-communication oblivious selection (OS) protocols by exploiting nice properties of three-party replicated secret sharing (RSS) and distributed point function. Mostree combines OS protocols with a tree encoding method and three-party secure computation to achieve sublinear communication. We observe that most of the protocol components already maintain privacy even in the presence of a malicious adversary, and what remains to achieve is correctness. To ensure correctness, we propose a set of lightweight consistency checks and seamlessly integrate them into Mostree. As a result, Mostree achieves sublinear communication and malicious security simultaneously. We implement Mostree and compare it with the state-of-the-art. Experimental results demonstrate that Mostree is efficient and comparable to semi-honest PDTE schemes with sublinear communication. For instance, when evaluated on the MNIST dataset in a LAN setting, Mostree achieves an evaluation using approximately 768 ms with communication of around 168 KB.
1 April 2023 in Proceedings on Privacy Enhancing Technologies
Dynamic searchable symmetric encryption (DSSE) enables the data owner to outsource its database (document sets) to an untrusted server and make searches and updates securely and efficiently. Conjunctive DSSE can process conjunctive queries that return the documents containing multiple keywords. However, a conjunctive search could leak the keyword pair result pattern (KPRP), where attackers can learn which documents contain any two keywords involved in the query. File-injection attack shows that KPRP can be utilized to recover searched keywords. To protect data effectively, DSSE should also achieve forward privacy, i.e., hides the link between updates to previous searches, and backward privacy, i.e., prevents deleted entries being accessed by subsequent searches. Otherwise, the attacker could recover updated/searched keywords and records. However, no conjunctive DSSE scheme in the literature can hide KPRP in sub-linear search efficiency while guaranteeing forward and backward privacy. In this work, we propose the first sub-linear KPRP-hiding conjunctive DSSE scheme (named HDXT) with both forward and backward privacy guarantees. To achieve these three security properties, we introduce a new cryptographic primitive: Attribute-updatable Hidden Map Encryption (AUHME). AUHME enables HDXT to efficiently and securely perform conjunctive queries and update the database in an oblivious way. In comparison with previous work that has weaker security guarantees, HDXT shows comparable, and in some cases, even better performance.