Response to the Issues of Privacy

The statement "In this case, values of $\check{\mathbf{A}}\mathbf{x}$ will always be multiples of $x_1$" has caused me considerable confusion. How can a vector be a multiple of a scalar? Using the parameters from General Response 1 as an example, suppose the user vector is $\mathbf{x}=(7,0,0)$ and $\mathbf{y}=\check{\mathbf{A}}\mathbf{x}=(42,56)$. Could you please provide further clarification using this example? Our approach differs from the compression-based method you mentioned. Their focus is orthogonal to ours, and we have already demonstrated in our paper that our compression is lossless (if without DVE).

Response to Detailed Comments

1. The mask-related approaches indeed belong to SMPC. However, due to the broad implications of mask-related approaches, many works [1][2] classify mask-based solutions separately. "(i) improving the masking mechanism" refers to the introduction of novel masking mechanisms as proposed in [2][3]. "The security of FL" pertains to safeguarding the privacy of user inputs.
2. Please refer to Input correctness in [4] on page 3: "...providing strong guarantees against malicious inputs remains an open problem. Some works use zero-knowledge proofs to bound how much a client can bias the final result, but they are unable to formally prove the absence of all possible attacks." Similarly, establishing strong constraints against malicious inputs remains an unresolved challenge, and it falls beyond the scope of our work. For the end-to-end comparison, please refer to Fig. 2. The local training steps required by ML are independent of the overhead of secure aggregation, and the overhead of the local training steps is not the focus of this paper.
3. $AK$ is addressed in Lemma 1 and Lemma 2 of Appendix D.2 (Eq. 21 and Eq. 22). $\mathbf{A}$ undergoes certain pre-checks (see Sec. 4.1). Since $\mathbf{A}$ is public and agreed upon by all clients, any malicious construction would require collusion among all users and can be detected by the honest users. Clearly, an overly simplistic $\mathbf{A}$ cannot be used.
4. "... even if some secagg entries are compromised": We are considering extreme cases here. "complicating the relationships among entries and further enhancing privacy": We have not employed obfuscation techniques. Our objective is to ensure that $\mathbf{y}_j$ is not solely related to the privacy vector $\mathbf{x}_j$ of the current $j$-th group, but also to elements from other groups (as shown in Eq. 8). This is to prevent the leakage of certain elements within the current group from undermining the security of other elements.
5. Note that PVF does not attempt to alter SAP or eliminate the dependency of the dimension of a vector, it reduces the number of entries processed in SAPs while ensuring intact aggregation of all entries in the original vector. Furthermore, the experimental results of PVF are highly significant.
6. The proportion of SecAgg overhead in the computational cost of a local training step for a client is unrelated to the goal of reducing SAP computational overhead in this paper.

Reference

[1] Liu, Ziyao, et al. "Privacy-preserving aggregation in federated learning: A survey." IEEE Transactions on Big Data (2022).

[2] Liu, Ziyao, et al. "Efficient dropout-resilient aggregation for privacy-preserving machine learning." IEEE Transactions on Information Forensics and Security 18 (2022): 1839-1854.

[3] Stevens, Timothy, et al. "Efficient differentially private secure aggregation for federated learning via hardness of learning with errors." 31st USENIX Security Symposium (USENIX Security 22). 2022.

[4] Ma, Yiping, et al. "Flamingo: Multi-round single-server secure aggregation with applications to private federated learning." 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023.

Let me answer your question regarding the major concerns (i.e., the insecurity of the protocol).

You ask "How can a vector be a multiple of a scalar?": the answer to your question is right there in the example you provide. It is clear that all the elementss of vector $\mathbf{y}$ are multiple of $7$ (i.e., $42= 7\times 6$, $56=7\times 8$). In fact this will happen for any $\check{A}$ you choose. Therefore, the distribution of $\mathbf{y}$ will assign probability equal to $0$ to all numbers that are not multiples of $7$. This distribution is then clearly distinguishable from uniformly random numbers, making (as said in my review) your claim for hybrid 1 (and therefore Theorem 1) incorrect.

This is one way to easily illustrate the security problems, showing the strong dependence between the private data and $\mathbf{y}$. Other broader arguments that align with mine are the ones provided by Reviewers zANE and SAYu.

Response to Questions

1. Please refer to the second paragraph of Appendix E.1 in our paper.
2. Please read Sec. 3.2, specifically the Phase 2: Main.SecAgg(·) section.

We express our sincere gratitude for your recognition and support!

1. About the expression of DP. What we want to express is that relying solely on the minimal noise added by DP is insufficient to thwart attacks, and our solution does not rely solely on DP to ensure privacy.

2. Compression-based baselines. These baselines are the closest in nature to our proposal, so we list them separately.

3. Threat model. Our threat models (please refer to line 145) are

   1. Semi-honest Model[1], also referred to as the "honest-but-curious" model, where participants in a protocol are assumed to follow the protocol correctly but may try to extract additional information from the data they receive. In this model, adversaries do not deviate from the protocol's rules or engage in malicious behavior like collusion or input manipulation. However, they may attempt to infer sensitive data from the information they have access to, using computational resources to gain an advantage. This model is often used in cryptography and secure multiparty computation, where participants are trusted to some extent but must be safeguarded from exploiting any inadvertent information leakage.
   2. Active Adversary Model[1], also known as the "malicious adversary" model. In this scenario, adversaries are not only capable of following the protocol but can also actively deviate from it, forging messages, manipulating inputs, or colluding with other participants to subvert the protocol. This model assumes that adversaries might engage in arbitrary, harmful behavior with the intention of compromising the security or correctness of the system.

4. General Response 1 provides a simple example, which we hope will assist you in understanding Fig.4.

5. Data Accuracy. We add a small amount of DP noise to the original vector before PVF. After PVF and SAP, we get the aggregation result with a little noise, which is consistent with the LDP-based SAP. Due to the existence of SAP, a small $\sigma$ is sufficient. Consistent with [2], we set the standard deviation of the noise to 0.0409 in Fig. 6.

6. Experimental issues. $\lambda = 100$ refers to the parameter $\lambda$ in PVF. In the "End-to-end comparison" in Sec. 5.3 (line 405) and "Disrupting Variables Extension" in Sec. 5.4 (line 446), we introduce the datasets and models used. In other experiments, such as those in Tab. 1 and Fig. 5, the user's original vectors are randomly generated. This is because these experiments primarily focus on the overhead of the secure aggregation phase, and the attributes of models (apart from the total parameter count) and datasets do not influence the results, as consistently pointed out in previous works [3][4].

Reference

[1] Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

[2] Stevens, Timothy, et al. "Efficient differentially private secure aggregation for federated learning via hardness of learning with errors." 31st USENIX Security Symposium (USENIX Security 22). 2022.

[3] Hahn, Changhee, et al. "VerSA: Verifiable Secure Aggregation for Cross-Device Federated Learning." IEEE Transactions on Dependable and Secure Computing 20.1 (2023): 36-52.

[4] Liu, Ziyao, et al. "Efficient dropout-resilient aggregation for privacy-preserving machine learning." IEEE Transactions on Information Forensics and Security 18 (2022): 1839-1854.

We would like to appreciate you for your constructive feedback. We address your questions and concerns in the following.

1. Privacy issues of two identical input. After introducing DVE, Eq. 8 ensures that when the noise of $\mathcal{N}(0,\sigma^2)$ is only added to $\mathbf{x}$, the noise of $\mathcal{N}(0,(1+\frac{l}{\lambda})\sigma^2)$ is added to $\mathbf{y}$. For example: $A_{1,1} (x_{(j-1) \lambda + 1} + \underline{k_1 +\cdots+ k_{\left \lfloor \frac{l}{\lambda} \right \rfloor }})+\cdots+A_{1, \lambda} (x_{j\lambda} + \underline{k_{l- \left \lfloor \frac{l}{\lambda} \right \rfloor} + \cdots + k_l}) =y_{(j-1) \lambda + 1}.$ The additional noise does not affect the recovery of $\mathbf{x}$, as it is eliminated during the thawing process, i.e., $A_{1,1} (\sum x_{(j-1) \lambda + 1} )+\cdots+A_{1, \lambda} (\sum x_{j\lambda} )=\sum y_{(j-1) \lambda + 1} - \underline{ \sum \sum_{o\in [1, \lambda]} A_{1,o}\sum_{r\in \left[(o-1)\left \lfloor \frac{l}{\lambda} \right \rfloor+1,o\left \lfloor \frac{l}{\lambda} \right \rfloor \right]} k_{r} }.$ Moreover, as pointed out in PracAgg[1] on page 12 of their paper: "...almost all of the computation cost comes from expanding the various PRG seeds to mask the data vector. Compared to this, the computational costs of key agreement, secret sharing and reconstruction, and encrypting and decrypting messages between clients, are essentially negligible." Therefore, the efficiency gains brought by PVF are of considerable importance.
2. The indistinguishability between $H_0$ and $H_1$. Here, we no longer prove the randomness of $y^i$. we modify "we replace the frozen vectors $\{\mathbf{y}^{i}\} _ {i\in\mathcal{U}}$ received by $\mathcal{S}$ with uniformly random vectors." in H1 of Theorem 1 to "replace $\{\mathbf{x}^{i}\} _ {i\in\mathcal{U}}$ with random vectors that maintain the same correlation between $\{\mathbf{x}^{i}\} _ {i\in\mathcal{U}}$ and $\{\mathbf{y}^{i}\} _ {i\in\mathcal{U}}$". This adjustment ensures the continued validity of Theorem 1. Please see the modification of the proof Theorem 1 in the document. We proceed to demonstrate that the original vector remains random even with the knowledge of the correlation. Let $\mathbf{x}$ denote a fragment of an original vector. We denote the general solution obtained by the adversary as $\mathbf{x'}=\rho\mathbf{a}+\mathbf{b}$, where $\mathbf{a}$ and $\mathbf{b}$ are solved given $\mathbf{y}^i$, $\rho$ is an uncertain variable. The correct $\rho$ corresponds to $\mathbf{x}$ is $\rho _ *$, i.e., $\mathbf{x} = \rho _ * \mathbf{a}+\mathbf{b}$. It can be seen that $\mathbf{x'}$ differs from $\mathbf{x}$ in both magnitude and direction. That means upon acquiring the correlation, the server essentially gains that $\mathbf{x}$ is still randomly distributed with its initial point and terminal point on two parallel lines respectively (as visually apparent from Fig. 9 in the new PDF), which does not compromise privacy.
3. The call to the ideal function. We expressed it correctly in the main text (line 309). Thank you for pointing out the typo in the appendix.
4. Please note that the server's computation time in PracAgg is not 5 seconds, but rather 50 seconds. Authors of PracAgg do not provide the source code, but we have strictly followed the implementation outlined in their proposal, as detailed in Appendix E.2 in our paper. We speculate that this discrepancy might be due to differences in machine configurations. The results in Ref[2][3] are similar to those in our paper, with the client computation time being around 10 seconds and the server overhead approximately 100 seconds.

Reference

[1] Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

[2] Hahn, Changhee, et al. "VerSA: Verifiable Secure Aggregation for Cross-Device Federated Learning." IEEE Transactions on Dependable and Secure Computing 20.1 (2023): 36-52.

[3] Liu, Ziyao, et al. "Efficient dropout-resilient aggregation for privacy-preserving machine learning." IEEE Transactions on Information Forensics and Security 18 (2022): 1839-1854.

Dear Reviewer zANE:

Thank you for your comment. We hope the following response can help clarify your concerns.

1. Privacy in the Active Adversary Model

In the active adversary model, malicious participants may:

• send malformed or incorrect messages to disrupt the calculations of honest parties.
• forge fake users to engage in the protocol.
• attempt to forge or tamper with the messages of other parties.
• attempt to send a fabricated special message.

All of these attacks can be avoided by the use of symmetric authenticated encryption and digital signatures (as in $H_1$ and $H_2$ of our proof). This security assurance is also evident in the security analysis of other aggregation protocols, such as the proof of Theorem IV.4 in [1] and the proof of Theorem A.2 in [2].

2. Indistinguishability between $H_1$ and $H_0$

In fact, replacing all plaintext inputs with dummy messages in $H_1$ does not change the distribution compared to $H_0$. This is because the symmetric authenticated encryption we employ satisfies both IND-CPA (Indistinguishability under Chosen Plaintext Attack) and INT-CTXT (Integrity of Ciphertexts), as stated in line 878 of our paper. Let's briefly introduce these two security requirements:

• IND-CPA ensures that an encryption scheme maintains indistinguishability under chosen plaintext attacks[3]. It means that even if an attacker can select arbitrary plaintexts and observe their corresponding ciphertexts, they cannot deduce any information related to the plaintext from the ciphertext. In short, the attacker is unable to distinguish between ciphertexts with any significant advantage over random guessing, regardless of the plaintext encrypted.

• INT-CTXT guarantees that an attacker, without knowledge of the plaintext or the key, cannot generate a valid ciphertext that, when decrypted, results in a legitimate plaintext[3].

Thus, after replacing the plaintext in $H_0$ with dummy messages, SIM is unable to distinguish the ciphertexts after encryption. This point is widely acknowledged in the security aggregation literature, as evidenced by the proof of Theorem 6.3 in [2], specifically $Hyb_2$, as well as $Hyb_4$ and $Hyb_5$ of the proof of Theorem A.2 in [2].

If you have any other questions, please let us know.

Reference

[1] Liu, Ziyao, et al. "Efficient dropout-resilient aggregation for privacy-preserving machine learning." IEEE Transactions on Information Forensics and Security 18 (2022): 1839-1854.

[2] Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

[3]Bellare, Mihir, and Chanathip Namprempre. "Authenticated encryption: Relations among notions and analysis of the generic composition paradigm." International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000.

1. Your security proof does not account for actively malicious behavior. I am not the first reviewer to point this out (e.g., see https://openreview.net/forum?id=E1Tr7wTlIt&noteId=iog03MH6Wy). See for instance the Theorem A.2 in your reference [2] for additional steps required to achieve malicious security in secure aggregation protocols.
2. In my understanding of your definition of H1, you “replace the plaintext with dummy messages”. This will lead to a different output of the protocol, because it does not depend on the real inputs anymore. In the hybrids you reference from [2], the replacement is done in such a way that this does not lead to a different output (e.g., only encrypted messages between parties controlled by the simulator).

To be clear, this answer does not address my concerns about security of your protocol.

Your proof still does not account for actively malicious adversaries. While the primitives you reference (e.g., symmetric authenticated encryption and digital signatures) are known to enhance security, your proof does not explicitly demonstrate how these are applied within your protocol to address malicious behavior. I recommend referring to theory on simulation-based proofs or established approaches in related work to illustrate how to formally account for such adversaries.

Similarly, your statement that "the security of the remaining steps [...] is inherently ensured by the integrated SAP itself" is not substantiated in your security proof. Typically, such a claim would require invoking the simulator or ideal functionality of the integrated SAP explicitly. Without this, the connection between the SAP and your protocol's security remains unclear.

Dear Reviewer zANE:

R1. The Relationship between PVF and SAP

From your comments, we guess you may not have fully comprehended the calculation process of PVF. Therefore, we will first provide you with a detailed explanation of the relationship between PVF and the integrated Secure Aggregation Protocol (SAP).

For example, given $\mathbf{x}^i = (x_1, x_2, x_3)$, the user computes $\mathbf{y}^i = \check{\mathbf{A}}(\mathbf{x}^i + \mathbf{e}) = (y_1, y_2)$. The user only inputs $k^i =\alpha(x_3 + e_3)$ into SAP while simultaneously transmitting $\mathbf{y}^i$ as a piggyback message to the server during the protocol. Due to the hardness of LWE search and decision problem, $\mathbf{y}^i$ does not reveal any private information about $\mathbf{x}^i$.

Upon completing the SAP, the user obtains $\sum \mathbf{y}^i$ and $\sum k^i$. By leveraging Eq. (9), $\sum \mathbf{x}$ can be reconstructed. And we refer to the SAP integrated with PVF as $\lambda$-SecAgg. Clearly, throughout this process, PVF does not modify the operations of SAP and remains decoupled from it. As long as the SAP can securely aggregate $\sum k^i$, it can be seamlessly integrated with PVF.

R2. How Cryptographic Primitives are Applied in PVF

The utilization of these cryptographic primitives is illustrated in Fig. 13. Here, based on the description of PVF in R1, we provide a detailed explanation of the active attacks that malicious participants can launch within PVF and how PVF leverages these cryptographic primitives to defend against them.

First and foremost, it is evident that in PVF, the user only transmits $\mathbf{y}^i$ to the server, and the server only sends $\sum \mathbf{y}^i$ back to the users after SAP ends. Notably, $k^i$ and $\sum k^i$ are transmitted through the SAP, independent of PVF.

1. Forging Fake Users to Participate in PVF. This type of attack, also known as a Sybil Attack, involves fake users reporting received information to the server. Such attacks primarily target scenarios where users share secret keys among themselves but keep the keys secret from the server, like PPDL [1]. Alternatively, an attacker may attempt to forge a large number of fake users (more than $\frac{1}{3}|\mathcal{U}|$) to reconstruct users’ private keys in the secret-sharing scheme. Since PVF does not involve information that is kept secret from the server but shared among all users, and consistent with the assumption in [2] that the number of malicious users does not exceed $\frac{1}{3}|\mathcal{U}|$ (line 147), PVF is resistant to this type of attack.

2. Attempting to Forge or Tamper with Honest Users' Messages. Such attacks may occur in PVF in the following situations: malicious participants forging or tampering with an honest user's $\mathbf{y}^i$. This can be avoided by the digital signature $\sigma_{1}^{i}$ employed in PVF. Similarly, malicious participants may attempt to forge or tamper with $\sum \mathbf{y}^i$ sent by the server, which is prevented by the use of $\sigma_{3}$. These protections are reflected in $H_2$ of the proof.

3. Sending Malformed Messages. In PVF, such attacks include malicious users sending malformed ciphertexts of $\mathbf{y}^i$ or the malicious server sending malformed ciphertexts of $\sum \mathbf{y}^i$. Such attacks are prevented by the IND-CPA and IND-CTXT security of the symmetric authenticated encryption used in PVF. If decryption fails, the protocol is immediately terminated. These protections are reflected in $H_1$ of the proof.

4. Intercepting and Stealing Private Information. Malicious adversaries may intercept messages sent by honest users to extract private information. This is effectively avoided by the symmetric authenticated encryption employed in PVF. This protection is reflected in $H_1$ of the proof.

The use of symmetric authenticated encryption and digital signatures to ensure privacy under the active adversary model is a relatively mature application in the field of secure aggregation, and our design follows these existing works. In the proof, under the UC framework, $H_1$ and $H_2$ formally explain the impossibility of active adversaries forging or tampering with messages in PVF, as well as the fact that any attack by an active adversary would lead to the termination of the protocol, thus demonstrating the security of PVF under the active adversary model.

If you believe there are specific steps missing, please do not hesitate to offer your guidance.

R3. Security provided by the Integrated SAP

We believe that after reading R1, you will clearly understand the relationship between PVF and the integrated SAP. PVF and the integrated SAP operate independently and do not interfere with each other. They are completely decoupled.

Therefore, when proving security, we have omitted the security analysis of the aggregation of $k^i$, as the security of the aggregation process for $k^i$ is handled by the integrated SAP, not by PVF. This is why we can assert that "the security of the remaining steps, except PVF, is inherently ensured by the integrated SAP itself".

If you believe there are any deficiencies in our approach, please feel free to share your insights.

Reference

[1] Aono, Yoshinori, et al. "Privacy-preserving deep learning via additively homomorphic encryption." IEEE transactions on information forensics and security 13.5 (2017): 1333-1345.

[2] Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

Thanks for your response and the simple example in the general response 1.

Let me clarify my comments with your example. I'd like to claim that $y^1_1 \in \mathbb{F}_p^2$ provides some information about $x^1_1 \in \mathbb{F}_p^3$ to the server even though the server cannot fully deduce $x^1_1$ from $y^1_1$.

This is because $H(x^1_1)=3log(p)$ while $H(x^1_1 | y^1_1)=log(p)$. Intuitively, before the server receives $y^1_1$, the number of free variables was 3 (as the number elements in $x^1_1$ is 3). After the server knows the $y^1_1$, however, the number of free variables is reduced to 1.

Please correct me if I miss something.

1. Firstly, in Theorem 1, we explicitly state that $\mathbf{\lambda > 2}$. And you did not compute $\mathbf{y}$ using the correct method, please refer to General Response 1 for clarification.

2. Secondly, the conditional probability of guessing an element (like $x_1$) is inherently $\frac{1}{p}$. Where does $\frac{1}{p^2}$ come from?

Thank you for your recognition and hope the response can address your concerns.

1. Clarity and readability. General Response 1 provides a simple example, which we hope will assist you in better understanding PVF.
2. Impact of noise on accuracy. Note that Differential Privacy (DP) is an extension of PVF. The experiments on DP are not the primary focus of this paper. As demonstrated in the experiments in [1][2], the experiments shown in Fig. 6, conducted in two scenarios, are sufficient to demonstrate that the impact of DP noise on accuracy is negligible.
3. Scalability to Multiple Users. All experiments in our paper focus on exploring multi-user scenarios. Please refer to the setup of each experiment (typically indicated in the titles of figures and tables).

Reference

[1] Stevens, Timothy, et al. "Efficient differentially private secure aggregation for federated learning via hardness of learning with errors." 31st USENIX Security Symposium (USENIX Security 22). 2022.

[2] Liu, Zizhen, et al. "SASH: Efficient secure aggregation based on SHPRG for federated learning." Uncertainty in Artificial Intelligence. PMLR, 2022.

I would like to differ with the authors in this comment. I have never acknowledged that the proposed method preserves privacy at any point of my discussion and review.

Dear Reviewer r5Dg:

We greatly appreciate your meticulous and insightful feedback, which will be invaluable in refining our work. We hope our response addresses your concerns.

R1. Discussion on Combining DP in PracAgg

Please refer to Appendix A in [1]:

"While secure aggregation alone may suffice for some applications, for other applications stronger guarantees may be needed, as indicated by the failures of ad-hoc anonymization techniques [6, 45, 52], and by the demonstrated capability to extract information about individual training data from fully-trained models (which are essentially aggregates) [26, 50, 51]. In such cases, secure aggregation composes well with differential privacy [21]. This is particularly advantageous in the local privacy setting [20], which offers provable guarantees for the protection of individual training examples [1, 3] even when the data aggregator is not assumed to be trusted [25, 53]."

R2. Presentation of Sec. 3.3

First, we would like to provide an explanation for the sentence in the original text:
"to ensure the privacy of frozen entries even if some secagg entries are compromised."
Secagg entries refer to the elements that need to undergo SAP, such as $\mathbf{k}^i$ in General Response 1. Frozen entries refer to $\mathbf{y}^i$. In Sec. 3.2, the security of $\mathbf{x}^i$ relies on the hardness of determining a specific solution to an under-determined system of linear equations, meaning whether frozen entries can ensure the privacy of $\mathbf{x}^i$ depends on the security of secagg entries. This is exactly what you have mentioned: the Main PVF may lead to the leakage of correlations between entries. To address this vulnerability, we provide an imporved version in Sec. 3.3.

Regarding the inappropriate use of the term "enhancement", we have revised the phrasing in the latest version of the document.

Furthermore, we have improved the presentation of Sec. 3. In the new PDF, Sec. 3 outlines the entire design process, starting from the motivation behind PVF (Sec. 3.1), to the introduction of a foundational version (Sec. 3.2), and then to the improved version (Sec. 3.3). The foundational version exposes the linear relationship between elements, and thus, in the improved version, we introduce a new method to address this issue. In the improved version, PVF does not disclose any information about $\mathbf{x}^i$ except for $\sum\mathbf{x}^i$.

R3. LWE Parameters

It is important to clarify that the noise added in Eq. (10) is not based on the principles of Local Differential Privacy (LDP), although it may appear similar. Instead, it is based on Learning With Errors (LWE) (Lemma 3). We have revised the ambiguous parts in the original PDF to eliminate any confusion.

The security parameters of LWE are ($v, q, \sigma$), where $v$ denotes the width of $\check{\mathbf{A}}$, $q$ represents the size of the input space, and $\sigma$ is the standard deviation of $\mathcal{X}$. The relationship between the LWE parameters and security can be found in Remark 3 of Appendix D.3 in the latest PDF:

Regev[2] shows that if the size of $q$ is polynomial in $v$ and $\mathcal{X}$ is a discrete Gaussian distribution on $\mathbb{F}_q$ with standard deviation $\sigma > \frac{2\sqrt{v}}{\sqrt{2\pi}}$, the LWE decision problem is at least as hard as the LWE search problem and solving the LWE search problem can be reduced to solving the Shortest Vector Problem. In DVE, $v=\lambda$, and we use $\mathbb{Z}_p$ as $\mathbb{F}_q$.

R4. The standard deviation of $\mathcal{X}$

In the original presentation, our focus was on aligning the noise with that added in [3] to assess its impact on model accuracy, specifically by adding noise with the same standard deviation of 0.0409 to the aggregation results (as mentioned in the final paragraph of Sec. 5.1.1 of [3]).

Due to the varying sizes of the input space ($q$) and the matrix width ($v$), adding noise of the same magnitude can impact model accuracy to different extents. Intuitively, adding noise of the same magnitude in a 16-bit space will have a much smaller impact on accuracy than in a 32-bit space. Therefore, for consistency, we determine the noise added to the input space according to the noise added to the aggregation result (in float) and the security requirements of LWE.

We have included the missing experimental details in the latest PDF (Sec. 5.4):

In the 32-bit input space, the $\sigma$ is set to 8783 $(>\frac{2 \times 1000}{\sqrt{2\pi}})$, which can meet security requirements in Remark 3 and is equivalent to adding noise with a standard deviation of 0.0409 to the aggregation result (float).

R5. Modeling malicious participants

We have added the modeling of malicious participants in the active adversary model, as detailed in Appendix D.3. Specifically, we outline potential active attacks that a malicious participant might execute during the PVF process and describe how we defend against these attacks using symmetric authenticated encryption and digital signatures.

Question

We are unable to fully comprehend the meaning of the following sentence in your comment:

"you would be already required to add a prohibitive amount of noise if the dimension of private vectors is large."

Could you kindly elaborate on the relationship between the required noise magnitude and the dimensionality of the private vectors? Additionally, regarding the relationship between the standard deviation of noise and the hardness of LWE, please refer to R3 of our response.

If you have any questions, please do not hesitate to raise them.

Authors

Reference

[1] Bonawitz, Keith, et al. "Practical secure aggregation for privacy-preserving machine learning." proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017.

[2] Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.

[3] Stevens, Timothy, et al. "Efficient differentially private secure aggregation for federated learning via hardness of learning with errors." 31st USENIX Security Symposium (USENIX Security 22). 2022.

Dear Reviewer r5Dg:

Based on the questions you raised, we speculate that you may not have thoroughly reviewed the latest version of our PDF. In the following response, we will include relevant excerpts from the PDF where necessary.

R1. The theoretical foundation of Remark 3 in our paper

Remark 3 in our paper summarizes the content of "THEOREM 3.1 (MAIN THEOREM)" on page 20 of [1]. In simple terms, Regev demonstrated that when $\alpha q > 2\sqrt{v}$, or equivalently $\sigma > \frac{2\sqrt{v}}{\sqrt{2\pi}}$, where $\sigma = \frac{\alpha q}{\sqrt{2\pi}}$ (see II.B in [2]), solving the LWE problem would be equivalent to solving the Shortest Vector Problem, a well-known NP-hard problem. In our experiment (Fig. 6), $\sigma$ is set to 8783 $(>\frac{2 \times \sqrt{1000}}{\sqrt{2\pi}})$, which satisfies the security requirements.

R2. The standard deviation of $\mathcal{X}$

Please refer to the description in R1. The standard deviation of the added noise must satisfy $(>\frac{2 \times \sqrt{\lambda}}{\sqrt{2\pi}})$. In our experiments, $\lambda$ ranges from [100, 1000], so the maximum required minimum standard deviation is $\frac{2 \times \sqrt{1000}}{\sqrt{2\pi}} = 25$. We set it to 8783 merely to demonstrate that even when noise far exceeding the security requirements is added, the impact on the model's accuracy remains negligible.

About the Question

"you would be already required to add a prohibitive amount of noise if the dimension of private vectors is large."

We still do not understand this comment based on the response you provided. We have emphasized that the security foundation of this paper is based on LWE, not DP. Although both DP and LWE involve Gaussian noise, their principles for achieving privacy protection are entirely different. The LWE problem and the conditions under which it is difficult have been clearly explained in our paper. We kindly ask the reviewer to consult the definitions of DP and LWE and compare them to understand the differences between the two. Furthermore, based on your intuitive and simple explanation, we do not understand why the noise intensity in our proposed scheme (or in LWE problem) would be related to the vector dimension. We would appreciate it if the reviewer could provide a formal explanation or an example to clarify this, or perhaps refer to relevant literature and theoretical foundations to support this claim.

If you have any questions, please do not hesitate to raise them.

Reference

[1] Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.

[2] Marcolla, Chiara, et al. "Survey on fully homomorphic encryption, theory, and applications." Proceedings of the IEEE 110.10 (2022): 1572-1609.

I have already read that $\check{A}$ is public in the paper and in your previous comment. However, it does not mean that your use of Theorem 3.1 is correct.

Let me be more specific:

The LWE problem stated in Regev's paper defines observations as pairs $(\mathbf{a}, \mathbf{a}^\top \mathbf{x} + e)$ where $\mathbf{x}$ is your secret vector of dimension $\lambda$, $\mathbf{a}$ is a random vector sampled uniformly at random from $\mathbb{Z}_p^{\lambda}$ and $e$ is a scalar sampled from the gaussian distribution $\Psi$. For all observations $e$'s are i.i.d samples of a given $\Psi$.

In your paper you have a matrix $\check{A} \in \mathbb{Z}\_p^{(\lambda-1) \times \lambda }$. The pair $(\check{A}, \check{A}\mathbf{x} + \mathbf{e}')$ cannot be used as a single observation, because observations are vector-vector products and not matrix-vector products. This in itself is not a problem as you can define the set of $\lambda-1$ observations of the form $(\check{A}\_{i,:}, \check{A}\_{i,:}\mathbf{x} + \mathbf{e}'\_i )$, where for all $i \in \\{1,\dots, \lambda-1\\}$, $\check{A}\_{i,:}$ is the $i$th row of $\check{A}$ and $\mathbf{e}'\_i = \check{A}_{i,:} \mathbf{e}$ for a vector $\mathbf{e}$ that follows a multivariate Gaussian distribution.

Lets examine the distribution of your observations. Each vector $\check{A}\_{i,:}$ is a random vector as $\check{A}$ is a random matrix in the adequate domain. However, your distribution of pairs cannot be stated as the distributions of the paper for the following reasons:

• each sample $\mathbf{e}'\_i$ has a different Gaussian distribution dependent on $\check{A}_{i,:}$, while in Regev's paper they should all be samples from the same distribution
• all samples $\mathbf{e}'\_i$ are correlated with each other, as they all depend on $\mathbf{e}$. However, in Regev's paper all samples of $\mathbf{e}'\_i$ must be independent.

Therefore, your protocol does not appear to meet the preconditions to apply Theorem 3.1 of Regev's paper.

Dear authors and reviewer r5Dg,

Thanks for your detailed discussion and sorry for interrupting the conversation.

I also agree with the reviewer r5Dg, i.e., I am also not convinced that the distribution of observations in your protocol is the same as the distribution required in Theorem 3.1 of (Regev. et al.).

I think the misunderstanding stems from the author's statement "$\sum{\mathbf{x}}^{i}$ does not compromise the privacy of any individual ${\mathbf{x}}^{i}$, which is a fundational principle and consensus in secure multi-party computation", which is not true. The sum of the local models definitely includes some information about the local model, and the amount of leaked information in secure aggregation protocol is $O(1/N)$ where $N$ is the number of models to be aggregated [1].

[1] Elkordy, A., et al. "How Much Privacy Does Federated Learning with Secure Aggregation Guarantee?." PETS. 2023.