Private Set Intersection (PSI) allows two mutually untrusted parties to compute the intersection of their private sets without revealing additional information. In general, PSI operates in a static setting, where the computation is performed only once on the input sets of both parties. Badrinarayanan et al. initiated the study of Updatable PSI (UPSI), which extends this capability to dynamically updating sets, enabling both parties to securely compute the intersection as their sets are modified while incurring significantly less overhead than re-executing a conventional PSI. However, existing UPSI protocols either do not support arbitrary deletion of elements or incur high computational and communication overhead. This work combines asymmetric PSI with Private Set Union (PSU) to present a novel UPSI protocol, which supports arbitrary additions and deletions of elements, offering a flexible approach to update sets. Furthermore, we design a primitive called multi-round OPRF to satisfy the forward security (IEEE TIFS 2024). Our protocol enjoys efficient performance compared to previous work. Specifically, we implement our protocol and compare it against state-of-the-art conventional PSI and UPSI protocols. Experimental results demonstrate that our UPSI protocol achieves up to three orders of magnitude reduction in computational overhead and incurs 190 ∼ 707×less communication overhead than the state-of-the-art UPSI protocol (ASIACRYPT 2024) that supports arbitrary additions and deletions.

Private Set Intersection (PSI) enables us to compute the intersection of private sets without leaking additional data. The state-of-the-art PSI protocol$\mathsf {RR22}$(CCS 2022) is derived from an Oblivious Pseudo-Random Function (OPRF) protocol based on Oblivious Key-Value Stores (OKVS). However, the existing OKVS suffers either low computation efficiency or high encoding redundancy. In this work, we propose a new efficient bucket-based OKVS with only 1% redundancy. The encoding algorithm of our OKVS is 4 to 15 times faster than the recent state-of-the-art OKVS (USENIX Security 2023). Specifically, our OKVS can encode$2^{24}$key-value pairs in only 2.1 to 8.5 seconds, corresponding to 30% to 1% redundancy, while the latter takes about 30 seconds with at least 3%. We can then obtain a new ultra-fast PSI protocol with lower communication from our OKVS in both semi-honest and malicious settings. Furthermore, we implemented our PSI protocol and conducted an extensive evaluation, which shows that it outperforms the existing PSI protocols, such as$\mathsf {KKRT16}$(CCS 2016),$\mathsf {CM20}$(Crypto 2020),$\mathsf {RS21}$(EuroCrypt 2021),$\mathsf {RR22}$(CCS 2022), and$\mathsf {KBM23}$(NDSS 2023). Since our PSI features an ultra-low communication overhead, it has overall advantages for the network environment with a small bandwidth. For example, our PSI takes only about 468 and 476 seconds in semi-honest and malicious settings with the input size of$2^{24}$when the bandwidth is 10 Mbps, while the state-of-the-art$\mathsf {RR22}$requires about 541 and 625 seconds. Our implementation is available onhttps://github.com/ShallMate/fastpsi.

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.

Integrated sensing and communication (ISAC) is a promising technique that simultaneously provides communication and sensing services, thereby attracting significant attention as a hot topic for next wireless systems. Leveraging communication signal echoes for environmental sensing holds significant potential. Channel estimation (CE), being closely related to environmental information, stands to benefit from incorporating this echo sensing. However, despite the promise of ISAC, the utilization of communication signal echo sensing in sensing-assisted CE has not been well explored, hampering the progress in enhancing CE accuracy. To bridge this gap and overcome this challenge, we propose a sensing-aided CE method tailored specifically for vehicle-to-everything (V2X) communication scenarios using orthogonal frequency-division multiplexing (OFDM) modulation, extracting sensing prior information from communication echoes. The proposed scheme employs radar signal processing algorithms to extract sensing parameters from received communication echoes at the base station (BS). Subsequently, the false path suppression is performed to refine these sensing parameters, yielding echo sensing-based prior information reflecting the channel attributes between the target vehicle and the BS. By leveraging this prior information, an echo sensing-aided CE is proposed to fully exploit channel sparsity and bounded characteristics in the delay-Doppler (DD) domain, thereby enhancing CE accuracy. Simulation results demonstrate the effectiveness of the proposed method in rectifying estimation error by using echo sensing information. Notably, the proposed method not only achieves significantly improved CE accuracy compared to classic enhancement methods and deep learning (DL) methods, but also exhibits robustness against the parameter variations.

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.