PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectrum-Aware Bounds on Invertibility for Privacy-Enhancing Instance Encoding

Seokjin Hwang, Yuting, Li, Kiwan Maeng

arXiv:2608.23382v1cs.LGcs.CR

TL;DR

Instance encoding seeks to preserve utility while making sensitive data difficult to reconstruct, but prior theoretical guarantees can be loose, require randomness, and focus only on MSE. The paper introduces spectrum-aware bounds covering deterministic encoders and additional norm-based metrics, and concludes that these bounds are tighter and useful beyond the prior method.

  • Problem

    Existing instance-encoding work mostly lacks rigorous guarantees, while the prior MSE bound can be loose, excludes deterministic encoders, and does not cover other similarity metrics.

  • Method

    The paper develops bounds that account for the encoder’s spectral geometry, extend to deterministic encoders and norm-based metrics, and estimate the data prior with a pre-trained DDPM.

  • Results

    The bounds are tighter than prior work in many cases and remain useful when the encoder has no randomness or when a norm-based metric other than MSE is used.

  • Takeaways & Limitations

    The bounds can serve as indicative metrics for an encoder’s invertibility across settings where prior bounds do not apply.

  • Takeaways & Limitations

    The absolute value of a norm-based bound becomes less informative as it grows and saturates, because its meaning depends heavily on context.

Abstract

from arXiv · show

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.

1 Introduction

Instance encoding replaces sensitive inputs with embeddings to preserve downstream utility while hindering reconstruction, but existing approaches largely lack rigorous privacy guarantees. This paper develops tighter, more general bounds that account for encoder spectral structure.

  • Instance encoding releases privacy-enhancing embeddings instead of raw sensitive data for remote training or inference.The approach aims to retain enough information for downstream tasks while making inversion difficult.
  • Empirical resistance to known attacks does not establish which privacy properties encoders provide or how invertibility should be quantified.The paper motivates principled guarantees because previously considered-safe schemes have later been attacked.
  • Maeng et al.’s MSE bound can be loose, applies only to randomized encoders, and does not capture all reconstruction quality.MSE may disagree with semantic leakage: reconstructions can have high MSE yet reveal sensitive meaning, or low MSE without meaningful leakage.
  • The proposed bounds use the encoder’s spectral geometry to improve tightness, remain non-trivial without encoder randomness, and extend beyond MSE to metrics such as LPIPS and CLIP score.They account for information loss along encoder directions and target norm-based similarity metrics.

2 Background: Instance Encoding

Instance encoding transforms secret inputs into shared embeddings, supporting computation without directly sharing raw data. The literature includes many encoder designs but has relied mainly on empirical rather than theoretical evidence of non-invertibility.

  • Instance encoding maps a secret input x ∈ R^d to an embedding e ∈ R^m that is shared with untrusted parties.Training and inference are intended to operate on e while preventing reconstruction of x.
  • Prior work commonly claimed non-invertibility through tests against a few known attacks rather than theoretical analysis.
  • Most proposals use DNN encoders, with some adding noise and others using deterministic networks.The paper focuses mainly on DNN-based encoders.
  • Theoretical work indicates that strong data indistinguishability and utility cannot be achieved simultaneously, motivating weaker guarantees such as non-invertibility.
  • Maeng et al. introduced an early MSE reconstruction bound, while metric-DP approaches instead constrain distinguishability within ℓp neighborhoods.The paper compares primarily against Maeng et al.’s bound and identifies limitations of both directions of prior work.

3 Bounding the Encoder’s Invertibility Through its Spectral Geometry

The paper analyzes reconstruction through the encoder’s spectral geometry under a strong adversary and regularity assumptions. Its bounds improve on prior work for anisotropic and low- or zero-noise encoders, while exposing assumptions and rank-dependent limits.

  • Threat model: The threat model gives the attacker knowledge of both the encoder Enc and data prior π, allowing arbitrary use of them to reconstruct x from e.
  • Prior bound: Maeng et al.’s bound requires differentiable randomized encoders, so practitioner DNNs require smoothed operators and added Gaussian output noise.
  • Assumptions: The analysis relies on regularity assumptions that commonly used datasets such as natural images may not satisfy, motivating evaluation with smoothed images.
  • Prior bound limitations: The prior bound becomes trivial at σ = 0 and can be loose for encoders that remain difficult to invert with little or no randomness.
  • Improved MSE bound: The improved MSE bound uses the trace of the inverse rather than the inverse of the trace, exploiting the full spectral geometry and becoming tighter for anisotropic encoders.The two bounds coincide for isotropic encoders; otherwise, the improved bound is at least as large in the comparison described.
  • Zero-noise bound: For deterministic encoders, the zero-noise bound remains non-trivial when the expected FIM is lower-rank, with reconstruction becoming harder as rank decreases below d.If the expected FIM has full rank r = d, the bound collapses to zero.
  • Spectral interpretation: The bounds become smaller when discarded directions are strongly constrained by the prior, because those directions are easier to guess from prior information.

4 Extending to Metrics Beyond MSE

The paper extends reconstruction bounds beyond MSE to norm-based metrics such as LPIPS and CLIP, including deterministic encoders. These bounds quantify how encoder geometry and metric sensitivity jointly affect reconstruction difficulty, including in the zero-noise setting.

  • 4 Extending to Metrics Beyond MSE: The Ψ-bound extends reconstruction guarantees to squared ℓ2 similarity after projecting inputs through a twice-differentiable function Ψ, covering metrics such as LPIPS and CLIP.The bound is derived for a general Ψ and uses orthogonal projectors to separate encoder-related directions.
  • 4 Extending to Metrics Beyond MSE: When the encoder discards directions that Ψ captures, the bound remains large as encoder noise increases because the discarded information is unavailable for reconstruction under Ψ.Alignment between JΨ and the encoder’s null space produces a finite dominating term that does not scale with 1/σ2.
  • 4 Extending to Metrics Beyond MSE: When the encoder preserves Ψ-relevant directions, the bound is driven by encoder noise and collapses as σ approaches zero.In this case, JΨ aligns with the encoder’s range space, so preventing precise reconstruction requires substantial encoder noise.
  • 4.2 Extending with Zero Noise: The zero-noise Ψ-bound is nontrivial only when the encoder’s expected Fisher information matrix is rank-deficient.With full rank, the bound becomes zero.
  • 4.2 Extending with Zero Noise: A privacy-enhancing encoder for Ψ should have low rank and discard directions that Ψ is sensitive to.The numerator of the zero-noise bound increases when discarded directions matter more to Ψ.

5 Practical Considerations

Applying the bounds requires estimating the encoder’s Fisher information matrix and the data-prior score, then separating its range and null spaces. Practical choices affect tightness, while absolute bound values can saturate, motivating the ratio-to-ceiling metric RTC.

  • 5.1 Choosing P1 and P2: Different projector choices yield valid bounds with different tightness, and the range/null-space choice used throughout may not be optimal for LPIPS.The authors leave potentially tighter choices, likely involving more than two projectors, for future work.
  • 5.2 Estimating S: A pretrained DDPM can estimate the score sπ(x), and the paper reports that this gives a better estimate than a trained NICE model.DDPM noise-prediction outputs are related to the score through sπt(xt) = −εθ(xt,t)/√(1−ᾱt).
  • 5 Practical Considerations: The bounds require estimating E, separating its range and null spaces, and averaging encoder-related quantities over samples from the training data.Range–null separation is specifically required for the noiseless bounds.
  • 5.3 Estimating E: Thresholding small eigenvalues as null-space directions empirically gives a tighter bound than using the exact estimated null space.The threshold treats directions below τ · λmax as null, avoiding conservatism from negligibly small but nonzero eigenvalues.
  • 5.5 Bound as a Proxy for Invertibility: Absolute MSE or LPIPS bound values become less informative when they grow and saturate, so the paper introduces RTC as a relative indicator of reconstruction hardness.RTC compares the bound with its no-information ceiling; lower RTC indicates better privacy, and RTC = 0 means the bound equals the prior-only ceiling.
  • 5.5 Bound as a Proxy for Invertibility: The bounds directly constrain reconstruction when the metric has an interpretable absolute value; otherwise, RTC provides a theoretically principled proxy for reconstruction hardness.The paper specifically contrasts direct interpretation for quantities such as patient weight or height with weaker absolute interpretation for natural-image metrics.

6 Evaluation

Across datasets, encoder types, ranks, spectra, attacks, and similarity metrics, the proposed bounds consistently hold and generally improve on prior bounds, though tightness varies by setting.

  • MSE bound: The Gaussian MMSE attack exactly matches the proposed bounds, which remain valid for optimization and DNN attacks across natural-image settings.The prior bound is tight only when d ≪m and σ > 0.
  • MSE bound: The bounds increase sharply or become nontrivial after m = r = d, where the encoder begins losing information through its spectral geometry.This transition occurs both with noisy and zero-noise encoders.
  • LPIPS bound: LPIPS bounds always hold but are generally looser and nearly flat when m < d, making them less informative than the MSE bounds.The authors attribute possible looseness to their projector choice or attack quality.
  • Controlling the Skewness of E: As spectral skewness α increases, the proposed bounds rise and capture information loss, while the prior bound remains flat; the proposed bounds hold for both attackers.For isotropic encoders with α = 0, the proposed bound coincides with Maeng et al.’s bound.
  • Bounds with DNN-based Encoders: Across encoder architectures and weight-training methods, the MSE bound always holds, with tighter results for linear or split-early encoders and looser results for deeper encoders.The deeper-encoder looseness may reflect uncaptured depth effects or suboptimal attacks.
  • Bounds with DNN-based Encoders: The zero-noise bound remains valid but is often loose because it captures skewed spectral information loss only when the encoder has a null space.The noisy bound can capture skewness-induced information loss directly.
  • Bounds with DNN-based Encoders: DDPM-based estimation of S more closely matches the required Fisher-information condition than the prior method, although some eigenvalues still fall below 1.The violation is described as rarer and milder for the proposed approach.

7 Conclusion

The paper develops reconstruction-error bounds for instance encoding that are tighter than prior work, remain useful for deterministic encoders, and extend beyond MSE to norm-based metrics. It also proposes estimating the data prior with a pretrained DDPM and positions the bounds as an indicative invertibility metric.

  • The bounds lower-bound an adversary’s ability to reconstruct original data from an instance-encoding embedding.
  • They are tighter than prior bounds in many cases and remain useful when encoders have no randomness or when metrics other than MSE are used.
  • A pretrained DDPM provides a practical way to estimate the data prior more accurately.
  • The bounds can serve as an indicative metric for an encoder’s invertibility.

A.1.1 Encoder Architecture

The encoder architecture combines a backbone network with a compression block that controls the embedding size by changing channels and, when necessary, spatial dimensions. A corresponding decompression block reverses these architectural changes.

  • The DNN encoder uses backbone models split at different points, followed by an added compression block.
  • The compression block first changes channel dimension from C_in to C_out and reduces height and width if needed to meet the target embedding size m.
  • For m = C_out × s, compression uses Conv2d, GELU, and AdaptiveAvgPool2d, while decompression uses upsampling, Conv2d, and GELU.

A.1.2 Attack Details

The evaluation tests optimization-based and neural-network attacks under Gaussian and natural-image settings, with deterministic and randomized encoder cases handled separately. The reported bounds hold for both attacks.

  • For σ > 0, inputs are encoded repeatedly, whereas σ = 0 uses one deterministic encoding; MNIST and CIFAR-10 use 16 inputs.
  • The optimization attack uses Adam, specified β sweeps or β = 2σ^2, 500 steps, learning rate 0.05, cosine annealing, and image clamping.
  • The DNN attack adapts a convolutional architecture to arbitrary embedding dimension m using linear, convolutional, and transposed-convolutional layers.

A.2 Van Trees Inequality (in the form from Bouchard et al. [2])

This appendix states the inequalities and proof ingredients used to derive the paper’s bounds, including generalized van Trees results, projector decompositions, and Gaussian MMSE estimators. It also records assumptions governing regularity, integrability, nonsingularity, and limiting behavior.

  • A.2 Van Trees Inequality (in the form from Bouchard et al. [2]): A.2 restates the matrix van Trees inequality for an estimator of θ from a noisy observation y under density and boundary conditions.
  • A.2 Van Trees Inequality (in the form from Bouchard et al. [2]): The inequality requires absolute continuity, vanishing boundary terms, and a nonsingular expected information-plus-prior-information matrix.
  • A.3 Generalized Multivariate van Trees Inequality (in the form from Gill & Levit [16]): A.3 introduces a generalized multivariate van Trees inequality using a differentiable function Ψ, its Jacobian, a score function, and a differentiable matrix weight field.
  • A.5 Proofs of the Bounds: Corollary 1 applies the matrix inequality to obtain an improved MSE bound under Assumption 1 and additional boundary conditions.
  • A.5 Proofs of the Bounds: Theorem 2 derives a Ψ-bound by decomposing the input with mutually orthogonal projectors P1 and P2 and imposing finite-moment and positive-definiteness conditions.
  • A.5 Proofs of the Bounds: The proof maximizes (w^Tn)^2/(w^TDw) using the D-inner product and Cauchy–Schwarz, with equality when w is proportional to D^-1n.
  • A.5 Proofs of the Bounds: The zero-noise Ψ-bound separates encoder range and null spaces, while the full-rank case collapses the bound to zero.
  • A.6 Proofs of the MMSE Attack: A.6 derives Gaussian MMSE estimators by separating row-space information from a null-space component invisible to the observation, then treating the posterior as Gaussian.
Loading 2608.23382v1…