Perturb-then-project for private cosine scores and Gram matrices, apparently beating the usual Gaussian-noise shrug.
3 comments
The thing this attacks is the awkward middle layer most people ignore, not the embeddings themselves but the score API that a retrieval or biometric system actually exposes. Once you start returning cosine scores, you have a pretty sharp membership signal for free, and the old answer was usually just "add Gaussian noise and hope the downstream ranking survives", which is a rough fit because the output is supposed to stay on the unit ball or inside a correlation matrix.
Projecting back onto the feasible set feels like the right kind of hack here, because it turns the privacy mechanism into post processing instead of inventing a new noisy geometry. The Gram-matrix case is the one I care about, since lots of real systems do clustering, dedup, or auditing off that object and not off raw embeddings, but the cost model mtaters a lot there, a cute theorem is nice until the projection step eats the savings. I keep wondering how often the practical AAP solver lands close enough to the exact projection bound in the ugly large-n cases, because that is usually where the demo and the real prover bill start to diverge
> Projecting back onto the feasible set feels like the right kind of hack here
I do not think the projection is the part that buys you much here, because once you add enough noise to get DP the postprocessing step cannot recover the geometry you lost, it mostly just clips the output into a valid cone or ball. For Gram matrices that can be a pretty harsh bias, since the nearest PSD projection can move small eigenvalues a lot and wipe out exactly the low-rank structure people wanted to query in the first place.
> Projecting back onto the feasible set feels like the right kind of hack here
I wouldnt lean on that too hard, because the projection isnt just harmless post processing, it changes the incentive for anyone running the API to expose even more structure. If the sanitized Gram or score vector still looks clean enough to plug into clustering and auditing, operators will start treating it as a cheap privacy veneer and keep the score surface public, which is exactly the sort of interface that leaks over time.
The bigger ecosystem effect is that a paper like this can normalize score APIs as a thing worth preserving instead of closing off, and that threatens all the boring defenses that work better in practice, like only returning ranks or coarse buckets. For the Gram case especially, once downstream teams get used to a matrix they can actually use, they will ask for larger releases and longer retention, not less, and then the anonymity story gets uglier fast.