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.

Private set intersection (PSI) allows two participants to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. It is known that oblivious linear evaluation (OLE) can be used to construct the online efficient PSI protocol. However, oblivious transfer (OT) and fully homomorphic encryption (FHE)-based offline OLE generation are expensive, and the online computational complexity is super-linear and still a heavy burden for large-scale sets. In this paper, we propose VCR, an efficient PSI protocol from vector OLE (VOLE) with the offline-online paradigm. Concretely, we first propose the batched short VOLE protocol to reduce offline overhead for generating VOLE tuples. Then, we design a batched private membership test protocol from pre-computed VOLE to accelerate the online computation. Experiments demonstrate that VCR outperforms prior art. Compared to state-of-the-art work, we reduce the total communication costs (resp. running time) by 341× and 9.1× (resp. 6.5× and 2.5×) on average for OT and FHE-based protocols.

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.

Presently, similar sequence search is a fundamental technique in genomic data research. Patients or researchers, who want to check whether they or their research objects have genetic diseases or potential illnesses, need to query similar sequences with their genes in certain genomic databases. As a consequence, this may raise privacy issues since the genomic data are regarded as an identifier of each individual and contain lots of sensitive information. Up to date, some solutions have been brought up for achieving secure similarity search over genomic data, but they are still defective in searching exact similar sequences, supporting fine-grained access control, preventing side information leakage, and being built on strong security models at the same time. In this paper, aiming at the above challenge, we propose a maliciously secure similar sequence search scheme with fine-grained access control over genomic data, named PriGenX. Based on oblivious transfer and authenticated garbling techniques, our scheme also supports secure access control with anonymity for protecting the identity of each party preventing side information leakage, and implementing a flexible over-threshold similarity search. Experimental results and security analysis indicate that our scheme is scalable and maliciously secure.

Genomic data is being produced rapidly by both individuals and enterprises, and outsourcing this ever-increasing data into clouds is promising for cutting the cost of data owners and mining the wealth of genomic data at a larger scale. However, genome carries sensitive information about individuals, and it is challenging to securely and efficiently perform analysis on remotely hosted genomic databases. In this paper, we present a privacy-preserving range-constrained intersection query scheme on genomic data. To achieve security and efficiency, we propose a protocol to fulfill range-constrained intersection query, named PriRanGe. With PriRanGe, a client can securely query genomic data in a specific range in a database while keeping this whole process private. The security of our design targets genomic database confidentiality, query range/result confidentiality, and access pattern protection, and the advantage in efficiency is due to most employed primitives are symmetric. We thoroughly evaluated our design by security proof, experimental analysis and comparison to the state-of-the-art works, all of which support the conclusion that this design is both secure and fast.

Genome-Wide Association Study (GWAS) aims at detecting the association between diseases and Single-Nucleotide Polymorphisms (SNPs) with statistical techniques and has great potential for disease diagnosis. To obtain high-quality results, GWAS requires large-scale genomic data containing individuals’ privacy information. Thus, how to improve the efficiency of GWAS while protecting the privacy of genomic data becomes a critical challenge. In this paper, we propose a secure and efficient GWAS scheme. By using secure three-party computation, we present a series of protocols, i.e., Secure Quality Control, Secure Principle Component Analysis, Secure Cochran-Armitage trend test, and Secure Logistic Regression, to cover the most significant procedures of secure GWAS. In these protocols, a new comparison protocol is designed to reduce communication and improve efficiency. Furthermore, by extending the above comparison protocol to be maliciously secure and utilizing other technologies, e.g., consistency check, we extend the whole GWAS scheme to malicious security with rationally additional overhead. Experimental results demonstrate that our protocols achieve about 33% performance improvement than the state-of-art secure GWAS scheme using two-party computation in terms of runtime and communication in the semi-honest setting. The cost of our scheme in the malicious setting is around 1.5X than that in the semi-honest setting.

The optimal location selection is one type of the location-based services (LBS) that aims to find the best location for a new facility from some candidate facilities given a set of existing facilities and a set of customers. Due to reliable and flexible cloud services, outsourcing such heavy-computation tasks has been a popular trend. However, since the cloud is not fully trusted, and the location data contains the sensitive information, privacy protection becomes an essential requirement for these services. Although some related works have been proposed to provide privacy protection, the privacy of data and queries, accuracy of query results, and multiple features of location data are not considered by them simultaneously. In this paper, we propose a privacy-preserving optimal location query scheme PPOLQ that supports multiple-condition filter and queries over multiple data providers in outsourced environments. Specifically, we first design a secure division protocol and a secure inner product protocol based on the Paillier algorithm and the random masking technique, respectively. After that, based on the proposed algorithms, the additive homomorphic encryption, and the secure two-party computation techniques, we develop a privacy-preserving optimal location query scheme. Finally, we analyze the security of our proposed algorithms and scheme in the semi-honest model. Meanwhile, we implement all algorithms and the proposed scheme, and our implementation is open source at Gitee. We also evaluate their performances using synthetic datasets, and extensive experiments show that our scheme is practical for the real-world applications.

In this paper, the generative model is used to introduce the structural properties of the signal to replace the common sparse hypothesis, and a non-convex compressed sensing sparse deviation model based on the generative model (ℓq-Gen) is proposed. By establishing ℓqvariant of the restricted isometry property (q-RIP) and Set-Restricted Eigenvalue Condition (q-S-REC), the error upper bound of the optimal decoder is derived when the recovered signal is within the sparse deviation range of the generator. Furthermore, it is proved that the Gaussian matrix satisfying a certain number of measurements is sufficient to ensure a good recovery for the generating function with high probability. Finally, a series of experiments are carried out to verify the effectiveness and superiority of the ℓq-Gen model.