Secure three-party computation (3PC) with semi-honest security under an honest majority offers notable efficiency in computation and communication; for Boolean circuits, each party sends a single bit for every AND gate, and nothing for XOR. However, round complexity remains a significant challenge, especially in high-latency networks. Some works can support multi-input AND and thereby reduce online round complexity, but they requireexponentialcommunication for generating the correlations in either preprocessing or online phase. How to extend the AND gate to multi-input while maintaining high correlation generation efficiency is still not solved. To address this problem, we propose a round-efficient 3PC framework ALKAID for Boolean circuits through improved multi-input AND gate. By mixing correlations and redundancy, we propose a concretely efficient correlation generation approach for small input bitsNN> 4. Exploiting the improved multi-input AND gates, we design fast depth-optimized parallel prefix adder and share conversion primitives in 3PC, achieved with new techniques and optimizations for better concrete efficiency. We further apply these optimized primitives to enhance the efficiency of secure non-linear functions in machine learning. We implement ALKAID and extensively evaluate its performance. Compared to state of the arts like ABY3 (CCS’2018), Trifecta (PoPETs’2023), and METEOR (WWW’2023), ALKAID enjoys 1.5×–2.5× efficiency improvements for boolean primitives and non-linear functions, with better or comparable communication.

Circuit Private Set Intersection (Circuit-PSI) allows two parties to compute a function f on items in the intersection of their input sets without revealing items in the intersection set. It is a well-known variant of PSI and has numerous practical applications. However, existing Circuit-PSI protocols only provide security against semi-honest adversaries. A straightforward approach to constructing a maliciously secure Circuit-PSI is to extend a pure garbled-circuit-based PSI (NDSS'12) to a maliciously secure circuit-PSI, but it will not be concretely efficient. Another is converting state-of-the-art semi-honest Circuit-PSI protocols (EUROCRYPT'21; PoPETS'22) to be secure in the malicious setting. However, it will come across the consistency issue (EUROCRYPT'11) since parties can not guarantee the inputs of the function f stay unchanged as obtained from the last step. This paper tackles the previously mentioned issue by presenting the first maliciously secure Circuit-PSI protocol. Our key innovation, the Distributed Dual-key Oblivious Pseudorandom Function (DDOPRF), enables the oblivious evaluation of secret-shared inputs using dual keys within the SPDZ MPC framework. Notably, this construction seamlessly ensures fairness within the Circuit-PSI. Compared to the state-of-the-art semi-honest Circuit-PSI protocol (PoPETS'22), experimental results demonstrate that our malicious Circuit-PSI protocol not only reduces around 5x communication costs but also enhances efficiency, particularly for modest input sets (<= 2^{14}) in the case of the WAN setting with high latency and limited bandwidth.

Dynamic searchable encryption (DSE) with forward and backward privacy reduces leakages in early-stage schemes. Security enhancement comes with a price - maintaining updatable keyword-wise state information. State information, if stored locally, incurs significant client-side storage overhead for keyword-rich datasets, potentially hindering real-world deployments.

Decision tree classifiers are pervasively applied in a wide range of areas, such as healthcare, credit-risk assessment, spam detection, and many more. To ensure effectiveness and efficiency, clients usually choose to adopt classification services that are offered by model providers. However, the required data interactions in the evaluation process raise privacy concerns for both the provider and the client, indicating an imminent need for private decision tree evaluation (PDTE). Recently, some works, e.g., [1] (ESORICS'19) and [2] (NDSS'21), try to achieve PDTE by secure outsourcing computation. However, to hide the decision tree structure, [1] and [2] require non-complete decision trees to be made complete by padding dummy nodes, which lead to exponential (provider-side and cloud-side) computation and communication complexity in the depth of the decision tree. This is especially impractical for deep but sparse decision trees. In this paper, we propose a secure and efficient outsourced PDTE protocol with a focus on sparse trees. We avoid padding dummy nodes by vector dot products in outsourcing settings. Through experiments, we show the competitive performance of our design. Compared with [2] on Spambase dataset in the cloud-side, we are 486× more communication efficient in offline phase and 15× more communication efficient in online phase.

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.

Advancements in deep learning enable neural network (NN) inference to be a service, but service providers and clients want to keep their inputs secret for privacy protection.Private Inferenceis the task of evaluating NN without leaking private inputs. Existing secure multiparty computation (MPC)-based solutions mainly focus on fixed bit-width methodology, such as 32 and 64 bits. Binary Neural Network (BNN) is efficient when evaluated in MPC and has achieved reasonable accuracy for commonly used datasets, but prior private BNN inference solutions, which focus onBoolean Circuits, are still costly in communication and run-time. In this paper, we introduce FLEXBNN, a fast private BNN inference framework using three-party computation (3PC) inArithmetic Circuitsagainst semi-honest adversaries with honest-majority. In FLEXBNN, we propose to employ flexible and small bit-width equipped with a seamless bit-width conversion method and design several specific optimizations towards the basic operations: i) We propose bit-width determination methods for Matrix Multiplication and Sign-based Activation function. ii) We integrate Batch Normalization and Max-Pooling into the Sign-based Activation function for better efficiency. iii) More importantly, we achieve seamless bit-width conversion within the Sign-based Activation function with no additional cost. Extensive experiments illustrate that FLEXBNN outperforms state-of-the-art solutions in communication, run-time, and scalability. On average, FLEXBNN is 11× faster than XONN (USENIX Security’ 19) in LAN, 46× (resp. 9.3×) faster than QUOTIENT (ACM CCS’19) in LAN (resp. WAN), 10× faster than BANNERS (ACM IH&MMSec’21) in LAN, and 1.1-2.9× (resp. 1.5-2.7×) faster than FALCON (semi-honest, PoPETs’21) in LAN (resp. WAN), and improves the respective communication by 500×, 127×, and 1.3-1.5× compared to XONN, BANNERS, and FALCON.

Private decision tree evaluation (PDTE) allows a decision tree holder to run a secure protocol with a feature provider. By running the protocol, the feature provider will learn a classification result. Nothing more is revealed to either party. In most existing PDTE protocols, the required communication grows exponentially with the tree's depth d, which is highly inefficient for large trees. This shortcoming motivated us to design a sublinear PDTE protocol with $O(d)$ communication complexity. The core of our construction is a shared oblivious selection (SOS) functionality, allowing two parties to perform a secret-shared oblivious read operation from an array. We provide two SOS protocols, both of which achieve sublinear communication and propose optimizations to further improve their efficiency. Our sublinear PDTE protocol is based on the proposed SOS functionality and we prove its security under a semi-honest adversary. We compare our protocol with the state-of-the-art, in terms of communication and computation, under various network settings. The performance evaluation shows that our protocol is practical and more scalable over large trees than existing solutions.

With the rapid development of Internet and the widespread application of distributed computing, people enjoy various conveniences while at the same time their privacy has also been threatened. Secure multiparty computation (MPC) can solve the problem of how data owners who do not trust each other jointly compute in distributed scenarios. Using MPC technique, people can not only realize data joint computing, but also ensure data privacy. In most data application scenarios, private data held by different parties can often be represented by sets. To complete the relevant statistical computations of the intersection of two private sets, we propose a suite of protocols based on MPC. These protocols can compute the statistical functions of the associated data of the intersection, including cardinality, sum, average, variance, range, and so forth, without revealing any additional information other than the result. To achieve these functions, we design a private membership test protocol with the result as the arithmetic sharing value, called the arithmetic shared private membership test (ASPMT) protocol. On the basis of the ASPMT protocol, the size and other statistics of the intersection can be computed securely and efficiently. All fundamental computations are constructed based on secret sharing and oblivious transfer techniques. Thanks to the use of precomputation technique, all protocols are highly efficient.

To achieve efficiently search and update on outsourced encrypted data, dynamic searchable symmetric encryption (DSSE) was proposed by just leaking some well-defined leakages. Though small, many recent works show that an attacker can exploit these leakages to undermine the security of existing DSSE schemes. In particular, an attacker can exploit even seemingly harmless size pattern to perform severe attacks. Many exiting schemes resort to oblivious RAM (ORAM) to hide search/access pattern; however, even such powerful cryptographic primitive cannot protect size pattern leakage. In this article, we first show that size pattern can lead to more information leakages, which is not well studied or protected by existing schemes. We then extend the existing privacy notion for DSSE to capture the size pattern leakage, achieving a strong forward and backward privacy definition. Following the definition, we propose a new DSSE scheme Eurus. Eurus can eliminate search/access pattern by relying on a multi-server ORAM scheme, meanwhile reducing size pattern with reasonable efficiency. We show that Eurus can reduce leakage significantly with better efficiency, compared with state-of-the-art leakage reduction schemes.

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.

Oblivious transfer (OT) is a cryptographic primitive originally used to transfer a collection of messages from the sender to the receiver in an oblivious manner. OT extension protocol reduces expensive asymmetric operations by running a small number of OT instances first and then cheap symmetric operations. While most earlier works discussed security model or communication and computation complexity of OT in general case, we focus on concrete application scenarios, especially where the sender in the OT protocol is a database with less computation and limited interaction capability. In this paper, we propose a generic outsourced OT extension protocol ( O Tex ) that outsources all the asymmetric operations of the sender to a semihonest server so as to adapt to specific scenarios above. We give O Tex a standard security definition, and the proposed protocol is proven secure in the semihonest model. In O Tex , the sender works on the fly and performs only symmetric operations locally. Whatever the number of rounds OT to be executed and the length of messages in OT to be sent, our protocol realizes optimal complexity. Besides, O Tex can be used to construct high-level protocols, such as private membership test (PMT) and private set intersection (PSI). We believe our O Tex construction may be a building block in other applications as well.

Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become a must-have property of all new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost's scheme is constructed with a relatively inefficient public key cryptographic primitive, and has poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost's scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost's scheme. The experiment results show that both our schemes are highly efficient.