Spectrum-Aware Bounds on Invertibility for Privacy-Enhancing Instance Encoding
2026-08-24 • Machine Learning
Machine LearningCryptography and Security
AI summaryⓘ
The authors study how encoding data before sharing it can protect privacy by making original data hard to recover. They point out that past methods only gave weak guarantees and worked only with some types of encoders. The authors develop new mathematical bounds that better measure how well data can be hidden, work with all encoder types, and apply to more ways of measuring similarity. They test their improved bounds and find they are more reliable than previous ones.
instance encodingprivacy enhancementmean-squared errordeterministic encodersrandomized encodersspectral structurenorm-based similarity metricsdata reconstructionerror boundsprivacy guarantees
Authors
Seokjin Hwang, Yuting, Li, Kiwan Maeng
Abstract
Instance encoding is a popular empirical technique for privacy enhancement when sharing data to an untrusted server. It transforms sensitive data through an encoding process before sharing, with the hope that the encoding process retains utility but makes it hard to reconstruct the original data. However, most work offers no theoretical guarantee that the encoding process is actually irreversible. A recent work derived a mean-squared error (MSE) bound limiting any adversary's reconstruction accuracy, offering one of the first theoretical results in this domain. This bound, however, has three critical limitations: it is often too loose, only works with randomized encoders (excluding many deterministic encoders practitioners use), and only bounds MSE. We introduce a family of new bounds that (1) are tighter, (2) applicable even to fully deterministic encoders, and (3) can extend beyond MSE to other norm-based similarity metrics, by properly accounting for the encoder's spectral structure. We evaluate our bounds across a range of encoders, datasets, and attacks, showing they hold consistently and improve upon the existing bound.