Breaking Euston: Recovering Private Inputs from Secure Inference by Exploiting Subspace Leakage

1. Problem Statement

The paper addresses a critical privacy vulnerability in Euston, a secure transformer inference framework proposed by Gao et al. for the 47th IEEE Symposium on Security and Privacy (IEEE S&P 2026).

• Context: Euston aims to enable efficient secure inference on Large Language Models (LLMs) using a combination of Fully Homomorphic Encryption (FHE) and Secure Multi-Party Computation (MPC).
• The Vulnerability: To reduce the massive communication overhead associated with transmitting input matrices, Euston employs a Singular Value Decomposition (SVD)-based transmission protocol. In this protocol, the user masks the input matrix $A$ with a random matrix $R$. The random mask $R$ is decomposed via SVD into two orthogonal matrices ($U, H$) and a singular value vector ($d$).
• The Flaw: While the singular value vector $d$ is encrypted and sent to the model owner, the orthogonal matrices $U$ and $H$ are transmitted in plaintext. The authors argue that transmitting these matrices leaks the subspace information of the random mask, allowing the model owner to reconstruct the original private input.

2. Methodology

The authors propose a Data Recovery Attack that exploits the leaked subspace information to reconstruct the user's private input.

A. Attack Mechanism

The attack operates under the assumption that the Model Owner (MO) has access to:

1. The masked input $X = A - R$ (sent by the user).
2. The orthogonal matrices $U$ and $H$ (sent in plaintext).
3. The encrypted singular values (which the MO can decrypt or utilize in homomorphic operations).

The recovery process involves the following steps:

1. Projection: The MO computes $\hat{D} = U^T X H^T$.
2. Approximation: The MO extracts the diagonal matrix $\tilde{D} = \text{diag}(\hat{D})$ as an approximation of the original singular value matrix $D$.
3. Reconstruction: The MO approximates the random mask as $\tilde{R} = -U \tilde{D} H$.
4. Recovery: The original input is recovered via $\tilde{A} = X + \tilde{R}$.

B. Theoretical Analysis

The paper provides a rigorous mathematical proof regarding the Relative Recovery Error (RRE), defined as $\frac{\|\tilde{A} - A\|_F}{\|A\|_F}$.

• Theorem 1: The expected RRE is bounded by $\frac{1}{\sqrt{n}}$, where $n$ is the column dimension of the input matrix.
• Implication: As the dimensionality of the input increases (common in Transformers and high-resolution images), the expected error approaches zero. This implies that for high-dimensional data, the reconstructed input $\tilde{A}$ is nearly identical to the original input $A$.

3. Key Contributions

1. Identification of Subspace Leakage: The authors identify that transmitting orthogonal matrices in plaintext, even when singular values are encrypted, fundamentally compromises privacy by revealing the subspace structure of the masking noise.
2. Novel Attack Vector: They design a specific algebraic attack that allows a malicious model owner to recover private inputs without breaking the underlying FHE scheme. The attack relies solely on the protocol design flaw, not on cryptographic weaknesses.
3. Theoretical Proof: They establish a theoretical upper bound on the recovery error, proving that the attack becomes more effective as input dimensionality increases.
4. Empirical Validation: The attack is validated across multiple datasets and modalities, demonstrating its practical feasibility.

4. Experimental Results

The authors evaluated the attack on both language and image datasets:

• Datasets:
  • Language: GLUE benchmark tasks (RTE, SST-2, QNLI) using a BERT-base model.
  • Image: CIFAR-100 dataset.
• Metrics: Relative Recovery Error (RRE).
• Findings:
  • Language Datasets: The RRE was consistently low (approx. 0.036 or 3.6%) across all masking scales ($\eta$).
  • Image Datasets (CIFAR-100): The RRE was slightly higher (approx. 0.178 or 17.8%) due to the smaller input dimension compared to language tokens, but still allowed for high-fidelity reconstruction.
  • Visual Evidence: Figure 1 in the paper shows that regardless of the masking scale (from $\eta=0.5$ to $\eta=100$), the recovered images are visually indistinguishable from the original inputs, effectively bypassing the privacy protection.
  • Independence from Mask Scale: The attack's success is independent of the magnitude of the random mask; it depends entirely on the leaked subspace.

5. Significance and Conclusion

• Fundamental Design Flaw: The paper demonstrates that encrypting only the low-rank representation (singular values) while leaving the basis vectors (orthogonal matrices) in plaintext is insufficient for secure inference.
• Privacy Risk: The results indicate that the Euston framework, as designed, fails to protect user privacy, allowing model owners to easily recover sensitive user data (text or images).
• Broader Impact: This work serves as a cautionary tale for the design of secure inference protocols. It highlights that efficiency optimizations (like SVD-based compression) must be rigorously scrutinized for information leakage, particularly regarding the transmission of structural components of random masks. The authors conclude that such designs require significant security re-evaluation before deployment.