Multi-party computation (MPC) has gained increasing attention in both research and industry, with many protocols adopting the preprocessing model to optimize online performance through the strategic use of offline-generated, data-independent correlated randomness (or correlation). However, while extensive research has been dedicated to enhancing the online phase, the equally critical offline phase remains largely overlooked. This gap imposes significant yet unaddressed challenges in both security and efficiency, hindering the practical adoption of MPC systems. To address these challenges, we build upon the pseudorandom correlation generator (PCG) concept by Boyle et al. (CRYPTO’19, FOCS’20) and propose HPCG, a programmable, verifiable, and concretely efficient PCG construction using small security hardware. Our core technique, termed verifiable silent preprocessing, enables virtually unbounded, on-demand generation of diverse correlated randomness with provable correctness while effectively reducing offline overhead in a correlation-agnostic manner. To demonstrate the benefits of our approach, we experimentally evaluate HPCG and compare it with other preprocessing techniques. We also show how HPCG can further optimize specialized secure computation tasks (e.g., shuffling and equality test) by promoting new, customized correlations, which may be of new interest.

We instigate the study of adversarial congestion in the context of the Domain Name System (DNS). By strategically choking inter-server channels, this new type of DoS attack can disrupt a large user group's access to target DNS servers at a low cost. In reminiscence of classic network congestion control, we propose a DNS congestion control (DCC) framework as a fundamental yet practical mitigation measure for such attacks. With an optimized fair-queuing message scheduler, DCC ensures benign clients fair access to inter-server channels regardless of an attacker's behavior; with a set of extensible anomaly detection and signaling mechanisms, it minimizes collateral damage to innocuous clients. We architect DCC in a non-invasive style so that it can readily augment existing DNS servers. Our prototype evaluation demonstrates that DCC effectively mitigates adversarial congestion while incurring minor performance overheads.

Encrypted databases have garnered considerable attention for their ability to safeguard sensitive data outsourced to third parties. However, recent studies have revealed the vulnerability of encrypted databases to leakage-abuse attacks on their search module, prompting the development of countermeasures to address this issue. While most studies have focused on static databases, limited research has been conducted on dynamic encrypted databases. To bridge this gap, this paper focuses on undertaking a comprehensive examination of leakage exploitation in dynamic encrypted databases, with the aim of providing effective mitigations. Our investigation begins with two attacks that can be employed to recover encrypted queries. The first attack, known as an active attack, involves injecting encoded files and utilizing correlated file volume information. The second attack, referred to as a passive attack, identifies unique relational characteristics of queries across database updates, assuming certain background knowledge of the plaintext databases. To mitigate these attacks, a two-layer encrypted database hardening approach is proposed, which obfuscates both search indexes and files in a continuous way. Doing so allows us to eliminate the unique characteristics emerging after data updates constantly. We conduct a series of experiments to confirm the severity of our attacks and the effectiveness of our countermeasures.

Despite the central importance of DNS, numerous attacks and vulnerabilities are regularly discovered. The root of the problem is the ambiguity and tremendous complexity of DNS protocol specifications, amid a rapidly evolving Internet infrastructure. To counteract the vicious break-and-fix cycle for improving DNS infrastructure, we instigate a foundational approach: we construct the first formal semantics of end-to-end name resolution, a collection of components for the formal analyses of both qualitative and quantitative properties, and an automated tool for discovering DoS attacks. Our formal framework represents an important step towards a substantially more secure and reliable DNS infrastructure.

To keep web users away from unsafe websites, modern web browsers enable the embedded feature of safe browsing (SB) by default. In this work, through theoretical analysis and empirical evidence, we reveal two major shortcomings in the current SB infrastructure. First, we derive a feasible tracking technique for industry best practice. We show that the current mitigation techniques cannot eliminate the threat of de-anonymization permanently. Second, we gauge the effectiveness of blacklists provided by major vendors. Our discovery indicates the urge for blacklist integration in order to boost service quality. In light of this, we propose a new three-party paradigm${{\sf PEBA}}$with an intermediate third party decoupling the direct interaction of users and proprietary blacklist vendors. To satisfy practical usage requirements, we instantiate our design with trusted hardware, detailing how it can be leveraged to fulfill the requirements of privacy enhancement and broader content coverage at the same time. We also tackle numerous implementation challenges that emerged from this proxy-based and hardware-enabled solution. Extensive evaluation confirms that${{\sf PEBA}}$can balance well among desirable goals of security, usability, performance, and elasticity, making it suitable for deployment in practice.

Decentralized storage (DS) projects such as Filecoin are gaining traction. Their openness mandates effective auditing mechanisms to assure users that their data remains intact. A blockchain is typically employed here as an unbiased public auditor. While the case for static data is relatively easy to handle, on-chain auditing of dynamic data with practical performance guarantees is still an open problem. Dynamic Proof-of-Storage (PoS) schemes developed for conventional cloud storage are not applicable to DS, since they require large storage proofs and/or large auditor states that are unmanageable by a resource-constrained blockchain. To fill the gap, we propose a family of dynamic on-chain auditing protocols that can produce concretely small auditor states while retaining the compact proofs promised by static PoS schemes. Our design revolves around a set of succinct data structures and optimization techniques for index information management. With proper instantiation and realistic parameters, our protocols can achieve 0.25MB on-chain state and 1.2KB storage proof for the auditing of 1TB data, outperforming previous dynamic PoS schemes that are adaptable for DS by orders of magnitude. As another practical contribution, we introduce a data abstraction layer that allows one to deploy the auditing protocols on arbitrary storage systems hosting dynamic data.

Outsourcing decision tree inference services to the cloud is highly beneficial, yet raises critical privacy concerns on the proprietary decision tree of the model provider and the private input data of the client. In this paper, we design, implement, and evaluate a new system that allows highly efficient outsourcing of decision tree inference. Our system significantly improves upon prior art in the overall online end-to-end secure inference service latency at the cloud as well as the local-side performance of the model provider. We first present a new scheme which securely shifts most of the processing of the model provider to the cloud, resulting in a substantial reduction on the model provider's performance complexities. We further devise a scheme which substantially optimizes the performance for secure decision tree inference at the cloud, particularly the communication round complexities. The synergy of these techniques allows our new system to achieve up to$8 \times$better overall online end-to-end secure inference latency at the cloud side over realistic WAN environment, as well as bring the model provider up to$19 \times$savings in communication and$18 \times$savings in computation.

As a promising alternative solution to cloud storage, decentralized storage networks (DSN) are widely anticipated to develop continuously and reshape the storage market share in the foreseeable future. In particular, one of the most important research problems is how to enforce the quality of service (QoS) in the context of storage solutions. Despite plenty of auditing-related works in the context of cloud storage, none of them can be directly applied to the decentralized storage paradigm. The challenges of designing a feasible storage auditing framework emanate from two aspects: 1) security problems unique to the decentralized settings and 2) performance overhead due to on-chain operations. In this article, we first put forward a basic storage auditing framework that satisfies the security and efficiency requirements, and outperforms the existing approaches. We also identify a critical and overlooked security problem that would compromise the integrity of storage auditing solutions in the blockchain paradigm. With our refined storage auditing design based on customized zero knowledge protocols, we propose a convenient mitigation solution in our revised security model. The evaluation results confirm that our solution would only incur a 10–15 percent increase in the overall auditing costs for common usage scenarios, compared to the basic design.

Outsourcing machine learning inference services to the cloud is getting increasingly popular. However, this also entails privacy risks to the provider's proprietary model and the client's sensitive data. Focusing on inference with decision trees, this article proposes a framework for securely and efficiently outsourcing decision tree inference. Targeting both privacy and efficiency, we propose a customized protocol using only lightweight cryptography in the online execution of secure inference. We resort to additive secret sharing and tackle the problems in various components including secure input feature selection, decision node evaluation, and inference result generation. Our protocol requires no interaction from the provider and client during online secure inference, a distinct advantage over prior works for practical deployment as they all operate under the client-provider setting where synchronous and continuous interaction is required. Performance evaluation demonstrates our security design's efficiency, as well as substantial performance benefits for the client (up to four orders of magnitude in computation and 163 times in communication), as opposed to prior art in the non-outsourcing setting. To facilitate the practical usage for meeting more service demands, we also investigate the extensions for secure outsourced inference of random forests and categorical feature-based decision trees.

Large volumes of images are being exponentially generated today, which poses high demands on the services of storage, processing, and management. To handle the explosive image growth, a natural choice nowadays is cloud computing. However, coming with the cloud-based image services is acute data privacy concerns, which has to be well addressed. In this paper, we present a secure cloud-based image service framework, which allows privacy-preserving and effective image denoising on the cloud side to produce high-quality image content, a key for assuring the quality of various image-centric applications. We resort to state-of-the-art image denoising techniques based on deep neural networks (DNNs), and show how to uniquely bridge cryptographic techniques (like lightweight secret sharing and garbled circuits) and image denoising in depth to support privacy-preserving DNN based image denoising services on the cloud. By design, the image content and the DNN model are all kept private along the whole cloud-based service flow. Our extensive empirical evaluation shows that our security design is able to achieve denoising quality comparable to that in plaintext, with high cost efficiency on the local side and practically affordable cost on the cloud side.

Searchable symmetric encryption (SSE) enables users to make confidential queries over always encrypted data while confining information disclosure to pre-defined leakage profiles. Despite the well-understood performance and potentially broad applications of SSE, recent leakage-abuse attacks (LAAs) are questioning its real-world security implications. They show that a passive adversary with certain prior information of a database can recover queries by exploiting the legitimately admitted leakage. While several countermeasures have been proposed, they are insufficient for either security, i.e., handling only specific leakage like query volume, or efficiency, i.e., incurring large storage and bandwidth overhead. We aim to fill this gap by advancing the understanding of LAAs from a fundamental algebraic perspective. Our investigation starts by revealing that the index matrices of a plaintext database and its encrypted image can be linked by linear transformation. The invariant characteristics preserved under the transformation encompass and surpass the information exploited by previous LAAs. They allow one to unambiguously link encrypted queries with corresponding keywords, even with only partial knowledge of the database. Accordingly, we devise a new powerful attack and conduct a series of experiments to show its effectiveness. In response, we propose a new security notion to thwart LAAs in general, inspired by the principle of local differential privacy (LDP). Under the notion, we further develop a practical countermeasure with tunable privacy and efficiency guarantee. Experiment results on representative real-world datasets show that our countermeasure can reduce the query recovery rate of LAAs, including our own.

How to audit outsourced data in centralized storage like cloud is well-studied, but it is largely under-explored for the rising decentralized storage network (DSN) that bodes well for a billion-dollar market. To realize DSN as a usable service in a fully decentralized manner, the blockchain comes in handy - to record and verify audit trails in forms of proof of storage, and based on that, to enforce fair payments with necessary dispute resolution. Leaving the audit trails on the blockchain offers transparency and fairness, yet it 1) sacrifices privacy, as they may leak information about the data under audit, and 2) overwhelms onchain resources, as they may be practically large in size and expensive to verify. Prior auditing designs in centralized settings are not directly applicable here. A handful of proposals targeting DSN cannot satisfactorily address these issues either. We present an auditing solution that addresses on-chain privacy and efficiency, from a synergy of homomorphic linear authenticators with polynomial commitments for succinct proofs, and the sigma protocol for provable privacy. The solution results in, per audit, 288-byte proof written to the blockchain, and constant verification cost. It can sustain long-term operation and easily scale to thousands of users on Ethereum.

Truth discovery in mobile crowdsensing has recently received wide attention. It refers to the procedure for estimating the unknown user reliability from collected sensory data and inferring truthful information via reliability-aware data aggregation. Though widely studied in the plaintext domain, truth discovery remains largely under-explored in privacy-aware mobile crowdsensing. Existing works either do not consider user reliability issue or fall short of achieving practical cost efficiency, due to iterative transmission and computation over large ciphertexts from homomorphic cryptosystem. In this paper, we propose two new privacy-aware crowdsensing designs with truth discovery that significantly improve the bandwidth and computation performance on individual users. Our insight is to identify the core atomic operation in the iterative truth discovery procedure, and carefully craft security designs accordingly to enable efficient truth discovery in the ciphertext domain. Our first design is highly customized for the single-server setting, while our second design under the two-server model further shifts most of user workloads to the cloud server side. Both our designs protect individual sensory data and reliability degrees throughout the truth discovery procedure. Experiments show that compared with the prior result, our designs gain at least 30x and 10x savings on user communication and computation, respectively.

Running off-site software middleboxes at third-party service providers has been a popular practice. However, routing large volumes of raw traffic, which may carry sensitive information, to a remote site for processing raises severe security concerns. Prior solutions often abstract away important factors pertinent to real-world deployment. In particular, they overlook the significance of metadata protection and stateful processing. Unprotected traffic metadata like low-level headers, size and count, can be exploited to learn supposedly encrypted application contents. Meanwhile, tracking the states of 100,000s of flows concurrently is often indispensable in production-level middleboxes deployed at real networks.

The emerging hardware-assisted security technologies facilitate the deployment of secure and trustworthy applications in today's cloud computing infrastructure. Despite promising, the advantages appear to diminish due to limited resources of trusted execution environments and ever-increasing workload to be processed inside. Different from existing task-specific and system-level optimizations, our key observation is that those redundant computations occur commonly among several applications when handling the same input data. In light of this, we propose SPEED, a secure and generic computation deduplication system in the context of Intel SGX. It allows SGX-enabled applications to identify redundant computations and reuse computation results, while protecting the confidentiality and integrity of code, inputs, and results. To maximize the benefit of computation deduplication, we design a cross-application deduplication scheme, empowering multiple applications to securely utilize the shared results as long as they perform identical computations. To ease the use of SPEED, we implement a fully functional prototype and provide a concise and expressive API for developers to deduplicate rich computations with minimal effort, as few as 2 lines of code per function call. Extensive evaluations of four popular applications demonstrate that SPEED improves performance by up to 400 times. The source code is available on GitHub for public use.

In-the-cloud middleboxes have drawn widespread attentions recently, along with the rapid advancement of network function virtualization (NFV). Despite the well known benefits like reduced hardware and maintenance cost, deploying middleboxes in the remote environment poses new performance and security concerns, due to invisibility of the untrusted cloud and susceptible software implementations. One essential requirement for enterprise customers is to monitor performance compliance, while ensuring that packets are faithfully processed by remote middleboxes. In this paper, we propose a practical scheme towards verifiable performance measurement over in-the-cloud middleboxes. It employs “sample and replay” to achieve performance measurement and packet processing attestation. It estimates performance by collecting receipts in a tunable way, while coping with dynamic traffic changes made by middleboxes. In particular, our sampling is stateful which can capture a sequence of packets sharing same states of middleboxes for correct local replay. More importantly, it ensures high-confidence packet processing attestation by enforcing middleboxes to bind execution assurances with packets using commitment messages, and by using delayed verification procedure to defeat any potential biased results against selected sampling. To demonstrate the feasibility and efficiency of our scheme, we implement a prototype consisting of various types of middleboxes on Click, and conduct extensive experiments on Amazon EC2 with real traces. The experimental results show that our scheme imposes marginal processing delay for packets with various middleboxes and presents negligible throughput degradation.

Promising unprecedented convenience, Online Ride Hailing (ORH) service such as Uber and Didi has gained increasing popularity. Different from traditional taxi service, this new on-demand transportation service allows users to request rides from the online service providers at the touch of their fingers. Despite such great convenience, existing ORH systems require the users to expose their locations when requesting rides - a severe privacy issue in the face of untrusted or compromised service providers. In this paper, we propose a private yet efficient ride request scheme, allowing the user to enjoy public ORH service without sacrificing privacy. Unlike previous works, we consider a more practical setting where the information about the drivers and road networks is public. This poses an open challenge to achieve strong security and high efficiency for the secure ORH service. Our main leverage in addressing this problem is hardware-enforced Trusted Execution Environment, in particular Intel SGX enclave. However, the use of secure enclave does not lead to an immediate solution due to the hardware's inherent resource constraint and security limitation. To tackle the limited enclave space, we first design an efficient ride-matching algorithm utilizing hub-based labeling technique, which avoids loading massive road network data into enclave during online processing. To defend against side-channel attacks, we take the next step to make the ride-matching algorithm data-oblivious, by augmenting it with oblivious label access and oblivious distance computation. The proposed solution provides high efficiency of real-time response and strong security guarantee of data-obliviousness. We implement a prototype system of the proposed scheme and thoroughly evaluate it from both theoretical and experimental aspects. The results show that the proposed scheme permits accurate and real-time ride-matching with provable security.

Crowdsensing, driven by the proliferation of sensor-rich mobile devices, has emerged as a promising data sensing and aggregation paradigm. Despite useful, traditional crowdsensing systems typically rely on a centralized third-party platform for data collection and processing, which leads to concerns like single point of failure and lack of operation transparency. Such centralization hinders the wide adoption of crowdsensing by wary participants. We therefore explore an alternative design space of building crowdsensing systems atop the emerging decentralized blockchain technology. While enjoying the benefits brought by the public blockchain, we endeavor to achieve a consolidated set of desirable security properties with a proper choreography of latest techniques and our customized designs. We allow data providers to safely contribute data to the transparent blockchain with the confidentiality guarantee on individual data and differential privacy on the aggregation result. Meanwhile, we ensure the service correctness of data aggregation and sanitization by delicately employing hardware-assisted transparent enclave. Furthermore, we maintain the robustness of our system against faulty data providers that submit invalid data, with a customized zero-knowledge range proof scheme. The experiment results demonstrate the high efficiency of our designs on both mobile client and SGX-enabled server, as well as reasonable on-chain monetary cost of running our task contract on Ethereum.

Fog computing has emerged as a promising paradigm in overcoming the growing challenges (e.g., low latency, location awareness, and geographic distribution) arising from many real-world Internet of Things (IoT) applications, by extending the cloud to the network edge. With the widespread deployment of fog-assisted IoT applications, unprecedentedly huge volumes of network traffic from massive IoT devices would continuously arrive at the fog nodes. Archiving the network traffic can be highly beneficial to fog computing, which forms the basis of forensic, monitoring, troubleshooting, and many other critical tasks. Such high value, however, constantly renders traffic archives the first-order target to experienced attackers. This mandates the traffic archives to be built in a trustworthy way and stayed encrypted at rest. Security aside, it is yet highly desirable to retain the utility of the encrypted traffic archives, in particular by making them privately queryable. In this paper, we take the first research attempt and explore a new design point to delicately bridge trusted hardware and searchable encryption for building trustworthy, encrypted, yet queryable network traffic archives for fog-assisted IoT applications. We take a systematic approach to address several key challenges, which are unsolvable by synthesizing out-of-box techniques, from ground up. Extensive evaluations show that our system can achieve stable archiving throughput of 350 Mb/s with one core, and saturate a 1 Gb/s link with four cores; for a real trace, it outperforms a baseline system without any of our designs by over 110× .

Verifiable pattern matching is the problem of finding a given pattern verifiably from the outsourced textual data, which is resident in an untrusted remote server. This problem has drawn much attention due to a large number of applications. The state-of-the-art method for this problem suffers from low efficiency. To enable fast verifiable pattern matching, we propose a novel scheme in this paper. Our scheme is based on an ordered set accumulator data structure and a newly developed verifiable suffix array structure, which only involves fast cryptographic hash computations. Our scheme also supports fast multiple-occurrence pattern matching. A striking feature of our proposed scheme is that our scheme works even with no secret keys, which ensures public verifiability. We conduct extensive experiments to evaluate the proposed scheme using Java. The results show that our scheme is orders of magnitude faster than the state-of-the-art work. Specifically, our scheme with public verifiability only costs a preprocessing time of 47 s (merely one-time off-line cost during outsourcing), a search time of 30 μs, a verification time of 149 μs, and a proof size of 2760 bytes for a verifiable pattern matching query with pattern length 200 on 10-million long textual data which consists of sequences of two-byte, Unicode characters in Java.

Mobile crowdsensing enables convenient sensory data collection from a large number of mobile devices and has found various applications. In the real practice, however, the sensory data collected from various mobile devices are usually unreliable. To extract truthful information from the unreliable sensory data in mobile crowdsensing, the topic of truth discovery has received wide attention recently, which essentially operates by estimating user reliability degrees and performing reliability-aware truthful aggregation. Despite the effectiveness, applying truth discovery in mobile crowdsensing faces several privacy and security challenges. First, the sensory data and reliability degrees of users may reveal privacy-sensitive information and, thus, demand strong protection. Second, the requester that initiates a crowdsensing application usually needs to have monetary investment, so the inferred truths can be the requester's proprietary information and should be protected as well. In this paper, we propose a new system architecture enabling encrypted truth discovery in mobile crowdsensing. We focus on general and realistic mobile crowdsensing scenarios with varying levels of user participation, and our security design is built on the confidence-aware truth discovery (CATD) approach for its state-of-the-art accuracy in such scenarios. In our system architecture, users send encrypted sensory data to the cloud, where CATD is then conducted in the encrypted domain. The final encrypted inferred truths are sent to the requester for decryption. Along the whole workflow, the sensory data and reliability degrees of users, as well as the inferred truths of the requester, are kept private. Extensive experiments over real-world mobile crowdsensing dataset show that our design achieves practical performance on mobile devices.

Migrating middleboxes to third-party service providers (e.g., clouds and ISPs) has drawn widespread attentions recently from both industry and academia. While its benefits on reduced local cost and increased service scalability are well understood, such deployment also introduces new security concerns, due to the fact that these boxes are no longer under the direct control of enterprises. Among others, one fundamental desideratum here is to ensure that those middleboxes consistently perform network functions as intended. In this work, we propose practical solutions towards enabling runtime execution assurances of outsourced middleboxes with high confidence. As an initial effort, we target on pattern matching based network functions, which cover a broad class of middlebox applications such as instruction detection, web firewall, and traffic classification. For efficiency, our design follows the same roadmap of probabilistic checking that provides tunable levels of assurance, as in outsourced computation and distributed computing literature. We show how to synthesize the design intuitions in the context of outsourced middleboxes and the dynamic network effect. We present diligent technical instantiations, in the case of single middlebox and the composition of multiple middlebox service chaining, respectively. For a large batch of packets, sufficiently high assurance levels can be achieved by pre-processing only a few randomly selected packets, with marginal overhead. Evaluations of our system prototype on Amazon EC2 show that, the processing of 1000 packets, which includes pattern matching and execution proof generation, results in 200–500ms latency and throughput up to 360Mbps.

Outsourced middlebox services have drawn broad attentions recently from both industry and academia [1]. Despite benefiting enterprises from reduced cost and increased service scalability, such services also introduce acute security concerns, because these boxes are no longer under direct control of enterprises. Among others, one fundamental and immediate requirement is to ensure that those middleboxes always perform network functions truthfully and correctly [2]. Fulfilling this requirement will extend enterprises' visibility into remote middleboxes and promote further adoption of middlebox outsourcing services. Unfortunately, to our best knowledge, little work investigates the above problem, i.e., making network functions executed by middleboxes verifiable.