Function Privatization in the Local Model

Source: arXiv:2607.27164 · Published 2026-07-29 · By Yuting Liang, Tian Shu, Ke Yi

TL;DR

This paper tackles the challenging problem of privately releasing continuous functions representing personal data (e.g., trajectories or 1D density curves) under local privacy constraints. Standard local differential privacy (DP) treats any two functions as equally indistinguishable regardless of their similarity, resulting in excessive noise and poor utility for functional data. To overcome this, the authors adopt Geo-Privacy (GP), a generalization of differential privacy that makes indistinguishability proportional to a chosen metric distance between functions—in this case, the L2 metric. By linking the privacy guarantees to the L2 distance between functions, GP allows more utility while still protecting functions that differ by small amounts. The authors propose a suite of mechanisms that privatize functions by projecting them onto basis functions representing correlations in the data (linear, polynomial, piecewise bases), adding noise calibrated to the corresponding geometry. They also present a private method to adaptively select the dimension of approximation to optimize the tradeoff between noise and approximation error. Experimental evaluation on real-world functional datasets demonstrates substantial utility improvements over naive local DP mechanisms that treat function values independently.

Key findings

• Under local ε-GP with L2 distance, the expected L2 error of privatizing a function projected onto an m-dimensional basis space is E[dist2(f˜a, fa)] = m/ε for spherical Laplace noise (Theorem 3.2, Lemma 3.4).
• Using concentrated Geo-Privacy (CGP) with Gaussian noise, the expected error grows only as roughly √m/√ρ (Theorem 3.3, Lemma 3.5), which is an improvement over Laplace noise.
• Naive local DP that adds noise to pointwise function evaluations individually consumes privacy linearly in the number of points k, resulting in poor utility, whereas the proposed methods exploit correlations via basis projection for better accuracy.
• The mechanism adding noise to the coefficients after projecting onto basis functions respects ε-GP by calibrating noise using the Gram matrix Σ−1 of the basis, reflecting the L2 geometry of functions (Eq. 4).
• The authors develop a private adaptive algorithm that uses the Sparse Vector Technique to select the number of basis functions m, balancing approximation error and privacy noise to optimize utility automatically (Section 3.4).
• The framework extends naturally to vector-valued functions and multivariate functions by extending the Gram matrix accordingly (Section 3.3).
• For piecewise linear or polynomial approximations relevant to curves, the covariance matrix Σ−1 becomes block diagonal, allowing efficient privacy noise calibration (Remark 3.1).
• Experiments on trajectory and density curve datasets show the proposed GP mechanisms provide substantially better accuracy than local DP baselines, preserving curve-like structure.

Threat model

The adversary is an untrusted data analyst who observes the privatized outputs of function-valued user data generated locally on individual devices. The adversary knows the mechanism but cannot observe raw data. The adversary cannot distinguish between two functions that are close under the L2 metric beyond the privacy budget ε or ρ. It cannot tamper with user devices or break the cryptographic guarantees of the mechanism. The privacy model is local and metric-based, allowing degrading privacy guarantees smoothly as functions differ more.

Methodology — deep read

1. Threat model & assumptions: The adversary is an untrusted analyst who receives privatized functional data produced by local mechanisms on individual user's function-valued input. The adversary can observe the output but not the raw function. The adversary is bounded by ε-Geo-Privacy (GP) or ρ-concentrated GP (CGP) with respect to the L2 metric between functions, which generalizes local DP by scaling indistinguishability proportionally to the L2 distance. This allows distinguishing widely different functions while protecting close ones. The privacy domain is the infinite-dimensional function space L2(I), focusing on continuous 1D functions (curves). The setting is strictly local: no trusted curator nor multiple users’ data aggregation.

2. Data: The work is theoretical and algorithmic with experiments on real-world continuous function datasets such as trajectories and density curves, though precise dataset details are in the experimental section (not fully shown). The functions typically map from intervals I=[0,T] into R^n (vector-valued). Projections on bases allow truncation to finite-dimensional approximations for computation.

3. Architecture / algorithms: Key algorithms build on projecting functions onto finite-dimensional basis spans U_f = {f_a = sum_j a_j phi_j}. The core innovation is noise addition to the coefficient vector a in R^m with carefully calibrated covariance matrices Σ derived from the Gram (inner product) matrix of basis functions under the L2 norm. For linear functions, Σ has a closed form via integrated polynomial terms. For more bases, Σ entries are integrals of products of basis functions.(Eq.4)

The privacy mechanisms are:

• An ε-GP mechanism adding spherical Laplace noise scaled by Σ^1/2 to coefficient vector a, guaranteeing GP in function space.
• A ρ-CGP variant adding Gaussian noise similarly scaled.

For infinite-dimensional function spaces, an adaptive algorithm privately selects m by running a Sparse Vector Technique (SVT) on queries monitoring errors, balancing basis approximation error and noise. Piecewise function approaches divide the domain and apply localized bases.

4. Training/evaluation: This is a non-ML privacy mechanism paper; training corresponds to computing projections and adding noise. Theoretical analyses prove privacy and utility (expected and high-probability L2 error bounds) are derived with standard concentration for spherical Laplace and Gaussian noise.

5. Evaluation protocol: The methods are compared mainly to naive baseline releasing privatized function values pointwise under local DP, which consumes privacy linearly and yields poor utility. Utility is measured by expected L2 reconstruction error on real continuous functional data, demonstrating impacts of basis dimension m and adaptive dimension selection. Experiments evaluate privacy vs utility tradeoffs.

6. Reproducibility: The paper includes detailed algorithms, theoretical proofs, and numerical examples (Figures 2 and 3). The code and datasets were not explicitly mentioned as released in the truncated text.

Example end-to-end: For a linear function f a(t) = a_1 t + a_2 over [0,T], the paper shows that directly adding isotropic Laplace noise to coefficients a fails GP. Instead, authors derive a covariance matrix Σ based on integrals of t, t², etc. (Eq. 2), then output privatized coefficients by adding Σ^½ scaled spherical Laplace noise: ˜a = a + (1/ε) Σ^{1/2} Z, achieving ε-GP w.r.t. L2 metric on the function space. This yields controlled expected error m/ε with m=2 here. The privatized function is reconstructed as f˜a(t).

Technical innovations

• Application of Geo-Privacy (GP) with the L2 metric for local differential privacy on continuous function-valued data, allowing noise calibration sensitive to functional similarity.
• Novel mechanism adding noise to projected basis coefficients scaled by the Gram matrix of basis functions, aligning privacy noise with the geometry of the function space instead of naive pointwise noise.
• Adaptive private selection of basis dimension using Sparse Vector Technique under GP to balance approximation and noise errors automatically.
• Extension of the GP-based privatization framework to vector-valued and multivariate functions and piecewise functional approximations.

Datasets

• Real-world trajectory datasets — size and source not specified in truncated paper
• 1D density curve datasets — unspecified

Baselines vs proposed

• Naive pointwise local DP baseline: utility (L2 error) scales poorly with number of discretization points k, significantly higher than proposed GP-based projected mechanisms.
• Proposed ε-GP mechanism with m basis functions: Expected L2 error = m/ε, improving over naive methods by exploiting function correlations.
• Gaussian noise ρ-CGP variant: Expected L2 error approximately sqrt(m)/sqrt(2ρ), better noise scaling than Laplace for large dimensions.
• Adaptive basis dimension selection algorithm: empirically obtains lower utility loss than fixed-dimension methods by optimizing basis truncation.

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.27164.

Fig 1: Reference locations for example trajectories.

Fig 2 (page 6).

Fig 3 (page 6).

Fig 4 (page 6).

Fig 5 (page 6).

Fig 6 (page 6).

Fig 7 (page 6).

Fig 8 (page 6).

Limitations

• The approach requires knowledge or assumption of suitable basis functions capturing data correlations; performance depends on basis choice.
• Computing covariance matrix Σ involves integrals over basis functions that may be challenging for complex bases or domains.
• Privacy guarantee depends on metric choice (L2 here); other metrics may require new mechanism design.
• Experiments and detailed evaluations on more diverse or high-dimensional function spaces remain limited in the truncated text.
• No discussion of adversarial adaptive attacks or robustness beyond standard GP guarantees.
• Code and dataset release status unclear, impacting reproducibility.

Open questions / follow-ons

• How to efficiently compute or approximate the Gram matrix and noise calibration for complex or adaptive basis functions beyond simple polynomials or piecewise linear segments?
• Can the GP framework and noise calibration be extended effectively to high-dimensional functional data (e.g., 3D trajectories, video signals)?
• How does the choice of metric (e.g., other than L2) affect privacy/utility balance and can mechanisms be adapted accordingly?
• Can adaptive mechanisms be made more computationally efficient and interpretable in selecting basis across varying domains?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, the paper's core insight is that function-valued data—such as user behavioral trajectories or time series—can be privatized locally with better utility by exploiting correlations captured via functional bases under a suitable metric. The generalized privacy definition Geo-Privacy (GP) avoids overly strict indistinguishability demands across function space imposed by standard local DP. This allows more utility in releasing signals generated by single users while still providing a strong, distance-aware privacy guarantee. The mechanisms and adaptive dimension selection techniques presented could inform design of privacy-preserving telemetry or biometrics releases used in CAPTCHAs for bot detection, where continuous signals (mouse movements, typing patterns) must be locally privatized before analysis. Understanding the mathematical basis for noise calibration tuned to L2 geometry can help system designers balance privacy and data utility in local function release, which classical local DP approaches struggle with. However, practical integration depends on availability of suitable basis functions representing signal correlations and handling vector-valued or multi-dimensional inputs encountered in real behavioral biometrics.

Cite

@article{arxiv2607_27164,
  title={ Function Privatization in the Local Model },
  author={ Yuting Liang and Tian Shu and Ke Yi },
  journal={arXiv preprint arXiv:2607.27164},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.27164}
}

Read the full paper

• arXiv:2607.27164 (abstract)
• arXiv:2607.27164 (PDF)