A privacy-preserving collaborative query protocol for distributed multi-server systems (DMS-P$^{2}$CQ) enables a querying party to interact with multiple independent servers using an identifier$x_{u}$and receive a categorical decision (e.g.,Good/Moderate/Poor) determined by the total number of servers whose datasets contain$x_{u}$. This setting is motivated by financial applications such as credit assessment, where the querying party must not reveal$x_{u}$to data-owning institutions, and each institution must protect its proprietary user list. To meet both the functionality and privacy requirements of the querying party and the servers, we present two protocols that represent a privacy-efficiency trade-off. DMS-P$^{2}$CQ$_{1}$is a lightweight protocol inspired by OPRF-based PSI. It achieves identifier privacy and hides the identifier-to-server membership relation from the querying party via a two-stage OPRF with an aggregation/re-randomization server. However, it reveals the aggregate count to a randomly selected leader server and relies on a non-collusion assumption between two special servers. DMS-P$^{2}$CQ$_{2}$strengthens privacy by secret-sharing the count so that no single party learns the true aggregate count and removes the need for a trusted re-randomization server. We prove the security of two protocols under the semi-honest model. Experimental results on our local testbed show that with 20 servers and a dataset size of$2^{20}$, the runtimes for DMS-P$^{2}$CQ$_{1}$and DMS-P$^{2}$CQ$_{2}$are approximately 8.034s and 16.697s, respectively.

Collaborative graph processing refers to the joint analysis of inter-connected graphs held by multiple graph owners. To honor data privacy and support various graph processing algorithms, existing approaches employ secure multi-party computation (MPC) protocols to express the vertex-centric abstraction. Yet, due to certain computation-intensive cryptography constructions, state-of-the-art (SOTA) approaches are asymptotically suboptimal, imposing significant overheads in terms of computation and communication. In this paper, we present RingSG, the first system to attain optimal communication/computation complexity within the MPC-based vertex-centric abstraction for collaborative graph processing. This optimal complexity is attributed to Ring-ScatterGather, a novel computation paradigm that can avoid exceedingly expensive cryptography operations (e.g., oblivious sort), and simultaneously ensure the overall workload can be optimally decomposed into parallelizable and mutually exclusive MPC tasks. Within Ring-ScatterGather, RingSG improves the concrete runtime efficiency by incorporating 3-party secure computation via share conversion, and optimizing the most cost-heavy part using a novel oblivious group aggregation protocol. Finally, unlike prior approaches, we instantiate RingSG into two end-to-end applications to effectively obtain application-specific results from the protocol outputs in a privacy-preserving manner. We developed a prototype of RingSG and extensively evaluated it across various graph collaboration settings, including different graph sizes, numbers of parties, and average vertex degrees. The results show RingSG reduces the system running time of SOTA approaches by up to 15.34× and per-party communication by up to 10.36×. Notably, RingSG excels in processing sparse global graphs collectively held by more parties, consistent with our theoretical cost analysis.

Private Set Intersection (PSI) enables each party with a private set to compute the intersection without disclosing other information. However, even in maliciously secure PSI, it does not guarantee input authenticity and output integrity, which becomes problematic in certain scenarios. For instance, in Web 3.0, one of the essential requirements is to find common certifiers among the parties. However, if certifier identities are meant to be protected, some parties may attempt to forge certifier identities or intentionally exclude a particular certifier during protocol execution. Recently, the Private Certifier Intersection (PCI), a variant of PSI, has been proposed to address this problem. Nevertheless, it incurs significantly high computational and communication overhead. This work proposes thePrivate Identity Intersection(PII), which takes private identifiers and corresponding anonymous signatures from mutually distrusting parties as input, verifies them, and delivers the intersection of the successfully verified identifiers to all parties while ensuring the integrity of the output. Furthermore, PII can naturally extend from two to multiple-party settings while resisting the collusion attack. To achieve the ideal functionality of PII, we implement a user-friendly MPC framework called$\mathsf {Oryx}$without third-party libraries. Based on$\mathsf {Oryx}$, we instantiate PII with two digital signature schemes, one proposed in this paper. Compared to existing work, our PII protocols reduce the computation overhead by up to$163\times$and the communication overhead by up to$190\times$, representing an improvement of two orders of magnitude. To demonstrate the practicality of our work, we evaluate its performance in WAN environments with bandwidths of 100 Mbps and 500 Mbps, under a fixed latency of 20 ms.

Private Set Intersection (PSI) allows two parties, the sender and the receiver, each possessing a private set, to compute the intersection of their sets, with only the receiver learning the intersection and without revealing any additional information. Privacy-Preserving Feature Retrieval PSI (P2FRPSI) is a variant of PSI. In P2FRPSI, the receiver designs a predicate and obtains the intersection of private sets that satisfy this predicate, while the sender learns nothing about the predicate. However, the existing two PRFPSI protocols (TIFS 2024), based respectively on the DH key agreement and Oblivious Pseudo- Random Function (OPRF), are not highly efficient due to their reliance on expensive homomorphic encryption. Moreover, the existing DH-based P2FRPSI protocol reveals the output size and the original intersection size to the sender. We also observed that the existing P2FRPSI protocols do not support threshold retrieval and the logical connective OR and can only work when feature values of the sender have very low dimensionality. This paper also proposes two new P2FRPSI protocols, one based on DH key agreement and the other based on OPRF, to fully address the issues present in existing P2FRPSI protocols. Our DH-based P2FRPSI is 30× faster than the existing DH-based protocol, with only a 36% increase in communication overhead. Furthermore, our OPRF-based P2FRPSI protocol is 2× as fast as existing OPRF-based protocol and reduces communication overhead by a factor of 4.6. Our DH-based P2FRPSI protocol completely eliminates the leakage of the original intersection size and the output size. Meanwhile, our protocols support the logical connective OR for linking sub-predicates and also enable threshold-based retrieval. They are proven to be secure in the semi-honest model. Our open-source implementations can be found at https://github.com/ShallMate/pfrpsi, which can help readers understand our protocols and reproduce the experiments.

Collaborative graph learning represents a learning paradigm where multiple parties jointly train a graph neural network (GNN) using their own proprietary graph data. To honor the data privacy of all parties, existing solutions for collaborative graph learning are either based on federated learning (FL) or secure machine learning (SML). Although promising in terms of efficiency and scalability due to their distributed training scheme, FL-based approaches fall short in providing provable security guarantees and achieving good model performance. Conversely, SML-based solutions, while offering provable privacy guarantees, are hindered by their high computational and communication overhead, as well as poor scalability as more parties participate.

Private Set Intersection (PSI) protocols can securely compute the intersection of the private sets on the server and the client without revealing additional data. This work introduces the concept of Privacy-Preserving Feature Retrieved Private Set Intersection ($\mathsf {P^{2}FRPSI}$). In$\mathsf {P^{2}FRPSI}$protocols, the client can obtain the intersection that satisfies a given predicate without revealing the predicate and additional data. We formally define the$\mathsf {P^{2}FRPSI}$protocol, including its inputs, outputs, functionality, and security. To achieve the privacy guarantee in$\mathsf {P^{2}FRPSI}$protocols, a new two-party protocol is designed, namely Secure Secret Shared Retrieval ($\mathsf {S^{3}R}$), which can be used to securely determine whether each item on the server satisfies the predicate. We construct an$\mathsf {S^{3}R}$protocol and prove its security in the semi-honest model. On the basis of this, we design an efficient OT-based$\mathsf {P^{2}FRPSI}$protocol and an easy-to-implement DH-based$\mathsf {P^{2}FRPSI}$protocol and prove that they are secure in the semi-honest model. Our implementation shows that the OT-based$\mathsf {P^{2}FRPSI}$protocol can perform the matching for about 1000K items in 3.8 seconds with a single thread. Moreover, the DH-based$\mathsf {P^{2}FRPSI}$can perform the matching for about 7000K items in one hour with four threads, with communication totaling 1456 MB, while the OT-based$\mathsf {P^{2}FRPSI}$protocol requires 1673 MB.

In cloud-assisted electronic health (eHealth) systems, the exponential growth of electronic health records (EHRs) has prompted healthcare organizations to move it to the cloud. However, EHRs are encrypted before being outsourced for privacy. Although searchable encryption schemes for EHRs have been proposed, their search efficiency and functionality for massive EHRs with high-dimensional are still insufficient. In this paper, we adopt an attribute hierarchy structure for medical datasets, enabling efficient multi-dimensional range search and reducing high-dimensional EHRs to low-dimensional vectors. To further improve search efficiency, we design an index tree that require no additional storage and computational overhead, significantly improving efficiency in search, trapdoor generation, and index building. Our scheme is well-suited for large-scale medical data scenarios, especially in dealing with high-dimensional and massive datasets. Extensive experiments demonstrate the superiority of our scheme over existing solutions, particularly in large-scale medical data scenarios. Compared to the classic EDMRS scheme, our scheme has a computational overhead in index building and search that is only about 1/500 and 1/10 of EDMRS when the number of keywords and electronic health records is 3,000 and 6,000, respectively. Moreover, as medical data and keywords increase, our scheme shows slower computational overhead growth compared to EDMRS.

Abstract Vertical Federated Learning (VFL) has many applications in the field of smart healthcare with excellent performance. However, current VFL systems usually primarily focus on the privacy protection during model training, while the preparation of training data receives little attention. In real-world applications, like smart healthcare, the process of the training data preparation may involve some participant’s intention which could be privacy information for this participant. To protect the privacy of the model training intention, we describe the idea of Intention-Hiding Vertical Federated Learning (IHVFL) and illustrate a framework to achieve this privacy-preserving goal. First, we construct two secure screening protocols to enhance the privacy protection in feature engineering. Second, we implement the work of sample alignment bases on a novel private set intersection protocol. Finally, we use the logistic regression algorithm to demonstrate the process of IHVFL. Experiments show that our model can perform better efficiency (less than 5min) and accuracy (97%) on Breast Cancer medical dataset while maintaining the intention-hiding goal.

Additively Homomorphic Encryption (AHE) has been widely used in various applications, such as federated learning, blockchain, and online auctions. Elliptic Curve (EC) based AHE has the advantages of efficient encryption, homomorphic addition, scalar multiplication algorithms, and short ciphertext length. However, EC-based AHE schemes require solving a small exponential Elliptic Curve Discrete Logarithm Problem (ECDLP) when running the decryption algorithm, i.e., recovering the plaintext$m\in \{0,1\}^{\ell} $from$m \ast G$. Therefore, the decryption of EC-based AHE schemes is inefficient when the plaintext length$\ell > 32$. This leads to people being more inclined to use RSA-based AHE schemes rather than EC-based ones. This paper proposes an efficient algorithm called$\mathsf {FastECDLP}$for solving the small exponential ECDLP at 128-bit security level. We perform a series of deep optimizations from two points: computation and memory overhead. These optimizations ensure efficient decryption when the plaintext length$\ell $is as long as possible in practice. Moreover, we also provide a concrete implementation and apply$\mathsf {FastECDLP}$to some specific applications. Experimental results show that$\mathsf {FastECDLP}$is far faster than the previous works. For example, the decryption can be done in 0.35 ms with a single thread when$\ell = 40$, which is about 30 times faster than that of Paillier. Furthermore, we experiment with$\ell $from 27 to 54, and the existing works generally only consider$\ell \leq 32$. The decryption only requires 1 second with 16 threads when$\ell = 54$. In the practical applications, we can speed up model training of existing vertical federated learning frameworks by 4 to 14 times. At the same time, the decryption efficiency is accelerated by about 140 times in a blockchain financial system (ESORICS 2021) with the same memory overhead.

Demand forecasting (DF) plays an essential role in supply chain management, as it provides an estimate of the goods that customers are expected to purchase in the foreseeable future. While machine learning techniques are widely used for building DF models, they also become more susceptible to data poisoning attacks. In this article, we study the vulnerability of targeted poisoning attacks for linear regression DF models, where the attacker controls the behavior of forecasting models on a specific target sample without compromising the overall forecasting performance. We devise a gradient-optimization framework for targeted regression poisoning in white-box settings, and further design a regression value manipulation strategy for targeted poisoning in black-box settings. We also discuss some possible countermeasures to defend against our attacks. Extensive experiments are conducted on two real-world datasets with four linear regression models. The results demonstrate that our attacks are very effective, and can achieve a high prediction deviation with control of less than 1% of the training samples.

In this paper, three constructions of balanced Boolean functions with optimal algebraic immunity are proposed. It is checked that, at least for small numbers of input variables, these functions have good behavior against fast algebraic attacks as well. Other cryptographic properties such as algebraic degree and nonlinearity of the constructed functions are also analyzed. Lower bounds on the nonlinearity are proved, which are similar to the best bounds obtained for known Boolean functions resisting algebraic attacks and fast algebraic attacks. Moreover, it is checked that for the numbernof variables with 5 ≤n≤ 19, the proposedn-variable Boolean functions have in fact very good nonlinearity.