Membership Inference in Privacy-Preserving Vector Search

What it is

The paper (Fuchsbauer, Luck, O'Neill and Rapko, IACR ePrint 2026/2570, received 20 October 2026) studies membership inference against "backend-compatible" protection of embedding databases. These schemes transform stored vectors so the search algorithm runs unchanged, but the protected database leaks distance geometry. The attacker gets one snapshot plus some known plaintexts and must decide whether a given vector is in the database.

The central finding is that membership privacy depends on two things, and each changes the effect of the other: how much geometry the scheme reveals, and whether known plaintexts can be linked to positions in the snapshot.

Results by scheme

• Scale-and-Perturb (SAP, FGHO, SCN 2022): broken with no known plaintexts. Attack advantage is 0.997 on MS-MARCO.
• Rotate-and-Perturb (RAP): a special case of FGHO's SAP-I, which FGHO left unanalyzed. For uniform data on the sphere the authors prove perfect membership privacy with no known plaintexts. For fixed noise parameter β in (0, 2], constant advantage needs at least a logarithmic number of known plaintext-ciphertext pairs in database size, provided that number stays below the embedding dimension. Empirically, advantage 0.5 takes 3 pairs at database size 100 and 7 pairs at 100,000 on text embeddings.
• Ideal DCRE (distance-comparison-revealing encryption): still vulnerable to known plaintext-ciphertext pairs.
• Encrypted HNSW index (function-hiding inner-product functional encryption): on the tested MS-MARCO databases, advantage 0.5 requires the attacker to know 19 to 32 percent of the database and the matching index vertices.

What to do

The page gives no patch or configuration. It tests two augmentations: shuffling and secret projection. Together they substantially raise the number of known plaintexts the tested attacks need against RAP and comparison-only leakage.

An engineer using SAP should treat it as broken for membership privacy. One using RAP should assume that a handful of known pairs, growing slowly with database size, is enough to reach advantage 0.5, and should consider the two mitigations.

Caveats

• Mitigations are measured only against the authors' own tested attacks. The abstract does not claim they remove the leak.
• The RAP proof covers uniform data on the sphere. The 3-pair and 7-pair figures are empirical, on text embeddings.
• The logarithmic bound holds only while the number of known pairs is below the embedding dimension.
• The page is a preprint and has not been peer reviewed.