Scalable and Privacy-Preserving Federated Principal Component Analysis

Introduction

Principal component analysis (PCA) is an algorithm for analyzing a high-dimensional dataset, represented as a matrix of samples (rows) by features (columns), to uncover a small set of orthogonal directions—principal components (PCs)—that together maximally capture the observed variance among the data samples. Given the ability of PCA to reduce the dimensionality of a dataset while preserving its information content, it is commonly used in many data analysis workflows, including predictive modeling and exploratory data analysis (e.g., clustering and data visualization) . PCA is also a common pre-processing technique in machine learning (ML) pipelines, where the goal is to reduce the number of features to avoid overfitting and improve generalization performance . While more sophisticated non-linear dimension-reduction approaches have been proposed (e.g., based on autoencoders ), PCA remains the de-facto standard method for dimension reduction, as it is computationally efficient, theoretically well-understood, and reliably accurate .

Many modern applications of PCA involve data from individuals, raising privacy-related challenges that limit the availability of data for such analyses. In the biomedical domain, the high-dimensional nature of biomedical measurements often necessitate the use of PCA to extract key features from personal data, including genetic sequences , single-cell transcriptomic data , medical images and time-series data . PCA is also commonly used in other domains involving personal data, including quantitative finance and recommender systems . Due to the privacy and security implications, the sharing of personal data in these domains is often prohibited, rendering the data analysis difficult or even impossible. This results in sensitive data remaining siloed in access-controlled repositories and not shared across organizations, which often hinders research, innovation, and routine organizational tasks .

Federated privacy-preserving analytics, which aims to facilitate the joint analysis of sensitive data held by multiple parties using privacy-enhancing technologies , has emerged as a promising solution to the aforementioned challenges with the potential to overcome regulatory barriers in data sharing . Despite the growing interest, many essential tools for data analysis including the PCA, especially those upstream of widely studied tasks such as model training and inference, have received limited interests and are often omitted from federated workflows. This creates an important gap in secure analytics, potentially undermining their security or utility if one falls back on a non-secure or less-accurate alternative in order to perform the full analysis.

A key challenge in developing a secure federated solution for PCA is that it requires complex and iterative computations (e.g. matrix factorization), which are costly given a large-scale input. These operations are not directly amenable to efficient computation with generic cryptographic techniques . Reflecting this difficulty, many existing federated solutions , propose that the data providers (DPs) independently perform an initial dimension reduction on their local data, before they combine their intermediate results and execute the final decomposition on the merged results. This approach, which we refer to as meta-analysis, results in a loss of accuracy as it alters the original PCA problem and is prone to overlooking patterns spanning multiple DPs’ datasets, especially when the data distributions differ among the DPs. Furthermore, most meta-analysis solutions require the DPs’ intermediate results to be revealed to an aggregator server (or to other DPs) hence are not end-to-end secure. Other existing PCA solutions based on secure multiparty computation (SMC) techniques require the entire input data to be securely shared with a few computing servers. With the high communication overhead of SMC, these solutions have difficulty supporting a large number of parties.

In this paper, we propose an efficient and secure system for performing a federated PCA on a distributed dataset, where the data remains protected and locally stored by the respective DPs. Our solution, named sf-pca (for Secure Federated PCA), executes the randomized PCA (RPCA) algorithm , the de facto standard for PCA on large-scale matrices, in a federated manner using a multiparty extension of homomorphic encryption . Contrary to meta-analysis solutions, sf-pca directly executes a standard PCA algorithm (i.e., RPCA) to achieve state-of-the-art accuracy similar to a centralized analysis, while ensuring end-to-end privacy by protecting even the intermediate results. Unlike SMC solutions, sf-pca is more communication-efficient and can be used by a large number of DPs. Note that our setting is related to cross-silo federated learning , except we do not focus on predictive model training and we use cryptographic techniques to provide end-to-end privacy.

Specifically, sf-pca is built upon the cryptographic framework of multiparty homomorphic encryption (MHE; see §.1). In MHE, analogous to related works on threshold HE , the collective secret (or decryption) key is secret-shared among all the DPs, and the corresponding public key and additional evaluation keys required for homomorphic operations are known by all DPs. This ensures that, while encryption and ciphertext computations can be independently performed by each DP, decrypting ciphertexts requires all DPs to collaborate . MHE’s ability to offload certain computations to be locally performed by each party using the cleartext data leads to key performance improvements, as we show in our work. Performing a compute-intensive algorithm like RPCA, which involves sophisticated linear algebra operations (e.g., orthogonalization and eigendecomposition) on input vectors and matrices of a wide range of dimensions, while efficiently working within the constraints of MHE and maximally exploiting its strengths is the key challenge we address in sf-pca by introducing optimization strategies and efficient MHE linear algebra routines.

Our evaluation demonstrates the practical performance of sf-pca on six real datasets. For example, sf-pca securely computes five PCs on the MNIST dataset with 60,000 samples and 760 features, split among six DPs, in 2.22 hours. In the same setting, it obtains the two PCs from a lung cancer dataset with 9,098 patients and 23,724 genomic features in 3.5 hours. sf-pca scales at most linearly with the input dimensions and with the number of DPs. sf-pca is one to two orders of magnitude faster than a centralized-HE solution. It is up to ten times faster than existing SMC solutions , which scale poorly with the number of DPs. We also show that sf-pca is highly accurate, resulting in Pearson correlation coefficients of above 0.9 (compared to the ground truth) in all settings, whereas meta-analysis often obtains inaccurate results (e.g., a correlation below 0.75 for both datasets mentioned above). Moreover, sf-pca executes PCA while ensuring end-to-end data confidentiality as long as one DP is honest, whereas meta-analysis reveals the intermediate results to the aggregator server. Both centralized-HE and the previous SMC solution require an honest third-party to hold the decryption key or to distribute correlated randomness for efficiency, respectively.

In this work, we make the following contributions:

We propose sf-pca, a system for an efficient, federated, and end-to-end confidential execution of PCA .

We demonstrate key design strategies underlying the practical performance of sf-pca, including: (i) maximizing operations on the DPs’ cleartext local data by restructuring the computation and (ii) developing efficient linear algebra routines under a consistent vectorized encoding scheme for encrypted matrices to fully utilize the packing and single-instruction multiple-data (SIMD) property of MHE without costly encoding conversion.

We introduce an adaptive approach for choosing both the high-level computational approach for PCA and the low-level MHE routines to maximize efficiency, based on the input dimensions for each computational step.

We propose efficient MHE-based algorithms for sophisticated linear algebra operations on encrypted matrices, including matrix multiplication, factorization, and orthogonalization, in the federated setting.

We demonstrate the practical performance of sf-pca on six real datasets and illustrate its utility for biomedical data analysis. We show that sf-pca is more scalable than existing solutions for privacy-preserving PCA while producing accurate results comparable to a centralized execution of PCA regardless of the data distribution among the parties.

To the best of our knowledge, sf-pca is the first system to enable federated PCA in a scalable and end-to-end confidential manner. We note that sf-pca’s optimization strategies and linear algebra building blocks are broadly applicable to the development of secure federated algorithms and thus are of independent interest.

Related Work

We discuss prior works on linear algebra in HE and on distributed HE schemes, two essential components of sf-pca (§.6).

HE for Linear Algebra. Multiple works have shown how to optimize matrix-vector multiplications and multiplications between small matrices (i.e., fitting in a single ciphertext) . Multiplication of large encrypted matrices, whose rows do not fit into single ciphertexts, has been less studied. PCA requires multiple types of multiplications involving large matrices of varying dimensions, and efficiently performing these operations under encryption is key to achieving practical performance. sf-pca jointly leverages a range of matrix multiplication methods whose complexities scale differently with the input dimensions, making an adaptive choice for each computational step in RPCA (§.6.1).

Distributed HE. When multiple parties use HE to combine their private data, they can either share all of their data encrypted under the same key held by a trusted entity (e.g., in a centralized scheme ), or adopt a distributed scheme where no single entity holds the decryption key. In threshold encryption schemes , the encryption key is known to all parties whereas the decryption key is secret-shared among the parties such that a predefined number of them must collaborate to decrypt a ciphertext. In multi-key schemes (including a hybrid with threshold schemes ), the parties have their own key pair and can jointly compute on data encrypted under different keys, but the complexity scales with the number of parties. In sf-pca, we rely on a multiparty HE scheme (MHE) proposed by Mouchet et al. , which corresponds to an $s$-out-of-$s$ threshold scheme. This scheme enables local computation with complexity independent of the number of parties and provides a lightweight, interactive protocol to refresh (bootstrap) a ciphertext—a key factor for sf-pca’s efficiency in contrast to alternative approaches (see §.5).

2 Principal Component Analysis (PCA)

Secure Centralized PCA. Few solutions have been proposed for the secure centralized computation of PCA due to its computational complexity. Pereiral and Aranhal proposed a method for performing PCA on an encrypted dataset using homomorphic encryption (HE). HE-based solutions typically incur a high computational overhead compared to their cleartext counterparts. In addition, they require a costly centralization of the data and have a single point-of-failure, i.e., the holder of the decryption key. In sf-pca, since the exchanged data are encrypted with a collective key, no single entity can decrypt them, and compute-intensive HE operations (e.g., bootstrapping) are replaced by lightweight interactive protocols. In §.7.6, we compare sf-pca with an HE-based centralized solution.

Non-Secure Federated PCA. Solutions that enable PCA on distributed data without privacy protection fall in two main categories: iterative and non-iterative . In the former, the DPs communicate and collaborate in order to perform each step of the algorithm. In the latter, the DPs perform the decomposition locally and then merge their results; we also refer to this approach as meta-analysis. Meta-analysis requires less communication but introduces inaccuracies by approximating PCA with two levels of decomposition, i.e., an independent local decomposition by each DP and a global one for the merged results. These solutions typically require that the local data distribution be consistent across DPs to obtain accurate results. In addition, they are not end-to-end secure as they require the DPs’ intermediate results to be revealed to an aggregator server (or to other DPs), representing a single point of failure. Intermediate results have been shown to reveal information about the original data in federated settings, e.g., in PCA and ML . In contrast, sf-pca implicitly performs RPCA on the joint data without altering the original approach, thus obtaining accurate results independently of the data distribution among the DPs (§.7). It also keeps all the exchanged information secret and does not rely on an aggregator server.

SMC-based PCA. Several solutions leverage secure multiparty computation (SMC) to perform PCA on data that are secret-shared among a limited number of parties (e.g., three). These solutions require the data to be outsourced to computing parties, incurring a high communication overhead for large datasets. Unlike SMC solutions, sf-pca can be efficiently used by a large number of parties, and their data are kept locally with a minimal amount of encrypted information exchanged for the PCA computation. In §.8, we discuss an extension of sf-pca where SMC techniques are integrated into our system to aid in carrying out non-polynomial function evaluations on small-dimensional inputs.

HE-based PCA. To our knowledge, Liu et al. proposed the only existing homomorphic encryption (HE)-based solution for federated PCA. However, they rely on an aggregator server that decrypts the aggregated values at each step of the process. Since the intermediate results can reveal information about the parties’ local data, these methods are not end-to-end secure. sf-pca demonstrates that a fully decentralized and end-to-end secure solution for PCA is practically feasible.

Differential Privacy-based PCA. Solutions based on differential privacy fundamentally differ from sf-pca in that their goal is to limit the privacy leakage of the intermediate or final results. To achieve this goal, these solutions introduce noise into the computation, making the final results less accurate. Furthermore, analogous to meta-analysis, some of these solutions rely on a local decomposition followed by a global aggregation of results, introducing an approximation error in addition to the noise added for differential privacy. In sf-pca, no intermediate result is revealed, hence differential privacy is not needed to protect the information exchanged during the algorithm. On the other hand, if the DPs wish to reveal the final PCA result with differential privacy, such guarantee can be added to sf-pca (§.8).

Background

Multiparty Homomorphic Encryption (MHE). To securely perform PCA across distributed datasets, we rely on a multiparty (or distributed) fully-homomorphic encryption scheme in which the secret key $sk$ is shared among the parties via a secret-sharing scheme, whereas the corresponding collective public key $pk$ is known to all of them. As a result, each party can independently compute on ciphertexts encrypted under $pk$, but all parties have to collaborate to decrypt a ciphertext.

$pk,evks\xleftarrow{}\text{DKeyGen}(\{sk_{i}\})$ generates the collective public key $pk$ and evaluation keys $evks$, which are required for ciphertext transformations such as rotations. The DPs aggregate the local shares of keys (randomly generated based on a public source of randomness) to obtain public collective keys .

$\bm{c}$ $\xleftarrow{}\text{DBootstrap}(\bm{c}^{\prime},\ \{sk_{i}\})$ collectively refreshes a ciphertext to obtain a fresh encryption. This operation is required after every $\lambda$ multiplications to ensure a correct decryption.

$\bm{c}_{pk^{\prime}}\xleftarrow{}\text{DKeySwitch}(\bm{c},\ pk^{\prime},\ \{sk_{i}\})$ changes the encryption of a ciphertext $\bm{c}$ from the public key $pk$ to another public key $pk^{\prime}$, without decrypting the ciphertext. The collective decryption is a special case of this operation (i.e., $\text{DKeySwitch}(\bm{c},\emptyset,\{sk_{i}\})$). To prevent information leakage upon decryption , a fresh noise with a variance larger than that of the ciphertext is added before decryption .

Each DP can independently encrypt, and perform the following operations listed in order of increasing computational complexity (Tab. II):

$\bm{c}^{\prime\prime}=\bm{c}$ + $\bm{c}^{\prime}$, addition of encrypted vectors.

$\bm{c}^{\prime\prime}=\bm{c}\cdot\bm{c^{\prime}}$, element-wise multiplication of two encrypted vectors. The result needs to be relinearized and rescaled to maintain ciphertext size and scale.

$\bm{c}^{\prime}=\text{Rot}_{y}(\bm{c},evks)$, cyclic rotation of length $y$ to the left (to the right if $y$ is negative) on the encrypted vector $\bm{c}$.

$\bm{c}^{\prime\prime}=\bm{c}\bullet\bm{c}^{\prime}$, dot product of two encrypted vectors. The result is encoded in the first position of a one-hot encoded vector $\bm{c}^{\prime\prime}$.

$\bm{c}^{\prime}=\text{Dup}_{y}(\bm{c})$, duplication of the first element of $\bm{c}$ to the first $y$ positions of $\bm{c}^{\prime}$ with $\lceil\log_{2}(y)\rceil$ rotations and additions.

SF-PCA System and Security Models

sf-pca enables the DPs to collaboratively execute a randomized PCA on their joint data. In the end, each DP obtains $\psi$ collectively encrypted PCs, on which each DP can locally project its data. If required by the application, each DP’s projected data (encrypted under the collective key) can be collectively switched (DKeySwitch, §.1) to each DP’s public key $pk_{i}$ to be locally decrypted. Similarly, the PCs can be collectively decrypted and shared among the DPs.

We adopt the semi-honest model, where the DPs follow the protocol as specified, but might try to infer information about another DP’s data, potentially colluding with other DPs. We require that the DPs’ data and all intermediate results remain confidential. In other words, sf-pca provides input confidentiality, i.e., no DP is able to learn any information about any other DP’s local data other than what it can infer from the final output of PCA (e.g., its projected local data). We require that this property holds as long as one DP remains honest and does not collude with others.

SF-PCA Protocol Design

We introduce an end-to-end confidential and federated approach to execute a RPCA (§.3) jointly over $s$ DPs holding their local data. At each step of the PCA execution, the DPs collectively compute encrypted global intermediate results through interactive protocols that combine the results of local computation on each DP’s cleartext data. The intermediate results remain encrypted under the DPs’ collective key and are never revealed. While our system’s ability to leverage local cleartext computation opens the door to efficient multiparty algorithms, a careful algorithmic design is still necessary for developing a practical PCA protocol.

Leveraging existing approaches for secure computation (e.g., HE or SMC), the DPs could outsource their encrypted (or secret-shared) data to one or multiple computing parties to jointly perform the PCA. However, the communication overhead of sharing the entire dataset as well as the computational burden of performing complex computations (e.g., multiplication and factorization of matrices) on the pooled dataset render these solutions impractical for large-scale datasets. Note that the repeated matrix multiplications are challenging to perform efficiently under HE due to the costly bootstrapping procedure. sf-pca addresses these challenges by introducing efficient MHE-based protocols based on a federated approach to joint computation. We compare sf-pca’s performance with existing approaches in §.7.

Obtaining Accurate Results by Emulating Centralized PCA. Existing federated approaches to PCA that combine the results independently obtained by the DPs (e.g., meta-analysis), are prone to errors introduced by differences in data distribution among the DPs. In sf-pca, we avoid this pitfall by securely combining the intermediate results at each step of the protocol (via collective aggregation $\Xi$ in Alg.1) to emulate a centralized analysis, thus obtaining the same PCs regardless of how the data are split (§.7.7).

Optimized Data Encoding for Linear Algebra on Encrypted Matrices. The secure execution of RPCA requires that the DPs iteratively perform various matrix operations on encrypted data, including multiplication and factorization. For example, the QR factorization, which is repeatedly executed in-between matrix multiplications (in Steps 4, 6, and 7 of RPCA; Fig. 1), is performed over the rows of an encrypted matrix in sf-pca. Selecting a row in a matrix of $m$ columns, where the columns are individually packed in ciphertexts, would require $m$ homomorphic multiplications, additions, and rotations; in contrast, row selection incurs no cost when the matrix is row-wise encoded. In fact, the overwhelming cost of transforming encrypted matrices from one encoding to another would make our system impractical. We therefore adopt a consistent vectorized encoding scheme throughout the algorithm to represent encrypted matrices and tailor the operations to efficiently work with this format without costly conversions. This also allows sf-pca to fully utilize the packing and SIMD properties of MHE thus minimizing its overall computation and communication costs.

Selective Bootstrapping to Minimize Communication. After a certain number of multiplications, a ciphertext needs to be bootstrapped (DBootstrap, §.1) to restore its capacity for computation. In sf-pca, this is a collective operation, which is computationally lightweight in contrast to its centralized equivalent, but requires the ciphertext to be exchanged among all DPs. To further minimize this communication overhead, we restrict the invocation of DBootstrap to places where an intermediate result is already globally synced and of a small dimension (e.g., during QR factorization in Steps 4 and 7 in Alg. 1; see §.6.2), while flexibly allowing a ciphertext to be bootstrapped even if some multiplication capacity remains.

2 Workflow Details

We describe the workflow of sf-pca from the point of view of DPi in Alg. 1. Recall that the DPs aim to compute $\psi$ encrypted PCs (rows of matrix $\bm{W}$) on their joint data. RPCA identifies $\rho=\psi+\alpha$ components with a small oversampling parameter $\alpha$ for improved accuracy. In addition to Alg. 1, we show in Fig. 8 in the Appendix how the matrix dimensions evolve in sf-pca’s workflow. The DPs interact by aggregating (represented by $\Xi$) encrypted matrices and broadcasting the encrypted result to all DPs.

Step 4: Power Iterations. The sketch of the input matrix obtained in the previous step is repeatedly multiplied with the input matrix to increase the spectral gap between the top eigenvectors of interest and the rest . We execute this step differently depending on the input dimensions for optimized performance; the two approaches considered by sf-pca are described below. Notably, in both approaches, we leverage the fact that the cost of cleartext operations is almost negligible compared to that of HE to optimize the computation.

Step 6: Eigendecomposition. The eigendecomposition (introduced in §.3) is executed on the encrypted matrix $\bm{Z}$. We detail our MHE-based algorithm for this step in Alg. 4. It requires the iterative execution of QRT and matrix multiplications.

Step 7: Reconstruction. The PCs (rows of $\bm{W}$) are computed by multiplying the eigenvectors from Step 6 with the approximated subspace from Step 3, followed by a final round of power iteration and orthogonalization (QRT) for numerical stability.

Optimized Routines for Linear Algebra and Non-Polynomial Functions on Encrypted Data

We describe how sf-pca efficiently executes matrix multiplications, sophisticated linear-algebra transformations and non-polynomial function evaluations on encrypted data. Although the methods in this section can also be employed in the centralized setting, we note that the adaptive use of matrix multiplication routines and the higher-level protocols for matrix transformations (e.g., QR factorization) are optimized while accounting for the unique properties of MHE, e.g., the availability of local cleartext data and a lightweight interactive bootstrapping routine, both of which alter the tradeoff between different computational strategies and present new ways to optimize the algorithm. Our secure federated routines may be of independent interest for other applications.

Encrypted matrix multiplications are frequently invoked in sf-pca’s workflow and hence are a key determinant of its performance. As outlined in Alg. 1, we introduce two high-level algorithmic workflows—Precomp and Seq—for executing RPCA. Both approaches involve different types of multiplications over matrices of varying dimensions, motivating our adaptive strategy for choosing the most efficient routine for each computational step in sf-pca among a range of multiplication methods.

We identify two main types of matrix multiplications in Alg. 1: (i) unbalanced multiplications between a large encrypted matrix and a large cleartext (or pre-transformed encrypted) matrix in Steps 4, 7 and 8, with the key property that operations are cheap on one matrix (cleartext) and expensive on the other (ciphertext); and (ii) duplicated-vector multiplications, referring to multiplications between a large encrypted matrix and another encrypted matrix whose rows (or columns) are identical (e.g., corresponding to the encrypted mean vector $\bm{o}$).

We identify the matrix multiplication costs of Precomp and Seq for a single iteration as $\zeta^{*}_{\text{M}}(\rho,m,m)$ and $\zeta^{*}_{\text{M}}(\rho,m,n_{\max})+\zeta^{*}_{\text{M}}(\rho,n_{\max},m)$, respectively, where $\rho$ is the number of reduced dimensions in RPCA, $m$ is the number of input features, and $n_{\max}=\max_{i}(n_{i})$ represents the largest number of samples locally held by the DPs. We consider the worst-case complexity as the overall runtime being as fast as the slowest DP. In addition, for both approaches, we incorporate the cost of lazy mean-centering when comparing the overall cost; Precomp requires $3b$ Mults and $b$ Rots, whereas Seq requires two duplicated-vector multiplications, which we detail in §.6.1.3. We further compare these approaches in §.7.

1.2 Unbalanced Multiplications

We describe the HE implementations of three matrix multiplication strategies: Dot-Product Method (M6.1.2), Element-Duplication Method (M6.1.2), and Diagonal Method (M6.1.2; adapted from Jiang et al. ). We jointly consider these three methods because their costs scale differently with the input dimensions, enabling sf-pca to optimize its performance in a wide range of scenarios. For each method, we show its cost in terms of the invocations of ciphertext rotations (Rots) and multiplications (Mults) for multiplying a pair of $a\times b$ and $b\times c$ matrices. The cost of cleartext operations is negligible. To simplify the computational complexity analysis, we assume that $b$ and $c$ are powers of two without loss of generality. We denote by $t$ the ciphertext capacity, i.e., the number of values that can be packed in a ciphertext. Due to sf-pca’s vectorized encoding, the inner dimension $b$ reduces to a small constant $\lceil\frac{b}{t}\rceil$ in terms of the number of ciphertext operations.

1.3 Duplicated-Vector Multiplications

This method addresses a special setting where we multiply an encrypted matrix $\bm{M}$ with another encrypted matrix $\bm{\Gamma}$ whose rows (Case 1) or columns (Case 2) are identical vectors $\bm{\mu}$. This setting frequently arises in sf-pca for the lazy mean-centering operations (i.e., all operations involving $\bm{o}$ in §.5.2). Our method accounts for this redundancy in the matrix to minimize the number of rotations on both encrypted matrices.

1.4 Further Optimizations

2 Matrix Transformations and Factorizations

We introduce new routines for executing sophisticated linear algebra operations required by the PCA on encrypted matrices and vectors. We begin with the Householder transformation , a key building block in other matrix transformations such as QRT and Eigen, which we subsequently describe. We also present a new algorithm, DQRT, for executing a QR factorization on a matrix that is distributed among multiple parties. Note that all methods except DQRT require communication only for bootstrapping (DBootstrap; §.1), which has a negligible computation cost. The reported communication costs are thus measured by our optimized number of invocations of bootstrapping on a single ciphertext.

Alg. 2 requires the evaluation of non-polynomial functions, including the sign function (alternatively, $g(x)$ = $x/\sqrt{x^{2}}$, Line 4), the square root, and the inverse square root. To this end, sf-pca applies Chebyshev polynomial approximation to each function on a pre-determined input range (agreed upon in Step 1; §.5.2). In addition, we use the baby-step giant-step technique to further reduce the complexity of evaluating degree-$d$ polynomials, resulting in a multiplicative depth of $\lceil\log{(d)}+1\rceil$ and $2\cdot\sqrt{2d}+\frac{1}{2}\log_{2}{(d)}+\mathcal{O}(1)$ ciphertext multiplications. We denote this quantity as $l(d)$ in our algorithms. We discuss the choice of approximation intervals in §.6.3. For the communication cost, we calculate the number of DBootstrap executions as the multiplicative depth of this method divided by the number of available ciphertext levels $\lambda$ (§.1).

QR Factorization of Encrypted Matrices. QR factorization decomposes an input matrix $\bm{V}$ into an orthogonal matrix $\bm{Q}$ and a lower-triangular matrix $\bm{R}$ such that $\bm{V}=\bm{R}\times\bm{Q}$. This is repeatedly used in Steps 4, 6 and 7 of sf-pca’s workflow. In Alg. 3, we describe both the transposed-QR factorization QRT that is executed by one DP on an encrypted matrix and its distributed equivalent DQRT. DQRT performs a QR factorization in a federated manner on an encrypted matrix that is distributed among the DPs, requiring the DPs to aggregate (denoted by $\Xi$) their partial results in Lines 3, 5, and 18. In Step 4 of sf-pca, QRT is executed on a matrix with $h=m$ columns (i.e., same as the number of features), whereas DQRT is executed on a matrix with $h=n$ columns distributed among the DPs, where each DPi has $n_{i}$ columns. HH and the vector-matrix multiplications in Lines 5 and 18 are the only operations with a cost that depends on $h$. DQRT requires more communication among the parties, and the complexity of QR factorization depends mainly on the number of rows $\delta$, which is the same in both QRT and DQRT, and not on $h$. Hence, we use DQRT only when the difference between $n_{i}$ and $m$ is large enough to compensate for the communication overhead, i.e., when $\xi\cdot\log_{2}{(n_{\max})}<\log_{2}{(m)}$, with a factor $\xi$ determined by the properties of the network setup (e.g., latency). Note that $n_{\max}=\max_{i}(n_{i})$.

Recall that we minimize bootstrapping by refreshing only small-dimensional data that are globally shared among the DPs (§.5). The intermediate values in QRT satisfy this condition as they are derived from the input matrix that is already aggregated. Hence, the optimized number of invocations of DBootstrap($\cdot$) for QRT corresponds to its multiplicative depth divided by $\lambda$. For DQRT, the input matrix is split among the DPs. In this case, the results of the collective aggregation ($\Xi$) in Lines 5 and 18, which constitute globally shared vectors among the DPs, are bootstrapped before being broadcast (shown as the additional cost).

Eigendecomposition of Encrypted Matrices. Alg. 4 decomposes an encrypted matrix $\bm{M}$ into $\bm{Q}\times\bm{L}\times\bm{Q}^{T}$, where $\bm{Q}$ is a matrix of eigenvectors and $\bm{L}$ is a diagonal matrix with the diagonal defined by the encrypted vector of eigenvalues $\bm{l}$. The eigenvalues are ordered from the largest to the smallest. We adapt the standard QR iteration algorithm to the setting with an encrypted input matrix. The encrypted matrix is first tridiagonalized, i.e., transformed to a matrix where the only nonzero elements are in the diagonal, the subdiagonal, or the superdiagonal, which is known to improve the convergence rate of eigendecomposition . The tridiagonalization is achieved by applying Householder transformations (using Alg. 2) to different subparts of the matrix to introduce zeros (Lines 2 to 11 in Alg. 4). The resulting encrypted matrix $\bm{T}$ is then iteratively factorized using QRT (Line 17) into $\bm{R}\times\bm{Q^{\prime}}$ (note the row-wise application of QR) and reconstructed as $\bm{Q^{\prime}}\times\bm{R}$ to gradually transform the matrix into a diagonal matrix. During this process, the last diagonal element converges to the smallest eigenvalue of the input. This is then executed for each eigenvalue in an ascending order, and the corresponding eigenvectors are obtained from the product of all $\bm{Q^{\prime}}$ matrices. We perform all small-matrix multiplications (Lines 6, 7, 8, 18) by encoding each matrix in a single ciphertext and employing the technique of Jiang et al. . We refer to this method as M5 to distinguish from the large-scale, unbalanced setting in M3 with ciphertext-cleartext multiplications. Multiplying two $s\times s$ encrypted matrices requires $5s$ Mults and $3s+5\sqrt{s}$ Rots. We convert the matrices to our row-wise encoding scheme (in Lines 6, 9, 10, 12, 15, 17, 20, 22, 23) using one multiplication and one rotation per row, only to efficiently perform row and column selections. Similarly as Alg. 3, this method operates on globally shared inputs, and its optimized communication cost scales with the multiplicative depth divided by $\lambda$, in addition to the costs of the HH and QRT subroutines.

3 Non-Polynomial Functions on Encrypted Inputs

To approximate non-polynomial functions on chosen intervals, sf-pca’s default approach is to rely on homomorphic evaluations of Chebyshev polynomial approximations . In Step 1 (Alg. 1), the DPs agree on the intervals and on the degree of the approximations. The complexity of the polynomial evaluation increases with the degree but is independent of the interval size, which influences the precision. While any interval selection approach may be used with sf-pca, the approach we adopt in our evaluation in §.7 is for a DP (e.g., the one coordinating the collaboration or the one with the highest number of local samples) to set the intervals based on the estimated range of intermediate values to be encountered by running RPCA on a simulated dataset, obtained by upsampling its local data to match the size of the joint data. In §.8, we discuss an extension to sf-pca that enables it to switch to secret sharing for the evaluation of non-polynomial functions, for which efficient bit-wise protocols exist for scaling the input to a common range for approximation. This effectively removes the need to choose intervals and, depending on the parameters, can further improve sf-pca’s accuracy (Appendix D.1).

System Evaluation

We show that sf-pca, enabled by our optimization techniques (§.5), efficiently computes a PCA on high-dimensional inputs distributed among a large number of DPs. We demonstrate sf-pca’s practicality and accuracy on various datasets with the number of features ranging from 8 to 23,724 and including up to 60,000 samples. sf-pca consistently obtains PCs that are highly similar ($r^{2}>0.9$) to those obtained by a standard non-secure PCA. sf-pca also outperforms alternative privacy-preserving approaches in terms of accuracy and runtime, and offers stronger security guarantees compared to some. In §.7.7, we show that, contrarily to meta-analysis, sf-pca remains accurate regardless of potential differences in the data distribution among the DPs.

sf-pca’s communication cost depends mainly on the number of features $m$, the number of components $\rho$ and the number of power iterations $p$. sf-pca’s computation cost depends on the same parameters and optionally on the number of samples per DP $n_{i}$. For both, the overall cost is amortized over the ciphertexts due to packing and the SIMD property of HE, effectively dividing the contributions of $m$ and $n_{i}$ to the complexity by the ciphertext capacity $t$. In Tab. I, we show the theoretical costs for a single DP (DPi) for each step in sf-pca (Alg. 1).

The communication in Step 1 is due to the generation of the public key $pk$ and evaluation keys $evks$ (including a relinearization key and $\log_{2}(t)$ rotation keys). All rotations in sf-pca are executed by combining rotations of power-of-two shifts using the pre-generated keys. DBootstrap requires each DP to transmit and receive the equivalent of a ciphertext, and to perform one ciphertext addition (at a negligible cost). In the remaining steps, we analyze the communication cost in terms of the number of DBootstrap invocations, which depends on the cryptographic parameters and the number of multiplications to perform in each routine (§.6.2). In turn, the number of multiplications depends on the input dimensions, the degree of polynomial approximations and, for Eigen, the number of iterations $w$.

sf-pca’s overall communication cost is independent of the number of samples and is dominated by the bootstrapping execution. We optimize the performance of sf-pca by selecting the computation approach with the lowest complexity, e.g., by choosing Precomp (whose complexity is independent of $n_{i}$) if the number of samples is large.

2 Implementation Details and Evaluation Settings

We implemented sf-pca in Go , building upon Lattigo and Onet , which are open-source Go libraries for lattice-based cryptography and decentralized system development, respectively. The communication between DPs is through secure TCP channels (using TLS). We evaluate our prototype based on a realistic network emulated using Mininet , with a bandwidth of 1 Gbps and a communication delay of 20ms between every two nodes. Unless otherwise stated, we uniformly and horizontally distribute the input data among 6 DPs. We deploy each DP on a separate Linux machine with Intel Xeon E5-2680 v3 CPUs running at 2.5 GHz with 24 threads on 12 cores and 256 GB of RAM. We provide the default system parameters of sf-pca considered in our evaluation in Appendix B.

3 Microbenchmarks for MHE Protocols in sf-pca

In Tab. II, we summarize the runtimes for sf-pca’s main ciphertext operations as well as high-level linear algebra routines. Recall that each ciphertext contains up to $t=2^{13}$ values and any operation is concurrently executed on all encrypted values. Multiplying a cleartext with a ciphertext is almost 8x faster than multiplying two ciphertexts with the default parameters. The transmission time of a ciphertext (Send($c$)) depends mostly on the communication delay (20ms in our setting). In our default setting, DKeyGen takes 9 seconds to generate the public key, relinearization key, and 13 rotations keys.

4 Practical Scalability of sf-pca Performance

We evaluated sf-pca’s scalability on simulated datasets of varying sizes. In Fig. 3, we show that sf-pca’s runtime (when computing eight PCs with ten power iterations) remains almost constant when the dimensions are smaller than the ciphertext capacity $t$ (set to 8,192 by default). It then grows linearly with the number of ciphertexts, i.e., with the number of features ($m$) and samples per DP ($n_{i}$) divided by $t$. Note that, since the protocol is synced among the DPs at each aggregation step, sf-pca’s runtime depends on the slowest DP, e.g., the DP with the largest local dataset, as shown in Fig. 3 and Fig. 7c in appendix. In all figures, we omit the negligible execution times of Steps 1 to 3. These steps require mostly non-iterative cleartext operations. In Fig. 3 (left panel), we set $n_{i}=1,024$ and show that all sf-pca’s approaches (i.e., Precomp and Seq with QRT or DQRT) similarly scale linearly with $m$. Precomp is the most efficient approach for this range of values for $m$ and $n=6,144$ but becomes impractical with a large $m$. In these experiments, we found DQRT to be consistently inferior to QRT as the former’s communication overhead overshadows its computational speedup. This is expected, since the computational gain of using DQRT depends on how much smaller $n_{i}$ is with respect to $m$ (see §.6.2). This difference is never large enough to compensate for the communication overhead in our settings. The results in Fig. 3 (right panel), for which $m$ is set to 256, show that sf-pca’s runtime remains constant when using Precomp, which does not depend on the number of samples.

We remark that sf-pca’s runtime is dominated by the time dedicated to the communication between the DPs (Fig. 4). The communication overhead ranges between 90% of the runtime with small input dimensions, i.e., when the packing capacity of the cryptoscheme is less exploited, and 45% of the runtime when the dimensions are equal or larger than $t$. Although sf-pca is able to minimize its computation runtime with optimized federated and parallelized computation methods, its communication overhead is bounded by the available communication network. When the number of DPs ($s$) doubles, sf-pca’s runtime increases only by a factor of around 1.1. This is because the amount of local computation does not grow with $s$ (Table I) and because the cost of interactive routines only slightly increases with $s$. Based on Fig. 4, we estimate practical runtimes even for hundreds of DPs, e.g., 110 minutes for 200 DPs with a maximum of 1,024 data samples per DP. We discuss in §.8 how sf-pca can be extended to handle availability issues given many DPs. In Fig. 4, sf-pca’s runtime grows linearly with the number of components in all its steps except in Step 6, where the eigendecomposition cost depends on the small matrix dimensions: $\rho\times\rho$. sf-pca’s runtime increases linearly with the number of power iterations; however, this parameter typically does not grow with the data size for RPCA.

In our default scenario, sf-pca’s runtime is multiplied by a small factor of 1.1x when the available bandwidth is halved and the communication delay doubled. Moreover, each ciphertext accounts for 2.5 MB, thus executing sf-pca on a dataset with 8,192 features (or less) requires each DP to send 3.8 GB, independently of the number of samples $n$ (which can be large).

5 Accuracy of SF-PCA Results

We demonstrate sf-pca’s accuracy and practicality on six real datasets, including MNIST and two genomic datasets with thousands of patients and up to 23,724 features (see Appendix E for dataset details). We evenly and randomly split each dataset among the DPs. In §.7.7, we show that sf-pca computes the same results regardless of the data distribution among the DPs. In Tab. 5, we show that sf-pca and the cleartext non-secure centralized Randomized PCA (RPCA, Fig. 1) achieve similar accuracy (according to the mean-squared error, MSE; and Pearson Correlation Coefficient, $r^{2}$), with respect to the PCs obtained using the standard non-secure PCA, i.e., the RPCA implemention provided by the sklearn Python package .

6 Comparison with Existing Works

We compare sf-pca with existing approaches for federated or multiparty PCA, which we categorize into meta-analysis, centralized HE (C-HE), and secret sharing-based SMC solutions. A more detailed review of these approaches is provided in §.2.

Meta-analysis. For comparison, we replicate the meta-analysis approach of Liang et al , whereby a central computing server performs a truncated SVD on the combined SVD results obtained independently by each DP. In Tab. 5, we show that this solution yields the least accurate results across all datasets. Note that sf-pca significantly improves upon the accuracy of meta-analysis by emulating a centralized PCA. Moreover, most meta-analysis solutions are not end-to-end secure as the DPs’ intermediate results are revealed to an aggregator server (or to the other DPs). These solutions achieve similar runtimes as non-secure centralized solutions because they also operate on unprotected cleartext data.

Centralized HE (C-HE). We estimate the runtime of an HE-based centralized solution based on sf-pca’s runtime as follows. We account for the fact that the computations cannot be distributed among the DPs and that all operations must be performed on the encrypted data. Recall that sf-pca exploits local cleartext operations to optimize computation (e.g., §.6.1) and that multiplying two ciphertexts is 8 times slower than a plaintext-ciphertext multiplication. We also include the overhead brought by a centralized bootstrapping routine , which is two orders of magnitude slower than DBootstrap, e.g., 26 seconds for vs. 0.49 seconds with DBootstrap. Furthermore, since centralized bootstrapping consumes levels and lowers the number of available levels for multiplications, C-HE would require more conservative cryptographic parameters with larger ciphertexts, and thus higher computation and communication costs. In Tab. 5, we show the estimated lower bound of the runtime for a C-HE solution executed by a single DP. We remark that sf-pca, by distributing its workload and relying on efficient interactive protocols, is consistently 1-2 orders of magnitude faster than a C-HE solution. We note that we consider C-HE solutions based on the same underlying scheme of sf-pca with comparable parameters, and that more sophisticated centralized solutions could be devised. However, those would still suffer from a high communication overhead and introduce a single point of failure due to the data centralization.

Secret Sharing-based SMC. In Tab. 5, we compare sf-pca’s runtime with the linear (additive) secret sharing-based SMC solution proposed by Cho et al. . In this solution, two computing servers perform PCA on secret-shared data, and a third server is responsible for the generation and distribution of correlated random numbers used in SMC protocols (e.g., Beaver triples ). This additional party is trusted to correctly generate these values and not to collude with any other party. We ran Cho et al.’s publicly available, two-party solution in our evaluation environment. We further estimated the runtime of this solution with 6 DPs under linear scaling with the number of DPs. We observe that sf-pca is between 3x and 10x faster than the SMC solution while operating in a stronger threat model without the need for an honest third party. We also note that the SMC solution requires the entire dataset to be secret-shared among the computing parties, which can be costly for large datasets and complicate regulatory compliance. For example, with the Lung dataset , this represents a communication overhead of more than 60 GB. Finally, we note that SMC solutions heavily rely on interactive computations, leading to many rounds of communication in total. Since a large portion of sf-pca is local non-interactive computation by each DP, sf-pca remains practical even in constrained networks with high communication delays, unlike the SMC solutions. For example, when we double the delay from 20ms to 40ms, we observed that sf-pca’s runtime remains almost constant, whereas the SMC solution becomes 1.9 times slower in the two-party setting. In §.8, we describe an extension of sf-pca which uses secret sharing specifically for non-polynomial operations over low-dimensional inputs.

7 Example Application of SF-PCA in Genomics

To further demonstrate the utility of sf-pca, we used it to analyze a genomic dataset of 2,504 individuals with 1,773 features (a subset of genetic variants from chromosome 20). PCA is a standard step in many genomic analysis workflows, e.g., in genome-wide association studies , for capturing ancestry patterns in a dataset. We split the data among three DPs such that each DP only has samples belonging to a specific ancestry group (Fig. 6.d). The plots show individual samples projected onto the first two PCs. Consistent with the quantitative evaluation in §.7.5, sf-pca (Fig. 6.b) is able to accurately identify the low-dimensional structure spanned by the data samples, almost exactly replicating the output of a centralized cleartext PCA on the full dataset, independently of how the data is split among the parties (Fig. 6.a). The meta-analysis approach for PCA (Fig. 6.c) results in a distorted data landscape due to the limited view of each DP. In Fig. 6.d, we highlight the output of sf-pca that is visible to one of the DPs; while all DPs obtain projected data according to a unified subspace identified by the PCA, each DP sees only a portion of the output associated with their local data as required by our security model.

Extensions

sf-pca can be extended in several ways to incorporate additional features. First, sf-pca’s multiparty construction enables it to seamlessly and securely (i.e., without decryption) switch between MHE and secret sharing-based SMC (see Appendix D.1). This enables sf-pca to leverage more efficient and accurate protocols to evaluate non-polynomial functions (e.g., sign tests) on small-dimensional inputs, while using MHE for operations over large encrypted vectors and matrices where the SIMD property of MHE leads to efficient performance with minimal communication. Next, the modular design of sf-pca enables its federated routines to be used to perform RPCA on vertically partitioned data (Appendix D.2). sf-pca could also be extended to provide differential privacy (Appendix D.3), although setting a meaningful privacy parameter may be difficult, by incorporating an interactive protocol in which the DPs sequentially shuffle an encrypted list of noise values before adding them to the results upon decryption . Lastly, to cope with the possibility of a subset of DPs becoming unavailable during the PCA computation—particularly relevant for the setting with many DPs, sf-pca can be instantiated with a threshold secret sharing of the MHE secret key to allow a subset of DPs to continue the protocol execution (Appendix D.4).

Discussion and Conclusions

We introduced sf-pca, a decentralized system for securely and efficiently executing PCA on data held by multiple data providers. sf-pca ensures input confidentiality as long as at least one DP is honest. Furthermore, the local private data never leave the DPs’ premises given the federated design of sf-pca. Our system builds on a range of optimized MHE-based routines we developed for key computational operations in PCA such as large-scale cleartext-ciphertext matrix multiplications and sophisticated linear algebra transformations, including matrix factorization and orthogonalization. sf-pca obtains accurate results within practical runtimes on large matrices including tens of thousands of features, and efficiently scales with the number of data providers and the input dimensions due to our optimization strategies.

Our work shows that an end-to-end secure solution for high-complexity data analysis tasks such as PCA is practically feasible. Incorporating sf-pca into existing privacy-preserving federated analysis methods (e.g., see Appendix G) and deploying it in a range of practical applications are natural next steps for our work. Our design principles and optimization techniques that have led to the practical performance of sf-pca, as well as the optimized MHE routines for key linear algebra operations such as eigendecomposition are broadly applicable to other problems in federated analytics.

Acknowledgements

We thank Louis Vialar and the reviewers for their comments. This work was partially supported by NIH R01 HG010959 (to B.B.) and by NIH DP5 OD029574, RM1 HG011558, and Broad Institute’s Schmidt Fellowship (to H.C.). J.R.T.-P. and J.-P.H. are co-founders of the start-up Tune Insight. All authors declare no other competing interests.

References

Appendix A CKKS

Appendix B Symbols & Default Values

Appendix C Security Analysis

We rely on the real/ideal simulation paradigm to show that sf-pca achieves the input confidentiality requirement defined in §.4. A computationally bounded adversary that controls up to all but one DP cannot distinguish a real world experiment, in which the adversary is given actual data from an execution of our protocol from the views of the compromised DP(s), and an ideal world experiment, in which the adversary is given random data generated by a simulator.

The semantic security of the ckks scheme used in sf-pca is based on the hardness of the decisional-rlwe problem . Mouchet et al. proved that their distributed protocols, i.e., DKeyGen and DKeySwitch, are secure under the simulator paradigm. They show that the distribution of the cryptoscheme preserves its security in the passive-adversary model with all-but-one dishonest DPs, as long as the decisional-rlwe problem is hard. Their proofs are based on the bfv cryptoscheme; Froelicher et al. showed that the proofs still hold with ckks, as the same computational assumptions hold, and the security of ckks is based on the same hard problem as bfv. They make a similar argument for DBootstrap and prove its security. The security of the cryptoscheme used by sf-pca follows from these results.

Assume that sf-pca uses ckks encryptions with parameters $(\mathcal{N},\ \Delta,\ \eta,\ mc)$ ensuring post-quantum security. Given a passive adversary corrupting at most $s-1$ parties out of $s$ parties in total, sf-pca achieves input confidentiality.

Appendix D Extensions

sf-pca’s multiparty construction enables it to seamlessly switch between MHE and secure multiparty computation (SMC) primitives based on secret sharing . Intuitively, an MHE ciphertext is transformed to linear (additive) secret shares (LSS) through a collective masked decryption by the DPs, i.e., each DP partially decrypts the ciphertext and masks the result with its secret share, whereas the last DP decrypts and obtains its share. After the computations in the LSS domain, to transform the result back to an MHE ciphertext, each DP encrypts its local share of the result such that it can be aggregated under MHE with all DPs’ encrypted shares. We detail these procedures in Protocol 1. sf-pca always employs MHE to execute large-dimensional matrix operations and can perform non-polynomial operations, e.g., square root and divisions (in Alg. 2), as well as small-matrix operations (in Alg. 4), using LSS-based routines . This combines the strengths of both approaches: On the one hand, relying on edge-computing and the SIMD property of MHE, sf-pca efficiently performs vectorized and parallel operations over large encrypted matrices while minimizing communication. On the other hand, relying on LSS-based SMC, sf-pca simplifies its usage by removing the need to choose intervals for non-polynomial function approximations. Note that efficient protocols exist for computing the bit-length of a secret-shared value , which can be used to map the input to a common interval for accurate approximation. In addition, LSS-based routines can be more efficient for computation over small data, e.g., eigendecomposition of a tiny matrix in RPCA, where the ciphertext packing is underutilized for MHE. In sf-pca, all costly non-polynomial operations (e.g., see Alg. 2) are executed on a single scalar input. Thus, executing these operations on compact secret-shared data can further reduce the computational cost of sf-pca.

Evaluation. Switching to LSS removes the need for defining approximation intervals to evaluate non-polynomial functions hence simplifies the usage of sf-pca. Depending on the setting, it can also improve sf-pca’s accuracy. The intervals for the non-polynomial operations depend on the DPs’ data and, as sf-pca’s intermediate results are repeatedly orthogonalized (through $\text{QR}^{T}$), these ranges can be accurately inferred upfront by the DPs, e.g., by simulating the protocol (§.6.3).

For example, with the MNIST dataset and the parameters of Tab. 5, the DPs define 16 distinct intervals to evaluate 1,047 polynomial approximations. This is because the ranges of values are constant across the dimensions and across the iterations of the same operations. For the same dataset, relying on sf-pca +lss improves the Pearson correlation between sf-pca’s PCs and the PCs obtained with a standard non-secure centralized PCA from 0.91 to 0.92 (when using our default parameters, Tab. III). sf-pca’s accuracy depends on the size and degree of the intervals hence can be improved by refining these parameters. We illustrate this on the execution of a single $\text{QR}^{T}$ in Tab. 7b. We note that QRT is used (iteratively) in Steps 4, 6 and 7 of sf-pca and that all non-polynomial operations in sf-pca are executed in the Householder (HH, Alg. 2) that is called in line 2 of QRT. For QRT on a 8x8 matrix, HH is called seven times and requires the evaluation of three non-polynomial functions. In sf-pca, this requires the definition of 21 approximation intervals, i.e., one per non-polynomial function. We show that using a single large interval (with a polynomial of degree 63; [0:1000;63]) for all operations already yields results that are correlated with the results obtained by a cleartext solution. sf-pca’s accuracy can then be improved by either downsizing the interval (to [0:100;63]), increasing the approximation degree (to [0:1000;127]), or by using more fine-grained intervals for the different steps in the computation ([0:100;63] for the first execution of HH and [0:1;63] afterwards).

In Fig. 7a, we show that sf-pca’s runtime is similar with or without this extension. sf-pca’s computational cost is reduced by computing on secret shares, instead of on encrypted vectors, but this gain is overshadowed by the communication overhead brought by both the protocol for switching between MHE and LSS and by LSS distributed computations. sf-pca scales similarly with its default approach (sf-pca in Fig. 7a) and when switching to LSS for non-polynomial and small-dimensional operations (sf-pca +lss). Switching to LSS only for non-polynomial operations (sf-pca +lss-op) is around 1.4x slower than sf-pca +lss due to the communication overhead brought by the high-number of switches between the two schemes. sf-pca can optimize its runtime for the small-dimensional eigendecomposition (Step 6) by performing it entirely in the LSS domain, which is up to 1.5x faster than in its basic approach in this scenario. When operating on larger dimensions, i.e., in Step 4 (Alg. 1), sf-pca only switches to LSS for small-dimensional (i.e., single value as shown in Alg. 2) non-polynomial operations as this can improve its precision. Performing sequences of operations in LSS in Step 4 would require to switch and operate on large-dimensional secret-shared elements, which would further increase the communication overhead. In Tab. 7b, we show that the runtimes of most LSS operations are in the same order of magnitude as MHE operations.

D.2 Vertically Partitioned Data

D.3 Differential Privacy

sf-pca can be extended to provide differential privacy by leveraging an interactive protocol in which the DPs sequentially shuffle an encrypted list of noise values before adding them to the results upon decryption . The choice of privacy parameters and maintaining accuracy are part of future work.

D.4 Fault Tolerance

To cope with the possibility of a subset of DPs becoming unavailable during the PCA computation, which is particularly relevant when there are many DPs, sf-pca can be extended by employing a $\hat{s}$-out-of-$s$ threshold secret-sharing for the MHE secret keys , where $s$ is the number of DPs. Note that the main setting of sf-pca considers $\hat{s}$ = $s$. Setting $\hat{s}$ to be smaller than $s$ changes sf-pca’s security model to tolerate up to $\hat{s}-1$ dishonest DPs. As long as at least $\hat{s}$ DPs are available for each interactive step, sf-pca’s execution continues without interruption. In certain steps of sf-pca the omission of a subset of parties may result in their local data not being accounted for in the computation. However, given the iterative nature of the RPCA algorithm, the overall results are expected to be robust against such omissions with a sufficient number of iterative steps.

Appendix E Datasets

The Wine dataset contains 4,898 wine samples with physicochemical attributes as features and a quality score as label. The Lung dataset contains 9,098 patients with 23,724 genomic variations (as features) and a label indicating the presence of a cancer. The PIMA dataset ($768\times 8$) contains medical observations collected from an Indian community that can be used to predict the presence of diabetes. Chr20 ($2,502\times 1,773$) is a subset of the genomic data available in the 1,000 Genomes dataset. In the MNIST dataset ($70,000\times 784$) , each sample describes the grey-scale image of a single handwritten digit. Finally, the Vehicle dataset contains 19 features extracted from each of the 435 images of buses or cars.

Appendix F Runtime Scales with the Slowest DP

We show in Figure 7c that sf-pca’s runtime depends on the maximum number of local samples among the DPs. In this example, the DP with the maximum number of samples has 32,768 samples and the other samples are evenly split among the remaining 5 DPs. Even as the total number of data samples increases, sf-pca’s runtime remains constant since the maximum number of local samples stays the same.

Appendix G Using sf-pca to Improve Machine Learning Efficiency and Accuracy

By combining sf-pca with a privacy-preserving solution for a downstream machine learning (ML) task, a secure federated ML workflow supporting the full analytic pipeline, encompassing pre-processing (e.g., dimension reduction), training, and inference, can be built. For example, sf-pca can be seamlessly integrated with existing MHE-based solutions for training generalized linear models or neural networks (NNs) . As the training time of these solutions increase with the number of features in the dataset, sf-pca may be a useful solution for reducing the scale of high-dimensional datasets to speedup model training. For example, executing sf-pca on the MNIST dataset (see Tab. 5) to project it on 5 PCs takes 1 hour and reduces the number of features by a factor of 152. Training a model using the PCs instead of the original features would reduce by a factor 7 the runtimes of previously mentioned secure solutions. Such an approach can also improve the accuracy of ML models when dimension reduction results in noise removal and more informative features, especially in limited data settings . We illustrate this use case by training a NN model (i.e., a multilayer perceptron with hidden layer made of four nodes, sigmoid activation functions, and one output node) to perform classification on the Vehicle dataset , which contains 435 samples with 18 features derived from vehicle images (Appendix E). We observed that the model trained without any preprocessing achieves a prediction accuracy of $55\%$ on the test set, whereas training the model on 5 PCs obtained by sf-pca (applied to the training data) as features yields an accuracy of $87\%$, which increases to $97\%$ with 8 PCs. This small example illustrates the fact that by de-correlating the features and reducing their number, PCA can improve ML model accuracy.