The Isometry Tax: At-Rest Leakage in Rotation-Isolated Multi-Tenant Vector Search as an Instance of Property-Preserving-Encryption Leakage, with Bounds on Its Mitigations

Abstract

Multi-tenant vector indexes promise large cost savings by sharing one approximate-nearestneighbour structure across many tenants. Per-tenant orthonormal rotation is an appealing way to isolate those tenants: each tenant's vectors are rotated under a per-tenant key, within-tenant search is preserved exactly because rotation is an isometry, and a wrong-key query returns coherent but incorrect results. We run a falsification-first evaluation on SIFT1M with per-tenant rotation keys and pre-registered leak, isolation and cost gates. Rotation preserves query isolation at modest scale, and leaves a persistent at-rest metadata channel against an observer of the stored index: membership-style classifiers reach 0.505 accuracy on a shared unpadded index. This leakage is neither new nor a defect. It is the vector and rotation instance of a principle the searchable-encryption literature established a decade ago, that any transformation preserving the structure needed to compute also preserves the structure that identifies the data. An informationconservation argument specialises this to isometric rotation, and the leakage is carried by exactly two channels, the per-tenant frame and the rotation-invariant shape, which are jointly exhaustive. That yields a closed taxonomy of the only three ways to close the channel, each a known and formally costed approach. A sixteen-cell threat and mitigation closeout shows query-side two-pass masking drives accesspattern leak to chance while at-rest structure stays exposed. Only uncapped uniform padding closes both axes, at roughly 9.4 MB index size and 44 QPS, which is not deployable. The cheapest at-rest mitigation we validate is K=3 k-anonymity with count-shape-matched phantoms, bounding attribution at 1/K against storage-only and adaptive-invariant adversaries at roughly 3× storage. It fails against an access-pattern-correlating adversary and recovers only at (K−1)/K query-traffic overhead. No single inexpensive candidate closes both surfaces. The same invariance admits a constructive reading. Because a legitimate rotation preserves inner products, that preservation is itself checkable, giving a zero-disclosure at-rest integrity and isolation audit that detects non-orthogonal corruption and tenant mixing, blind by construction to substitution of one valid key for another. Four limits are load-bearing and stated up front. The shared heterogeneous index fails at T=100, where wrong-key recall reaches 0.3585 and exceeds matched recall at 0.2665. The membership and padding results are on SIFT1M as a proxy embedding distribution, and where both substrates were measured together the proxy proved not conservative: the norm-only channel sits at chance on SIFT1M at 0.4998 and leaks at 0.7730 on real language-model key-vectors. Table 1's reported configuration is the one passing cell of ten measured, and the leak is strongly dependent on vectors per tenant. Query-side content isolation holds, but tenant attribution against a query-only adversary does not.