💻 computer science

Function Privatization in the Local Model

This paper addresses the challenge of privately releasing curve-based data in the local model by introducing a Geo-Privacy framework that relaxes standard differential privacy requirements to enable meaningful utility while providing strong protection for similar functions.

Original authors: Yuting Liang, Tian Shu, Ke Yi

Published 2026-07-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuting Liang, Tian Shu, Ke Yi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to keep a secret, but the secret isn't just a single number or a password; it's a whole story written in a continuous line, like a heartbeat monitor, a GPS path of a delivery truck, or the smooth curve of a stock price over a day. In the world of data science, this is called "function privatization." The goal is to share this story with a researcher without letting them peek at the specific details that could identify you.

To do this safely, scientists use a rulebook called "differential privacy." Think of it like a foggy window: if you change the story just a tiny bit, the view through the window should look exactly the same, so no one can tell if you changed it. However, for continuous lines, this "fog" has a problem. If you try to make every possible line look the same, the fog becomes so thick that the story becomes unreadable gibberish. It's like trying to hide a whisper in a hurricane; you protect the whisper, but you also destroy the message. This paper tackles a smarter way to handle the fog, using a concept called "Geo-Privacy." Instead of making everything look identical, Geo-Privacy acts like a smart lens: it makes lines that are very similar (like two people walking almost the same path) look indistinguishable, but it allows lines that are very different (like a straight road vs. a winding mountain trail) to be seen clearly. This way, you get to keep your privacy without losing the shape of your story.

The authors of this paper, Liang, Shu, and Yi, have built a new toolkit to apply this smart lens to curves and lines. They realized that many real-world data points aren't random scribbles; they have patterns. A trajectory might be mostly straight with a few turns; a heartbeat might follow a repeating wave. The paper argues that if we assume these patterns exist, we can be much more efficient. Instead of treating every single point on the line as a separate secret (which would require a massive amount of "fog" and ruin the data), their method looks at the whole line as a single object made of building blocks.

They start with the simplest building blocks: straight lines. They show that if a curve is just a straight line, you only need to hide two numbers (the slope and the starting point) rather than thousands of points. They then expand this to more complex shapes made of a mix of different "basis functions" (like mixing sine waves or polynomials to build a curve). The magic trick here is that they figured out exactly how to add the right amount of "noise" (the fog) to these building blocks so that the final curve stays private but still looks like the original.

Crucially, the paper rules out the "naive" approach of just picking random points on the line and hiding them one by one. The authors demonstrate that this old method is inefficient and ignores the natural connections between points. If you know a car is moving smoothly, knowing its position at one second tells you a lot about where it will be the next second. The paper's method uses this connection to its advantage. If the data is messy and doesn't fit a simple pattern, their toolkit includes a "smart selector" (using a technique called Sparse Vector Technique) that automatically figures out how many building blocks are needed. It balances the error from the approximation (making the curve too simple) with the error from the privacy noise, ensuring the best possible result without wasting the privacy budget.

Finally, the researchers tested their ideas on real-world data, like trajectories. They found that their method produces curves that are much closer to the original truth than the old methods, all while keeping the same level of privacy protection. They even showed how to handle curves that might stop briefly or change speed, proving that their "smart lens" can handle the messy, real-world shapes we actually encounter, not just perfect mathematical lines. In short, they found a way to share your life's path with the world without giving away your exact location, by understanding that the path itself has a shape worth preserving.

Technical Summary: Function Privatization in the Local Model

Problem Statement

The paper addresses the problem of function privatization, specifically focusing on releasing data that naturally exists as curves (images of continuous functions on a finite interval), such as trajectory data or 1D density curves. The setting is the local model of differential privacy, where each user privatizes their own data before sending it to an untrusted analyst.

The core challenge identified is that standard Local Differential Privacy (Local DP) requires any two distinct functions to be indistinguishable, regardless of their similarity. This uniform guarantee is too strong for functional data, leading to low utility. For instance, two nearly identical linear functions ( $2t+3$ and $2.01t+2.99$ ) would require the same level of noise as two vastly different functions ( $2t+3$ and $2000t-3000$ ).

To resolve this, the authors adopt Geo-Privacy (GP), a generalized notion of differential privacy. GP stipulates that the level of indistinguishability is proportional to the distance between two instances in a metric space. For functions, the paper utilizes the $L_2$ metric (root mean square distance), which is robust against small, localized variations and aligns with physical energy concepts.

Methodology

The paper proposes a series of mechanisms tailored to different assumptions about the structure of the input functions, moving from simple parametric forms to arbitrary continuous curves.

1. Parametric Functions (Linear and Basis Representations)

The authors first consider functions that can be represented as linear combinations of a fixed number of basis functions.

Linear Functions: For a function $f_a(t) = a_1 t + a_2$ , the problem reduces to privatizing the coefficient vector $a \in \mathbb{R}^2$ . A naive application of standard vector privatization (adding spherical Laplace noise to $a$ ) fails because the Euclidean distance between coefficient vectors does not match the $L_2$ distance between the resulting functions.
Solution: The authors derive a specific noise distribution. By expressing the $L_2$ distance between two functions in terms of their coefficients, they identify a covariance matrix $\Sigma$ (derived from the inner products of the basis functions). The mechanism adds noise to the coefficient vector $a$ in the form of $a + \frac{1}{\varepsilon}\Sigma^{1/2}Z$ , where $Z$ is a standard spherical Laplace vector. This ensures the output satisfies $\varepsilon$ -GP with respect to the $L_2$ metric.
Generalization: This approach extends to functions with $m$ basis functions (e.g., polynomials) and vector-valued functions. The noise magnitude scales with $\sqrt{m}$ (or $m$ in expectation for Laplace noise), balancing the dimensionality of the function space against privacy loss.

2. Arbitrary Functions (Project-and-Privatize)

For functions in $L_2(I)$ that do not strictly adhere to a specific parametric form, the authors propose a Project-and-Privatize framework:

Projection: Project the input function $q$ onto a finite-dimensional subspace $U_f$ spanned by a chosen set of basis functions.
Privatization: Apply the parametric mechanism described above to the projection coefficients.
Error Analysis: The total error consists of the approximation error (distance between $q$ and its projection) and the privacy noise. A trade-off exists: using more basis functions reduces approximation error but increases privacy noise.

3. Automatic Basis Selection (PrivFuncSelect)

To automate the trade-off between approximation error and privacy noise, the paper introduces Algorithm 3 (PrivFuncSelect). This algorithm uses the Sparse Vector Technique (SVT) to:

Identify a sufficiently large set of basis functions that approximates the input well.
Privately select a subset of basis functions by filtering out coefficients with small magnitudes (which contribute little to accuracy but add significant noise).
The algorithm balances the two error sources while maintaining $\varepsilon$ -GP through careful composition of privacy budgets.

4. Curve Privatization (Piecewise Approximation)

For general curves, the authors propose Algorithm 4 (PrivFuncSeg) and Algorithm 5 (ReduceSeg), which utilize piecewise basis functions.

Segmentation: The algorithm uses SVT to determine the number of sub-intervals required to balance approximation and noise.
Refinement: It employs a recursive reduction process to remove unnecessary sub-intervals in flatter regions of the curve, thereby reducing the dimensionality of the noise vector without significantly increasing approximation error.
Continuity: A post-processing step ensures the privatized curve is continuous across segment boundaries by solving a constrained quadratic program to find the nearest continuous curve.
Unbounded Intervals: The framework is extended to unbounded domains ( $\mathbb{R}$ ) by first using SVT to find a truncation point $\bar{T}$ where the function's energy outside the interval is negligible, then applying the bounded interval algorithm.

Key Contributions

Geo-Privacy Framework for Functions: The paper establishes a rigorous framework for applying Geo-Privacy to functional data using the $L_2$ metric, demonstrating that this metric provides stronger protection for similar functions compared to point-wise metrics.
Optimal Noise Mechanisms: The authors derive specific noise mechanisms for linear and multi-basis functions that account for the geometry of the function space (via the matrix $\Sigma$ ), correcting the failures of naive isotropic noise addition.
Adaptive Algorithms: The development of PrivFuncSelect and PrivFuncSeg allows for the automatic, private selection of basis functions and segmentation points. These algorithms dynamically balance approximation error and privacy noise without requiring prior knowledge of the function's complexity.
Vector-Valued Support: The methods naturally extend to vector-valued functions and coefficients, making them applicable to multi-dimensional trajectories.
Continuity Preservation: The paper provides a method to enforce continuity in privatized piecewise functions, a critical requirement for realistic curve reconstruction.

Experimental Results and Claims

The paper conducts experimental evaluations on several datasets (including trajectory data) to demonstrate the practical utility of the proposed methods.

Utility Improvement: The results show that the proposed methods achieve significantly better utility (lower $L_2$ error) compared to naive solutions that privatize discrete points independently.
Adaptability: The adaptive algorithms successfully identify the optimal number of basis functions or segments for different types of curves, effectively reducing noise in regions where the function is smooth or flat.
Comparison to Local DP: The paper claims that under standard Local DP, meaningful utility for general curves is impossible without restricting the data universe to a very small space. In contrast, the GP-based approach allows for high utility on typical real-world functional data.

Significance

The paper argues that function privatization in the local model is a distinct and challenging problem that cannot be solved by simply discretizing the function and applying point-wise privacy. By leveraging the Geo-Privacy definition and the $L_2$ metric, the authors provide a theoretically sound and practically effective framework. The significance lies in:

Capturing Correlations: The methods automatically exploit correlations inherent in functional data (e.g., smoothness, periodicity) to reduce noise.
Theoretical Elegance: The solution outputs functions defined over the reals rather than just discrete points, preserving the continuous nature of the data.
Practical Applicability: The algorithms are designed to handle real-world scenarios, including vector-valued trajectories and arbitrary continuous curves, offering a viable path for privacy-preserving data analysis in domains like transportation and signal processing.

The authors maintain a modest stance, noting that the choice of the initial basis collection (e.g., Fourier, polynomials, sinc functions) remains application-dependent, but their framework provides the mechanism to optimally utilize any such collection.