Hidden No More: Attacking and Defending Private Third-Party LLM Inference

Thank you for your review and for recognizing Cascade's effectiveness against the vocab-matching attack (VMA). We address your comments below.

W1

Regarding white-box access: we clarify this differs from open-weights. Our setting involves access to permuted hidden states and weights, but not the corresponding input tokens. We emphasize that the security of schemes [1], [2] and [3] all assume the difficulty of this reversal problem for security. To the best of our knowledge, there is no prior work that demonstrates the insecurity of permuted hidden states.

Furthermore, our attack extends to break the schemes of [2, 3] even in the closed-weights setting. These protocols give permuted model weights and embeddings to the party doing inference, where the embeddings are computed locally by the user. Therefore, the VMA may be applied exactly as mentioned in our submission - except that now the embedding matrix is not known, so the first step of inference in the attack seemingly cannot be done.

However, it is straightforward to bypass this. The adversary can collect the (finite) set of input embeddings in the vocabulary over repeated inference calls, and can perform the VMA by iterating through this set. Decoding of the embeddings to tokens is also possible even if the tokenizer remains private – this essentially constitutes a simple substitution cipher, where each token in the vocabulary is substituted by its embedding vector. This may be easily broken by collecting data over many queries and using straightforward methods such as frequency analysis and contextual modelling.

Therefore, our result extends to breaking the proposed schemes of [2] and [3] even in the closed-weight setting. We further note that the proposed scheme of [1] explicitly provides the model weights to the party performing inference, and so corresponds to the open-weights setting.

W2

We wish to clarify your statement that: “The authors note that Cascade does not secure individual input embeddings and suggest SMPC for this layer. However, embeddings protected by SMPC provide computational indistinguishability, which means that VMA cannot work in this case.”

First we assume that you mean that Cascade cannot work in this case. We clarify that here we mean the using SMPC for the first layer, but then decoding into plaintext after it -- e.g. in additive secret sharing, parties send shards of their additive shares to Cascade nodes, who sum them. In this way, Cascade can be used on the plaintext hiddens from layer 1 onwards. Similarly, SMPC can be applied to any number of initial layers, followed by Cascade on the plaintext token-sharded hiddens for the remaining layers.

Regarding lack of cryptographic guarantees - we are clear in our submission that Cascade is not a cryptographic scheme (e.g. lines 80, 321, 414). However, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [4], [5], [6], none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).

W3

Regarding the tuning of parameters, we have shown from our experiments that for sufficiently large values of $c$ and $\delta$, good security is obtained. Although optimum performance may indeed be dependent on the use case, we are confident that users may follow our prescribed heuristics of $c \geq 8, \alpha \geq 12$ and $m \geq 4$ and achieve good security in the majority of cases.

Regarding the difficulty of obtaining enough nodes, we point to the success of previous projects in decentralized training and inference ([7], [8], [9]) that received contributions from thousands of distinct participants. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to enable the use of Cascade.

Conclusion

Thank you again for your considered review. We have responded to your points above, where in some cases - such as the open-weights setting - we have shown extensibility of our method to also cover the closed-weights setting, and we have also clarified some misunderstandings, such as the compatibility of SMPC with Cascade. We strongly believe in the value of our work, both to show the insecurity of existing proposed schemes, as well as to offer a potential solution to their insecurity. We would be grateful if you would consider raising your score in light of the above.

Thank you for your detailed review. We are glad that you found our proposed attack to be effective in the open-weights setting, and that Cascade is novel. We provide responses to some of the points you have raised below.

W1 + Q1

A slight extension of our vocab-matching attack can additionally break the schemes of [1] and [2] in the closed-weights setting. Due to space constraints, please find the details of this in the response to reviewer nbMt.

W2

Thank you for raising this important point. We have now tested Cascade in a real life WAN network setting with up to 18 different physical machines, and 72 different logical nodes. Our full results for single layer inference on BERT under these settings is shown below:

The above table shows the average runtimes for Cascade under three choices of $\alpha$. Larger $\alpha$ has more nodes. Mean results are given over 100 runs, and a 95% confidence interval is additionally shown in brackets. Values for MPCFormer and Puma are taken from their respective papers.

We also measured the total communicated bytes in the same setting. Even in the most expensive $\alpha = 8$ setting, Cascade is $\sim150\times$ more efficient in total bytes transferred than the baselines. We conclude that although Cascade will be negatively impacted by poor network conditions, this is true for any SMPC method, and the effect of this will be less deleterious on Cascade than other protocols.

W3

We point to the success of previous projects in decentralized training and inference ([3], [4], [5]) that received contributions from thousands of distinct participants over diverse geographies. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to provide good security.

Q2

In fact, our security analysis already assumes the worst case of perfect knowledge of the security parameters $c$ and $\delta$ by the adversary. In practical deployment, the exact sharding scheme may not be known (it can even be changed or randomized continually). We have now made this point more clearly in our local draft and will update it for the camera-ready version.

Claims 1

We agree with your assessment. We have now additionally computed BLEU, F1 and token accuracy, as well as provided reconstruction examples in the local draft.

Claims 2

Examining the literature, we did not find existing methods of attack that are not learning-based. Are there particular alternative methods that you believe are applicable to this setting?

Theoretical Claims

We are clear in our submission that Cascade is not a cryptographic scheme (e.g. lines 80, 321, 414). However, we do examine all possible sources of leakage in Appendix J of our submission. Moreover, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [6], [7], [8], none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).

Other Comments

We agree with all of the readability points you have suggested, and have now included them in our local draft. We will make these changes to the camera-ready version as well.

Thank you once again for your thorough review and your insightful comments. If you have any further comments, or if you think our submission can be improved in any way, please let us know. We have made a significant effort to address each of your points and would appreciate it if you would consider raising your score in light of our response. Thank you!

Thank you for your detailed review of our submission. We appreciate that you found our paper effectively identifies potential security risks in existing privacy-preserving schemes and that our work is comprehensive in coverage.

W4

We agree with your point. We have now modified the implementation of MPCFormer in Crypten ([1]), the SMPC framework they used, to support the use of public weights. Crypten uses Beaver’s triples for matrix multiplication - see Appendix C.1.1 of their paper. For fair comparison, we run on the same setup as Cascade. The table below shows means and 95% confidence intervals over 100 runs:

MPCFormer indeed benefits from a significant speedup by the use of public weights in its protocol - approximately in the range of 7-10x. However, this is still 50-100x slower than Cascade. Moreover we note that the runtime of Cascade does not seem to grow very quickly as a function of $\alpha$.

We will also update the result of PUMA. This requires the use of a separate SMPC framework ([2]). We will have the experimental results for this ready for the final draft of the paper.

W2

Thank you for bringing to our attention the work of [3]. It is a stark reminder of the importance of applying care when making claims about the strength of guarantees provided by a scheme – as with the claimed strength of plaintext permuted hidden states, which we demonstrate are easily decodable. We note that the work [3] devises a successful attack against, BAYHENN, claimed the same formal guarantees of privacy as FHE, by misapplication of the LWE assumption. However we are clear in our submission that Cascade is not a cryptographic scheme (e.g. lines 80, 321, 414), and therefore do not claim any formal guarantees against e.g. learning-based attacks.

The subtract-max variant of softmax works by calculating the maximum $m^x_k$ over each partial row $a^x_k$ of the attention scores given to AttnNodes, where $x$ is the row and $k$ is the column index of the AttnNode – as well as $v^x_k=expsum(a_k^x-m_k^x)$. Thus in standard softmax, CompNode$_i$ gets $o^x_k=softmax(a^x_k)V_k,w^x_k=expsum(a^x_k)$ for all $k$ and rows $x\in R_i$; and for subtract-max, it gets $o^x_k,m^x_k,v^x_k$.

We analyze the security of standard softmax in Appendix J, showing that it necessitates large ‘gaps’, which $(c,\delta)$ sharding satisfies. We can now also show such gaps are sufficient for first layer security – by showing equivalence to the subset-sum problem over vectors. Due to the 5000 character limit, we will include details of this in our next response. We briefly mention here that the subtract-max variant simply adds 1 to the value of $c$ required for security over standard softmax.

W1

Our attack is not brute-force; it exploits the properties of attention and a finite dictionary to break permuted hidden states in linear time rather than the exponential time that is assumed in the schemes of [4], [5] and [6]. [6] even has a ‘proof’ using a misapplication of distance correlation theory, that is incorrect; we will include further details in the next response. The attack also requires suitable ‘matching functions’ such as sorted-L1-distance (see lines 234-235). Further, practical success of this attack was not obvious a-priori, due to the possibility of many ‘collisions’ of states when matching over all N hidden states - the result of nearly 0 collisions is intriguing in its own right.

Moreover, our proposal for Cascade has not to our knowledge been proposed in prior literature. Even if it is considered intuitive, our extensive experimental coverage of performance and security is, we think, of value to the wider community.

W3

Thank you for your points. We agree with your suggestions, and have added a notation table and modified the Python-style notation.

Thank you once again for your thorough feedback. Even if we do not fully align on the value of our work, we feel that your review was particularly thoughtful and of high value. We look forward to following up with our next response to expand on some of the above points in further detail.

Thank you for your review. We are glad that you found our attack effective, and found our experimental work to be extensive. We address your comments below.

W3

Thank you for raising this important point. We have now run scaling experiments to investigate the effect of model size on the performance of both our attack as well as the defense. We present this below.

This table shows the average attack time over 10 decodings for each of the above models, including the optimizations mentioned in Section 4.2.2 of our submission. As can be seen, the attack time does not significantly increase due to model size, but is primarily a function of the vocabulary size, as well as the parameter $\epsilon$. Even if $\epsilon$ is not very well chosen, the attack still takes on the order of minutes for perfect decoding of length 100 prompts.

Next, we present model-size-scaling analysis for Cascade:

The above numbers are obtained over 100 runs, with $\alpha = 2$. The models for the 110M and 335M sizes are BERT-base and BERT-Large, and for 1B-13B are Llama 2. We see that the runtime grows sublinearly with the number of parameters. We emphasize that our baseline, [1], reported a single forward pass on Llama 7B in approximately 300s, so our approach is ~24x faster. Due to computational constraints, we have not yet run on 70B, but we believe the same scaling law will apply as above. We have now updated our local revision to include the above results, and will include those - as well as the 70B result - in our camera ready version.

W2

Thank you for mentioning this point. We agree, and we are very clear in our submission that Cascade is not a cryptographic scheme (e.g. lines 80, 321, 414). However, it is our belief that novel defensive methods are of value to the wider research community if they provide sufficient practical defence, even if they do not have formal guarantees that can be proven. We point to the extensive literature on adversarial attacks and defences of neural networks such as [2], [3], [4], none of which have formal guarantees, yet are used commonly in practice due to their efficacy (e.g. see https://robustbench.github.io/).

Q2

To be clear, the use of multiple parties in Cascade is to provide additional security via token-sharding. For feasibility of obtaining enough parties, we point to the success of previous projects in decentralized training and inference ([5], [6], [7]) that received contributions from thousands of distinct participants over diverse geographies. As such, we are optimistic that sufficient nodes can be gathered in such a setting in order to provide good security.

W1

We agree with all the points you have raised here. We have now included references to Figure 1 in the text, reorganized certain sections such as experimental results and related works, and brought some of the Appendix D details regarding Algorithm 2 to the main body. We also thank you for your eagle-eyed spotting of the typo in Algorithm 2, which we have now fixed.

Thank you once again for your thoughtful and considered review. We strongly believe in the value of our work both to highlight the security inadequacy of permuted hidden states proposed by several existing protocols, and our proposed solution as a potential method to address it. In light of our addressal of your points above, we would be very grateful if you would consider raising your score. Thank you!