Governing the KV Cache: Preventing Timing Side-Channel Leakage in Multi-Tenant LLM Inference
2026-08-10 • Cryptography and Security
Cryptography and SecurityArtificial Intelligence
AI summaryⓘ
The authors explain that in large language models, a shared cache storing previous inputs can leak private information between users because attackers can detect timing differences. They show that existing attacks can fully recover secret prompts by exploiting this timing side channel. To fix this, they propose KVGov, which uses cryptographic techniques to separate cache entries per user, stopping attacks without losing much cache efficiency. They tested their method both in real hardware and simulations, confirming it works well at scale and reduces attackers' success significantly.
Large Language ModelsKey-Value CacheTiming Side ChannelMulti-Tenant DeploymentCryptographic SaltingPrefix ReuseCache Hit LatencyAdversarial AttackPerformance OptimizationSecurity Mitigation
Authors
Tejasvi C. Addagada
Abstract
The key-value (KV) cache is the primary throughput optimization in modern large language model (LLM) inference, enabling prefix reuse across requests. In multi-tenant deployments this cache is shared across tenants, creating a timing side channel: an adversarial tenant can reconstruct another tenant's private prompt by probing cache-hit latency. Three published attacks exploit it -- PROMPTPEEK, EarlyBird and InputSnatch -- reaching up to 100% attack success rate against unprotected vLLM and SGLang, with rates varying by cache architecture and prompt structure. We present KVGov, a governance layer addressing all three attack families' prefix-cache paths under one mechanism. A per-principal salt sigma_p = HMAC_K(secret, principal_id) seeds the block-hash chain, making cache keys cryptographically disjoint across principals. An ablation (N=1000 trials, seed 2026, deterministic judges) isolates this salt as the necessary and sufficient component. KVGov adds ORIGAMI, a Stackelberg water-filling audit scheduler that reduces adversary expected utility by 12.6% at realistic tenant heterogeneity (Gini 0.63), and an evolutionary stability analysis giving a 31.6% adversary-prevalence tipping point below which global caching remains stable. On real hardware (Qwen2.5-7B-Instruct, vLLM 0.26.0, NVIDIA A100) we measure a gate-verified cold/cached TTFT ratio of 0.22, confirming the channel is exploitable at production scale; the defense itself is evaluated in simulation calibrated to those measurements. We replicate the channel on an independent stack (llama.cpp on Apple Metal, ratio 0.093). Finally, isolation and cache efficiency need not conflict: identifying information resides only where prompts diverge, so injecting the salt at that boundary rather than the chain root retains an estimated 93% of the prefix-cache benefit with no cross-principal signal.