Search papers, labs, and topics across Lattice.
This paper introduces a new family of bounds on the invertibility of instance encoding methods used for privacy enhancement, addressing critical limitations of previous mean-squared error (MSE) bounds. By accounting for the spectral structure of encoders, the authors derive tighter bounds that are applicable to both randomized and deterministic encoders, and extend beyond MSE to other norm-based similarity metrics. The evaluation demonstrates that these new bounds consistently outperform existing ones across various encoders, datasets, and adversarial attacks, providing stronger theoretical guarantees for privacy-preserving data sharing.
Tighter bounds on instance encoding invertibility reveal that deterministic encoders can be just as secure as their randomized counterparts, transforming our understanding of data privacy techniques.
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.
