The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs

The Right to Be Forgotten under Correlation: Privacy–Utility Tradeoffs Luis Massny∗ , Rawad Bitar∗ , Fangwei Ye† , Salim El Rouayheb‡

arXiv:2610.17088v1 [cs.IT] 12 Oct 2026

∗ School of Computation, Information and Technology, Technical University of Munich, Munich, Germany † College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China ‡ ECE Department, Rutgers University, New Brunswick, NJ, USA

Abstract—We study privacy-preserving algorithms that redact information from a correlated dataset. The goal is to reduce the information leakage about sensitive parts. We analytically characterize the optimal tradeoff between privacy (leakage through correlation) and utility (number of redactions) for local mechanisms and binary Markovian correlations. Our result shows how to decompose the mechanism design problem into a sequence of local mechanism design problems and reveals their sequential relation. The optimal mechanism is the solution to a Finite-Horizon Deterministic Markov Decision Process. Index Terms—Differential Privacy, Redaction, Markov Decision Process

I. I NTRODUCTION HE right to be forgotten is a central promise of recent privacy protection legislation such as the European Union’s General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA). Data ecosystems [1], [2] that collect valuable datasets for machine learning training and big data analysis can pose a threat to the privacy, and thus, must implement technologies that comply with these regulations. When data are correlated, however, fulfilling the promise of being forgotten can be challenging as only redacting the data samples flagged for removal is often not enough. Data correlation emerges in various settings: information or data sequences that evolve over time, such as activity data [3], location traces [4], [5], financial transactions [6], or energy demands in smart metering [7]–[9], are naturally correlated through their temporal evolution. Furthermore, data from separate individuals connected through social relationships are naturally correlated by these connections [10], [11]. Also, data used downstream in a learning algorithm can make intermediate results depend on it, creating correlation and potentially necessitating an unlearning [12], [13] for its information to be removed. In this work, we advocate for a stronger notion of the right to be forgotten, one that takes a holistic view of privacy by accounting for correlations across the dataset. Under this notion, simply removing the requested data sample is not sufficient; one must also limit

T

Emails: {luis.massny,rawad.bitar}@tum.de, fangweiye@nuaa.edu.cn, salim.elrouayheb@rutgers.edu R. Bitar is supported by the German Research Foundation (DFG) grant agreement number BI 2492/1-1. The work of S. El Rouayheb was supported in part by the Rutgers Global International Collaborative Research Grant.

the information about that sample that can still be inferred from the remaining correlated data. Differential privacy (DP) [14] and local differential privacy (LDP) [15] do not cover correlated datasets [16], [17]. Therefore, several alternative information leakage measures [18]– [22] and adapted DP algorithms [16], [17], [23]–[29] have been proposed for stronger privacy guarantees. Our leakage measure is syntactically equivalent to inferential privacy [21], an instance of pufferfish privacy [18], which provides explicit information leakage guarantees in correlated settings. Unlike most of the DP literature, which designs additive noise, we ask: which data samples must be removed from downstream processing to guarantee the right to be forgotten for a desired sample? Therefore, our mechanisms follow a redact or release approach and are called redaction mechanisms. A data sample is either processed noise-free by a downstream procedure (could be a machine learning algorithm or other data analysis procedures) or redacted, thereby, limiting the trace a redacted sample leaves in the non-redacted data [30]. Prior work [31]–[33] has shown that nontrivial redaction mechanisms can achieve perfect privacy if the full dataset is processed sequentially. We take a different approach and turn towards Local Redaction Mechanisms (LRMs), which process each data sample individually. This enables parallel processing of the data samples, gives small algorithmic complexity, memory efficiency, and is crucial in distributed settings at the expense of relaxing the privacy guarantee. A suboptimal family of such mechanisms named Three-Region (3R) mechanisms has been studied in [34], which restricts the redactions to a sufficient subset of correlated samples. Contributions: We characterize the optimal privacyutility tradeoff for LRMs. Through a recursive decomposition of a mechanism’s leakage, we show how a privacy constraint w.r.t. a sample X0 can be decomposed into a sequence of local leakage constraints w.r.t. correlated samples X1 , X2 , . . . , Xn , respectively. This allows us to characterize the family of mechanism that an optimal LRM lives in, which is characterized by a vector ε of local leakages. We also find that the optimal vector ε is the solution to a FiniteHorizon Deterministic Markov Decision Process (MDP), yielding an analytic characterization of the optimal privacyutility tradeoff.

II. P ROBLEM S ETTING AND D EFINITIONS Notation: For integers, m, n such that m < n, we define [m, n] ≜ {m, m + 1, . . . , n} and abbreviate [n] ≜ [1, n]. Vectors are represented by bold letters, e.g., X and x, and sets are represented by calligraphic letters, e.g., Q. For a vector X = (X1 , . . . , Xn ) and a set Q ⊂ [n], we let XQ be the vector of Xi ’s indexed by Q, i.e., XQ ≜ (Xi )i∈Q . Random variables and random vectors are denoted by uppercase letters X and X, respectively, and their realizations are denoted by lower-case letters, i.e., x and x, respectively. For a random variable X ∈ X , we define its support as supp(X) ≜ {x ∈ X | Pr (X = x) > 0}. The support of a random vector is defined accordingly. For x ∈ {0, 1}, we denote its complement by x̄ ≜ 1 − x. Abusing the notation, we refer to the event {Xi = a | i ∈ Q} as {XQ = a}. 1{·} denotes the indicator function. Problem formulation: Consider samples X0 , . . . , Xn ∈ X modeled by discrete random variables that are correlated. Suppose X0 is flagged for redaction. The goal is to find a probabilistic redaction algorithm M : X n → Y n , called mechanism, which takes as input X ≜ (X1 , . . . , Xn ) and returns a partially redacted view Y ≜ (Y1 , . . . , Yn ) ∈ Y n in order to limit the information leakage about X0 . The mechanism either releases Xt and Yt = Xt or redacts it and Yt = ⋆, i.e., Y = X ∪ {⋆}. We focus on LRMs that process each Xt individually and for which Pr (Y = y|X = x) = Q t∈[1,n] Pr (Yt = yt |Xt = xt ). The information leakage is quantified as follows. Definition 1 (Leakage). A mechanism M : X n → Y n , with input X and output Y has a leakage L(X0 → Y) about X0 ∈ X defined as L(X0 → Y) ≜ log

Pr (Y = y|X0 = x) . ′ y∈supp(Y), (x,x′ )∈X 2 Pr (Y = y|X0 = x ) sup

For given ϵ, a mechanism is private if L(X0 → Y) ≤ ϵ. We aim for maximizing a mechanism’s utility defined as follows. Definition 2 (Utility). The utility ν of a mechanism M : X n → Y n with input X and output Y is " n # X 1 ν≜ E 1{Xt = Yt } . n t=1 Small leakage requires redacting data, whereas high utility requires revealing it. An LRM with leakage ϵ is called optimal if it achieves the maximum utility among all LRMs with leakage at most ϵ. We model the correlation between the samples by a Markov chain1 X0 –X1 – · · · –Xn , which is publicly known. The setting is depicted in Fig. 1. We note that X0 can also

...

X−1

X0

Sensitive history

...

X1

Xt = xt

...

Pr (Y1 |X1 )

Pr (Yt |Xt )

Y1 = ⋆

Yt = ⋆ or Yt = xt

Xn Pr (Yn |Xn ) M

Yn = Xn

Fig. 1. Depiction of the problem setting. X0 is flagged for removal. The goal is to guarantee that any non-redacted samples cause a leakage about X0 of at most ϵ, see Definition 1, while retaining as many of the correlated Markovian data samples X1 , . . . , Xn as possible to maintain utility, see Definition 2. A Local Redaction Mechanism M operates locally on each sample Xt and probabilistically outputs Yt ∈ {Xt , ⋆} according to a prescribed distribution Pr (Yt |Xt ).

be seen as the boundary beyond which a sensitive history X0 , X−1 , . . . is to be forgotten.2 We focus on the elementary problem for binary alphabets X = {0, 1}, where our leakage criterion guarantees the indistinguishability between realizations of X0 . For larger alphabets, this criterion means to guarantee the indistinguishability between binary features of the data. Definitions: We view the correlation between the samples through the lens of the so-called pointwiseinfluence [34]. Definition 3. The pointwise-influence from sample X0 on the realization Xt = xt is i(X0 ⇝ Xt = xt ) ≜ log

max ′

(x0 ,x0

)∈X 2

Pr (Xt = xt |X0 = x0 ) . Pr (Xt = xt |X0 = x′0 )

I(X0 ⇝ Xt ) ≜ maxxt ∈X i(X0 ⇝ Xt = xt ) is called the max-influence from X0 on Xt . The pointwise-influence defines a separation of the samples into three (possibly empty) sets, called regions: RL ≜ {t ∈ [n] | ϵ < i(X0 ⇝ Xt = xt ) for all xt ∈ X }, RS ≜ {t ∈ [n] | ϵ ≥ i(X0 ⇝ Xt = xt ) for all xt ∈ X }, RM ≜ [n] \ {RL ∪ RS }. To simplify the notation, we denote the first sample that has a pointwise-influence of less than ϵ as τ ≜ min{t ∈ [n] | i(X0 ⇝ Xt = xt ) < ϵ for some xt ∈ X }, and let x̂τ ≜ arg maxxτ i(X0 ⇝ Xτ = xτ ), x̌τ = 1 − x̂τ . For t > τ we then recursively define: t =xt |Xt−1 =x̂t−1 ) Λt (xt ) ≜ log Pr(X Pr(Xt =xt |Xt−1 =x̌t−1 ) with,

(1)

x̂t ≜ arg max Λt (xt ), x̌t = 1 − x̂t

(2)

ℓt ≜Λt (x̂t ),

(3)

xt

1 We

neglect the corner case of independent samples, where privacy holds trivially. For instance, when the correlation is modeled by a timehomogeneous binary Markov chain with state transition probabilities α and β, the samples are independent when 1 − α − β = 0.

2 The Markovity together with standard pre-processing inequalities [15], [35] implies that if the leakage about X0 is bounded by ϵ, the leakage about the whole history is bounded by ϵ.

and, with 0 ≤ εt < ℓt , γτ (ετ ) ≜ − log maxx∈X

1 Pr(Xτ =x̂τ |X0 =x)−eετ Pr(Xτ =x̂τ |X0 =x̄) eετ Pr(Xτ =x̌τ |X0 =x̄)−Pr(Xτ =x̌τ |X0 =x)

,

(4)

0.8

The functions γt are increasing and defined only by the data correlation. For a more compact notation, we may abbreviate ( γt (εt ) if εt < ℓt or t = τ, γ̃t : [0, ∞) → R∪{∞}, εt 7→ ∞ otherwise, (6) and q̂t ≜ Pr (Yt = ⋆|Xt = x̂t ), q̌t ≜ Pr (Yt = ⋆|Xt = x̌t ). III. M AIN R ESULTS We find a recursive decomposition (Lemma 2) of the leakage ϵ for an LRM into a sequence of interrelated local leakage constraints ετ , ετ +1 , . . . , εn . We define εn+1 ≜ 0. This motivates the family of leakage-induced mechanisms. (τ )

Definition 4. A leakage-induced mechanism Mε is defined 3 by a leakage vector ε ∈ Rn≥0 with ε[1,τ −1] = 0 and uses
Pr Y[1,τ −1] = ⋆ = 1 and for t ∈ [τ, n]: ( 1 if εt < ℓt or t = τ, Pr (Yt = ⋆|Xt = x̂t ) = 0 otherwise, ( e−(γ̃t (εt )−εt+1 ) if εt < ℓt , Pr (Yt = ⋆|Xt = x̌t ) = 0 otherwise. Designing a leakage-induced mechanism reduces the problem to a core dichotomy: for each sample Xt a mechanism can: either exploit the allowed local leakage εt to reduce the redaction probability of Xt ; or benefit from a lower redaction probability for Xt+1 , . . . , Xn . (τ )

Theorem 1. The leakage-induced mechanism Mε is private if and only if ετ = ϵ and 0 ≤ εt ≤ γ̃t−1 (εt−1 ) for τ + 1 ≤ t ≤ n. The utility-maximizing choice ε⋆ gives an optimal LRM. We show that the problem of finding a utility-maximizing leakage vector ε⋆ is a Finite-Horizon Deterministic MDP with state st = εt and action at = εt+1 . This yields an analytic expression for the privacy-utility tradeoff of an optimal LRM M⋆ in terms of the so-called value [36], which is recursively defined as h i M⋆ VtM⋆ (εt ) = max Rt (εt , εt+1 ) + Vt+1 (εt+1 ) (7) εt+1 ∈[0,γ̃t (εt )]

M⋆ for τ ≤ t ≤ n, with Vn+1 (εn+1 ) = 0 and

Rt (εt , εt+1 ) ≜ 1 − q̂t Pr (Xt = x̂t ) − q̌t Pr (Xt = x̌t ) ( 1 if εt ≥ ℓt ,   = (8) Pr (Xt = x̌t ) 1 − e−(γt (εt )−εt+1 ) otherwise. 3 For notational convenience, we let ε ∈ Rn , but use only ε

[τ,n] .

Utility ν

εt

t =x̂t |Xt−1 =x̂t−1 )−e Pr(Xt =x̂t |Xt−1 =x̌t−1 ) γt (εt ) ≜ − log ePr(X . εt Pr(X =x̌ |X t t t−1 =x̌t−1 )−Pr(Xt =x̌t |Xt−1 =x̂t−1 ) (5)

0.6

Reveal RM ∪ RS Optimal tradeoff (Corollary 1) 3R mechanism [34] Reveal only RS

0.4

0.2 −5 10

10−4

10−3

10−2 10−1 Leakage ϵ

100

101

Fig. 2. Optimal privacy-utility tradeoff for LRMs. For comparison, the utility achievable by always revealing RS (lower bound) or RS ∪ RM (upper bound, might exceed leakage ϵ) is given. The optimal tradeoff is given by Corollary 1. We consider n = 10 samples correlated by a time-homogeneous binary Markov chain with transition probabilities Pr (Xt+1 = 1|Xt = 0) = 10−2 , Pr (Xt+1 = 0|Xt = 1) = 8 · 10−1 initialized in its stationary distribution.

Corollary 1. The optimal privacy-utility tradeoff is ν⋆ = VτM⋆ (ϵ)/n.

(9)

We plot the optimal privacy-utility tradeoff in Fig. 2 for a particular parameter set. IV. O PTIMAL L OCAL R EDACTION M ECHANISM Our main result is built from three layers, which we explain and discuss sequentially. As the foundation, we study the fundamental properties of the leakage for LRMs in Section IV-A first. We then, build up on this to establish a decomposition law for the leakage in Section IV-B and subsequently outline the proof of Theorem 1. Finally, this yields a characterization of the optimal privacy-utility tradeoff as discussed in Section IV-C. A. General Properties A mechanism’s leakage is discontinuous in the redaction probability: allowing realizations with higher pointwiseinfluence to be revealed necessarily elevates the leakage. This observation provides insights into the output distribution’s shape of an optimal redaction mechanism as follows. Lemma 1. If an LRM is optimal, then for every t ∈ [1, n] the following holds: (i) Pr (Yt = ⋆|Xt = xt ) < 1 ∀xt ∈X =⇒ Pr (Yt = ⋆) = 0, (ii) Pr (Yt = ⋆) = 0 =⇒ Pr (Ys = ⋆) = 0 ∀s≥t . Proof. It can be shown that the leakage of an LRM is lowerbounded by the pointwise influence i(X0 ⇝ Xt = xt ) of any realization Xt = xt that is revealed with positive probability, cf. Appendix A. Hence, redaction does not affect the leakage unless there is at least one realization that is always redacted,

i.e., Pr (Yt = ⋆|Xt = xt ) = 1. The second property is an implication of the Markovian data correlation. We give the full technical proof of Lemma 1 in Appendix A. Corollary 2. For every t ∈ [n], an optimal LRM either never redacts Xt (Pr (Yt = ⋆) = 0) or there exists at least one x̂t ∈ X that is always redacted (Pr (Yt = ⋆|Xt = x̂t ) = 1). Proof. Either Pr (Yt = ⋆) = 0 or Pr (Yt = ⋆) > 0. In the latter case, if Pr (Yt = ⋆|Xt = xt ) < 1 ∀xt ∈X , then Lemma 1 implies that Pr (Yt = ⋆) = 0 contradicting the fact that Pr (Yt = ⋆) > 0. Hence, there must exist at least one x̂t ∈ X with Pr (Yt = ⋆|Xt = x̂t ) = 1 in this case. Due to Lemma 1, we can restrict to mechanisms that form a contiguous set of w probabilistically redacted samples, i.e. {t | Pr (Yt = ⋆) > 0} = [w]. We can also assume without loss of optimality that for all t ∈ [1, w] ( 1 xt = x̂t , (10) Pr (Yt = ⋆|Xt = xt ) = q̌t xt = x̌t , for some x̂t and x̌t = 1 − x̂t (a leakage-induced mechanism chooses according to Eq. (2)). Any output of a redaction mechanism can be written as y(t) = (⋆, . . . , ⋆, xt+1 , yt+2 , . . . , yn ) for a t ∈ [w] and xt+1 ∈ supp(Yt+1 ) ∩ X . By the Markovity, i(X0 ⇝ Y = y(t) ) is independent of yt+2 , . . . , yn . Therefore, the pointwiseinfluence of an output y(t) is uniquely characterized by its equivalence class Yx(t) ≜{y = (⋆, . . . , ⋆, xt+1 , yt+2 , . . . , yn ) t+1

of possible combinations, involving discrete optimization variables w and x̂t , and continuous variables q̌t , and is computationally and analytically intractable. The following questions emerge, which we answer in our work: (Q1) When should the redaction window [w] terminate? (Q2) Which realization x̂t should be redacted? (Q3) How should one choose q̌t for t ∈ [w]? The optimal redaction mechanism is trivial for I(X0 ⇝ Xτ ) ≤ ϵ (i.e., when |RM | = 0), namely, [w] = RL and thus, q̌t = 1 for all t ∈ [w]. We consider only the nontrivial case where I(X0 ⇝ Xτ ) = i(X0 ⇝ Xτ = x̂τ ) > ϵ ≥ i(X0 ⇝ Xτ = x̌τ ) in the sequel. In this case, Pr (Yτ = ⋆|Xτ = x̂τ ) = 1 and the constraint in P0 is satisfied for t = τ − 1 by definition of τ . Hence, only the constraints for t ∈ [τ, w] are nontrivial. B. Decomposition into Local Leakage Constraints Lemma 2 (Recurrence relation). Suppose y(t) ∈ supp(Y). For all s, τ + 1 ≤ s ≤ t, and for εs ≥ 0 it holds:   (t) Pr Y[s,t+1] = y[s,t+1] |Xs−1 = x̂s−1   ≤ eεs (11) (t) Pr Y[s,t+1] = y[s,t+1] |Xs−1 = x̌s−1 if and only if εs ≥ ℓs or   (t) q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s (12)   (t) − q̌s eγs (εs ) Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s ≤ 0.

Proof. The rigorous proof is technical and deferred to Appendix B. The main idea is to exploit the Markovity We can write an LRM’s leakage as the maximum of leakages Xs−1 – Xs – Y[s,t+1] and write   over all redaction windows: (t)
Pr Y = y |X = x (t) s−1 s−1 [s,t+1] [s,t+1] Pr Y = y |X0 = x  
, L(X0 → Y) = max max log (t) x∈X t∈[τ −1,w] Pr Y = y(t) |X0 = x̄ = q̌s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s | (yt+2 , . . . , yn ) ∈ supp(Y[t+2,n] )}.

xt+1 ∈supp(Yt+1 ) (t)

where y(t) ∈ Yxt+1 . Its utility can be expressed as: 1 X ν =1 − (Pr (Xt = x̂t ) + q̌t Pr (Xt = x̌t )). n t∈[w]

In summary, we can formulate the general mechanism design problem explicitly as: X P0 : min (Pr (Xt = x̂t ) + q̌t Pr (Xt = x̌t )) τ ≤w≤n t∈[τ,w] x̂t ,t∈[τ,w] 0<q̌t ≤1,t∈[τ,w]

s.t.

Pr Y = y(t) |X0 = x
≤ eϵ Pr Y = y(t) |X0 = x̄ for all x ∈ X , (t)

for all y(t) ∈ Yx̌t+1 , t ∈ [τ − 1, w − 1] (w)

(w)

for all y(w) ∈ Yx̌w+1 ∪ Yx̂w+1 . The optimization problem P0 is nonconvex, the solution of which requires a search among an exponential number

· Pr (Xs = x̌s |Xs−1 = xs−1 )   (t) + q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s · Pr (Xs = x̂s |Xs−1 = xs−1 ). The remainder of the proof relies on two arguments: (i) Substituting the expression derived above into Eq. (11) shows that the constraint is always satisfied when εs is sufficiently large; (ii) If εs is small, then γs (εs ) is well-defined and Eq. (11) is equivalent to Eq. (12). Proof of Theorem 1. We give an overview of the proof idea here and defer the technical details to Appendix C. The proof is inductive and shows for each τ + 1 ≤ t ≤ n that the overall leakage requirement holds if and only if 0 ≤ εt ≤ γ̃t−1 (εt−1 ). This proves the privacy of a leakageinduced mechanism according to Theorem 1. Then, we re-formulate the optimization problem P0 into an MDP. Hence, the solution of that MDP gives an optimal LRM. Importantly, the MDP can be understood as choosing the

utility-maximizing leakage vector ε⋆ for a leakage-induced (τ ) mechanism Mε . We start the induction by showing that, for every output y(t) ∈ supp(Y), the leakage requirement

Pr Y = y(t) |X0 = x0 − eϵ Pr Y = y(t) |X0 = x̄0 ≤ 0 is equivalent to   (t) Pr Y[τ +1,t+1] = y[τ +1,t+1] |Xτ = x̂τ   (t) − q̌τ eγτ (ετ ) Pr Y[τ +1,t+1] = y[τ +1,t+1] |Xτ = x̌τ ≤ 0. | {z } ≜eετ +1

with ετ = ϵ. By the change of variable to ετ +1 , we obtain a condition similar to Eq. (11). From this on, we employ Lemma 2 to transform the constraints of P0 into   (t) q̂t Pr Yt+1 = yt+1 |Xt = x̂t   (t) − q̌t eγt (εt ) Pr Yt+1 = yt+1 |Xt = x̌t ≤ 0. Similar to above, we can introduce a new variable εt+1 for each t and define q̌t eγt (εt ) ≜ eεt+1 . At the same time, we note that q̂t = 1 is necessary. Nonetheless, we note that this holds only if εt < ℓt . If εt is sufficiently large, then q̌t = q̂t = 0 is feasible and optimal instead. We re-iterate this line of arguments for t = τ + 1, τ + 2, . . . , n. Note that γt (εt ) is well-defined in the case εt < ℓt and defines the feasible region for εt+1 . In the other case, in contrast, the feasible εt+1 is unconstrained since it is feasible to have Pr (Yt+1 = ⋆) = · · · = Pr (Yn = ⋆) = 0. To arrive at an MDP representation, we view the local leakage as the state st = εt of a process, which evolves as st+1 = at , when at = εt+1 denotes the action taken in state st . Namely, the action describes how much leakage is propagated on to the next state. Re-writing the utility as P ν = n1 t∈[τ,n] Rt (st , at ), we arrive at an equivalent finitehorizon deterministic MDP: X Rt (st , at ) (13) max at ,τ ≤t≤n

t∈[τ,n]

s.t. st+1 = at and at ∈ [0, γ̃t (st )], τ ≤ t ≤ n. The initial and final states are sτ = ϵ, and sn+1 = 0. Rt (εt , εt+1 ) as defined in Eq. (8) is the reward of transitioning from state εt to state εt+1 . We note that our transformation steps into (13) do not transform the optimization objective. As such, the same steps can be applied to establish a result similar to Theorem 1 under other utility measures. The formulation is a proper MDP whenever P the utility measure can be written as an additive reward t∈[τ,n] Rt (st , at ). C. Interpretation and Characterization The design of a leakage-induced mechanism and its MDP representation permit the following alternative views. A private leakage-induced mechanism according to Theorem 1 can be understood as a sequential composition of the leakage. The MDP form can be understood as a sequence of decisions:

whether to collect an immediate reward by revealing more about the current instance (allow low subsequent leakage εt+1 ); or to maintain a high redaction probability in the hope to reveal more about future instances (allow high subsequent leakage εt+1 ). An illustration of both perspectives is provided in Appendix D. The leakage allowed in subsequent releases can be thought of as a budget that is to be consumed. As standard for an MDP, we can describe the optimization objective in terms of a value function. The value that allowing leakage εt provides under a mechanism M (which takes actions at (εt ) = εt+1 ) is defined recursively as: VtM (εt ) = M Rt (εt , εt+1 ) + Vt+1 (εt+1 ). According to Bellman’s principle of optimality [36], an optimal mechanism M⋆ satisfies: h i M⋆ Rt (εt , εt+1 ) + Vt+1 (εt+1 ) VtM⋆ (εt ) = max εt+1 ∈[0,γ̃t (εt )]

M⋆ for τ ≤ t ≤ n, with Vn+1 (εn+1 ) = 0. This yields the optimal privacy-utility tradeoff in Corollary 1.

V. D ISCUSSION AND C ONCLUSION Our result answers the stated questions as follows. (Q1) When to terminate the redaction window: The redaction window is terminated as soon as the leakage budget εt saved from previous releases reaches a threshold ℓt . Whether it pays off to save more leakage budget depends on the function γt and on the marginal distribution of Xt . It is always possible to find a policy to terminate the redaction window at the end of the region RM , but not always optimal. (Q2) Which realization to redact: The realization x̂τ that is redacted surely corresponds to the high-leaking realization that is influenced most by X0 . In the same spirit, x̂t for t > τ corresponds to the high-leaking realization w.r.t. Xt−1 = x̂t−1 . While the high-leaking realization must be redacted necessarily, the low-leaking realization x̌t can be released with positive probability. Nonetheless, the redaction probability must be strictly positive to preserve plausible deniability about x̂t when Yt = ⋆. (Q3) How to design the redaction probabilities: The optimal redaction probabilities have a threshold-type relation to the allowed leakage εt . For leakage εt ≥ ℓt , the redaction probability vanishes. For leakage εt < ℓt , the redaction probability for sample Xt decays exponentially in the leakage consumed. The leakage consumption is upper bounded by γt (εt ), which describes the amplification of the leakage budget saved through previous redaction decisions. We evaluate the optimal privacy-utility tradeoff in Fig. 2, by numerically approximating the MDP solution through Approximate Dynamic Programming [37], discretizing the state and action space to ∆ = 100 equally spaced values.4 This reveals the sub-optimality of the previously proposed 3R mechanism [34], for small allowed leakage in particular. As future work, we pursue the development of efficient algorithms to achieve the optimal privacy-utility tradeoff and the extension to nonbinary alphabets. 4 We implemented the approximate MDP solution using the DynaProg MATLAB toolbox [38].

S TATEMENT OF AI U SE The authors acknowledge the use of Claude Opus 5.5 (Anthropic) for the discovery of related literature and GPT5.6 (Open AI) for sketching the definition of a leakageinduced mechanism according to our ideas. The authors take full responsibility for the contents in this manuscript. R EFERENCES [1] G. Kazmaier, “Building the most open data cloud ecosystem.” cloud.google.com/blog/products/data-analytics/ building-most-open-data-cloud-all-data-all-source-any-platform, 2022. Accessed: 2026/07/23. [2] E. Aimeur, G. Brassard, and M. Guo, “How data brokers endanger privacy,” Transactions on Data Privacy, 2022. [3] N. Zufferey, M. Humbert, R. Tavenard, and K. Huguenin, “Watch your watch: Inferring personality traits from wearable activity trackers,” in 32nd USENIX Security Symposium, 2023. [4] A. Karatzoglou, D. Köhler, and M. Beigl, “Semantic-enhanced multidimensional markov chains on semantic trajectories for predicting future locations,” Sensors, vol. 18, no. 10, 2018. [5] B. Liu, W. Zhou, T. Zhu, L. Gao, and Y. Xiang, “Location Privacy and Its Applications: A Systematic Study,” IEEE Access, vol. 6, 2018. [6] B. Chen and Y. Hong, “Testing for the markov property in timeseries,” Econometric Theory, vol. 28, no. 1, 2012. [7] J. Torriti, “A review of time use models of residential electricity demand,” Renewable and Sustainable Energy Reviews, vol. 37, 2014. [8] S. Li, A. Khisti, and A. Mahajan, “Information-theoretic privacy for smart metering systems with a rechargeable battery,” IEEE Transactions on Information Theory, vol. 64, no. 5, 2018. [9] L. Sankar, S. R. Rajagopalan, S. Mohajer, and H. Poor, “Smart meter privacy: A theoretical framework,” IEEE Transactions on Smart Grid, vol. 4, no. 2, 2013. [10] E. W. D. Luca, A. Said, and S. Albayrak, “How social relationships affect user similarities,” in Proceedings of the Social Recommender Systems Workshop, in Conjunction with the 2010 International Conference on Intelligent User Interfaces, 2010. [11] P. Bonhard and M. A. Sasse, “’Knowing me, knowing you’ — Using profiles and social networking to improve recommender systems,” BT Technology Journal, vol. 24, no. 3, 2006. [12] L. Bourtoule, V. Chandrasekaran, C. A. Choquette-Choo, H. Jia, A. Travers, B. Zhang, D. Lie, and N. Papernot, “Machine unlearning,” in 2021 IEEE Symposium on Security and Privacy, 2021. [13] Y. Cao and J. Yang, “Towards making systems forget with machine unlearning,” in 2015 IEEE Symposium on Security and Privacy, 2015. [14] C. Dwork, “Differential Privacy,” in Automata, Languages and Programming (M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, eds.), Lecture Notes in Computer Science, (Berlin, Heidelberg), Springer, 2006. [15] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local Privacy and Statistical Minimax Rates,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013. [16] D. Kifer and A. Machanavajjhala, “No free lunch in data privacy,” in Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery, 2011. [17] C. Liu, S. Chakraborty, and P. Mittal, “Dependence Makes You Vulnerable: Differential Privacy Under Dependent Tuples,” in Proceedings 2016 Network and Distributed System Security Symposium, Internet Society, 2016. [18] D. Kifer and A. Machanavajjhala, “Pufferfish: A framework for mathematical privacy definitions,” ACM Transactions on Database Systems, vol. 39, no. 1, 2014.

[19] B. Yang, I. Sato, and H. Nakagawa, “Bayesian Differential Privacy on Correlated Data,” in Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery, 2015. [20] J. Zhao, J. Zhang, and H. V. Poor, “Dependent Differential Privacy for Correlated Data,” in 2017 IEEE Globecom Workshops, 2017. [21] A. Ghosh and R. Kleinberg, “Inferential privacy guarantees for differentially private mechanisms,” in 8th Innovations in Theoretical Computer Science Conference (C. H. Papadimitriou, ed.), vol. 67 of Leibniz International Proceedings in Informatics (Lipics), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [22] S. Wang, S. Zheng, Z. Lin, G. Fanti, and Z. S. Wu, “Inferentiallyprivate private information,” in Proceedings of the ACM Web Conference 2025, Association for Computing Machinery, 2025. [23] R. Chen, B. C. M. Fung, P. S. Yu, and B. C. Desai, “Correlated network data publication via differential privacy,” The VLDB Journal, vol. 23, no. 4, 2014. [24] Y. Xiao and L. Xiong, “Protecting Locations with Differential Privacy under Temporal Correlations,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2015. [25] T. Zhu, P. Xiong, G. Li, and W. Zhou, “Correlated Differential Privacy: Hiding Information in Non-IID Data Set,” IEEE Transactions on Information Forensics and Security, vol. 10, no. 2, 2015. [26] S. Song, Y. Wang, and K. Chaudhuri, “Pufferfish Privacy Mechanisms for Correlated Data,” in Proceedings of the 2017 ACM International Conference on Management of Data, ACM, 2017. [27] S. Song and K. Chaudhuri, “Composition properties of inferential privacy for time-series data,” in 2017 55th Annual Allerton Conference on Communication, Control, and Computing, 2017. [28] D. Chakrabarti, J. Gao, A. Saraf, G. Schoenebeck, and F.-Y. Yu, “Optimal local bayesian differential privacy over markov chains,” in Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2022. [29] J. Bai, G. He, X. Gu, D. Kifer, and K. Maeng, “Composition for pufferfish privacy,” in Proceedings of the VLDB Endowment, vol. 19, VLDB Endowment, 2026. [30] S. Garg, S. Goldwasser, and P. N. Vasudevan, “Formalizing data deletion in the context of the right to be forgotten,” in Advances in Cryptology – EUROCRYPT 2020 (A. Canteaut and Y. Ishai, eds.), (Cham), Springer International Publishing, 2020. [31] F. Ye, C. Naim, and S. E. Rouayheb, “On-off privacy in the presence of correlation,” IEEE Transactions on Information Theory, vol. 67, no. 11, 2021. [32] F. Ye, H. Cho, and S. El Rouayheb, “Mechanisms for Hiding Sensitive Genotypes With Information-Theoretic Privacy,” IEEE Transactions on Information Theory, vol. 68, no. 6, 2022. [33] F. Ye, Z. Liu, P. Parag, and S. El Rouayheb, “Perfect privacy and strong stationary times for markovian sources,” in 2026 IEEE International Symposium on Information Theory, 2026. [34] L. Maßny, R. Bitar, F. Ye, and S. El Rouayheb, “Between close enough to reveal and far enough to protect: a new privacy region for correlated data,” in 2025 IEEE Information Theory Workshop, 2025. [35] C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3-4, 2013. [36] R. Bellman, “The theory of dynamic programming,” Bulletin of the American Mathematical Society, vol. 60, no. 6, pp. 503–515, 1954. [37] W. B. Powell, Approximate Dynamic Programming: Solving the Curses of Dimensionality. Newark: John Wiley & Sons, Incorporated, 2011. [38] F. Miretti, D. Misul, and E. Spessa, “Dynaprog: Deterministic dynamic programming solver for finite horizon multi-stage decision problems,” SoftwareX, vol. 14, 2021.

A PPENDIX A G ENERAL PROPERTIES OF LRM S Lemma 3. Let P ≜ {t ∈ [n]|Pr (Yt = ⋆) < 1} denote the set of samples that are revealed with positive probability. The leakage of an LRM about X0 is at most

Therefore, Pr (Y = y|X0 = x) Pr (Y = y|X0 = x̄) Pr (XQ = yQ |X0 = x) ≥ log max yQ ,x Pr (XQ = yQ |X0 = x̄) =i(X0 ⇝ XQ = yQ ).

L(X0 → Y) = log max y,x

L(X0 → Y) ≤ I(X0 ⇝ XP ). For any subset Q ⊆ P, if the realization xQ ∈ supp(YQ ) ∩ X |Q| is revealed with positive probability, then the leakage of an LRM about X0 is at least L(X0 → Y) ≥ i(X0 ⇝ XQ = xQ ). The above properties follow from the Markovity and the definition of redaction mechanisms. One can observe that the leakage is confined between the max-influence of released samples and the pointwiseinfluence of the revealed realizations. Concretely, Lemma 3 shows that no LRM with leakage at most ϵ can reveal a sample from the region RL . In contrast, revealing all samples from region RS never exceeds the allowed leakage, which serves as a trivial baseline redaction mechanism, cf. [34]. Most interestingly, RM contains samples the disclosure of which, for some realizations, does not exceed the allowed leakage per se, but for other realizations does. The crux of designing a private mechanism boils down to ensuring indistinguishability between realizations of the former kind and the latter kind. Proof of Lemma 3. Suppose there exists y ∈ supp(Y) with yt ̸= ⋆ for all t ∈ Q. Define Q̄ = [n] \ Q. It holds: Pr (Y = y|X0 = x)

Proof of Lemma 1. Let t ∈ [1, n] and xt ∈ X . Suppose Pr (Yt = ⋆|Xt = xt ) < 1, but also Pr (Yt = ⋆|Xt = xt ) > 0. Then there exists a y ∈ supp(Y) such that yt = xt . For this y it holds that Pr (Y = y|X0 = x) X Pr (Y = y|Xt = x′t , X0 = x)Pr (Xt = x′t |X0 = x) = x′t

=Pr (Y = y|Xt = xt , X0 = x)Pr (Xt = xt |X0 = x) (16) The last equality holds, because a local redaction mechanism has Pr (Yt = xt |Xt = x′t ) = 0 when x′t ̸= xt , and thus, Pr (Y = y|Xt = x′t , X0 = x) =Pr (Y−t = y−t |Xt = x′t , X0 = x) Pr (Yt = xt |Xt = x′t , X0 = x) =Pr (Y−t = y−t |Xt = x′t , X0 = x) Pr (Yt = xt |Xt = x′t ) = 0. As a result, the leakage is L(X0 → Y) = log

(a)

= Pr (Y = y|X0 = x, XQ = yQ )Pr (XQ = yQ |X0 = x)

(b)

=Pr (YQ̄ = yQ̄ |X0 = x, XQ = yQ ) · Pr (XQ = yQ |X0 = x)Pr (YQ = yQ |XQ = yQ )

where (a) follows since Pr (Yt = xt |Xt = x) = 0 if x ̸= xt for redaction mechanisms, and (b) follows by the Markovity of the chain. Hence, we can conclude that Pr (Y = y|X0 = x) Pr (YQ̄ = yQ̄ |X0 = x, XQ = yQ ) = Pr (Y = y|X0 = x̄) Pr (YQ̄ = yQ̄ |X0 = x̄, XQ = yQ ) (14) Pr (XQ = yQ |X0 = x) · . (15) Pr (XQ = yQ |X0 = x̄) For every x, we can always choose a y with yQ̄ such that in Eq. (14) it holds Pr (YQ̄ = yQ̄ |X0 = x, XQ = yQ ) ≥ 1. Pr (YQ̄ = yQ̄ |X0 = x̄, XQ = yQ ) Otherwise, we have a contradiction: Pr (YQ̄ = yQ̄ |X0 = x, XQ = yQ ) < Pr (YQ̄ = yQ̄ |X0 = x̄, XQ = yQ )∀yQ̄ X =⇒ 1 = Pr (YQ̄ = yQ̄ |X0 = x, XQ = yQ ) yQ̄

<

X yQ̄

Pr (YQ̄ = yQ̄ |X0 = x̄, XQ = yQ ) = 1.

≥ log

max

Pr (Y = y|X0 = x)

x∈X , Pr (Y = y|X0 = x̄) y∈supp(Y)

max

Pr (Y = y|X0 = x)

x∈X , Pr (Y = y|X0 = x̄) y−t ∈supp(Y−t ), yt ∈X

,

where by Eq. (16), it holds: Pr (Y = y|X0 = x) Pr (Y = y|X0 = x̄) Pr (Y = y|Xt = yt , X0 = x) Pr (Xt = xt |X0 = x) = · Pr (Y = y|Xt = yt , X0 = x̄) Pr (Xt = xt |X0 = x̄) Pr (Y−t = y−t |Xt = yt , X0 = x)Pr (Yt = yt |Xt = yt ) = Pr (Y−t = y−t |Xt = yt , X0 = x̄)Pr (Yt = yt |Xt = yt ) Pr (Xt = xt |X0 = x) · Pr (Xt = xt |X0 = x̄) Pr (Y−t = y−t |Xt = yt , X0 = x) = Pr (Y−t = y−t |Xt = yt , X0 = x̄) Pr (Xt = xt |X0 = x) · . Pr (Xt = xt |X0 = x̄)

Consider another mechanism M′ with outputs Y′ and with the same distributions Pr (Yi′ |Xi ) = Pr (Yi |Xi ) for i ̸= t, ′ but with Pr (Yt′ = ⋆) = 0. Then, supp(Y−t ) = supp(Y−t ). The leakage is Pr (Y′ = y′ |X0 = x) L(X0 → Y′ ) = log max x∈X , Pr (Y′ = y′ |X0 = x̄) ′ ′

Pr(Xs =xs |Xs−1 =x̂s−1 ) If εs ≥ maxxs log Pr(X , then both sums =xs |Xs−1 =x̌s−1 ) mands are non-positive. Thus, any Pr (Ys = ⋆|Xs = x̌s ) ≥ 0 and Pr (Ys = ⋆|Xs = x̂s ) ≥ 0 are feasible. Otherwise, we have in this case:

Pr (Xs = x̂s |Xs−1 = x̂s−1 ) −e Pr (Xs = x̂s |Xs−1 = x̌s−1 ) > 0,

y ∈supp(Y )

= log

max

x∈X , ′ ′ y−t ∈supp(Y−t ), yt′ ∈X

Pr (Y′ = y′ |X0 = x) , Pr (Y′ = y′ |X0 = x̄)

where, as before, Eq. (16) gives Pr (Y′ = y′ |X0 = x) Pr (Y′ = y′ |X0 = x̄) Pr (Y′ = y′ |Xt = yt′ , X0 = x) Pr (Xt = xt |X0 = x) = · Pr (Y′ = y′ |Xt = yt′ , X0 = x̄) Pr (Xt = xt |X0 = x̄)
′ ′ Pr Y−t = y−t |Xt = yt′ , X0 = x
= ′ = y′ |X = y ′ , X = x̄ Pr Y−t t 0 t −t Pr (Xt = xt |X0 = x) · Pr (Xt = xt |X0 = x̄)
′ ′ Pr Y−t = y−t |Xt = yt′ , X0 = x
= ′ = y′ |X = y ′ , X = x̄ Pr Y−t t 0 t −t Pr (Xt = xt |X0 = x) . · Pr (Xt = xt |X0 = x̄) It can be observed that L(X0 → Y′ ) ≤ L(X0 → Y). Furthermore, Pr (Yt′ = ⋆) = 0 < Pr (Yt = ⋆) implies that the utility ν ′ of M′ is larger than the utility ν of M. Thus, M′ achieves higher utility than M with at most the same leakage, which contradicts the fact that M has an optimal utility ν. To prove the last statement, we recall the Markovian relation X0 − Xt − Y[t+1,n] . Therefore, if a record Xt is always released, i.e., Pr (Yt = ⋆) = 0, then Yt = Xt and, hence,
Pr Y[t] = y[t] |X0 = x Pr (Y = y|X0 = x)
. = Pr (Y = y|X0 = x̄) Pr Y[t] = y[t] |X0 = x̄ Since the leakage does not depend on Y[t+1,n] , the utility is maximized by setting Y[t+1,n] = X[t+1,n] , i.e., Pr (Ys = ⋆) = 0 for all s > t. A PPENDIX B P ROOF OF L EMMA 2 Let t ≥ τ and τ + 1 ≤ s ≤ t. Suppose y(t) ∈ supp(Y). It holds   (t) Pr Y[s,t+1] = y[s,t+1] |Xs−1 = x̂s−1   (t) − eεs Pr Y[s,t+1] = y[s,t+1] |Xs−1 = x̌s−1 ≤ 0   (t) ⇔q̌s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s  · Pr (Xs = x̌s |Xs−1 = x̂s−1 )  − eεs Pr (Xs = x̌s |Xs−1 = x̌s−1 )   (t) +q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s  · Pr (Xs = x̂s |Xs−1 = x̂s−1 )  − eεs Pr (Xs = x̂s |Xs−1 = x̌s−1 ) ≤ 0.

(17)

εs

s =xs |Xs−1 =x̂s−1 ) with x̂s ≜ arg maxxs log Pr(X Pr(Xs =xs |Xs−1 =x̌s−1 ) . This also implies

Pr (Xs = x̌s |Xs−1 = x̂s−1 )

(18)

εs

−e Pr (Xs = x̌s |Xs−1 = x̌s−1 ) < 0, since (17) + (18) = 1 − eεs ≤ 0. Therefore, we can reformulate the equation above as   (t) q̌s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s εs

Pr(Xs =x̌s |Xs−1 =x̌s−1 ) s =x̌s |Xs−1 =x̂s−1 )−e · Pr(X Pr(Xs =x̂s |Xs−1 =x̂s−1 )−eεs Pr(Xs =x̂s |Xs−1 =x̌s−1 )   (t) + q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s ≤ 0   (t) ⇔q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s   (t) − q̌s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s εs

Pr(Xs =x̌s |Xs−1 =x̌s−1 )−Pr(Xs =x̌s |Xs−1 =x̂s−1 ) · ePr(X =x̂ |X =x̂ )−eεs Pr(Xs =x̂s |Xs−1 =x̌s−1 ) ≤ 0 s s s−1 s−1  (t) ⇔q̂s Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̂s   (t) − q̌s eγs (εs ) Pr Y[s+1,t+1] = y[s+1,t+1] |Xs = x̌s ≤ 0.

where εs

Pr(Xs =x̌s |Xs−1 =x̌s−1 )−Pr(Xs =x̌s |Xs−1 =x̂s−1 ) γs (εs ) ≜ log ePr(X ε s =x̂s |Xs−1 =x̂s−1 )−e s Pr(Xs =x̂s |Xs−1 =x̌s−1 )

is well-defined since the argument of the logarithm is strictly positive, cf. Eq. (17) and Eq. (18). A PPENDIX C F ULL PROOF OF T HEOREM 1 We prove the more technical result below. Theorem 2. Let ετ = ϵ and εn+1 = 0 and suppose {εt }τ +1≤t≤n are the solution to X P1 : min (q̂t Pr (Xt = x̂t ) + q̌t Pr (Xt = x̌t )) {εt }τ +1≤t≤n

s.t.

t∈[τ,n]

0 ≤ εt ≤ γ̃t−1 (εt−1 ), τ + 1 ≤ t ≤ n,

An optimal binary LRM with leakage ϵ is Pr (Yt = ⋆) = 1 for all t ∈ [1, τ − 1] and ( 1 if εt < ℓt or t = τ, Pr (Yt = ⋆|Xt = x̂t ) = q̂t ≜ 0 otherwise, ( e−(γt (εt )−εt+1 ) if εt < ℓt , Pr (Yt = ⋆|Xt = x̌t ) = q̌t ≜ 0 otherwise.

ϵ = ϵτ X0

···

Xτ

Yτ +2

···

ϵτ +2

ϵτ +1 Xτ +1

ℓn ϵt

Yτ +1

Yτ

Xτ +2

···

(a) Sequential composition view: The mechanism design problem is to find a leakage sequence {εt }t , where each εt quantifies the relative leakage of Y[t,n] w.r.t. the reference Xt−1 , respectively.

ϵ 0

sn sτ +1

∆ sτ aτ X0 · · · Xτ

sτ +2 aτ +1 Xτ +1

Xτ +2 · · ·

Xn

(b) MDP view: The mechanism design problem is to find an optimal sequence of actions (at )t to move between states (st )t . Numerical algorithms quantize the states with resolution ∆.

Fig. 3. Illustration of the perspectives on the mechanism design problem.

for t ∈ [τ, n]. The proof is inductive. The starting point is established by similar arguments as used in the proof of Lemma 2. A mechanism has leakage ϵ if and only if     Pr Y = y(t) |X0 = x0 − eϵ Pr Y = y(t) |X0 = x̄0 ≤ 0

In every iteration t, we introduce a variable εt+1 and determine q̌t and q̂t as a function of εt and εt+1 . Pr(Xt =x̂t |Xt−1 =x̂t−1 ) For each t ≥ τ + 1, if εt ≥ log Pr(X , t =x̂t |Xt−1 =x̌t−1 ) (t−1)

then y(t−1) with yt = x̂t can be in supp(Y). Thus, q̌t = q̂t = 0 is feasible and is the optimal choice to maximize utility. t =x̂t |Xt−1 =x̂t−1 ) (t−1) Otherwise, if εt < log Pr(X Pr(Xt =x̂t |Xt−1 =x̌t−1 ) , then y

holds for all x0 ∈ X and for all t ≥ τ for which y(t) ∈ (t−1) = x̂t cannot be in supp(Y), as this would supp(Y). We first, exploit the Markovity X0 – Xτ – Y to with yt contradict Lemma 2. Therefore, it must hold that q̂t = 1 and show that     q̌t is defined through γt (εt ) accordingly. Note that, for the Pr Y = y(t) |X0 = x0 − eϵ Pr Y = y(t) |X0 = x̄0 ≤ 0 same reason, q̌ > 0 is necessary, as otherwise, the symbol ⋆ t   (t) would only be a renaming of x̂t (thus, violating the leakage ⇔Pr Y = y[τ,t+1] |Xτ = x̂τ requirements again). Hence, we can define q̌t eγt (εt ) ≜ eεt+1 .   (t) Rewriting this, gives q̌t = e−(γt (εt )−εt+1 ) . As q̌t ≤ 1, − eγτ (ετ ) Pr Y = y[τ,t+1] |Xτ = x̌τ ≤ 0. (19) we require εt+1 ≤ γt (εt ). Since Eq. (22) is infeasible for εt+1 < 0, we use εt+1 ≥ 0 without loss of optimality. for ετ = ϵ and γτ (ετ ) as defined in Eq. (4). After that, we Note that γt (εt ) is well-defined in the case εt < introduce the variable ετ +1 and transform the constraint as log Pr(Xt =x̂t |Xt−1 =x̂t−1 ) and defines the feasible region for t =x̂t |Xt−1 =x̌t−1 ) follows. By the conditional independence of Yτ and Y[τ +1,n] ε Pr(X t+1 . In the other case, in contrast, the feasible εt+1 is uncongiven Xτ = xτ , Eq. (19) is equivalent to: strained since the leakage requirement becomes independent   (t) Pr Y = y[τ +1,t+1] |Xτ = x̂τ (20) from Y[t+1,n] , thus allowing for Pr (Yt+1 = ⋆) = · · · =   Pr (Yn = ⋆) = 0. (t) − q̌τ eγτ (ετ ) Pr Y = y[τ +1,t+1] |Xτ = x̌τ ≤ 0. (21) | {z } A PPENDIX D ≜eετ +1 C OMPOSITION VS . MDP PERSPECTIVE Here, we use that q̂τ = 1 necessarily. Changing the opThe design of a leakage-induced mechanism and its MDP timization variable from q̌τ to ετ +1 , we thus, have q̌τ = representation permit the following alternative views. A e−(γτ (ϵ)−ετ +1 ) . Since 0 < q̌τ ≤ 1, we require ετ +1 ≤ private leakage-induced mechanism according to Theorem 1 γτ (ετ ). Since the constraint in Eq. (21) is infeasible for can be understood as a sequential composition of the leakage. negative ετ +1 , we can set ετ +1 ≥ 0 without loss of The MDP form can be understood as a sequence of decisions: generality. whether to collect an immediate reward by revealing more The core induction goes as follows. For each t = τ + about the current instance (allow low subsequent leakage 1, . . . , n, we repeatedly apply Lemma 2 to Eq. (21) (starting ε ); or to maintain a high redaction probability in the hope t+1 from s = τ + 1 up to s = t), which produces the constraint to reveal more about future instances (allow high subsequent   (t) leakage εt+1 ). The two perspectives are illustrated in Fig. 3a q̂t Pr Yt+1 = yt+1 |Xt = x̂t and Fig. 3b, respectively.   (t) − q̌t eγt (εt ) Pr Yt+1 = yt+1 |Xt = x̌t ≤ 0. (22)

Related documents

• The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs#1341968
• Inference-Aware &amp; Privacy-Preserving Deletion in Databases#2786
• Privacy-Preserving Inclusion Lists / Zhengwei Tong, Saba Eskandarian, Kartik Nayak#1188468
• TRAP: Understanding and Mitigating Privacy Memorization in Language Models#1116624
• Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning#609724