Secure two-party machine learning has made substantial progress through the use of mixed-mode protocols, but existing approaches often suffer from efficiency bottlenecks due to inherent mismatch between optimal domains of various cryptographic primitives. In response to these challenges, we introduce framework M&M, which features an efficient modulus conversion protocol. This breakthrough enables seamless integration of the most suitable cryptographic subprotocols within their optimal modulus domains with a minimal modulus conversion overhead. We further establish new benchmarks and practical optimizations for the performance of fundamental primitives, namely comparison and multiplication, across various two-party techniques.By incorporating these techniques, M&M demonstrates significant performance enhancements over state-of-the-art solutions: i) we report a$6\times$-$100\times$improvement for approximated truncations with 1-bit error tolerance; ii) an average of$5\times$(resp.$4\times$) reduction in communication (resp. runtime) for machine learning functions; iii) and a 25%-99% improvement in cost-efficiency for private inference of deep neural networks and 50% improvement in private training of gradient boosting decision trees.

ChatGPT is recognized as a significant revolution in the field of artificial intelligence, but it raises serious concerns regarding user privacy, as the data submitted by users may contain sensitive information. Existing solutions for secure inference face significant challenges in supporting GPT-like models due to the enormous number of model parameters and complex activation functions. In this paper, we develop CipherGPT, the first framework for secure two-party GPT inference, building upon a series of innovative protocols. First, we propose a secure matrix multiplication that is customized for GPT inference, achieving upto 3.8× speedup and 4.3× bandwidth reduction over SOTA. We also propose a novel protocol for securely computing GELU, surpassing SOTA by 3.2× in runtime, 1.3× in communication and 7.4× in precision. Furthermore, we propose the first protocol for secure top-k sampling. We provide a full-fledged implementation and comprehensive benchmark for CipherGPT. In particular, we measure the runtime and communication for each individual operation. We believe this will serve as a reference for future research in this area.

In the field of artificial intelligence, secure model inference is essential for protecting data confidentiality, which allows users to interact with trained models for decision-making support without privacy leakage. However, current secure inference methods often overlook the simultaneous verification of data origins for both user inputs and model weights, which is crucial for maintaining the integrity of inference outcomes. In this study, we present a novel verifiable secure inference scheme that leverages blockchain to enhance the verifiability of both the inference process and the origins of user inputs and model weights. We integrate the decentralized ledger to store the committed inputs and weights, serving as convincing data origins. We then transform neural networks into zero-knowledge proof constraints with optimized structures for the inference process. To illustrate its application scenario, we propose a regulatable privacy-preserving transaction scheme. Its regulation depends on anomaly detection on private transactions without privacy leakage, which takes the encrypted ledger as the data source and the committed detection model as the parameter source to perform our verifiable secure inference. We provide rigorous security proofs for our schemes, demonstrating their authenticity and privacy. We implement them to demonstrate their scalability through analyzing their computational and communication performance.

Approximate nearest neighbor search (ANNS), also known as vector search, is an important building block for various applications, such as recommendation systems, biometric authentication, and machine learning. In this work, we are interested in the private ANNS problem, where the client wants to learn (and can only learn) the ANNS results without revealing the query to the server. Previous private ANNS works either suffer from high communication cost (Chen et al., USENIX Security 2020) or work under a stronger security assumption of two non-colluding servers (Servan-Schreiber et al., SP 2022). We present Panther, an efficient private ANNS framework under the single server setting. Panther achieves its high performance via several novel co-designs of private information retrieval, secret-sharing, garbled circuits, and homomorphic encryption. We made extensive experiments using Panther on four public datasets, showing that Panther could answer an ANNS query on 10 million points in 18 seconds with 284 MB of communication. This is more than 7.8× faster and 20× more compact than Chen et al.

Money laundering is the process that intends to legalize the income derived from illicit activities, thus facilitating their entry into the monetary flow of the economy without jeopardizing their source. It is crucial to identify such activities accurately and reliably in order to enforce anti-money laundering (AML).

State-machine replication (SMR) allows a deterministic state machine to be replicated across a set of replicas and handle clients’ requests as a single machine. Most existing SMR protocols are leader-based requiring a leader to order requests and coordinate the protocol. This design places a disproportionately high load on the leader, inevitably impairing the scalability. If the leader fails, a complex and bug-prone fail-over protocol is needed to switch to a new leader. An adversary can also exploit the fail-over protocol to slow down the protocol.In this paper, we propose a crash-fault tolerant SMR named$\mathsf{Aurora}$Aurora, with the following properties:•Leaderless: it does not require a leader, hence completely get rid of the fail-over protocol.•Scalable: it can scale up to$11$11replicas.•Robust: it behaves well even under a poor network connection.We provide a full-fledged implementation of$\mathsf{Aurora}$Auroraand systematically evaluate its performance. Our benchmark results show that$\mathsf{Aurora}$Auroraachieves a throughput of around two million Transactions Per Second (TPS), up to 8.7$\boldsymbol{\times}$×higher than the state-of-the-art leaderless SMR.

Encrypted database is an emerging and promising technology. It is able to run SQL operations on encrypted data. However, most existing encrypted databases haveno data interoperability, i.e., the output of an operator (e.g., addition) cannot be taken as input of another (e.g., comparison). As a result, these encrypted databases can only support simple queries like addition, multiplication and comparison, but unable to support a composition of these simple queries (e.g.,SELECT user_id FROM salary WHERE$V_{1} + V_{2} > 5000$V1+V2>5000). In SIGMOD ’14, Wong et al. propose SDB, which to the best of our knowledge is the only encrypted database that achieves data interoperability. Unfortunately, it has recently been broken (VLDB ’21). In this paper, we propose a novel encrypted database namedSDB+. It achieves data interoperability based on a suit of sophisticated designs. We formally prove thatSDB+achieves indistinguishability under chosen query attacks (IND-CQA). We provide a full-fledged implementation and run it on three benchmarks. Our experimental results show thatSDB+achieves comparable efficiency with SDB, even though the latter is insecure.

Graph clustering is an unsupervised machine learning method that partitions the nodes in a graph into different groups. Despite achieving significant progress in exploiting both attributed and structured data information, graph clustering methods often face practical challenges related to data isolation. Moreover, the absence of collaborative methods for graph clustering limits their effectiveness. In this paper, we propose a collaborative graph clustering framework for attributed graphs, supporting attributed graph clustering over vertically partitioned data with different participants holding distinct features of the same data. Our method leverages a novel technique that reduces the sample space, improving the efficiency of the attributed graph clustering method. Furthermore, we compare our method to its centralized counterpart under a proximity condition, demonstrating that the successful local results of each participant contribute to the overall success of the collaboration. We fully implement our approach and evaluate its utility and efficiency by conducting experiments on four public datasets. The results demonstrate that our method achieves comparable accuracy levels to centralized attributed graph clustering methods. Our collaborative graph clustering framework provides an efficient and effective solution for graph clustering challenges related to data isolation.

Byzantine fault-tolerant state machine replication (BFT-SMR) replicates a deterministic state machine across a set of replicas, and processes requests as a single machine even in the presence of Byzantine faults. BFT-SMR is crucial for ensuring system reliability in distributed computing, where the integrity of data and the correct execution of operations are of utmost importance. Recently, synchronous BFT-SMRs have received tremendous attention due to their simple design and high fault-tolerance threshold. However, existing solutions are not efficient enough to achieve high throughput. In this paper, we propose Arena, the firstmulti-leadersynchronous BFT-SMR. Thanks to the synchrony assumption, Arena gains high throughput benefit from multi-leader with a much simpler design (compared to other partially synchronous multi-leader designs). Furthermore, it is more robust: “no progress” of a leader will not trigger a view-change. Our experimental results show that Arena achieves a peak throughput of up to 7.7× higher than the state-of-the-art.

The recent popularity of cryptocurrencies like Bitcoin and Ethereum has drawn widespread attention to the blockchain technique. In particular, some private cryptocurrencies like Zerocash and Monero enhance privacy protection by concealing the identities of participants and transaction amounts. However, such comprehensive privacy measures present regulatory challenges to malicious activities like money laundering and extortion. Therefore, building a novel blockchain that maintains privacy while supporting regulatory oversight is crucial. In this paper, we propose a regulatable and privacy-preserving blockchain scheme that introduces a decoupled and preparatory regulatory process. It serves as a privacy-preserving first line of defense, enabling the identification of anomalous transactions without compromising the confidentiality of the underlying data. Our approach pioneers a method for anomaly screening on private transactions, mitigating risks without resorting to key escrow or content recovery, thus preserving end-to-end privacy for legitimate users. Initially, we explore suitable transaction features within private blockchains for training machine learning classifiers to detect anomalous behaviors. Subsequently, we customize a privacy-centric classifier employing homomorphic encryption to achieve private computation of anomaly detection without leaking sensitive information from private transaction content. We then construct the zero-knowledge proof for validating the encrypted computation process. Our work pioneers in fully integrating homomorphic encryption with zero-knowledge proof, enabling credible and trustworthy verification of the homomorphic ciphertext computations. Finally, we conduct comprehensive security analysis and experimental simulations. The experimental results demonstrate the efficiency and scalability of our approach.

Multimodal large language models (MLLMs) have recently achieved impressive general-purpose vision-language capabilities through visual instruction tuning. However, current MLLMs primarily focus on image-level or box-level understanding, falling short in achieving fine-grained vision-language alignment at pixel level. Besides, the lack of mask-based instruction data limits their ad-vancements. In this paper, we propose Osprey, a mask-text instruction tuning approach, to extend MLLMs by incor-porating fine-grained mask regions into language instruction, aiming at achieving pixel-wise visual understanding. To achieve this goal, we first meticulously curate a mask-based region-text dataset with 724K samples, and then design a vision-language model by injecting pixel-level representation into LLM. Specifically, Osprey adopts a convolutional CLIP backbone as the vision encoder and employs a mask-aware visual extractor to extract precise visual mask features from high resolution input. Experimen-tal results demonstrate Osprey's superiority in various region understanding tasks, showcasing its new capability for pixel-level instruction tuning. In particular, Osprey can be integrated with Segment Anything Model (SAM) seamlessly to obtain multi-granularity semantics. The source code, dataset and demo can be found at https://github.com/CircleRadon/Osprey.

Encrypted packet inspection (EPI) allows a middle-box to perform DPI over encrypted packets without decryption. Existing EPI systems rely on expensive cryptographic operations, hence they are not yet ready to be deployed in real-world. Fur-thermore, such solutions only support exact keyword matching, unable to securely support regular expression, which is the major tool for DPI rule description due to its powerful and flexible expressive ability. In this paper, we propose PrivRE, the first EPI system that can securely support regular expressions. The main idea of PrivRE is to have middlebox run regular expressions on a desensitized version of the payload, in which sensitive information has been replaced with dummy characters. We provide a full-fledged implementation of PrivRE. In particular, we override OpenSSL to make PrivRE transparent to the application layer, so that the software developers do not need to be aware of the existence of PrivRE. We systematically evaluate PrivRE on a testbed that consists of 3 intercontinental EC2 VMs. Our experimental results show that it introduces at most 0.03 % accuracy loss, and it is only 1.78 x −8.23 x slower than SplitTLS (where the middle box can decrypt the packets).

The popularity of cloud computing has made outsourced databases prevalent in real-world applications. To protect data security, numerous encrypted outsourced databases have been proposed for this paradigm. However, the maintenance of encrypted databases (EDBs) has scarcely been addressed. In this paper, we focus on a typical maintenance task - functional dependency (FD) discovery. We develop novel FD protocols in EDBs while guaranteeing minimal leakages: nothing is revealed besides the database size and the actual discovered FDs. As far as we know, we are the first to formally define secure FD discovery with minimal leakage. We present two oblivious FD discovery protocols and prove them secure in the presence of the persistent adversary (monitoring processes on the server). The first protocol leverages oblivious RAM (ORAM) and is suitable for dynamic databases. The second protocol relies on oblivious sorting and is more practical in static databases due to high parallelism. We present a thorough experimental evaluation of the proposed methods.

Private information retrieval (PIR) is a cryptographic protocol that enables a wide range of privacy-preserving applications. Despite being extensively studied for decades, it is still not efficient enough to be used in practice. In this paper, we propose a novel PIR protocol named PIRANA, based on the recent advances in constant-weight codes. It is up to 188.6× faster than the original constant-weight PIR (presented in Usenix SEC ’22). Most importantly, PIRANA naturally supports multi-query. It allows a client to retrieve a batch of elements from the server with a very small extra-cost compared to retrieving a single element, which results in up to an 14.4× speedup over the state-of-the-art multi-query PIR (presented in Oakland ’23). We also discuss a way to extend PIRANA to labeled private set intersection (LPSI). Compared with existing LPSI protocols, PIRANA is more friendly to the scenarios where the database updates frequently.

Oblivious map (OMAP) is an important component in encrypted databases, utilized to prevent the server inferring sensitive information about client's encrypted databases based on access patterns. Despite its widespread usage and importance, existing OMAP solutions face practical challenges, including the need for a large number of interaction rounds between the client and server, as well as substantial communication bandwidth. For example, the SOTA protocol OMIX++ in VLDB 2024 still requires O (log n ) interaction rounds and O (log 2 n ) communication bandwidth per access, where n denotes the total number of key-value pairs stored. In this work, we introduce more practical and efficient OMAP constructions. Consistent with all prior OMAPs, our constructions also adapt only the tree-based Oblivious RAM (ORAM) and oblivious data structures (ODS) to achieve OMAP for enhanced practicality. In complexity, our approach needs O (log n /log log n )+ O (log λ ) interaction rounds and O (log 2 n /log log n ) + O (log λ log n ) communication bandwidth per data access where λ is the security parameter. This new complexity results from our two main contributions. First, unlike prior works relying solely on search trees , we design a novel framework for OMAP that combines hash table with search trees. Second, we propose a more efficient tree-based ORAM named DAORAM, which is of significant independent interest. This new ORAM accelerates our constructions as it supports obliviously accessing hash tables more efficiently. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.

Cryptocurrencies such as Bitcoin and Ethereum are gaining popularity thanks to their prominent advantages compared to legacy financial transaction systems. However, they require all participants to reach a consensus on the order of transactions, which fundamentally limits their performance in terms of confirmation latency and throughput, thus hindering their further deployment. Off-chain payment network is the state-of-the-art approach of solving this performance issue. Unfortunately, all existing payment networks are based on payment channels, which bring extra overhead, cost and vulnerabilities. In this paper, by leveraging trusted monotonic counters, we propose monoCash, the first off-chain payment network that is channel-free, thereby it is one-hop, routing-free, concurrency-friendly, rebalancing-free and wormhole-resilient. We implement and deploy monoCash on a wide area network of 3,000 nodes. The benchmark shows that it provides a throughput up to 30,000 transactions per second (higher than credit card systems, e.g., VISA).

Federated Learning (FL) has been an emerging trend in machine learning and artificial intelligence. It allows multiple participants to collaboratively train a better global model and offers a privacy-aware paradigm for model training since it does not require participants to release their original training data. However, existing FL solutions for vertically partitioned data or decision trees require heavy cryptographic operations. In this article, we propose a framework named$\mathsf {FederBoost}$for private federated learning of gradient boosting decision trees (GBDT). It supports running GBDT over both vertically and horizontally partitioned data. Vertical$\mathsf {FederBoost}$doesnotrequire any cryptographic operation and horizontal$\mathsf {FederBoost}$only requires lightweight secure aggregation. The key observation is that the whole training process of GBDT relies on theorderingof the data instead of the values. We fully implement$\mathsf {FederBoost}$and evaluate its utility and efficiency through extensive experiments performed on three public datasets. Our experimental results show that both vertical and horizontal$\mathsf {FederBoost}$achieve the same level of accuracy with centralized training where all data are collected in a central server; and they are 4-5 orders of magnitude faster than the state-of-the-art solutions for federated decision tree training; hence offering practical solutions for industrial applications.

Deep unsupervised domain adaptation (UDA) has significantly boosted the performance of deep models on different domains by transferring knowledge from a source domain to a target domain. However, its robustness against adversarial attacks has not been explored due to the challenges of highly non-convex deep models and different data distribution. In this paper, we give the first attempt to analyze the vulnerability of deep UDA and propose a label-free poisoning attack (LFPA), which injects poisoning data into the training data to mislead adaptation between the two domains without ground truth in target domain. Specifically, we design an unsupervised adversarial loss as the attack goal, in which the pseudo-labels are used to approximate the ground-truth. Since retraining the model will gradually degrade the attack performance, we also add a regularization term to the unsupervised loss, which eliminates negative interactions between the training goal and the attack goal. To accelerate the craft of poisons, we select influential samples as the initial poisons and propose a fast reverse-mode optimization method which updates poisons according to the approximate truncated gradients. Experimental results on multiple state-of-the-art deep UDA methods demonstrate the effectiveness of the proposed LFPA and the high sensitivity of UDA to poisoning attacks.

Swift advancements in large language model (LLM) technologies lead to widespread research and applications, particularly in integrating LLMs with auxiliary tools, known as tool-using LLM agents. However, amid user interactions, the transmission of private information to both LLMs and tools poses considerable privacy risks to users. In this paper, we delve into current privacy-preserving solutions for LLMs and outline three pivotal challenges for tool-using LLM agents: generalization to both open-source and closed-source LLMs and tools, compliance with privacy requirements, and applicability to unrestricted tasks. To tackle these challenges, we present PrivacyAsst, the first privacy-preserving framework tailored for tool-using LLM agents, encompassing two solutions for different application scenarios. First, we incorporate a homomorphic encryption scheme to ensure computational security guarantees for users as a safeguard against both open-source and closed-source LLMs and tools. Moreover, we propose a shuffling-based solution to broaden the framework's applicability to unrestricted tasks. This solution employs an attribute-based forgery generative model and an attribute shuffling mechanism to craft privacy-preserving requests, effectively concealing individual inputs. Additionally, we introduce an innovative privacy concept,$t$-closeness in image data, for privacy compliance within this solution. Finally, we implement PrivacyAsst, accompanied by two case studies, demonstrating its effectiveness in advancing privacy-preserving artificial intelligence.

Federated learning (FL) requires frequent uploading and updating of model parameters, which is naturally vulnerable to gradient leakage attacks (GLAs) that reconstruct private training data through gradients. Although some works incorporate differential privacy (DP) into FL to mitigate such privacy issues, their performance is not satisfactory since they did not notice that GLA incurs heterogeneous risks of privacy leakage (RoPL) with respect to gradients from different communication rounds and clients. In this paper, we propose an Adaptive Privacy-Preserving Federated Learning (Adp-PPFL) framework to achieve satisfactory privacy protection against GLA, while ensuring good performance in terms of model accuracy and convergence speed. Specifically, a leakage risk-aware privacy decomposition mechanism is proposed to provide adaptive privacy protection to different communication rounds and clients by dynamically allocating the privacy budget according to the quantified RoPL. In particular, we exploratively design a round-level and a client-level RoPL quantification method to measure the possible risks of GLA breaking privacy from gradients in different communication rounds and clients respectively, which only employ the limited information in general FL settings. Furthermore, to improve the FL model training performance (i.e., convergence speed and global model accuracy), we propose an adaptive privacy-preserving local training mechanism that dynamically clips the gradients and decays the noises added to the clipped gradients during the local training process. Extensive experiments show that our framework outperforms the existing differentially private FL schemes on model accuracy, convergence, and attack resistance.

Recent studies have demonstrated that existing deep neural networks (DNNs) on 3D point clouds are vulnerable to adversarial examples, especially under the white-box settings where the adversaries have access to model parameters. However, adversarial 3D point clouds generated by existing white-box methods have limited transferability across different DNN architectures. They have only minor threats in real-world scenarios under the black-box settings where the adversaries can only query the deployed victim model. In this paper, we revisit the transferability of adversarial 3D point clouds. We observe that an adversarial perturbation can be randomly factorized into two sub-perturbations, which are also likely to be adversarial perturbations. It motivates us to consider the effects of the perturbation and its sub-perturbations simultaneously to increase the transferability for sub-perturbations also contain helpful information. In this paper, we propose a simple yet effective attack method to generate more transferable adversarial 3D point clouds. Specifically, rather than simply optimizing the loss of perturbation alone, we combine it with its random factorization. We conduct experiments on benchmark dataset, verifying our method's effectiveness in increasing transferability while preserving high efficiency.

Weakly-supervised image segmentation has recently attracted increasing research attentions, aiming to avoid the expensive pixel-wise labeling. In this paper, we present an effective method, namely Point2Mask, to achieve high-quality panoptic prediction using only a single random point annotation per target for training. Specifically, we formulate the panoptic pseudo-mask generation as an Optimal Transport (OT) problem, where each ground-truth (gt) point label and pixel sample are defined as the label supplier and consumer, respectively. The transportation cost is calculated by the introduced task-oriented maps, which focus on the category-wise and instance-wise differences among the various thing and stuff targets. Furthermore, a centroid-based scheme is proposed to set the accurate unit number for each gt point supplier. Hence, the pseudo-mask generation is converted into finding the optimal transport plan at a globally minimal transportation cost, which can be solved via the Sinkhorn-Knopp Iteration. Experimental results on Pascal VOC and COCO demonstrate the promising performance of our proposed Point2Mask approach to point-supervised panoptic segmentation. Source code is available at: https://github.com/LiWentomng/Point2Mask.

The current challenge of Deepfake detection is the cross-domain performance on unseen Deepfake data. Instead of extracting forgery artifacts that are robust to the cross-domain scenarios as most previous works, we propose a novel method named Single-sIde Guided Meta-leArning framework for DeepFake detection (SIGMA-DF) which simulates the cross-domain scenarios during training by synthesizing virtual testing domain through meta-learning. In addition, SIGMA-DF integrates the meta-learning algorithm with a new ensemble meta-learning framework, which separately trains multiple meta-learners in the meta-train phase to aggregate multiple domain shifts in each iteration. Hence multiple cross-domain scenarios are simulated, better leveraging the domain knowledge. In addition, considering the contribution of hard samples in single-side distribution optimization, a novel weighted single-side loss function is proposed to only narrow the intra-class distance between real faces and enlarge the inter-class distance for both real and fake faces in embedding space with the awareness of sample weights. Extensive experiments are conducted on several standard Deepfake detection datasets to demonstrate that the proposed SIGMA-DF achieves state-of-the-art performance. In particular, in the cross-domain evaluation from FF++ to Celeb-DF and DFDC, our SIGMA-DF outperforms the baselines by 4.4% and 4.5% in terms of AUC, respectively.

Weakly-supervised segmentation with label-efficient sparse annotations has attracted increasing research attention to reduce the cost of laborious pixel-wise labeling process, while the pairwise affinity modeling techniques play an essential role in this task. Most of the existing approaches focus on using the local appearance kernel to model the neighboring pairwise potentials. However, such a local operation fails to capture the long-range dependencies and ignores the topology of objects. In this work, we formulate the affinity modeling as an affinity propagation process, and propose a local and a global pairwise affinity terms to generate accurate soft pseudo labels. An efficient algorithm is also developed to reduce significantly the computational cost. The proposed approach can be conveniently plugged into existing segmentation networks. Experiments on three typical label-efficient segmentation tasks, i.e. box-supervised instance segmentation, point/scribble-supervised semantic segmentation and CLIP-guided semantic segmentation, demonstrate the superior performance of the proposed approach.

Order-preserving encryption (OPE) allows efficient comparison operations over encrypted data and thus is popular in encrypted databases. However, most existing OPE schemes are vulnerable to inference attacks as they leak plaintext frequency. To this end, some frequency-hiding order-preserving encryption (FH-OPE) schemes are proposed and claim to prevent the leakage of frequency. FH-OPE schemes are considered an important step towards mitigating inference attacks. Unfortunately, there are still vulnerabilities in all existing FH-OPE schemes. In this work, we revisit the security of all existing FH-OPE schemes. We are the first to demonstrate that plaintext frequency hidden by them is recoverable. We present three ciphertext-only attacks named frequency-revealing attacks to recover plaintext frequency. We evaluate our attacks in three real-world datasets. They recover over 90% of plaintext frequency hidden by any existing FH-OPE scheme. With frequency revealed, we also show the potentiality to apply inference attacks on existing FH-OPE schemes. Our findings highlight the limitations of current FH-OPE schemes. Our attacks demonstrate that achieving frequency-hiding requires addressing the leakages of both non-uniform ciphertext distribution and insertion orders of ciphertexts, even though the leakage of insertion orders is always ignored in OPE.

Nowadays, machine learning models, especially neural networks, have became prevalent in many real-world applications. These models are trained based on a one-way trip from user data: as long as users contribute their data, there is no way to withdraw. To this end,machine unlearningbecomes a popular research topic, which allows the model trainer to unlearn unexpected data from a trained machine learning model. In this article, we propose the first uniform metric called forgetting rate to measure the effectiveness of a machine unlearning method. It is based on the concept of membership inference and describes the transformation rate of the eliminated data from “memorized” to “unknown” after conducting unlearning. We also propose a novel unlearning method calledForsaken. It is superior to previous work in either utility or efficiency (when achieving the same forgetting rate). We benchmarkForsakenwith eight standard datasets to evaluate its performance. The experimental results show that it can achieve more than 90% forgetting rate on average and only causeless than 5% accuracy loss.

In S&P 21, Jia et al. proposed a new concept/mechanism named proof-of-learning (PoL), which allows a prover to demonstrate ownership of a machine learning model by proving integrity of the training procedure. It guarantees that an adversary cannot construct a valid proof with less cost (in both computation and storage) than that made by the prover in generating the proof. A PoL proof includes a set of intermediate models recorded during training, together with the corresponding data points used to obtain each recorded model. Jia et al. claimed that an adversary merely knowing the final model and training dataset cannot efficiently find a set of intermediate models with correct data points. In this paper, however, we show that PoL is vulnerable to “adversarial examples”! Specifically, in a similar way as optimizing an adversarial example, we could make an arbitrarily-chosen data point “generate” a given model, hence efficiently generating intermediate models with correct data points. We demonstrate, both theoretically and empirically, that we are able to generate a valid proof with significantly less cost than generating a proof by the prover.

Blockchain is a distributed database shared among disparate parties. It promises to enable new applications and solutions to wide-ranging domains. However, today's blockchains suffer from low throughput and high latency. This impedes widespread adoption of more complex blockchain-based applications. We propose a new direction for the future development of blockchains: pushing utmost work to client-side to make the blockchain-core as simple as possible. To show the feasibility and practicability of this idea, we construct both client-assisted consensus and client-assisted smart contracts. The client-assisted consensus only requires a single round-trip between clients and blockchain nodes; it is leaderless and parallelizable. Our experimental results show that it can process thousands of transactions per second when the number of replicas is 400. The client-assisted smart contract pushes the expensive execution to client-side and ensures the correctness by verifiable computation. It avoids duplicated execution, allows parallel execution and reduces transaction/blockchain sizes.

Today's blockchains suffer from low throughput and high latency, which impedes their widespread adoption of more complex applications like smart contracts. In this article, we propose a novel paradigm for smart contract execution. It distinguishes between consensus nodes and execution nodes: different groups of execution nodes can execute transactions in parallel; meanwhile, consensus nodes can asynchronously order transactions and process execution results. Moreover, it requires no coordination among execution nodes and can effectively prevent livelocks. We show two ways of applying this paradigm to blockchains. First, we show how we can make Ethereum support parallel and asynchronous contract executionwithout hard-forks. Then, we propose a new public, permissionless blockchain. Our benchmark shows that, with a fast consensus layer, it can provide a high throughput even for complex transactions like Cryptokitties gene mixing. It can also protect simple transactions from being starved by complex transactions.

Encrypted database is an innovative technology proposed to solve the data confidentiality issue in cloud-based DB systems. It allows a data owner to encrypt its database before uploading it to the service provider; and it allows the service provider to execute SQL queries over the encrypted data. Most of existing encrypted databases (e.g., CryptDB in SOSP '11) do not support data interoperability: unable to process complex queries that require piping the output of one operation to another. To the best of our knowledge, SDB (SIGMOD '14) is the only encrypted database that achieves data interoperability. Unfortunately, we found SDB is not secure! In this paper, we revisit the security of SDB and propose a ciphertext-only attack named co-prime attack. It successfully attacks the common operations supported by SDB, including addition, comparison, sum, equi-join and group-by. We evaluate our attack in three real-world benchmarks. For columns that support addition and comparison , we recover 84.9% -- 99.9% plaintexts. For columns that support sum, equi-join and group-by , we recover 100% plaintexts. Besides, we provide potential countermeasures that can prevent the attacks against sum, equi-join, group-by and addition. It is still an open problem to prevent the attack against comparison.

Bitcoin uses the proof-of-work (PoW) mechanism where nodes earn rewards in return for the use of their computing resources. Although this incentive system has attracted many participants, power has, at the same time, been significantly biased towards a few nodes, called mining pools. In addition, poor decentralization appears not only in PoW-based coins but also in coins that adopt proof-of-stake (PoS) and delegated proof-of-stake (DPoS) mechanisms.

Consensus mechanisms used by popular distributed ledgers are highly scalable but notoriously inefficient. Byzantine fault tolerance (BFT) protocols are efficient but far less scalable. Speculative BFT protocols such as Zyzzyva and Zyzzyva5 are efficient and scalable but require a trade-off: Zyzzyva requires only 3f + 1 replicas to tolerate f faults, but even a single slow replica will make Zyzzyva fall back to more expensive non-speculative operation. Zyzzyva5 does not require a non-speculative fallback, but requires 5f + 1 replicas in order to tolerate f faults. BFT variants using hardware-assisted trusted components can tolerate a greater proportion of faults, but require that every replica have this hardware. We present SACZyzzyva, addressing these concerns: resilience to slow replicas and requiring only 3f + 1 replicas, with only one replica needing an active monotonic counter at any given time. We experimentally evaluate our protocols, demonstrating low latency and high scalability. We prove that SACZyzzyva is optimally robust and that trusted components cannot increase fault tolerance unless they are present in at least two-thirds of replicas.

Abstract Decision trees and random forests are widely used classifiers in machine learning. Service providers often host classification models in a cloud service and provide an interface for clients to use the model remotely. While the model is sensitive information of the server, the input query and prediction results are sensitive information of the client. This motivates the need for private decision tree evaluation, where the service provider does not learn the client’s input and the client does not learn the model except for its size and the result. In this work, we identify the three phases of private decision tree evaluation protocols: feature selection, comparison, and path evaluation. We systematize constant-round protocols for each of these phases to identify the best available instantiations using the two main paradigms for secure computation: garbling techniques and homomorphic encryption. There is a natural tradeoff between runtime and communication considering these two paradigms: garbling techniques use fast symmetric-key operations but require a large amount of communication, while homomorphic encryption is computationally heavy but requires little communication. Our contributions are as follows: Firstly, we systematically review and analyse state-of-the-art protocols for the three phases of private decision tree evaluation. Our methodology allows us to identify novel combinations of these protocols that provide better tradeoffs than existing protocols. Thereafter, we empirically evaluate all combinations of these protocols by providing communication and runtime measures, and provide recommendations based on the identified concrete tradeoffs.

The surging interest in blockchain technology has revitalized the search for effective Byzantine consensus schemes. In particular, the blockchain community has been looking for ways to effectively integrate traditional Byzantine fault-tolerant (BFT) protocols into a blockchain consensus layer allowing various financial institutions to securely agree on the order of transactions. However, existing BFT protocols can only scale to tens of nodes due to their$O(n^2)$message complexity. In this paper, we propose FastBFT, a fast and scalable BFT protocol. At the heart of FastBFT is a novel message aggregation technique that combines hardware-based trusted execution environments (TEEs) with lightweight secret sharing. Combining this technique with several other optimizations (i.e., optimistic execution, tree topology and failure detection), FastBFT achieves low latency and high throughput even for large scale networks. Via systematic analysis and experiments, we demonstrate that FastBFT has better scalability and performance than previous BFT protocols.

Machine learning models hosted in a cloud service are increasingly popular but risk privacy: clients sending prediction requests to the service need to disclose potentially sensitive information. In this paper, we explore the problem of privacy-preserving predictions: after each prediction, the server learns nothing about clients' input and clients learn nothing about the model.

Malware checking is changing from being a local service to a cloud-assisted one where users' devices query a cloud server, which hosts a dictionary of malware signatures, to check if particular applications are potentially malware. Whilst such an architecture gains all the benefits of cloud-based services, it opens up a major privacy concern since the cloud service can infer personal traits of the users based on the lists of applications queried by their devices. Private membership test (PMT) schemes can remove this privacy concern. However, known PMT schemes do not scale well to a large number of simultaneous users and high query arrival rates. We propose a simple PMT approach using a carousel: circling the entire dictionary through trusted hardware on the cloud server. Users communicate with the trusted hardware via secure channels. We show how the carousel approach, using different data structures to represent the dictionary, can be realized on two different commercial hardware security architectures (ARM TrustZone and Intel SGX). We highlight subtle aspects of securely implementing seemingly simple PMT schemes on these architectures. Through extensive experimental analysis, we show that for the malware checking scenario our carousel approach surprisingly outperforms Path ORAM on the same hardware by supporting a much higher query arrival rate while guaranteeing acceptable response latency for individual queries.

Abstract Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

Encrypting data on client-side before uploading it to a cloud storage is essential for protecting users' privacy. However client-side encryption is at odds with the standard practice of deduplication. Reconciling client-side encryption with cross-user deduplication is an active research topic. We present the first secure cross-user deduplication scheme that supports client-side encryption without requiring any additional independent servers. Interestingly, the scheme is based on using a PAKE (password authenticated key exchange) protocol. We demonstrate that our scheme provides better security guarantees than previous efforts. We show both the effectiveness and the efficiency of our scheme, via simulations using realistic datasets and an implementation.