$\lambda$-SecAgg: Partial Vector Freezing for Lightweight Secure Aggregation in Federated Learning

## Abstract

Abstract Secure aggregation of user vectors has become a critical issue in the field of federated learning. Many Secure Aggregation Protocols (SAP) face exorbitant computation costs, which severely limit their applicability.
We uncover that current endeavors to reduce computation costs tend to overlook a crucial fact: a considerable portion of SAP’s computation burden stems from processing each entry in the private vectors. Given this observation,
we propose PVF, a portable module for compressing computation costs.
PVF is able to “freeze” a substantial portion of the private vector through specific linear transformations, only requiring 1 λ 1 𝜆 \frac{1}{\lambda} divide start_ARG 1 end_ARG start_ARG italic_λ end_ARG of the original vector to participate in SAP. Eventually, users can “thaw” the public sum of the “frozen entries” by the result of SAP. To enhance functionality, we introduce extensions that can enforce consistency constraints on users’ original vectors, verify aggregated results, and enhance security when a portion of the private vector is known to the server.
We demonstrate that PVF can seamlessly integrate with various SAP and prove that it poses no threat to user privacy in the semi-honest and active adversary settings.
We select 8 8 8 8 baselines, encompassing 6 6 6 6 distinct types of SAP, and explore the acceleration effects of PVF on these SAP. Empirical investigations indicate that when λ = 100 𝜆 100 \lambda=100 italic_λ = 100 , PVF yields up to 99.5 × 99.5\times 99.5 × speedup and up to 32.3 × 32.3\times 32.3 × communication reduction, with the potential to approach nearly 1000 × 1000\times 1000 × acceleration as λ 𝜆 \lambda italic_λ increases.

## 1 Introduction

Machine learning technologies are applied in countless fields to improve service performance. However, aggregating large amounts of data for big data mining raises concerns regarding data privacy []. Given the powerful role of machine learning in real-life applications, connecting isolated data islands while protecting users’ data privacy is important. Distributed machine learning such as Federated Learning (FL) [] keeps original data on the local devices while only requiring data owners to submit local training updates to a central server. Nonetheless, as [, ] indicates, attackers can infer a user’s local data by reversing the submitted updates. To address this issue, numerous research efforts have been focusing on Secure Aggregation Protocols (SAP) [] for aggregating all user’s model information while preserving individual privacy.

Figure: Figure 1: Computation time of various operations in PracAgg for a single aggregation across different vector lengths, with 100 users and 10% dropout rate.
Refer to caption: x1.png

Limitations of Prior Works. Currently, many SAP have been proposed []. The widely discussed schemes are based on Secure Multi-Party Computation (SMPC) [, ], Mask [, , , , , ], Homomorphic Encryption (HE) [, ] and Differential Privacy (DP) [, ], among which the most cost-effective schemes revolve around DP-based solutions. However, DP reduces the utility of user data and impacts the training accuracy because of the added noise, leaving the balance of security and data utility as a major challenge for practical applications []. Moreover, the security of DP in secure aggregation faces challenges, necessitating its combination with mask to bolster privacy [].
The computation cost involved in SAP often scales proportionally with the length of the model update vectors since most schemes involve encrypting or masking each entry of the vector sequentially. Fig. [1](#S1.F1) showcases the computation overhead of a widely acclaimed SAP, PracAgg [], considered state-of-the-art, delineating the computation time required by various operations.
It is noticeable that the time for operations unrelated to vector length, such as secret sharing and key agreements, remains consistently low (a dozen milliseconds). Conversely, the computation time for both masking and unmasking experiences a steep escalation (over a hundred seconds) with the increase in vector length, significantly constraining real-world applications.

A new angle to reduce computation overhead. Most efforts to reduce computation cost focus on enhancing PracAgg: some concentrate on improving the masking mechanism [, , ], some focus on refining communication structures [, ], and some emphasize enhancing efficiency in key agreements among users [, ]. These endeavors, while showing promising results, haven’t addressed the root cause of computation overhead in SAP, i.e., encrypting each entry of the original vector. While a few sparse-related approaches [, ] try to reduce the dimensions of uploaded vectors, they raise an inevitable trade-off of discarding some information. To the best of our knowledge, there is currently no work that can reduce the number of entries processed in SAP while ensuring intact aggregation of all entries in the vector.

Our proposal. In this work, we propose a portable module to compress the computation cost of SAP based on systems of linear equations with $\lambda$ variables. Within the module, each user performs linear transformations on the original vector at a negligible computation cost, compressing the length of the vector involved in SAP to $\frac{1}{\lambda}$ of its original size. The additional operation required by the server also performs linear transformations. The PVF module doesn’t introduce extra interaction or additional communication overhead. When integrated with HE-based schemes, PVF can also reduce communication overhead thanks to the decreased number of ciphertext entries. Further, to cater to various secure aggregation needs, we incorporate several extensions into the Main PVF: (i) User Commitment Extension, which ensures the uniqueness of users’ original vectors to prevent malicious attempts at incorrect computations, (ii) Result Verification Extension, which ensures the correctness of performing linear transformations to prevent malicious server-side computations, and (iii) $\delta$-security Extension, which enhances privacy when adversaries possess prior knowledge of partial private vectors.
PVF remains decoupled from SAP and guarantees individual user privacy under semi-honest and active adversary settings, offering high portability.
Through extensive research into the latest developments in secure aggregation, we have found that PVF seamlessly integrates with various SAP. It harmonizes effortlessly with classical SAP [, , , , ], lightweight SAP [, ], aggregation verification SAP [, ], multi-round privacy SAP [, ] and defense against model inconsistency attack SAP [].
In our experiments, we integrate PVF with $8$ different baselines, revealing a significant reduction in overhead for secure aggregation. This reaffirms the high portability of PVF.
Moreover, unlike prior research that only compared with SAP of the same kind, our experiments include $6$ distinct categories of SAP, providing a comprehensive showcase of their respective strengths and weaknesses. Notably, HE-based SAP, previously deemed impractical due to overwhelming costs, becomes practical once integrated with PVF, and the fewer communication interactions along with the privacy of the global model make them favorable, especially in scenarios with unstable network connections. In essence, PVF revitalizes their viability for real-world applications!

Our contributions can be summarized as follows:

- •
We discover a novel research direction that efficiently reduces the costs of SAP and propose an instance without incurring additional communication overhead or harming accuracy and security in both semi-honest and active adversary settings. It reduces the entries processed in SAP while ensuring the aggregation of all entries in the original vector, which means it can compress the computation overhead of SAP to approximately $\frac{1}{\lambda}$ of the original ($\lambda$ is the compression factor). Moreover, it brings up to $32.3\times~{}(\lambda=100)$ additional communication enhancements for HE-based SAP.
- •
We propose several extensions to PVF to support the consistency of user inputs, aggregation result verification, and enhanced privacy when adversaries possess prior knowledge. These extensions, coupled with its inherent decoupling from SAP and relaxed security assumptions, allow for seamless integration with various SAP to address challenges such as erroneous aggregation, model inconsistency attacks, and multi-round privacy breaches.
- •
Extensive experiments show the portability and effectiveness of our proposal. We select $8$ baselines encompassing $6$ types of SAP for a comprehensive cost comparison, which is largely unexplored in most research endeavors.

## 2 Preliminaries and Notations

### 2.1 Federated Learning and Secure Aggregation Protocol

In the $t$-th round of FL, the user set $\mathcal{U}=\{u_{1},\ldots,u_{n}\}$ conduct local model training and submit model updates (Original Vectors) $\{\mathbf{x^{i(t)}}\}_{i\in\mathcal{U}}=\{(x^{i(t)}_{1},\ldots,x^{i(t)}_{m})\}
_{i\in\mathcal{U}}$ to the server $\mathcal{S}$. And there might be $\eta~{}(\leq 30\%)$ users that drop out during the aggregation. The server aggregates the model updates $\sum_{i\in\mathcal{U}}\mathbf{x^{i(t)}}$ and redistributes the updated global model to each user. This iterative process continues until the completion of model training. The aggregation method above is referred to as the Plain Aggregation.

A secure aggregation protocol has the following properties (* denotes extended requirements):

- •
Privacy: During the execution of secure aggregation, the malicious parties cannot learn any knowledge about the original vectors of the honest parties except for the sum.
- •
Correctness: $\mathcal{S}$ can obtain the same aggregated results as plain aggregation for updating the global model.
- •
Dropout resilience: $\mathcal{S}$ can efficiently handle dropouts and continue to complete the aggregation successfully.
- *
Verifiability of aggregation: It is required to prevent the malicious $\mathcal{S}$ from spoofing users with incorrect aggregated results to disrupt training.
- *
Model consistency: It is required to thwart the malicious $\mathcal{S}$ from sending deliberately crafted inconsistent models to different users for exploring user local information.
- *
Multi-round privacy: It is required to prevent the malicious $\mathcal{S}$ from compromising user privacy in multiple rounds of aggregation.

Privacy, correctness, and dropout resilience constitute the fundamental prerequisites for secure aggregation, while verifiability of aggregation, model consistency, and multi-round privacy are extension requirements for secure aggregation proposed by the latest works [, , ].

Input constraints. Several works [, ] are proposed to mitigate Poisoning Attacks in FL. They delineate that the erroneous inputs of malicious users can result in the server obtaining an inaccurate global model, thereby harming the training task. They propose methodologies utilizing zero-knowledge proofs to bound user inputs. However, there are numerous attacks they cannot defend against []. Establishing strong constraints against malicious inputs remains an unresolved challenge, and it falls beyond the scope of this work. What’s more,  [] recently employed Federated Rank Learning (FRL), where the server aggregates the parameter rankings instead of the model parameter updates. This enables direct aggregations without any constraints on user submissions, effectively resisting poisoning attacks. Therefore, FRL can be combined with SAP, and we do not have to worry about whether PVF can be integrated with input constraints in this work.

### 2.2 System of Linear Equations

A system of linear equations with $\lambda~{}(>2)$ variables and a $\lambda\times\lambda$ coefficient matrix $\mathbf{A_{\lambda}}$ is a type of equation system that conforms to the following form:

$$ $\left\{\begin{array}[]{l}a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots+a_{1,\lambda}x_{ \lambda}=b_{1}\\ a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots+a_{2,\lambda}x_{\lambda}=b_{2}\\ \vdots\\ a_{\lambda,1}x_{1}+a_{\lambda,2}x_{2}+\cdots+a_{\lambda,\lambda}x_{\lambda}=b_ {\lambda}\end{array}\right.$ (1) $$

Expressed in the concepts of linear algebra, the aforementioned system of linear equations can be formulated as follows:

$$ $\mathbf{A_{\lambda}x=b},$ (2) $$

where $\mathbf{x}$ is the vector of variables with $\lambda$ entries, and $\mathbf{b}$ is a vector with $\lambda$ entries. If the inverse matrix $\mathbf{A_{\lambda}^{-1}}$ of $\mathbf{A_{\lambda}}$ is known, then the variable vector $\mathbf{x}$ can be obtained by $\mathbf{x=A_{\lambda}^{-1}b}$.

We define Incomplete Matrix $\check{\mathbf{A}}_{\lambda}$, composed only of the first $\lambda-1$ rows of $\mathbf{A_{\lambda}}$:

$$ $\check{\mathbf{A}}_{\lambda}=\begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1, \lambda}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,\lambda}\\ \vdots&\vdots&\vdots&\vdots\\ a_{\lambda-1,1}&a_{\lambda-1,2}&\cdots&a_{\lambda-1,\lambda}\end{bmatrix},$ (3) $$

$\check{\mathbf{b}}$:

$$ $\check{\mathbf{b}}=\check{\mathbf{A}}_{\lambda}\mathbf{x},$ (4) $$

and Residual Vector $\bm{\alpha}_{\lambda}$:

$$ $\bm{\alpha}_{\lambda}=(a_{\lambda,1},a_{\lambda,2},\cdots,a_{\lambda,\lambda}).$ (5) $$

We define the function for finding the solution set of a system of linear equations as:

$$ $SLE_{AK}(\mathbf{Ax})\rightarrow\mathbf{x},$ (6) $$

where $AK$ denotes the additional knowledge. We use $rank(\cdot)$ to represent the rank of a matrix. If and only if $rank(\mathbf{A_{\lambda}})=rank(\mathbf{A_{\lambda},b})=\lambda$, the system of linear equations has a unique solution. If $rank(\mathbf{A_{\lambda}})=rank(\mathbf{A_{\lambda},b})<\lambda$, the system has innumerable solutions.

### 2.3 Pedersen Commitment

A commitment scheme is a cryptographic protocol involving two parties. The sender selects a message $s$ and sends a commitment to the receiver, signifying sender will not change $s$. During the reveal phase, the receiver can verify whether the message corresponds to the commitment provided.
The commitment scheme needs to meet two basic properties: hiding and binding. Hiding is the commitment will not disclose any information about $s$; Binding refers to the fact that no malicious sender can reveal the commitment as a non-‘$s$’ message that would pass verification, meaning that the receiver can be confident that $s$ corresponds to the commitment.

Pedersen Commitment is a perfectly hiding and computationally binding commitment scheme [], including the following algorithms:

- •
$PC.setup(\rho)\rightarrow(p,g,h)$. Given the security parameter $\rho$, it generates the group $(\mathbb{G}_{p},p,g)$, where $p$ is the order of $\mathbb{G}_{p}$ and $g$ is its generator. $h$ is an element of $\mathbb{G}_{p}$. $\mathbb{G}_{p},p,g,h$ are public.
- •
$PC.commit(\mathbb{G}_{p},g,h,s)\rightarrow C_{s}$. To commit $s\in\mathbb{G}_{p}$, it chooses $t\in\mathbb{G}_{p}$ at random and computes $C_{s}=g^{s}h^{t}$.
- •
$PC.reveal(C_{s}^{\prime},s,t,g,h)\rightarrow True~{}or~{}False$. If $C_{s}^{\prime}=g^{s}h^{t}$, it returns True. Otherwise, it returns False.

## 3 Partial Vector Freezing

In this section, we delineate the details of PVF using the same notations as in Sec. [2](#S2). We consider the scenario where the server $\mathcal{S}$ aggregates model updates with $m$ entries from the user set $\mathcal{U}=\{u_{1},\ldots,u_{n}\}$. Similar to other schemes  [, , , , , , , , ], we define the elements of $\mathbf{x^{i(t)}}~{}(i\in[1,n])$ within $\mathbb{Z}_{p}$ for some large public prime $p$ and assume there is a secure communication channel between each user and the server. In this section, our emphasis lies in introducing the computation approach of PVF, specifically considering a single-round aggregation process. To ensure multi-round privacy, employing a specialized user selection mechanism for each round is sufficient [, ].

Threat model: PVF can guarantee the security of the honest parties’ privacy under both semi-honest and active adversary settings. The lenient security assumptions of PVF allow its easy integration with secure aggregation protocols. When integrating with a protocol, the security assumptions originally employed in the corresponding protocol are adopted.

Figure: Figure 2: Workflow of Main PVF.
Refer to caption: x2.png

### 3.1 Motivation

Appendix. [B](#A2) summarizes the primary research directions aimed at reducing computational overhead in SAP. Despite offering excellent optimization solutions across various phases of SAP, these schemes inevitably involve secure aggregation for each entry in the user’s original vector. Within SAP, every minor operation on an entry by a participant accumulates $m$ times, ultimately imposing significant computational burdens on devices. Based on these observations, we try to reduce the number of entries processed in secure aggregation while ensuring users receive all entries of the aggregated vector. To accomplish this objective, we devise a module that can selectively freeze certain entries (Frozen entries) of the user’s original vector, and only perform secure aggregation on the other entries (SecAgg entries).
Upon SAP completion, this module thaws the frozen entries. Interestingly, this method bears some resemblance to fine-tuning in language model training []. Such a module must meet the following requirements:

- •
Privacy. The secagg entries are guaranteed security by SAP, whereas the frozen entries also demand security assurances. Apart from the owner, no participant can access any private information of the frozen entries beyond their collective sum.
- •
Correctness. The correctness of the aggregation results for secagg entries is ensured by SAP. Ultimately, we require accurate aggregation results for all entries, aligning with the outcomes of plain aggregation.
- •
Lightweight. The additional computational overhead generated by the module should be smaller than the reduced computational overhead of SAP. Simultaneously, it should strive to minimize any additional communication overhead.
- •
Portability. The module should be decoupled from specific SAP implementations, facilitating straightforward integration into varied protocols.

We observe that a system of linear equations with an invertible coefficient matrix can aid us in devising such a computation module. Consider the following system of linear equations:

$$ $\left\{\begin{matrix}{a_{1,1}x_{1}+a_{1,2}x_{2}+a_{1,3}x_{3}=b_{1}}\\ {a_{2,1}x_{1}+a_{2,2}x_{2}+a_{2,3}x_{3}=b_{2}}\\ {a_{3,1}x_{1}+a_{3,2}x_{2}+a_{3,3}x_{3}=b_{3}}\end{matrix}\right..$ (7) $$

We employ the same notations as in Sec. [2.2](#S2.SS2). Assuming that the coefficient matrix $\mathbf{A_{3}}$ of this system of linear equations is an invertible $3\times 3$ matrix, we consider the variable vector $\mathbf{x}=(x_{1},x_{2},x_{3})$ as the original vector of a user in a secure aggregation scenario.
Given that $\mathbf{A_{3}}$ is invertible, the knowledge of $\mathbf{A_{3}}$ and $\mathbf{b}$ allows for the unique solution of $\mathbf{x}$. However, when $\mathbf{\check{A}}_{3}$ and $\check{\mathbf{b}}$ are known, in the absence of knowledge about $\mathbf{a_{3}x}$, $\mathbf{x}$ presents an infinite set of possibilities, rendering it impossible to determine that specific confidential vector. Motivated by this, we propose PVF.

### 3.2 Main Method

In this section, we present the computation process of the Main PVF module during a single aggregation round, depicted by the workflow shown in Fig. [2](#S3.F2).

Phase 0: Main.Setup($\cdot$). Generate an invertible matrix $\mathbf{A_{\lambda}}\in\mathbb{Z}_{p}^{\lambda\times\lambda}$, and obtain $\mathbf{A_{\lambda}^{-1}}$, $\check{\mathbf{A}}_{\lambda}$ and $\bm{\alpha}_{\lambda}$, which are all public parameters. We refer to $\lambda$ as the Compression Factor.

Phase 1: Main.Freeze($\cdot$). For user $i\in[1,n]$, in $t$-th aggregation, the original vector of $i$ is $\mathbf{x^{i(t)}}=(x^{i(t)}_{1};x^{i(t)}_{2};\ldots;x^{i(t)}_{m})$. Initially, apply Random Padding to ensure that the length of the padded vector is a multiple of $\lambda$. The padded vector is $\mathbf{x^{i(t)}_{pad}}$:

$$ $\mathbf{x^{i(t)}_{pad}}=(x^{i(t)}_{1};x^{i(t)}_{2};\ldots;x^{i(t)}_{m^{\prime} }),$ (8) $$

where $m^{\prime}=l\lambda$. Divide $\mathbf{x^{i(t)}_{pad}}$ into $l$ groups, with each group consisting of $\lambda$ elements in sequential order. For each $j\in[1,l]$, define:

$$ $\mathbf{d^{i(t)}_{j}}=(x^{i(t)}_{(j-1)\times\lambda+1};x^{i(t)}_{(j-1)\times \lambda+2};\ldots;x^{i(t)}_{j\times\lambda}),$ (9) $$

and $\mathbf{x^{i(t)}_{pad}}$ can be expressed as:

$$ $\mathbf{x^{i(t)}_{pad}}=(\mathbf{d^{i(t)}_{1}};\mathbf{d^{i(t)}_{2}};\ldots; \mathbf{d^{i(t)}_{l}}).$ (10) $$

Then calculate:

$$ $\displaystyle\mathbf{y^{i(t)}}$ $\displaystyle=\left(\check{\mathbf{A}}_{\lambda}\mathbf{d^{i(t)}_{1}},\check{ \mathbf{A}}_{\lambda}\mathbf{d^{i(t)}_{2}},\ldots,\check{\mathbf{A}}_{\lambda} \mathbf{d^{i(t)}_{l}}\right)$ (11) $\displaystyle=\left(\mathbf{\check{b}^{i(t)}}_{1},\mathbf{\check{b}^{i(t)}}_{2 },\ldots,\mathbf{\check{b}^{i(t)}}_{l}\right)$ $\displaystyle=\left(\mathbf{y^{i(t)}_{1}},\mathbf{y^{i(t)}_{2}},\ldots,\mathbf {y^{i(t)}_{l}}\right),$ $$

and

$$ $\displaystyle\mathbf{k^{i(t)}}$ $\displaystyle=\left(\bm{\alpha}_{\lambda}\mathbf{d^{i(t)}_{1}},\bm{\alpha}_{ \lambda}\mathbf{d^{i(t)}_{2}},\ldots,\bm{\alpha}_{\lambda}\mathbf{d^{i(t)}_{l} }\right)$ (12) $\displaystyle=\left(k^{i(t)}_{1},k^{i(t)}_{2},\ldots,k^{i(t)}_{l}\right).$ $$

We designate $\mathbf{k^{i(t)}}$ as the Key Vector of $\mathbf{x^{i(t)}_{pad}}$, and $\mathbf{y^{i(t)}}$ as the Frozen Vector.

Phase 2: Main.SecAgg($\cdot$). Users and server $\mathcal{S}$ execute SAP, where the vector to be aggregated of user $i,i\in[1,n]$ is $\mathbf{k^{i(t)}}=(k^{i(t)}_{1},k^{i(t)}_{2},\ldots,k^{i(t)}_{l})\in\mathbb{Z}
_{p}^{l}$. Upon completion of SAP, the surviving user set $\mathcal{U}^{\prime}$ and $\mathcal{S}$ can receive the aggregated result of the key vectors: $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}}$ or $Enc(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}})$. All users send their respective $\mathbf{y^{i(t)}}$ to $\mathcal{S}$. Based on the final list of users online, the server computes $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}}$, immune to the impact of dropout users.

Phase 3: Main.Thaw($\cdot$). According to various aggregation needs, thawing can occur either at the server or user end, without compromising privacy.

(1) Thawing on the server side. The server, based on the acquired $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}}$ and $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}}$, can derive the aggregated result. The correctness stems from the linearity of $\mathbf{A_{\lambda}}$ and $\bm{\alpha}_{\lambda}$:

$$ $\begin{aligned} \mathbf{z}&=\left(\left(\sum_{i\in\mathcal{U}^{\prime}}\mathbf {y^{i(t)}_{1}},\sum_{i\in\mathcal{U}^{\prime}}k^{i(t)}_{1}\right),\ldots,\left (\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}_{l}},\sum_{i\in\mathcal{U}^{ \prime}}k^{i(t)}_{l}\right)\right)\\ &=\left(\left(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{\check{b}^{i(t)}}_{1}, \sum_{i\in\mathcal{U}^{\prime}}k^{i(t)}_{1}\right),\ldots,\left(\sum_{i\in \mathcal{U}^{\prime}}\mathbf{\check{b}^{i(t)}}_{l},\sum_{i\in\mathcal{U}^{ \prime}}k^{i(t)}_{l}\right)\right)\\ &=\left(\left(\sum_{i\in\mathcal{U}^{\prime}}\check{\mathbf{A}}_{\lambda} \mathbf{d^{i(t)}_{1}},\sum_{i\in\mathcal{U}^{\prime}}k^{i(t)}_{1}\right), \ldots,\left(\sum_{i\in\mathcal{U}^{\prime}}\check{\mathbf{A}}_{\lambda} \mathbf{d^{i(t)}_{l}},\sum_{i\in\mathcal{U}^{\prime}}k^{i(t)}_{l}\right)\right )\\ &=\left(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{A}_{\lambda}\mathbf{d^{i(t)}_{1 }},\ldots,\sum_{i\in\mathcal{U}^{\prime}}\mathbf{A}_{\lambda}\mathbf{d^{i(t)}_ {l}}\right)\\ &=\left(\mathbf{A}_{\lambda}\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{1 }},\ldots,\mathbf{A}_{\lambda}\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_ {l}}\right)\\ &=\left(\mathbf{b_{1}},\ldots,\mathbf{b_{l}}\right).\end{aligned}$ (13) $$

To thaw frozen vectors and obtain the aggregated results of all entries in the original vector, the server needs to perform $l$ linear transformations:

$$ $\begin{aligned} &\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{1}}=\mathbf{ A_{\lambda}^{-1}}\mathbf{A}_{\lambda}\sum_{i\in\mathcal{U}^{\prime}}(x^{i(t)}_ {1};x^{i(t)}_{2};\ldots;x^{i(t)}_{\lambda})=\mathbf{A_{\lambda}^{-1}}\mathbf{b _{1}}\\ &\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{2}}=\mathbf{A_{\lambda}^{-1} }\mathbf{A}_{\lambda}\sum_{i\in\mathcal{U}^{\prime}}(x^{i(t)}_{\lambda+1};x^{i (t)}_{\lambda+2};\ldots;x^{i(t)}_{2\lambda})=\mathbf{A_{\lambda}^{-1}}\mathbf{ b_{2}}\\ &\vdots\\ &\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{l}}=\mathbf{A_{\lambda}^{-1} }\mathbf{A}_{\lambda}\sum_{i\in\mathcal{U}^{\prime}}(x^{i(t)}_{(l-1)\lambda+1} ;x^{i(t)}_{(l-1)\lambda+2};\ldots;x^{i(t)}_{l\lambda})=\mathbf{A_{\lambda}^{-1 }}\mathbf{b_{l}}.\end{aligned}$ (14) $$

$\mathbf{A}_{\lambda}$ and $\mathbf{b}~{}(=\mathbf{z})$ are known to the server; hence, a unique solution can be determined:

$$ $\displaystyle\mathbf{sum}$ (15) $\displaystyle=\left(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{1}};\sum_ {i\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{2}};\ldots;\sum_{i\in\mathcal{U}^{ \prime}}\mathbf{d^{i(t)}_{l}}\right)$ $\displaystyle=\left(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{x^{i(t)}_{1}};\sum_ {i\in\mathcal{U}^{\prime}}\mathbf{x^{i(t)}_{2}};\ldots;\sum_{i\in\mathcal{U}^{ \prime}}\mathbf{x^{i(t)}_{l\lambda}}\right).$ $$

At this point, the server completes the thawing phase. Subsequently, it transmits $\mathbf{sum}$ to all online users. Upon receiving $\mathbf{sum}$, users can obtain the final aggregated result by removing the padding.

(2) Thawing on the user side. In certain SAP [, ], even the aggregated results of users’ original vectors remain invisible to the server to achieve heightened privacy, ensuring the protection of users’ intellectual property, among other goals. In this scenario, the server cannot perform the thawing. Instead, the server sends the sum of frozen vectors $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}}$ and $Enc(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}})$ to all surviving users. Users locally decrypt $Enc(\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}})$ and perform the thawing process to obtain $\mathbf{sum}$. By removing the padding, users attain the final aggregated result.

Unless specified otherwise, thawing phases in the subsequent text take place on the server side. Clearly, for an honest participant $i$, the adversary’s access to information about $\mathbf{x^{i(t)}}$ includes solely $\mathbf{sum}$ and underdetermined systems of linear equations for each $\lambda$-length subvector of $\mathbf{x^{i(t)}}$. Underdetermined systems of linear equations can effectively preserve the privacy of variables []. The adversary cannot access $\mathbf{x^{i(t)}}$ unless it can deduce a specific solution for an underdetermined system of linear equations without additional knowledge. Regarding the privacy of individual element within the vector, our analysis is conducted in Sec. [4.1](#S4.SS1). In the SecAgg phase, only a fraction, $\frac{1}{\lambda}$, of original vector entries require secure aggregation, thus reducing overhead. A detailed analysis of computation and communication overhead is carried out in Sec. [5.3](#S5.SS3). PVF only adds some computational steps before and after SAP execution without interfering with SAP’s internal operations. Therefore, it remains decoupled from SAP and has good portability.

### 3.3 User Commitment Extension

Threat. In PVF, if a malicious user $i$ uses inconsistent $\mathbf{d^{i(t)}_{j}}$ and $\mathbf{{d^{\prime}}^{i(t)}_{j}}$ for freezing, resulting in obtaining $\check{\mathbf{A}}_{\lambda}\mathbf{d^{i(t)}_{j}}$ and $\mathbf{a}_{\lambda}\mathbf{{d^{\prime}}^{i(t)}_{j}}$, or applies mismatched $\check{\mathbf{A}}_{\lambda}$ and $\bm{\alpha}_{\lambda}^{\prime}$ to $\mathbf{d^{i(t)}_{j}}$ for linear transformations, the frozen vector and key vector no longer correspond. Although this remains harmless to the privacy of honest users, it will lead to inaccuracies in the final aggregated result.

This malicious tampering is unrelated to SAP. In the freezing phase of PVF, we use Pedersen commitment to ensure users’ vector consistency. Note that, to enable verification, it’s crucial to ensure that during the validation phase, the server is semi-honest and cannot collude with users. Otherwise, a malicious server could illegitimately approve malicious user actions, preventing user verification, which is widely adopted in prior works []. Below, we outline User Commitment Extension (UCE) to modify the Main method to achieve the aforementioned functionality.
Note that UCE is only applicable to SAP where the server has access to the aggregated results.

Phase 0: MainUC.Setup($\cdot$). Execute Main.Setup($\cdot$). Execute $PC.setup(\cdot)$, and publicly disclose $g$ and $h$.

Phase 1: MainUC.Freeze($\cdot$). The user $i\in[1,n]$ generates the Random Vector $\bm{\zeta}^{i(t)}=(\zeta^{i(t)}_{1},\zeta^{i(t)}_{2},\ldots,\zeta^{i(t)}_{l
\lambda})$ and calculates the Commitment Vector:

$$ $\begin{aligned} \mathbf{c^{i(t)}}&=\left(\left(c^{i(t)}_{1(1)},\ldots,c^{i(t)} _{1(\lambda)}\right),\ldots,\left(c^{i(t)}_{l(1)},\ldots,c^{i(t)}_{l(\lambda)} \right)\right)\\ &=((g^{x^{i(t)}_{1}}h^{{\zeta}^{i(t)}_{1}},g^{x^{i(t)}_{2}}h^{{\zeta}^{i(t)}_{ 2}},\ldots,g^{x^{i(t)}_{\lambda}}h^{{\zeta}^{i(t)}_{\lambda}}),\ldots,\\ &(g^{x^{i(t)}_{(l-1)\lambda+1}}h^{{\zeta}^{i(t)}_{(l-1)\lambda+1}},g^{x^{i(t)} _{(l-1)\lambda+2}}h^{{\zeta}^{i(t)}_{(l-1)\lambda+2}},\ldots,g^{x^{i(t)}_{l \lambda}}h^{{\zeta}^{i(t)}_{l\lambda}}).\end{aligned}$ (16) $$

Execute Main.Freeze($\cdot$).

Phase 2: MainUC.SecAgg($\cdot$). Execute Main.SecAgg($\cdot$), once completed, all users obtain the aggregated result $\mathbf{sum}$. Each user $i$ sends $\mathbf{k^{i(t)}}$, $\mathbf{c^{i(t)}}$ and $\bm{\zeta}^{i(t)}$ to the server. For $j\in[1,l]$, $r\in[1,\lambda]$, $\mathcal{S}$ validates:

$$ $\prod_{i\in\mathcal{U}^{\prime}}c^{i(t)}_{j(r)}\overset{\text{?}}{=}g^{sum_{(j -1)\lambda+r}}h^{\sum_{i\in\mathcal{U}^{\prime}}{\zeta}^{i(t)}_{(j-1)\lambda+r }}.$ (17) $$

If the validation fails, it implies the user deviates from the protocol, and the protocol is terminated. Otherwise, it signifies that the user employs the consistent original vector when generating the frozen vector and key vector, and the utilized public parameters are accurate.

Phase 3: MainUC.Thaw($\cdot$). Execute Main.Thaw($\cdot$).

Clearly, this extension will inevitably introduce a performance decrease. The additional overhead it brings is analyzed in Sec. [5.5](#S5.SS5). It’s worth noting that in the majority of SAP [, , , , , , , , ], many malicious user behaviors, such as incorrectly executing key agreements or submitting counterfeited secret shares, result in aggregation errors. And strictly enforcing user behavior remains a pending issue [].

### 3.4 Result Verification Extension

Threat. The malicious server might intentionally provide incorrect aggregated results to disrupt training, even if it doesn’t compromise user privacy. When integrating PVF with SAP featuring result verification capabilities, we contemplate incorporating Result Verification Extension (RVE).

Most recent SAP that can verify aggregated results typically necessitate additional honest and non-dropping participants, such as Collectors [] and Auxiliary Nodes [], introducing several assumptions. Consequently, by utilizing this extension, we unavoidably add security assumptions. Without loss of generality, we adopt the approach and security assumptions from VerSA [] for PVF, which requires the server and users not to collude but does not need other trusted third parties.
Similarly, this extension results in a performance decrease. Most SAP [, , , , , , , ] lack the functionality to verify aggregated results. This extension merely constrains the server within the PVF module to obtain the correct $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}}$.

Phase 0: MainRV.Setup($\cdot$). Execute Main.Setup($\cdot$).

Phase 1: MainRV.Freeze($\cdot$). Execute Main.Freeze($\cdot$).

Phase 2: MainRV.SecAgg($\cdot$). During the execution of VerSA, all users obtain a set of random vectors $\left(\bm{\kappa_{1},\kappa_{2}}\right)$ derived from shared keys. In the verification step, users send $\mathbf{\grave{y}^{i(t)}}=\bm{\kappa_{1}}\mathbf{y^{i(t)}}$ and $\mathbf{\acute{y}^{i(t)}}=\mathbf{y^{i(t)}}+\bm{\kappa_{2}}$ to the server, which simultaneously aggregates $\mathbf{\grave{y}^{i(t)}}$ and $\mathbf{\acute{y}^{i(t)}}$. In this process, the verification of the sum of frozen vectors and the sum of key vectors is combined, avoiding additional interaction. VerSA ensures users obtain a consistent $\mathcal{U}^{\prime}$ and the correct $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}}$. Users also receive $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{\grave{y}^{i(t)}}$ and $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{\acute{y}^{i(t)}}$.

Phase 3: MainRV.Thaw($\cdot$). After receiving the results, users proceed with verification:

$$ $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{\grave{y}^{i(t)}}\setminus\bm{\kappa_{1 }}\overset{\text{?}}{=}\sum_{i\in\mathcal{U}^{\prime}}\mathbf{\acute{y}^{i(t)} }-|\mathcal{U}^{\prime}|\bm{\kappa_{2}}.$ (18) $$

$\mathbf{y^{i(t)}}$ is unknown to $\mathcal{S}$ throughout the process. If the verification passes, execute Main.Thaw($\cdot$) for thawing on the user side. Otherwise, conclude that the server deviates from the protocol and terminate the execution.

### 3.5 δ 𝛿 \delta italic_δ -security Extension

Threat. Consider an extreme scenario where an extremely powerful malicious server $\mathcal{S}$ somehow obtains an element $x^{i(t)}_{e}$ of $\mathbf{x^{i(t)}}$, although this is generally unrealistic in most cases. In this case, $\mathcal{S}$, during the PVF execution, would acquire $\lambda-1$ equations of the $j$-th group where $x^{i(t)}_{e}$ lies, namely $\mathbf{y^{i(t)}_{j}}=\check{\mathbf{A}}_{\lambda}\mathbf{d^{i(t)}_{j}}$ in ([11](#S3.E11)), along with $x^{i(t)}_{e}$. This allows $\mathcal{S}$ to solve for all elements in the $j$-th group. Even though only a very small fraction of original vectors, $\frac{\lambda}{m}$, is leaked, which is insufficient to compromise the privacy of the original data, we still aim to fortify against this. Assuming the adversary’s capability is to steal $\delta~{}(<\lambda-1)$ elements from each group of $\mathbf{x^{i(t)}}$.

We expand the definitions of incomplete matrix $\check{\mathbf{A}}_{\lambda}$, residual vector $\bm{\alpha}_{\lambda}$, and $\check{\mathbf{b}}$ of PVF. We define the Incomplete Matrix with $\delta$-security $\check{\mathbf{A}}^{\delta+1}_{\lambda}$, composed only of the first $\lambda-\delta-1$ rows of $\mathbf{A_{\lambda}}$:

$$ $\check{\mathbf{A}}^{\delta+1}_{\lambda}=\begin{bmatrix}a_{1,1}&a_{1,2}&\cdots& a_{1,\lambda}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,\lambda}\\ \vdots&\vdots&\vdots&\vdots\\ a_{\lambda-\delta-1,1}&a_{\lambda-\delta-1,2}&\cdots&a_{\lambda-\delta-1, \lambda}\end{bmatrix},$ (19) $$

$\check{\mathbf{b}}^{\delta+1}$ with $\delta$-security:

$$ $\check{\mathbf{b}}^{\delta+1}=\check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{x},$ (20) $$

and Residual Matrix with $\delta$-security $\bm{\alpha}^{\delta+1}_{\lambda}$:

$$ $\bm{\alpha}^{\delta+1}_{\lambda}=\begin{bmatrix}a_{\lambda-\delta,1}&a_{ \lambda-\delta,2}&\cdots&a_{\lambda-\delta,\lambda}\\ a_{\lambda-\delta+1,1}&a_{\lambda-\delta+1,2}&\cdots&a_{\lambda-\delta+1, \lambda}\\ \vdots&\vdots&\vdots&\vdots\\ a_{\lambda,1}&a_{\lambda,2}&\cdots&a_{\lambda,\lambda}\end{bmatrix}.$ (21) $$

Then Frozen Vector with $\delta$-security is:

$$ $\mathbf{y^{i(t)}}=\left(\check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t) }_{1}},\check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{2}},\ldots, \check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{l}}\right),$ (22) $$

and Key Vector with $\delta$-security is:

$$ $\mathbf{k^{i(t)}}=\left(\bm{\alpha}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{1}}, \bm{\alpha}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{2}},\ldots,\bm{\alpha}^{ \delta+1}_{\lambda}\mathbf{d^{i(t)}_{l}}\right).$ (23) $$

Clearly, the aforementioned changes won’t affect the execution process of PVF. However, the compression factor of PVF will decrease from ${\lambda}$ to $\frac{\lambda}{\delta+1}$ ($\delta<\lambda-1$). The specific impact is analyzed in Sec. [5.4](#S5.SS4). With these modifications, the adversary, apart from the known private elements, cannot obtain additional elements from the execution of PVF. Particularly, in the methodology outlined in Sec. [3.2](#S3.SS2), we consider $\delta=0$.

Figure: Figure 3: The pipline of SAP with PVF for one aggregation. The red and underlined parts are required in User Commitment Extension. The blue and underlined parts are required in Result Verification Extension.

### 3.6 Integrating PVF with SAP

Unless otherwise specified, subsequent references to PVF do not include the extensions. For a detailed analysis of portability, please refer to Appendix. [C](#A3).
The pipeline for integrating PVF into SAP is depicted in Fig. [3](#S3.F3). It’s essential to note that in the specific application of PVF  only one of UCE and RVE can be utilized. This limitation arises due to the different threat models associated with each, and to our knowledge, there is currently no work that combines user input validation and result verification.

## 4 Security Analysis

In this section, we utilize the same notations as in Sec. [2](#S2) and Sec. [3](#S3).

### 4.1 Individual Element Privacy

Within PVF, the server cannot derive the original vector via an underdetermined system of linear equations, thus ensuring user privacy. However, in cases of improper selection of $\mathbf{A_{\lambda}}$, the server can still access the privacy of individual elements within an original vector. Consider a coefficient matrix denoted as $\mathbf{A}_{3}$:

$$ $\mathbf{A}_{3}=\begin{bmatrix}1&2&3\\ 1&3&3\\ 1&2&4\end{bmatrix},$ (24) $$

which is an invertible matrix. The corresponding incomplete matrix is $\check{\mathbf{A}}_{3}$:

$$ $\check{\mathbf{A}}_{3}=\begin{bmatrix}1&2&3\\ 1&3&3\end{bmatrix}.$ (25) $$

The original vector is $\mathbf{x}=(x_{1};x_{2};x_{3})=(1;2;3)$.
The frozen vector is $\check{\mathbf{A}}_{3}\mathbf{x}=(14,16)$.

The server obtains the underdetermined system of linear equations as follows:

$$ $\left\{\begin{array}[]{l}x_{1}+2x_{2}+3x_{3}=14\\ x_{1}+3x_{2}+3x_{3}=16\end{array}\right.$ (26) $$

While the server still cannot obtain the complete $\mathbf{x}$, it can deduce that $x_{2}=2$. Unlike the server obtaining prior knowledge of elements through attacks as discussed in Sec. [3.5](#S3.SS5), here, the server deduces $x_{2}=2$ through the computation process within PVF. Clearly, by appropriately selecting the coefficient matrix $\mathbf{A}_{\lambda}$, we can circumvent the aforementioned issue. In the implementation, we initially generate $\mathbf{A}_{\lambda}$ randomly. Subsequently, we transform it into a row echelon matrix and verify that each row has no fewer than two non-zero elements. This ensures individual element privacy. Unless specified otherwise, all subsequent references to $\mathbf{A}_{\lambda}$ in the following text are designed to guarantee individual element privacy.

### 4.2 Security Analysis of PVF with δ 𝛿 \delta italic_δ -security

Let $\mathcal{C}$ denote the set of malicious participants, which is a subset of $\mathcal{U}\cup\mathcal{S}$ and $\mathcal{E}_{j}=\{e_{j(v)}\}_{v\in[1,\delta]}$ denote broken elements of $\mathbf{d^{i(t)}_{j}}$. We first present the following lemmas:

###### Lemma 1 .

Fix $p$, $\mathcal{U}$, $m$, $\lambda$, $\delta<\lambda-1$, $\mathbf{A}_{\lambda}$ and a private vector $\mathbf{x^{i(t)}}=(\mathbf{d^{i(t)}_{1}},\ldots,\mathbf{d^{i(t)}_{\lceil\frac{
m}{\lambda}\rceil}})$ of an honest user $i\in\mathcal{U}$. For any probabilistic polynomial-time (PPT) adversary $M$ who is given $\{\mathbf{y^{i(t)}}\}_{i\in\mathcal{U}}$, $\mathcal{C}$ and $\mathcal{E}_{j}$, the advantage of M to obtain any unbroken element $a_{j}$ is defined as:

$$ $Adv_{M,\delta}^{y}(\lambda):=Pr[SLE_{\mathcal{C},\mathcal{E}_{j}}(\check{ \mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{j}})\rightarrow a_{j}]_{j\in [1,\lceil\frac{m}{\lambda}\rceil]}.$ (27) $$

There exists a negligible function $\epsilon$ such that $Adv^{y}_{M,\delta}(\lambda)\leq\epsilon$.

###### Proof.

We can obtain $rank(\check{\mathbf{A}}^{\delta+1}_{\lambda})=\lambda-\delta-1$ under given conditions, and the number of variables of $\check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{j}}$ is $\lambda-\delta$. Hence there are infinite solutions, and the probability of $M$ determining the unique $\mathbf{d^{i(t)}_{j}}$ is $\frac{1}{\infty}$. What’s more, in Sec. [4.1](#S4.SS1), we demonstrate that $\mathbf{A}_{\lambda}$ can guarantee the privacy of any individual element.
∎

###### Lemma 2 .

Fix $p$, $\mathcal{U}$, $m$, $\lambda$, $\delta<\lambda-1$, $\mathbf{A}_{\lambda}$ and the sum of private vectors $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{x^{i(t)}}$. For any PPT adversary $M$ who is given $\{\mathbf{y^{i(t)}}\}_{i\in\mathcal{U}^{\prime}}$, $\mathcal{C}$, $\mathcal{E}_{j}$ and $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{k^{i(t)}}$, the advantage of M to obtain any unbroken element $a_{j}$ is defined as:

$$ $Adv_{M,\delta}^{y,k}(\lambda):=Pr[SLE_{\mathcal{C},\mathcal{E}_{j}}(\mathbf{A} _{\lambda}\sum_{j\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{j}})\rightarrow a_{ j}]_{j\in[1,\lceil\frac{m}{\lambda}\rceil]}.$ (28) $$

There exists a negligible function $\epsilon$ such that $Adv_{M,\delta}^{y,k}(\lambda)\leq\epsilon$.

###### Proof.

$\mathcal{S}$ can solve $\mathbf{A}_{\lambda}\sum_{j\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{j}}=
\mathbf{b_{j}}$, and obtain $\sum_{j\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{j}}$. For any individual $\mathbf{d^{i(t)}_{j}}$, the information known to $M$ is $\sum_{j\in\mathcal{U}^{\prime}}\mathbf{d^{i(t)}_{j}}$ and $\check{\mathbf{A}}^{\delta+1}_{\lambda}\mathbf{d^{i(t)}_{j}}$. So there are still infinite solutions, and $Adv_{M,\delta}^{y,k}(\lambda)=\frac{1}{\infty}$.
∎

Protocol security requires that no adversary can obtain private information from any honest participant. The view of a participant consists of its internal information and received messages. We define $\mathit{REAL}_{\mathcal{C}}^{\mathcal{U},\lambda}(\{\mathbf{x^{i(t)}}\}_{i\in
\mathcal{U}},\mathcal{U}^{\prime})$ as a random variable representing the joint view of adversaries in an actual protocol execution and $\mathit{SIM}_{\mathcal{C}}^{\mathcal{U},\lambda}(\{\mathbf{x^{i(t)}}\}_{i\in
\mathcal{U}},\mathcal{U}^{\prime})$ as the joint view of adversaries in a simulated protocol execution. Given a secure aggregation protocol that can maintain security in the active adversary setting, the following theorem guarantees its security when integrated with PVF. Our proof is carried out in a Random Oracle model. In this model, we add one trapdoor function to inform $SIM$ of the sum of existing honest users’ private information. During one execution of the protocol, $SIM$ can only access it once to obtain necessary information. The ideal function is ${Ideal}_{{\{\mathbf{x^{i(t)}}\}}_{i\in\mathcal{U}\backslash\mathcal{C}}}^{\mu}
(L)$, defined as follows:

$$ $\leavevmode\resizebox{433.62pt}{}{${Ideal}_{{\{\mathbf{x^{i(t)}}\}}_{i\in \mathcal{U}\backslash\mathcal{C}}}^{\mu}(L)=\left\{\begin{aligned} \sum_{i\in L }\mathbf{x^{i(t)}}&,~{}L\subseteq(\mathcal{U}\backslash\mathcal{C})~{}and~{}|L |\geq\mu\\ \bot&,~{}otherwise\\ \end{aligned}\right.$}.$ (29) $$

###### Theorem 1 .

Security against malicious participants. For all $\lambda>2,\mathcal{U},\mathbf{x^{i(t)}}_{i\in\mathcal{U}},\mathcal{U}^{\prime}$, $\mathcal{C}\subseteq\mathcal{U}\cup\{\mathcal{S}\}$ and SAP maintaining security in the active adversary setting, there exists a PPT simulator $SIM$ such that:

$$ $\mathit{SIM}_{\mathcal{C}}^{\mathcal{U},\lambda}(\{\mathbf{x^{i(t)}}\}_{i\in \mathcal{U}},\mathcal{U}^{\prime})\equiv\mathit{REAL}_{\mathcal{C}}^{\mathcal{ U},\lambda}(\{\mathbf{x^{i(t)}}\}_{i\in\mathcal{U}},\mathcal{U}^{\prime}),$ (30) $$

where “$\equiv$” denotes the distributions are identical.

###### Proof.

We use a standard hybrid argument to prove the theorem. We define a sequence of hybrid distributions ${H}_{0},{H}_{1},\ldots$ to denote a series of modifications to $REAL$, which can finally get $SIM$. We prove $SIM$ and $REAL$ are indistinguishable by proving two adjacent hybrids are indistinguishable.

- $H_{0}$
In this hybrid, $SIM$ is exactly the same as $REAL$.
- $H_{1}$
This hybrid is similar to the previous one, except we replace the frozen vectors $\{\mathbf{y^{i(t)}}\}_{i\in\mathcal{U}}$ received by $\mathcal{S}$ with uniformly random vectors selected by $SIM$. Lemma [1](#Thmlemma1) guarantees $\mathcal{S}$ does not obtain any private information from honest users through frozen vectors, hence the distribution of this hybrid is indistinguishable from the previous one.
- $H_{2}$
This hybrid is distributed similarly to the previous one, except we replace messages conveyed in SAP with random strings of equal length. The security of SAP guarantees the distribution of this hybrid is indistinguishable from the previous one.
- $H_{3}$
This hybrid is distributed similarly to the previous one, except for the following modification. $\mathcal{C}$ obtains $\sum_{i\in\mathcal{U}^{\prime}\backslash\mathcal{C}}\mathbf{x^{i(t)}}$ by calling ${Ideal}_{{\{\mathbf{x^{i(t)}}\}}_{i\in\mathcal{U}\backslash\mathcal{C}}}^{\mu}
({\mathcal{U}^{\prime}\backslash\mathcal{C}})$. $SIM$ aborts if there is an illegal request. Lemma [2](#Thmlemma2) guarantees $\mathcal{C}$ does not obtain any private information from honest users, so the distribution of this hybrid is indistinguishable from the previous one.

Therefore, the distribution of $SIM$ which is the same as $H_{3}$ is indistinguishable from $REAL$. $SIM$ does not depend on the inputs of honest parties. $\mathcal{C}$ can only learn about the sum of original vectors. If too many users drop out, SAP will abort and still guarantee the above conclusion.
∎

Clearly, the security of SAP integrated with PVF still holds in the semi-honest setting.

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Theorem 1 .

###### Proof.

### 4.3 Security Analysis of Extensions

User Commitment Extension. With the incorporation of this extension into PVF, malicious participants may gain additional knowledge about any honest user $i$, limited to the random vector $\bm{\zeta}^{i(t)}$ and the commitment vector $\mathbf{c^{i(t)}}$ of $\mathbf{x^{i(t)}}$. The hiding and binding property of Pedersen commitment [] ensures the privacy of $\mathbf{x^{i(t)}}$.

Result Verification Extension.
In this extension, the additional process involves validating $\sum_{i\in\mathcal{U}^{\prime}}\mathbf{y^{i(t)}}$. The method employed mirrors VerSA [], which ensures that malicious participants cannot compromise the privacy of honest participants.

## 5 Evaluation

In this section, we evaluate the performance of PVF to answer the following questions:

- $\mathbf{Q1}$
How does the theoretical computation complexity of SAP change before and after the integration of PVF?
- $\mathbf{Q2}$
Can PVF effectively mitigate SAP computation costs in practice? And how beneficial is it during actual model training?
- $\mathbf{Q3}$
How do hyperparameters (e.g., $\lambda$, $\delta$ and $n$) influence the performance of PVF?
- $\mathbf{Q4}$
What additional computation overhead does the inherent calculation of PVF entail? Following the incorporation of the user commitment extension or result verification extension, how much will the overhead of PVF increase?

**TABLE I: Theoretical complexity of SAP without and with PVF of single-round aggregation in the semi-honest setting. $\bm{O(m)}(n)$ in the rightmost column indicates the communication complexity pertains to users, followed by the number of interactions between users and the server. “P. of G. M.” stands for privacy of the global model. In the real world, $p\gg m\gg n$. $\uparrow$ indicates the integration of PVF into the protocol would increase its theoretical complexity.**
| SAP | User | Server | P. of | Communi. (Inter.) |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| w/o PVF | w/ PVF | w/o PVF | w/ PVF | G. M. |  |  |
| PPDL[] | $\bm{O(m)}$ | $O(\lambda m)\uparrow$ | $O(mn)$ | $O(\frac{1}{\lambda}mn+\lambda m)$ | ✓ | $\bm{O(m)}$ (1) |
| EPPFL[] | $\bm{O(m)}$ | $O(\lambda m)\uparrow$ | $O(mn)$ | $O(\frac{1}{\lambda}mn+\lambda m)$ | $\times$ | $O(m)$ (2) |
| NIVP-DS[] | $\bm{O(m)}$ | $O(\lambda m)\uparrow$ | $O(mn)$ | $O(\frac{1}{\lambda}mn+\lambda m)$ | ✓ | $\bm{O(m)}$ (1) |
| PracAgg[] | $O(mn+n^{2})$ | $O(\frac{1}{\lambda}mn+\lambda m+n^{2})$ | $O(mn^{2})$ | $O(\frac{1}{\lambda}mn^{2}+\lambda m)$ | $\times$ | $O(m+n)$ (4) |
| PracAgg+[] | $O(mlogn+log^{2}n)$ | $O(\frac{1}{\lambda}mlogn+\lambda m+log^{2}n)$ | $O(mnlogn+nlog^{2}n)$ | $O(\frac{1}{\lambda}mnlogn+\lambda m+nlog^{2}n)$ | $\times$ | $O(m+logn)$ (4) |
| EffiAgg[] | $O(m+n^{2})$ | $O(\lambda m+n^{2})\uparrow$ | $O(m\sqrt{p}+n)$ | $O(\frac{1}{\lambda}m\sqrt{p}+\lambda m+n)$ | $\times$ | $O(m+n)$ (4) |
| LPPFedL[] | $O(m+n^{2})$ | $O(\lambda m+n^{2})\uparrow$ | $\bm{O(m+n)}$ | $O(\lambda m+n)\uparrow$ | $\times$ | $O(m+n)$ (4) |
| VerSA[] | $O(mn+n^{2})$ | $O(\frac{1}{\lambda}mn+\lambda m+n^{2})$ | $O(mn^{2})$ | $O(\frac{1}{\lambda}mn^{2}+\lambda m)$ | $\times$ | $O(m+n)$ (4) |

### 5.1 Experimental Settings

Baselines. We select $8$ baselines that encompass $6$ types of SAP:

- •
PPDL [], utilizing Single-private-key HE, renders the server incapable of accessing aggregated results, thereby safeguarding the global model, all while necessitating only a single interaction between the users and the server.
- •
EPPFL [], relying on Multi-private-key HE, requires two interactions between the users and the server.
- •
NIVP-DS [], based on SMPC, requires two non-colluding servers, while involving only a single interaction between the users and the servers.
- •
PracAgg [], based on Pair-wise Masking, is widely regarded as the state of the art, involving multiple interactions between the users and the server.
- •
PracAgg+ [], built upon PracAgg, exhibits a more efficient communication structure.
- •
EffiAgg [], based on Non-pair-wise Masking, requires server computation of discrete logarithms alongside multiple interactions between users and the server.
- •
LPPFedL [], based on non-pair-wise masking, necessitates users to transmit multiple high-dimensional vectors along with multiple interactions.
- •
VerSA [], built upon PracAgg, enables the Verification of server-aggregated results.

To underscore the focal point of our work, our attention is exclusively directed towards secure-aggregation-related operations within the baselines, omitting other parts like “weight aggregation” in EPPFL.

Implementation Details.
We implement the baselines using Python. Specifically, we utilize AES-GCM with 128-bit keys for the symmetric authenticated encryption, standard $(t,n)$ Shamir Secret Sharing [], AES in counter mode for the pseudorandom generator, SHA-256 hash to implement a homomorphic pseudorandom generator for EffiAgg, Sympy library to compute discrete logarithms for EffiAgg, and Paillier Encryption with 1024-bit keys for PPDL. We run on a Linux workstation with 32GB of RAM and an AMD Ryzen 5 5600G. We use 1 NVIDIA GeForce RTX 3090 GPU with 24GB RAM only for model training, excluding the aggregation process. In all experimental settings, the space of the elements in the input vectors is 32-bit.
Same with PracAgg, our main experiments are conducted under a semi-honest setting, with a specific focus on assessing the speed enhancement brought by PVF. We disregard operations such as digital signatures and public key infrastructure in the active adversary setting, which will not impact the asymptotics of the results [].

Evaluation Metrics. To describe the efficacy of PVF, we denote the ratio between the overheads before and after integrating PVF as Improvement Factor. We utilize Aaccuracy to evaluate model performance. When evaluating communication overhead, we track costs for a single user, with the costs of the server being $n$ times that of one user, a convention widely adopted in prior works [, ]. The experimental results provided below are the average outcomes from 5 repeated executions.

### 5.2 Theoretical Complexity Analysis ( 𝐐𝟏 𝐐𝟏 \mathbf{Q1} bold_Q1 )

After integrating PVF, the number of entries to be aggregated reduces to $\frac{1}{\lambda}$ of the original quantity.

Communication. The communication overhead for internal vector-independent operations within SAP, such as key agreement and secret sharing, does not decrease, and the vectors sent from each user are $\mathbf{y^{i(t)}}\in\mathbb{Z}_{p}^{m-\lambda}$ and $\mathbf{k^{i(t)}}\in\mathbb{Z}_{p}^{\lambda}$, which contain the same number of entries as $\mathbf{x^{i(t)}}\in\mathbb{Z}_{p}^{m}$. Hence, the theoretical communication complexity of SAP remains unchanged. In HE-based SAP, PVF reduces the proportion of ciphertexts, i.e., $1\to\frac{1}{\lambda}$, within the vectors that users need to transmit, bringing communication improvements in practice. For specific details on the extent of gain, please refer to Sec. [5.3](#S5.SS3).

Computation. The additional computation operations required by PVF involve conducting $\lceil\frac{m}{\lambda}\rceil$ matrix-vector multiplications by both users and the server, incurring a computation cost of $O(\lambda m)$.

The theoretical complexity for one aggregation of users and the server, before and after PVF integration, is summarized in Table [I](#S5.T1), which indicates that for some SAP, the theoretical computation complexity increases after integrating PVF. This is attributed to the linear transformation required for the entire original vector within PVF. However, intuitively, the computation time for secure aggregation per entry tends to be significantly greater compared to the computation time per entry in linear transformations. This suggests that PVF still manages to compress computation overhead, which is evident in subsequent experiment outcomes.

Extensions. UCE necessitates users to commit to each dimension of the original vectors, while the server needs to validate each dimension. RVE requires users to submit frozen vectors twice and the server to perform summations twice. Thereby, both UCE and RVE impose on each participant an additional communication complexity of $O(m)$ and computation complexity of $O(m)$. $\delta$-security extension doesn’t introduce additional computation overhead to PVF but alters the compression factor from $\lambda$ to $\frac{\lambda}{\delta+1}~{}(\delta<\lambda-1)$.

**TABLE II: Comparison of secure aggregation protocols computation time (in milliseconds) and communication cost (in KB) before and after integrating PVF for a single round. The number of users $n$ is set to 100, with $\lambda$ set as 100. w/ denotes the corresponding protocol integrated with PVF.**
| Vector Length $(m)$ | 100k | 500k |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Operation | User | Server | Server | Server | Comm. Cost | User | Server | Server | Server | Comm. Cost |
| Dropout rate $(\eta)$ | 0% | 0% | 10% | 30% | 10% | 0% | 0% | 10% | 30% | 10% |
| PPDL[] | 139010 | 29759 | 27418 | 21789 | 27761 | 708579 | 149293 | 136155 | 107998 | 138679 |
| w/ PVF | 1401 | 304 | 283 | 225 | 859 | 7128 | 1571 | 1446 | 1133 | 4291 |
| Improvement Factor | $\bm{99.2\times}$ | $\bm{97.9\times}$ | $\bm{96.8\times}$ | $\bm{96.8\times}$ | $\mathbf{32.3\times}$ | $\bm{99.4\times}$ | $\bm{95.0\times}$ | $\bm{94.1\times}$ | $\bm{95.3\times}$ | $\mathbf{32.3\times}$ |
| EPPFL[] | 3464 | 755163 | 754261 | 749279 | 9962 | 17582 | 3763769 | 3732358 | 3745663 | 49798 |
| w/ PVF | 44 | 7686 | 7642 | 7711 | 681 | 219 | 38833 | 38924 | 39612 | 3400 |
| Improvement Factor | $\bm{78.7\times}$ | $\bm{98.2\times}$ | $\bm{98.7\times}$ | $\bm{97.2\times}$ | $\mathbf{14.6\times}$ | $\bm{80.3\times}$ | $\bm{97.0\times}$ | $\bm{95.9\times}$ | $\bm{94.6\times}$ | $\bm{14.6\times}$ |
| NIVP-DS[] | 15 | 386 | 372 | 331 | 586 | 72 | 1902 | 1834 | 1789 | 2932 |
| w/ PVF | 13 | 10 | 9 | 12 | 586 | 63 | 49 | 44 | 39 | 2931 |
| Improvement Factor | $\bm{1.2\times}$ | $\bm{38.6\times}$ | $\bm{41.3\times}$ | $\bm{27.6\times}$ | $\setminus$ | $\bm{1.1\times}$ | $\bm{38.9\times}$ | $\bm{41.7\times}$ | $\bm{45.9\times}$ | $\setminus$ |
| PracAgg[] | 13702 | 14249 | 139936 | 307031 | 785 | 73335 | 71607 | 697950 | 1515347 | 3910 |
| w/ PVF | 177 | 187 | 1472 | 3207 | 785 | 779 | 794 | 7063 | 15686 | 3910 |
| Improvement Factor | $\bm{77.4\times}$ | $\bm{76.2\times}$ | $\bm{95.1\times}$ | $\bm{95.7\times}$ | $\setminus$ | $\bm{94.1\times}$ | $\bm{90.2\times}$ | $\bm{98.8\times}$ | $\bm{96.6\times}$ | $\setminus$ |
| PracAgg+[] | 2773 | 13973 | 39735 | 69623 | 782 | 14487 | 70359 | 197540 | 347055 | 3908 |
| w/ PVF | 38 | 159 | 410 | 724 | 782 | 179 | 787 | 2026 | 4319 | 3908 |
| Improvement Factor | $\bm{72.9\times}$ | $\bm{87.9\times}$ | $\bm{97.0\times}$ | $\bm{96.2\times}$ | $\setminus$ | $\bm{80.9\times}$ | $\bm{89.4\times}$ | $\bm{97.5\times}$ | $\bm{80.4\times}$ | $\setminus$ |
| EffiAgg[] | 1227 | 537771 | 537329 | 539814 | 783 | 6014 | 2662161 | 2730404 | 2637768 | 3908 |
| w/ PVF | 32 | 5677 | 5702 | 6135 | 783 | 99 | 27175 | 27440 | 28068 | 3908 |
| Improvement Factor | $\bm{38.3\times}$ | $\bm{94.7\times}$ | $\bm{94.2\times}$ | $\bm{88.0\times}$ | $\setminus$ | $\bm{60.7\times}$ | $\bm{98.0\times}$ | $\bm{99.5\times}$ | $\bm{94.0\times}$ | $\setminus$ |
| LPPFedL[] | 176 | 63 | 59 | 46 | 1564 | 846 | 319 | 291 | 218 | 7814 |
| w/ PVF | 22 | 21 | 20 | 17 | 1564 | 53 | 77 | 70 | 61 | 7814 |
| Improvement Factor | $\bm{8.0\times}$ | $\bm{3.0\times}$ | $\bm{3.0\times}$ | $\bm{2.7\times}$ | $\setminus$ | $\bm{16.0\times}$ | $\bm{4.1\times}$ | $\bm{4.2\times}$ | $\bm{3.6\times}$ | $\setminus$ |
| VerSA[] | 14109 | 14337 | 142513 | 312555 | 1566 | 74708 | 71958 | 711182 | 1558844 | 7816 |
| w/ PVF | 643 | 192 | 1528 | 3291 | 1566 | 3044 | 811 | 7284 | 15878 | 7816 |
| Improvement Factor | $\bm{21.9\times}$ | $\bm{74.7\times}$ | $\bm{93.3\times}$ | $\bm{95.0\times}$ | $\setminus$ | $\bm{24.5\times}$ | $\bm{88.7\times}$ | $\bm{97.6\times}$ | $\bm{98.2\times}$ | $\setminus$ |

### 5.3 Performance Comparison ( 𝐐𝟐 𝐐𝟐 \mathbf{Q2} bold_Q2 )

Initially, we evaluate the overhead of SAP before and after integrating PVF, calculating the improvement factor. Then, we assess the speed enhancement brought by PVF during actual model training.

Effectiveness of compressing costs.
Table [II](#S5.T2) presents the comparison of computation times for baselines before and after integrating PVF.
The results in the table indicate that integrating PVF can yield a speedup ranging from $70\times$ to $99.5\times$ for the majority of baselines when $\lambda=100$.
The inability to achieve a $\lambda\times$ speedup is attributed to operations within SAP such as key agreements and secret sharing, which are independent of vector length, making PVF unable to reduce the computational overhead in this aspect. The acceleration effect of PVF on user-side computations is often slightly weaker than on the server-side, as there are more vector length-independent operations involved on the user side.
Overall, the gain from PVF is the weakest for LPPFedL. This is because LPPFedL increases user communication overhead to achieve highly lightweight masking and unmasking. Consequently, operations like secret sharing and secret reconstruction, independent of vector length, constitute a significant portion of its computation time. Hence, the acceleration effect is not pronounced when the number of entries involved in the protocol is reduced. However, as the original vector length increases from $100k$ to $500k$, the proportion of time spent on masking or encryption rises, so PVF exhibits a more noticeable acceleration effect for these SAP in general.
For PPDL and EPPFL (HE-based SAP), only $\frac{1}{\lambda}$ of the original vector is transformed into ciphertext. Therefore, PVF brings them communication improvements of about $32.3\times$ and $14.6\times$, respectively.

Figure: Figure 4: Comparison of training time and accuracy across various aggregation methods. The number of users involved in the training is $100$, each possessing local data for only two labels. The aggregation spans $300$ rounds, with a random 5% of users dropping out in each round. $\lambda=100$.
Refer to caption: x3.png

Figure: Figure 5: Computation acceleration for secure aggregation brought by different $\lambda$ in PVF. $n=100$, $m=100k$, and $\eta=10\%$.
Refer to caption: x4.png

End-to-end comparison.
We select three widely discussed SAP: PracAgg+, PracAgg, and PPDL. NIVP-DS falls behind due to the requirement of two non-colluding servers, while LPPFedL demands increased communication overhead. We compare $7$ aggregation approaches: plain aggregation, the aforementioned three protocols, and their integration with PVF, to assess the differences in model training time. The model employed is LeNet [], consisting of $61,706$ parameters. The utilized dataset is MNIST [].
As depicted in Fig. [4](#S5.F4), across different aggregation methods, the model eventually achieves commendable training outcomes. However, without PVF, the three SAP run slowly, exhibiting a training time approximately an order of magnitude higher than plain aggregation. Yet, the integration of PVF showcases a significant acceleration effect, greatly reducing the training speed gap between using SAPs and plain aggregation.
Remarkably, PPDL, previously considered impractical due to its use of HE, has its computational overhead significantly mitigated by integrating PVF. And its advantages of operating with a single server, single-interaction communication, and preserving the global model make it more appealing.

### 5.4 Hyperparameter Analysis ( 𝐐𝟑 𝐐𝟑 \mathbf{Q3} bold_Q3 )

In this section, we delve into the impact of certain hyperparameters on PVF performance, including compression factor $\lambda$ and the number of users $n$. We consider the $\delta$ of the $\delta$-security extension as a hyperparameter here. It symbolizes the scenario where the server gains knowledge of $\delta$ elements within every $\lambda$ elements of a user’s original vector through a certain method of intrusion.

$\bm{\lambda}$.
We conduct experiments to analyze the variation in the acceleration effect of PVF on all baselines under different $\lambda$ values, as depicted in Fig. [5](#S5.F5). PVF exhibits a more pronounced acceleration effect for participants with substantial original computational overhead, such as PPDL users. For certain SAP like EffiAgg, the improvement factor of the server can reach up to $1000\times$. As $\lambda$ increases, the improvement factor of PVF gradually stabilizes and may experience a slight decline in certain SAP. This trend emerges because when $\lambda$ becomes sufficiently large, the primary computational overhead in secure aggregation shifts from per-entry processing to vector-independent computations like secret sharing. It’s worth noting that when $\lambda$ reaches a certain threshold, for certain entities with relatively low primary computational load, such as users in NIVP-DS and servers in LPPFedL, integrating PVF may increase their computational overhead (improvement factor less than $1$). This occurs because the computation cost incurred by the linear transformation in PVF becomes notable. Nevertheless, the gains from PVF for the servers in NIVP-DS and users in LPPFedL remain enticing, rendering the cost of the PVF linear transformation negligible.

Figure: Figure 6: Improvement factor variation that PVF brings under different $\delta$. $n=100$, $m=100k$, $\lambda=100$, and $\eta=10\%$.
Refer to caption: x5.png

Figure: Figure 7: The gain introduced by PVF with respect to the number of users, with $\eta=10\%$. $m=100k$, and $\lambda=100$.
Refer to caption: x6.png

$\bm{\delta}$. The integration of PVF with the $\delta$-security extension reduces the entries of vectors involved in secure aggregation to $\frac{\delta+1}{\lambda}(\delta<\lambda-1)$ of their original size. Fig. [6](#S5.F6) demonstrates the impact of increasing $\delta$ on the effectiveness of PVF when $\lambda=100$. It showcases incorporating the $\delta$-security extension does diminish the improvement factor. However, even when $\delta=0.1\lambda$, PVF still yields an acceleration gain of $10\times$ along with communication improvements exceeding $5\times$.

$\bm{n}$. Fig. [7](#S5.F7) displays the variation in the improvement effect of PVF across different $n$. The acceleration effect of PVF remains consistently high for PracAgg+ and PPDL across various $n$, showing no significant fluctuations with an increase in $n$. However, as $n$ rises, the improvement factor of PVF for PracAgg diminishes. This occurs because PracAgg necessitates multiple secret sharings for each user across the entire user set, along with multiple secret reconstructions by the server. The proportion of computational overhead in this aspect increases as $n$ increases. Nonetheless, even when $n$ reaches $1000$, the gain brought by PVF for PracAgg servers remains above $85\times$, with user gain still exceeding $55\times$.

### 5.5 Ablation Study ( 𝐐𝟒 𝐐𝟒 \mathbf{Q4} bold_Q4 )

The computational process of PVF itself primarily comprises three components: (i) Partitioning user original vectors into groups and performing linear transformations on each subgroup before and after executing SAP, which are referred to earlier as freezing and thawing.
(ii) PVF necessitates padding the original vector, thereby increasing the vector size.
(iii) In scenarios demanding higher requirements for aggregation, extensions of PVF introduce additional overhead.
Here, we empirically explore each of these components in sequence.

Figure: Figure 8: Comparison of costs across different integrations. $n=100$, $m=100k$, $\lambda=100$, and $\eta=10\%$.
Refer to caption: x7.png

Figure: Figure 9: Additional computational overhead incurred by PVF itself under different $\lambda$ and vector lengths.
Refer to caption: x8.png

Linear transformation.
Fig. [9](#S5.F9) illustrates the computation costs of freezing and thawing concerning different vector lengths and values of $\lambda$. It is evident that when $\lambda=100$ and the original vector length is substantial (reaching $200k$), the computation time is less than 15 ms, nearly negligible compared to the computational time saved by PVF.
As $\lambda$ gradually increases while vector length remains fixed, the number of loops during freezing and thawing computations decreases in the beginning because of the reduced number of groups, resulting in a slight reduction in computational overhead. When $\lambda$ exceeds 60 and continues to increase, the scale of matrix-vector multiplication gradually rises, consequently increasing the computation cost. However, this cost remains consistently within the range of tens of milliseconds, posing a negligible computation burden.

**TABLE III: Comparison of overhead with and without padding. Padding length is the maximum value, i.e., $\lambda$. $n=100$, $m=100k$, $\lambda=100$, and $\eta=10\%$.**
| Scheme | User computation (ms) | Server computation (ms) | Comm. Cost (KB) |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| No pad | Pad | No pad | Pad | No pad | Pad |  |
| PPDL[] | 1402 | 1403, $\uparrow 1$ | 303 | 304, $\uparrow 1$ | 859 | 860, $\uparrow 1$ |
| EPPFL[] | 41 | 42, $\uparrow 1$ | 7337 | 7351, $\uparrow 14$ | 681 | 681, $\uparrow 0$ |
| NIVP-DS[] | 13 | 13, $\uparrow 0$ | 10 | 10, $\uparrow 0$ | 587 | 587, $\uparrow 0$ |
| PracAgg[] | 162 | 164, $\uparrow 2$ | 1456 | 1463, $\uparrow 7$ | 785 | 785, $\uparrow 0$ |
| PracAgg+[] | 38 | 39, $\uparrow 1$ | 405 | 409, $\uparrow 4$ | 783 | 783, $\uparrow 0$ |
| EffiAgg[] | 29 | 32, $\uparrow 3$ | 5404 | 5482, $\uparrow 78$ | 783 | 783, $\uparrow 0$ |
| LPPFedL[] | 19 | 19, $\uparrow 0$ | 20 | 20, $\uparrow 0$ | 1564 | 1564, $\uparrow 0$ |
| VerSA[] | 652 | 653, $\uparrow 1$ | 1552 | 1553, $\uparrow 1$ | 1566 | 1566, $\uparrow 0$ |

Padding.
In theory, padding introduces an additional cost of less than $\frac{\lambda}{m}$ in computation and communication. Table [III](#S5.T3) showcases the impact of no padding versus padding on the computation and communication overhead $(\frac{\lambda}{m}=0.001)$. It’s evident that the overhead induced by padding is almost negligible.

Extensions.
Fig. [8](#S5.F8) presents the overhead required for SAP when different extensions are added.
Compared to not integrating PVF, the computation overhead after adding extensions is still nearly an order of magnitude lower. Additionally, the result verification extension adds lower computation costs than the user commitment extension.
Communication costs from extensions primarily stem from the transmission of additional vectors, such as commitment vectors. We leave mitigating these overheads to future work.

## 6 Conclusion

We present a pioneering perspective aimed at mitigating the formidable overhead of SAP by reducing the number of involved entries while ensuring intact secure aggregation of original vectors. Based on this, we propose PVF, a concrete portable solution. After integrating with PVF, SAP involves only $\frac{1}{\lambda}$ of original vectors. Moreover, we introduce extensions augmenting functionality and security, providing seamless integration and affirming the preservation of user privacy. Extensive experiments showcase the remarkable improvements in acceleration and communication brought by PVF. Consequently, our method undoubtedly renders SAP genuinely feasible, promising inspiration for future research endeavors.

## Appendix A Notations

The primary notations used in this work are listed in Table [IV](#A1.T4).

**TABLE IV: Notations.**
| Symbol | Definition |
| --- | --- |
| $n$ | Number of users |
| $m$ | Length of original vectors |
| $\eta$ | Dropout rate |
| $\lambda$ | Compression factor |
| $\delta$ | The number of broken elements within every $\lambda$ elements |
| $\mathcal{U}$ | The user set |
| $\mathcal{S}$ | The server |
| $\mathbf{x^{i(t)}}$ | Original vector of $i$ in the $t$-th round of FL |
| $\mathbf{A_{\lambda}}$ | A $\lambda\times\lambda$ invertible matrix |
| $\mathbf{A_{\lambda}^{-1}}$ | The inverse matrix of $\mathbf{A_{\lambda}}$ |
| $\check{\mathbf{A}}_{\lambda}$ | A matrix composed only of the first $\lambda-1$ rows of $\mathbf{A_{\lambda}}$ |
| $\bm{\alpha}_{\lambda}$ | A vector composed of the $\lambda$-th row of $\mathbf{A_{\lambda}}$ |
| $\check{\mathbf{A}}^{\delta+1}_{\lambda}$ | $\check{\mathbf{A}}_{\lambda}$ with $\delta$-security |
| $\bm{\alpha}^{\delta+1}_{\lambda}$ | $\bm{\alpha}_{\lambda}$ with $\delta$-security |
| $SLE_{AK}(\mathbf{Ax})$ | Function for computing $\mathbf{x}$ of $\mathbf{Ax}$ with the knowledge $AK$ |
| $\mathbf{x^{i(t)}_{pad}}$ | $\mathbf{x^{i(t)}}$ after padding |
| $m^{\prime}$ | Length of $\mathbf{x^{i(t)}_{pad}}$ |
| $\mathbf{d^{i(t)}_{j}}$ | The $j$-th group of $\mathbf{x^{i(t)}_{pad}}$ |
| $\mathbf{y^{i(t)}}$ | Frozen vector of $\mathbf{x^{i(t)}_{pad}}$ |
| $\mathbf{k^{i(t)}}$ | Key vector of $\mathbf{x^{i(t)}_{pad}}$ |
| $\mathbf{c^{i(t)}}$ | Commitment vector of $\mathbf{x^{i(t)}}$ |
| $\bm{\zeta}^{i(t)}$ | Corresponding random vector of $\mathbf{c^{i(t)}}$ |

## Appendix B Related Work

In this section, we introduce various types of secure aggregation protocols, most of which can be seamlessly integrated with PVF.

SMPC-based Aggregation Protocols. Secure Multi-Party Computation (SMPC) [] involves multiple participants collaborating to complete a computational task while ensuring that the individual inputs of each participant remain confidential throughout the process. In certain works [, , ], users distribute locally trained models to a group of noncollusive proxies capable of collaboratively computing aggregate results.

**TABLE V: Symbolic representation of SAP execution process without and with PVF. The symbols’ meanings are as follows: $US$: User Selection; $UG$: User Grouping; $KA$: Key Agreements among Users; $SS$: Secret Sharing; $E/M$: Encryption or Masking user’s original vectors; $UA$: Upload and Aggregation; $D/U$: Decryption or Unmasking vectors; $Ver$: Verification of aggregated results; $F$: Freezing process in PVF Main Method, generating frozen vectors and key vectors; $T$: Thawing process in PVF Main Method, deriving all entries based on aggregated entries; $RV$: Result Verification Extension of PVF; $X^{\prime}$: Specialized design for process $X$ in the corresponding protocol; $SA(\cdot)$: Operations involved in the aggregation process; $\square$: Protocol can execute in the semi-honest setting; $\blacksquare$: Protocol can execute in the active adversary setting.**
| Type | Scheme | w/o PVF | w/ PVF |
| --- | --- | --- | --- |
| $\setminus$ | PlainAgg | $[US,UA]$ | $\setminus$ |
| HE-based | PPDL[] | $[US,\mathbf{SA}(KA,E/M,UA,D/U)]_{\square}$ | $[US,F,\mathbf{SA}(KA,E/M,UA,D/U),T]_{\square}$ |
| EPPFL[] | $[US,\mathbf{SA}(KA,E/M,UA,D/U)]_{\square}$ | $[US,F,\mathbf{SA}(KA,E/M,UA,D/U),T]_{\square}$ |  |
| SMPC-based | NIVP-DS[] | $[US,\mathbf{SA}(KA,SS,E/M,UA,D/U)]_{\square}$ | $[US,F,\mathbf{SA}(KA,SS,E/M,UA,D/U),T]_{\square}$ |
| Mask-based | PracAgg[] | $[US,\mathbf{SA}(KA,SS,E/M,UA,D/U)]_{\square\blacksquare}$ | $[US,F,\mathbf{SA}(KA,SS,E/M,UA,D/U),T]_{\square\blacksquare}$ |
| PracAgg+[] | $[US,\mathbf{SA}(UG,KA,SS,E/M,UA,D/U)]_{\square\blacksquare}$ | $[US,F,\mathbf{SA}(UG,KA,SS,E/M,UA,D/U),T]_{\square\blacksquare}$ |  |
| EffiAgg[] | $[US,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U^{\prime})]_{\square\blacksquare}$ | $[US,F,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U^{\prime}),T]_{\square\blacksquare}$ |  |
| LPPFedL[] | $[US,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U^{\prime})]_{\square}$ | $[US,F,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U^{\prime}),T]_{\square}$ |  |
| Result Veri. | VerSA[] | $[US,\mathbf{SA}(KA,SS,E/M,UA,D/U,Ver)]_{\square}$ | $[US,F,\mathbf{SA}(KA,SS,E/M,UA,D/U,Ver),RV,T]_{\square}$ |
| Multi. Privacy | LTPA[] | $[US^{\prime},\mathbf{SA}(KA,SS,E/M,UA,D/U)]_{\square}$ | $[US^{\prime},F,\mathbf{SA}(KA,SS,E/M,UA,D/U),T]_{\square}$ |
| MRSA[] | $[US^{\prime},\mathbf{SA}(KA,SS,E/M,UA,D/U)]_{\square}$ | $[US^{\prime},F,\mathbf{SA}(KA,SS,E/M,UA,D/U),T]_{\square}$ |  |
| Resist. M. Incon. | $\setminus$ | $[US,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U)]_{\square}$ | $[US,F,\mathbf{SA}(KA,SS,E/M^{\prime},UA,D/U),T]_{\square}$ |

Mask-based Aggregation Protocols. Leveraging pairwise mask, PracAgg [] augments users’ original vectors with a dual-layer One-time Pad for masking privacy. Enhancements in communication topology [, , ], in conjunction with quantization [, ] and sparsity techniques [, ], reduce the communication overhead of PracAgg. EffiAgg [] harnesses additive homomorphism of Shamir secret sharing, thereby enhancing dropout handling efficiency. SASH [] and FLDP [] streamline masking and unmasking procedures based on the Learning With Errors (LWE) problem. Additionally, LPPFedL [] reuses secret sharing to achieve a lightweight secure aggregation scheme.

HE-based Aggregation Protocols. Within such protocols, users employ HE to encrypt model update information before submission and the server performs cipher-text summation computations. In certain protocols [, , ], all users share a single private key kept confidential from the server, allowing users to collectively decrypt the aggregated result. Some enhancements [, , ] integrate threshold cryptography, necessitating collaboration from a threshold number of users for message decryption. While elevating security assurances over a single-key system, such configurations demand more interactions between the users and the server.

DP-based Aggregation Protocols. DP-based approaches [, ] add noise to model updates to protect sensitive information, requiring relatively minimal computational overhead to achieve secure aggregation. However, these methods also diminish the utility of data. Balancing security and data utility remains a significant challenge in such schemes, making it difficult to precisely manage in practical applications [].

Defense Against Malicious Server. Latest works indicate the malicious server can launch aggregation falsification attacks [], model inconsistency attacks [] and multi-round privacy leakage attacks []. Verifiable protocols [, , ] are able to verify the aggregation results through commitments sent by the server. Appending the hash of the received model to the pseudorandom generator seed can resist model inconsistency attacks without incurring additional overhead []. Some works [, ] propose an innovative user selection mechanism to mitigate user privacy leakage in multiple rounds of aggregation.

## Appendix C Portability Analysis

We conduct an analysis of PVF’s portability here.
PPDL [] and EPPFL [] employ homomorphic encryption, eliminating the need for secret sharing. NIVP-DS [] constitutes a dual-server secure multi-party computation scheme, requiring users to share secrets between two servers. PracAgg [] and PracAgg+ [] represent classic mask-based solutions, with PracAgg+ necessitating an additional user grouping process. EffiAgg [] and LPPFedL [] respectively introduce specialized masking mechanisms to lightweight PracAgg. VerSA [] enables users to verify the aggregated result at the conclusion, and its integration with PVF requires RVE. LTPA [] and MRSA [] individually design specific user selection mechanisms to ensure privacy in multi-round aggregation. Resistance against model inconsistency attacks can be achieved by making slight modifications to the mask method without incurring additional overhead [].

We symbolically represent the entire process of federated learning aggregation in Table [V](#A2.T5). It is evident that PVF is decoupled from SAP, not interfering with the internal execution process of SAP. Furthermore, integration with PVF does not necessitate additional security assumptions. However, SAP employing DP cannot integrate with PVF because such SAP cannot attain precise aggregation results, resulting in inaccurate completion of the thawing phase within PVF.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 1
presentation: 1
questions: Please see the comment in the weaknesses.
soundness: 1
strengths: 1. This paper considers a timely and important problem in secure aggregation protocol to reduce computational and communication overhead.
summary: This paper introduces $\lambda$-SecAgg, a secure aggregation protocol for federated learning (FL) designed to reduce computational and communication overhead through Partial Vector Freezing (PVF). This paper claims that by freezing and processing only a fraction of the private vector entries, the method significantly reduces the burden on the server and participating devices while ensuring all vector entries are eventually aggregated. To further enhance privacy, the paper incorporates Disrupting Variables Extension (DVE). The authors empirically demonstrate substantial performance gains in terms of speedup and communication reduction across various secure aggregation protocols.

While the paper presents an interesting method to reduce the overhead in secure aggregation, the privacy analysis in Section 4.1 is fundamentally flawed. The authors underestimate the information leakage from $y^{i}$, which compromises the claimed privacy guarantees.
weaknesses: 1. Most importantly, the privacy analysis in Section 4.1, which claims no privacy leakage from $y^{i}$, is flawed. Although the paper asserts that no specific element of the original vector $x$ can be deduced directly from $y^{i}$, this does not mean there is no privacy leakage. In fact, $y^{i}$ reveals significant information about $x$. For example, in the case where $\lambda = 2$ and $x$ has two elements, the server can infer $x_1$ in terms of $x_2$ from $y^{i} = a_{11}x_1 + a_{12}x_2$. While $x_1$ cannot be fully determined without $x_2$, the conditional probability of guessing $x_1$ correctly is now $1/p$ instead of $1/{p^2}$. This reduction in entropy, $H(x)$, shows that $y^{i}$ contains valuable information, thus reducing privacy. The authors should revise the privacy analysis and clarify the impact of knowing $y^{i}$ on the security of the original vectors.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. The baseline runtime figures for the secure aggregation protocols presented in Figure 1 and Table 1 appear notably higher than those reported in related literature. For instance, in the case of PracAgg with a vector length of 100k elements, Figure 1 shows a client runtime of 14 seconds and a server runtime of 140 seconds. In contrast, the original paper by Bonawitz et al. (2017) reports significantly lower runtimes for similar conditions, with client runtimes around 300 milliseconds (Figure 6a) and server runtimes at most 5 seconds (Figure 7a). Could you clarify the reasons for this discrepancy in runtime comparisons?
2. Could you provide a more detailed analysis of the privacy impact of your scheme, particularly focusing on the amount of differentially private noise that would be sufficient to mitigate privacy risks effectively? A clearer discussion on how the noise level was determined and its implications on both privacy and utility would be valuable.
soundness: 2
strengths: - The focus of privacy-preserving federated learning is a crucial topic
- Extensive evaluation that covers a wide range of existing secure aggregation protocols
summary: The authors present a new system to improve the computational overhead of secure aggregation using a new approach called Partial Vector Freezing. This approach reduces the number of entries processed in the secure aggregation protocol, by projecting chunks of the client input vector onto a different space, and only aggregating $1/\lambda$ of the entries of each chunk securely and sending the rest of the entries in the clear. The server aggregates the entries from all clients and recovers the original input vectors by projecting the inputs back to the original space. The paper further bolsters privacy through the Disrupting Variables Extension, which applies noise calibrated for Local Differential Privacy to frozen vectors. Experimental results demonstrate substantial computation improvements compared to state-of-the-art secure aggregation protocols.
weaknesses: - The approach impacts the robust privacy guarantees traditionally upheld by state-of-the-art secure aggregation protocols. These protocols typically ensure that an adversary gains no additional information about the inputs of honest clients beyond what is inferred from the aggregated output. However, Partial Vector Freezing (PVF) significantly reduces this privacy. As pointed out by the authors, it is possible for the server to learn whether two clients have similar vector chunks. Although the authors propose a mitigation strategy through Local Differential Privacy to reduce the detection of exact matches, this measure does not fully mitigate the issue of input privacy. The noised client inputs may still leak partial information that allows the server to deduce similarities between inputs. Given this trade-off, the computational gains provided by PVF do not justify the notable privacy impact. For instance, in the context of PracAgg, the masking computation is relatively lightweight. It involves field operations and pseudorandom generator evaluations, typically implemented with efficient cryptographic functions like AES. Additionally, the more computationally intensive pairwise key agreements are independent of the vector size and remain necessary regardless of the implementation of PVF.
- Another concern is the soundness of the security proof presented in Theorem 1. Specifically, the claim that the protocol execution is indistinguishable from random simulation seems to be inaccurate. The distribution of Hybrid 1 is not indistinguishable from that of Hybrid 0, as the distribution of frozen vectors $y_i$ does not exhibit properties of uniformly sampled vectors. While the random vectors are sampled uniformly from $\mathbb{Z}_p$, the frozen vectors in the protocol are the actual inputs masked with centered Gaussian noise of bounded variance. This results in a non-uniform distribution over $\mathbb{Z}_p$ undermining the indistinguishability between the two hybrids. Furthermore, other parts of the security proof are incomplete.  For instance, in Hybrid 3, it is stated that the adversary-controlled clients $\mathcal{C}$ call the ideal functionality. However, in simulation-based proofs, it is typically the simulator, not the adversary, that has direct access to the ideal functionality. Clarifying this aspect would strengthen the proof’s rigor and ensure alignment with standard cryptographic practices.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: This paper presents a novel and practical approach to reduce the computational overhead of secure aggregation in federated learning by proposing λ-SecAgg with partial vector freezing (PVF). The strengths of the method lie in its innovative design, theoretical rigor and comprehensive evaluation, showing significant performance improvements. However, there are areas that could benefit from further clarification, particularly in terms of readability, real-world evaluation, and the impact of noise on accuracy. It is recommended that the authors consider the above comments to further refine and optimize the paper.
soundness: 2
strengths: Innovation: The concept of freezing and unfreezing vector entries in the context of secure aggregation is very novel. This approach effectively reduces the computational burden on SAP, which has been a significant bottleneck in real-world federated learning applications, especially for large-scale models such as Large Language Models (LLMs).

Comprehensive Evaluation: The authors evaluate their approach on seven different baselines covering various secure aggregation protocols (e.g., homomorphic encryption-based, SMPC-based, mask-based). The experimental results show substantial improvements in computation time and communication cost.

Privacy and Security: The paper proves the privacy guarantees of λ-SecAgg under semi-honest and active adversary models through security analyses. In addition, the authors introduce extensions such as DVE, which further strengthens the privacy guarantees.
summary: This paper introduces a novel method called λ-SecAgg, which integrates a module named Partial Vector Freezing (PVF) into Secure Aggregation Protocols (SAPs) for federated learning. The main goal of this method is to reduce the computational overhead by “freezing” most of the entries in user update vectors, allowing only a fraction (1/λ) of the original vector to be processed through secure aggregation. The frozen entries can later be “thawed” to recover the full aggregated vector, ensuring that no information is lost in the final aggregation. Additionally, the paper proposes a Disrupting Variables Extension (DVE) that enhances privacy by adding noise to the frozen entries using Differential Privacy (DP). The authors perform extensive empirical evaluations across seven baselines, demonstrating that PVF can achieve up to 99.5× speedup and 32.3× communication reduction without compromising user privacy or security.
weaknesses: Clarity and readability: Although this paper presents a novel approach, some sections are dense and difficult to understand, especially the mathematical derivations and safety analyses. It is suggested that the authors could improve the readability of these sections by providing more intuitive explanations and breaking down the steps as much as possible. In addition, the readability of some diagrams and formulas (e.g., those in Sections 3 and 4) is too low, and it is suggested that the reader could improve them by simplifying them or providing more detailed explanations.

Impact of noise on accuracy: Although the paper claims that the impact of DVE (adding noise to DP) on accuracy is negligible, the experimental results on the loss of accuracy due to DP noise are not detailed enough. It is suggested that the authors can add relevant experiments for this part.

Scalability to Multiple Users: This paper focuses on performance improvements for single users and servers, but does not discuss scalability to multiple users. It is suggested that the authors validate the approach of this paper in the context of multiple simultaneous users, especially with respect to communication overheads and system latency.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. In practical applications, how should this value \lambda be determined?

2. Are there any fundamental differences between the aggregation method of k^i and that of y^i?
soundness: 3
strengths: 1. The PVF significantly compresses the length of the vector involved in SAP.
2. The disrupting variables extension method improves privacy, without the computational overhead.
3. The authors conduct extensive experiments
summary: The paper addresses the challenges of secure aggregation in federated learning, particularly the high computation costs associated with Secure Aggregation Protocols (SAPs). The paper introduces a novel approach called Partial Vector Freezing (PVF), designed to reduce computation without increasing communication overhead. In addition, the paper proposes the disrupting variable extension to PVF to support enhanced privacy. The extensive experiments show the effectiveness of the proposed proposal.
weaknesses: 1. Lack of Novelty in the Proposed Solution:
While I appreciate the clarity and straightforwardness presented in your methodology, I am concerned about the apparent simplicity of the proposed solution. The approach, as described, seems to lack the level of innovation. Consider expanding on the theoretical background, comparing your method with others in detail, and emphasizing any novel insights or improvements that your solution offers.
2. Informality in Security Analysis:
The security analysis section of your paper appears to be somewhat informal and lacks the rigor typically required for a comprehensive evaluation of a proposed system or method. Security is a critical aspect in many research domains, and a thorough, formal analysis is essential to establish trustworthiness and robustness. I recommend conducting a more structured and detailed security analysis, possibly incorporating formal security proofs, case studies, or simulations to demonstrate the effectiveness of your security measures.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: Please refer to the weakness above.
soundness: 2
strengths: 1.Theoretical proofs.
2.The experimental results demonstrate that PVF achieved 99.5 \times speedup and up to 32.3 \times communication reduction.
summary: This paper devises a portable module named \lamba-SecAgg for secure aggregation in federated learning. The authors also propose an extension involving disrupting variables to enhance privacy. Through extensive experiments, they demonstrate the efficiency of the proposed method, achieving up to 99.5× speedup and up to 32.3× communication reduction.
weaknesses: 1. Writing/technical issues:
(1) In the Introduction section, the author methioed that "the minimal noise added by DP is insufficient to thwart attacks", yet they also suggest considering "DP in the extension for enhanced privacy." Is there a deeper reason or gap that I might have overlooked?
(2) The introduction of "compression-based techniques" in Figure 3 and Section 2 feels somewhat abrupt, primarily due to the lack of clarity in the classification of existing solutions outlined in the Introduction section. I suggest providing a clearer explanation of the criteria used to categorize the methods into secure aggregation techniques and compression-based techniques. Additionally, providing an analysis of the limitations of existing methods would help readers better understand the motivation behind the development of the PVF.
(3) The definition of adversary in threat model is not very clear, particularly regarding key aspects such as adversary knowledge and adversary capabilities, which have not been adequately explained or defined.
(4) Figure 4 is too abstract to understand.
(5) In Section 3.3, while discussing secure aggregation, it is noted that the requirements for data accuracy are relatively high. However, the introduction of DP typically involves adding noise to the data. It would be beneficial to clarify how the accuracy of the data can be maintained after noise has been added, particularly in the context of the freezing and melting processes.

2. Experimental issues:
(1)The neural network architectures and datasets are not intruduced in the ‘Experimental settings’.
(2)The setting of (\lambda = 100) in some experiments requires further explanation.
(3)The experimental validation, although comprehensive, is limited to specific neural network architectures and datasets. Its generalisability to other models and types of data may require further examination.

---

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: Could please you address the points raised in "Main Weaknesses" above? 

In addition to these questions: 
- Could you illustrate in more detail what which masking operations of the compared SecAgg protocols do you avoid by the use of your proposal? It seems that either performing a matrix-vector multiplication or masking operations does not eliminate the dependency of the dimension of a vector $x$ in the computation. 

- If we compare the computational cost of the SecAgg protocol and the computational cost of a local training step for a client, what proportion of the computation the SecAgg overhead represents? How does this change for different models?
soundness: 1
strengths: - Reducing the communication cost in privacy preserving ML an interesting topic.

- The presentation of the protocol is fairly clear.
summary: The paper studies how to reduce the computational cost in privacy-preserving federated learning (FL) with secure aggregation (SecAgg). SecAgg is a primitive that improves the privacy-utility trade-off in FL as it hides individual model updates sent to the server. However, most efficient applications require to mask each parameter of the model with random noise, incurring into a large computational cost if models are big. 

The current work proposes a technique that reduces the computational cost by only performing SecAgg to a subset of model parameters, while still recovering the (claimed to be) private aggregation of the entire model.
weaknesses: # Main Weaknesses 

The major weakness of the protocol is the **lack of any standard notion of security**. The protocol is based on the fact that revealing the undetermined system of linear equations $\breve{A}x = y$ where $\breve{A}$ and $y$ are public does not compromise the privacy of $x$. From a security point of view, letting the adversary gain the knowledge of $\breve{A}x$ is **completely unsafe**. A clear example is already given the detailed comments subsection below for certain choices of $\breve{A}$. 

Even if the paper proposes some defenses to avoid the most obvious threats in the choice of $\breve{A}$ (i.e. if the system of equations already directly exposes some coordinates of $x$), these defenses are only a minor improvement in the overall security. The protocol is in fact insecure for any $\breve{A}$. For example, consider that a party joins the aggregation protocol with a vector $x = (x_1, 0, \dots, 0)$ (i.e., a vector where $x_1$ is the only non-zero value). In this case, values of $\breve{A}x$ will always be multiples of $x_1$. Therefore, the claim of Theorem 1 does not hold: multiples of $x_1$ are *distinguishable* from uniformly random numbers, contrary to what is claimed in hybrid 1 ($H_1$) in the proof of Theorem 1 (Appendix D.1).  This renders the proof of Theorem 1 incorrect. 

The computational improvements of this protocol come from the insecure modification described above. This makes the protocol inapplicable. Moreover, the attempts to further "complicate" the linear equations by the presented enhancements also follow an unsafe methodology lacking proper proofs (see my detailed comments below). 

In addition to the above, the work ignores important lines of work in compression under privacy constraints (e.g. see [R1-R5] below) and differentially private-based aggregation (e.g., by the use of correlated noise [R6-R8]), directly related to the current contribution. 


# Detailed Comments 

- Page 2, Section 2: 
    - "Mask-based" approaches are an instantiation of "SMPC-based" approaches. 
    - "(i) improving the masking mechanism":  it is not clear what this means 
    - "Note that the security of FL remains an open issue": this is too broad and it is not clear what "security" means in this context
- Page 3: 
    -  Section 2: "However, their ability to prevent poisoning attacks is limited (Ma et al., 2023)": not sure how the reference is relevant here. Does  (Ma et al., 2023) provides evidence about this statement? 
    - Section 3,  "ultimately imposing significant computational burdens": "burdens" $\rightarrow$ "burden"; is this computational burden significant with respect to the computational cost of local training steps required by ML? 
- Page 4: 
    - Def 1: "... where $AK$ denotes the additional knowledge ..": so far no mention of "additional knowledge has been made", so it is not clear to what this refers. Also, it should be explicitly clarified that $rank(A, Ax)$ means the rank of the horizontal concatenation of $A$ and $Ax$. 
   - "... rendering it impossible to determine that specific confidential vector." this is an overly strong statement (at least if no additional context is given). Consider for example that $A$ equals the identity matrix. Indeed $\breve{A}x$ has infinite solutions (all possible values of the removed coordinate of $x$). However, almost all coordinates of $x$ will be revealed if $\breve{A}x$ is revealed. 
- Page 5, Sec 3.3: 
    -  "... even if some secagg entries are compromised": There is no motivation of the extra defense, explaining how these entries would be compromised. 
    - "complicating the relationships among entries and further enhancing privacy": This lacks a proof. Providing privacy by obscurity (i.e, providing an obfuscation technique without proving that indeed it reduces to hard problem for the adversary) is a bad practice in the field of security.


# References 

[R1] Bassily, Raef, and Adam Smith. “Local, Private, Efficient Protocols for Succinct Histograms.” In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, 127–35. STOC ’15. New York, NY, USA: Association for Computing Machinery, 2015. https://doi.org/10.1145/2746539.2746632.

[R2] Feldman, Vitaly, and Kunal Talwar. “Lossless Compression of Efficient Private Local Randomizers.” In Proceedings of the 38th International Conference on Machine Learning, 3208–19. PMLR, 2021. https://proceedings.mlr.press/v139/feldman21a.html.

[R3] Liu, Yanxiao, Wei-Ning Chen, Ayfer Özgür, and Cheuk Ting Li. “Universal Exact Compression of Differentially Private Mechanisms.” arXiv, May 28, 2024. https://doi.org/10.48550/arXiv.2405.20782.

[R4] Shah, Abhin, Wei-Ning Chen, Johannes Ballé, Peter Kairouz, and Lucas Theis. “Optimal Compression of Locally Differentially Private Mechanisms.” In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 7680–7723. PMLR, 2022. https://proceedings.mlr.press/v151/shah22b.html.

[R5] Triastcyn, Aleksei, Matthias Reisser, and Christos Louizos. “DP-REC: Private & Communication-Efficient Federated Learning.” arXiv, December 7, 2021. https://doi.org/10.48550/arXiv.2111.05454.

[R6] Imtiaz, Hafiz, Jafar Mohammadi, and Anand D. Sarwate. “Distributed Differentially Private Computation of Functions with Correlated Noise.” arXiv, February 22, 2021. https://doi.org/10.48550/arXiv.1904.10059.

[R7] Kairouz, Peter, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. “Practical and Private (Deep) Learning Without Sampling or Shuffling.” In Proceedings of the 38th International Conference on Machine Learning, 5213–25. PMLR, 2021. https://proceedings.mlr.press/v139/kairouz21b.html.

[R8] Sabater, César, Aurélien Bellet, and Jan Ramon. “An Accurate, Scalable and Verifiable Protocol for Federated Differentially Private Averaging.” Machine Learning 111, no. 11 (November 1, 2022): 4249–93. https://doi.org/10.1007/s10994-022-06267-9.

Meta-review: The paper proposes $\lambda$-SecAgg, a secure aggregation protocol for federated learning (FL), to reduce computational and communication overhead using Partial Vector Freezing (PVF). However, most reviewers raised their concerns that PVF significantly reduces this privacy. Despite extensive discussion on these issues, reviewers have maintained their reviews and scores. Given these issues, I recommend rejection.

Decision: Reject