Distributed Differentially Private Data Analytics via Secure Sketching

We thank the reviewer for the constructive feedback and questions.

The discussion of shuffle model and other deployments where the central server is replaced by MPC is lacking details.

Regarding missing details on replacing trust in a central server by MPC, ​​we made an extensive comparison in Section 3.3. A complete introduction for MPC is out of scope, but we give some details for our constructions in the appendix. If the reviewer thinks specific points are missing, we would be grateful for pointers.

Your definition of corrupted clients / servers seems unusual to me since it assumes that they are faithfully following the protocol and we just know their result without privacy protections. Is this correct? (If yes, I would suggest calling them spoofed or something similar.)

The privacy guarantees will hold even if a large fraction of corrupted parties deviate from the protocol description. We currently only require the semi-honest assumption for the utility guarantees.

We thank the reviewer for the constructive feedback and questions.

We will incorporate the useful editorial suggestions about our Figures in the final version.

What happens with lager privacy budget?

We discuss our choice of privacy budget $\epsilon$ in the experiments in our answer to reviewer sQPT as well. We chose relatively small values, to showcase the separation of different mechanisms in the LTM, which is more prominent when more noise is added. Increasing $p$ for our Gaussian noise mechanism in the LTM while fixing $n$, can be interpreted as increasing $\epsilon$, so Figure 2 shows that increasing $\epsilon$ decreases the error significantly in all settings and for all values of $n$.

Please consider to add an explicit threat model.

We will further clarify the threat model in the next revision and make it explicit already at the beginning of Section 3. Specifically, in our privacy analysis, we assume that up to $t’ < n$ clients and up to $t < k$ servers may collude and share information with each other, while otherwise following the protocol honestly. This type of adversarial behavior is commonly referred to as passive, semi-honest, or honest-but-curious in the cryptography literature.

We thank the reviewer for the constructive feedback and questions.

I am not convinced that the utility analysis of Section 4 completely characterizes this gain. The term $\alpha_S$ which impacts the accuracy of the protocol is only analyzed order-wisely, while it should be more concretely quantified.

Regarding the concrete quantification of $\alpha_S$, we are unsure if the reviewer means the possible values of $\alpha_S$ that can be chosen and the concrete constants in our analysis. If the question’s focus is on the constants in our theorem statements, for low rank approximation the constant leading $\alpha_S$ is 1. For linear regression, we give the constants resulting from our analysis in Equation 12 in the appendix for linear regression. However, the final constants depend on the analysis of the chosen sketching constructions, which is taken from previous work. The target dimension of sketching constructions of related work from Table 3 have been analyzed up to absolute constants, but the absolute constants themselves are not known. If the focus of the question is rather on the exact value of $\alpha_S$, we remark that $\alpha_S$ can be chosen to be any number in (0,½), so one can trade off multiplicative and additive error to get a best possible tradeoff.

Experimental Designs Or Analyses: I am not sure that all the approximation error that impacts the accuracy is included in the comparison. (see the previous comments on $\alpha_S$).

Regarding the value of $\alpha_S$ in the experiments, it is not possible in general to experimentally determine which part of a cost function comes from a multiplicative error and which comes from an additive error. We can use the worst case bounds as a baseline, but these might not be tightly analyzed. The results presented in the experiments implicitly set the multiplicative error to a small constant and measure the excess risk, which is the closest approximation of a possible additive error.

Table 1 ignores the effect of $\alpha$ for space. However I think it is important to find a strategy to concisely include this effect.

The comparisons in Table 1 are with respect to additive error, since there is no multiplicative error in the central model. Multiplicative errors and additive errors cannot be fairly compared to each other, so we simply remark on the existence of our approach’s multiplicative error in the Table caption. These errors are analyzed in the proofs of the theorems in Section 4.

At the beginning of Section 3 the paper argues that the shuffle model is weaker…

We apologize for the confusion caused by the statement in Section 3 — this was not our intention. Our point was not to argue that the shuffle model is inherently weaker, but rather to highlight that the standard formalization of differential privacy in the shuffle model does not, as stated, account for the case of colluding clients. Our motivation for introducing a refined definition was simply to ensure that the privacy guarantee holds even when a bounded number of clients might collude with the adversary, as we believe this is important for the applicability of the definition to real world scenarios. We fully agree with the reviewer that this refinement can naturally be applied to both the shuffle model and the LTM, and our comment should not be interpreted as a point of comparison between the two models. It is solely about the formalization of the security notion itself. As noted in the paper, similar observations have already been made in prior work (e.g., Talwar et al., 2023), fully in line with the reviewer’s comment. We will make sure to revise the text to clearly reflect this intention.

Thank you for your constructive feedback and thoughts.

One modification that would be informative would be a plot of error versus privacy budget for the various methods. The privacy budgets used in the paper are 0.1 and 0.5, which are fairly narrow

Regarding the choice of privacy budgets in the experiments, we chose to include results for $\epsilon=0.1$ and $\epsilon=0.5$ as those show a clear separation in the error between different mechanisms in the LTM. Note that increasing $p$ while keeping $n$ fixed can be interpreted as increasing the privacy budget of our Gaussian noise mechanism, so Figure 2 shows that an increase of privacy budget above 0.5 decreases the error drastically in all settings. We will include a plot that explicitly shows the error versus privacy budget in the final version.

The sketch parameters are underexplored, it seems natural to ask if there is some relationship between the optimal sketch parameters for a particular privacy budget or number of clients

With respect to the sketch parameters, we would like to point out that one strength of the LTM is its modularity, in the sense that any sketch can be used when suitable for the data analytics task at hand. We explore different such sketches from the literature and list their parameters in Table 3 in the appendix.

You mention that the MPC protocols needed for shuffle are not practical while the MPC protocols for the LTM are. Can you explain this quantitatively, how much more communication/computation is needed for MPC shuffle?

We acknowledge that we did not sufficiently substantiate the claim that MPC-based shuffles are more expensive than the LTM-based approach for readers who are not familiar with MPC. Due to space constraints, we could not include a full quantitative comparison, but we clarify here the key differences:

1. Round Complexity: In MPC-based shuffles, each server must sequentially shuffle and randomize (or re-encrypt) the ciphertexts, leading to a round complexity proportional to the number of servers involved. This sequential dependency significantly increases the protocol’s latency. In contrast, the LTM enables all servers to perform their computations in parallel, resulting in lower round complexity and latency.
2. Computational Overhead: In the LTM, servers only need to perform simple linear operations on secret shares, such as matrix-vector multiplications, which are highly efficient. On the other hand, MPC-based shuffles typically rely on mix-nets or similar constructions, where each server performs, for every data point, multiple expensive public-key operations (e.g., modular exponentiations with large moduli and exponents). This introduces an overhead that is orders of magnitude higher compared to simple matrix multiplications.
3. Communication Complexity: The total amount of data transmitted is comparable between the two models, but the size of individual messages differs substantially. In the LTM, secret shares can be as small as the plaintext itself; for example, when working with 64-bit types, each share is just 64 bits per server. In contrast, MPC-based shuffles transmit ciphertexts that are significantly larger due to the inherent expansion of public-key encryption. For example, even with elliptic curve ElGamal, each ciphertext would be at least 512 bit. As a result, the total communication volume in MPC shuffles is larger.

Finally, we emphasize that MPC protocols, in general, tend to incur significant communication and computational costs when dealing with non-linear operations (e.g., multiplications on secret-shared data). The LTM model avoids this overhead by relying exclusively on linear operations on secret-shared data, which are much cheaper to compute.

What other tasks do you expect to be a good fit for the LTM? Do you expect that the LTM will be a strict upgrade over the shuffle algorithm or will there be tasks less related to numerical linear algebra that will be solvable with less error under the shuffle model.

Good Fit for the LTM: Currently, we expect many problems beyond numerical linear algebra to be addressable in the LTM. A promising example are certain clustering tasks like k-median clustering, which we are currently working on.

Comparison to Shuffle: We do not believe that the LTM will be an upgrade over the shuffle model, rather it is a complementary model with incomparable strengths and weaknesses. Proving a separation between the two models would be interesting and potentially challenging.