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.

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.

BACKGROUND: Genomic and other high dimensional analyses often require one to summarize multiple related variables by a single representative. This task is also variously referred to as collapsing, combining, reducing, or aggregating variables. Examples include summarizing several probe measurements corresponding to a single gene, representing the expression profiles of a co-expression module by a single expression profile, and aggregating cell-type marker information to de-convolute expression data. Several standard statistical summary techniques can be used, but network methods also provide useful alternative methods to find representatives. Currently few collapsing functions are developed and widely applied. RESULTS: We introduce the R function collapseRows that implements several collapsing methods and evaluate its performance in three applications. First, we study a crucial step of the meta-analysis of microarray data: the merging of independent gene expression data sets, which may have been measured on different platforms. Toward this end, we collapse multiple microarray probes for a single gene and then merge the data by gene identifier. We find that choosing the probe with the highest average expression leads to best between-study consistency. Second, we study methods for summarizing the gene expression profiles of a co-expression module. Several gene co-expression network analysis applications show that the optimal collapsing strategy depends on the analysis goal. Third, we study aggregating the information of cell type marker genes when the aim is to predict the abundance of cell types in a tissue sample based on gene expression data ("expression deconvolution"). We apply different collapsing methods to predict cell type abundances in peripheral human blood and in mixtures of blood cell lines. Interestingly, the most accurate prediction method involves choosing the most highly connected "hub" marker gene. Finally, to facilitate biological interpretation of collapsed gene lists, we introduce the function userListEnrichment, which assesses the enrichment of gene lists for known brain and blood cell type markers, and for other published biological pathways. CONCLUSIONS: The R function collapseRows implements several standard and network-based collapsing methods. In various genomic applications we provide evidence that both types of methods are robust and biologically relevant tools.