Preserving ON-OFF Privacy for Past and Future Requests

Carolina Naim; Fangwei Ye; Salim El Rouayheb

arxiv: 1907.07918 · v1 · pith:2IF4HKFMnew · submitted 2019-07-18 · 💻 cs.IT · math.IT

Preserving ON-OFF Privacy for Past and Future Requests

Fangwei Ye , Carolina Naim , Salim El Rouayheb This is my paper

Pith reviewed 2026-05-24 19:49 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords ON-OFF privacyMarkov chain requestsinformation theoretic privacydownload ratefuture request windowtwo sourcesquery constructionprivacy for past and future

0 comments

The pith

Optimal ON-OFF privacy schemes exist for two sources when requests follow a Markov chain and the user knows a window of future requests.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to design query schemes that keep private which of two sources a user is accessing at every time step, even at moments when the user turns privacy protection off. Because requests are correlated over time according to a Markov chain, turning privacy off at one step can leak information about steps where privacy was on. The user is allowed to know the next ω requests in advance and uses that lookahead to build queries that maintain privacy across the entire sequence. For the two-source case the paper gives explicit constructions and proves they achieve the lowest possible download rate. A sympathetic reader would care because the result shows how to reduce communication cost by sometimes skipping privacy without creating lasting information leaks.

Core claim

When user requests to one of two sources are generated by a Markov chain and the user knows the requests in a future window of size ω, it is possible to construct ON-OFF privacy schemes that protect the identity of the requested source for all past and future times while achieving the optimal download rate.

What carries the argument

The ON-OFF privacy scheme for N=2 that uses the Markov chain request model together with the window of future requests ω to produce queries whose download rate is minimal while preserving privacy across correlated time steps.

If this is right

Privacy is guaranteed for the entire request sequence even when privacy is turned off at some steps.
The constructions achieve the information-theoretic minimum download rate for two sources.
The Markov correlation is explicitly exploited so that knowledge of future requests compensates for periods when privacy is off.
Users can selectively disable privacy without creating retrospective leaks about earlier protected requests.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The two-source constructions may serve as building blocks for larger numbers of sources if similar rate-optimal schemes can be found.
Larger window size ω is expected to improve achievable rates; the paper's optimality result could be used to quantify that improvement.
The same modeling approach could be applied to other temporally correlated access patterns such as file caching or sensor data retrieval.

Load-bearing premise

The sequence of requested sources is generated by a known Markov chain and the user has exact knowledge of the requests inside a future window of positive length ω.

What would settle it

A specific Markov chain and window size ω for which either no query scheme meets the privacy definition for all times or every scheme requires a strictly higher download rate than the paper's construction.

read the original abstract

We study the ON-OFF privacy problem. At each time, the user is interested in the latest message of one of $N$ sources. Moreover, the user is assumed to be incentivized to turn privacy ON or OFF whether he/she needs it or not. When privacy is ON, the user wants to keep private which source he/she is interested in. The challenge here is that the user's behavior is correlated over time. Therefore, the user cannot simply ignore privacy when privacy is OFF, because this may leak information about his/her behavior when privacy was ON due to correlation. We model the user's requests by a Markov chain. The goal is to design ON-OFF privacy schemes with optimal download rate that ensure privacy for past and future requests. The user is assumed to know future requests within a window of positive size $\omega$ and uses it to construct privacy-preserving queries. In this paper, we construct ON-OFF privacy schemes for $N=2$ sources and prove their optimality.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers explicit ON-OFF privacy constructions for N=2 plus an optimality proof under a Markov request model with finite lookahead.

read the letter

The main point is that this paper gives concrete schemes for ON-OFF privacy with two sources and proves they hit the optimal download rate when requests follow a Markov chain and the user knows the next ω requests ahead of time. The schemes protect which source is being queried both for past and future requests even when the user sometimes turns privacy off. The lookahead is used to plan queries that break the correlation leaks that would otherwise occur. That construction and the matching optimality proof are what is actually new here. The work sits on standard information-theoretic PIR ideas but adds the ON-OFF incentive and the bidirectional protection requirement. The Markov model is handled directly rather than assumed away, which is a reasonable way to capture the correlation. The optimality argument appears to rest on rate bounds that match the constructed schemes, so the central claim holds up on its own terms. One clear limitation is the lookahead assumption itself; if future requests are not known, the schemes do not apply. The paper also stops at N=2, leaving open whether similar rates are achievable for more sources. No circularity or hidden fitting shows up in the stated claims. This is a narrow but cleanly executed result aimed at people working on private retrieval with temporal dependence. A reader who already follows PIR or query privacy papers would get direct value from the constructions and the proof technique. It is worth sending to referees because it supplies verifiable schemes and a proof rather than just a problem definition.

Referee Report

0 major / 3 minor

Summary. The paper studies the ON-OFF privacy problem in which a user queries the latest message from one of N sources at each time step, with the sequence of requests generated by a Markov chain. Privacy is required only when the user chooses to turn it ON; the goal is to design query schemes that protect the identity of the requested source both for past and future requests while achieving optimal download rate. The user is assumed to have a finite lookahead window of size ω. For N=2 the authors construct explicit schemes and prove that the achieved rates are optimal under the stated model.

Significance. If the constructions and optimality proofs hold, the work supplies the first concrete, rate-optimal solutions for ON-OFF privacy under temporal correlation, a setting that arises in private information retrieval when user interests are not independent across time. The explicit use of a finite lookahead window ω and the separation of ON and OFF regimes are technically distinctive and could serve as a template for larger N or more general request processes.

minor comments (3)

§2: the precise definition of the privacy leakage metric for future requests (beyond the current window ω) should be stated explicitly rather than left implicit in the Markov transition probabilities.
The optimality proof for the N=2 case would benefit from a short table comparing the achieved rate to the information-theoretic lower bound derived in the paper.
Notation: the symbols used for the ON and OFF query alphabets are introduced late; moving their definition to the problem-statement section would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our work on ON-OFF privacy for Markov sources with finite lookahead. The recommendation for minor revision is noted. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents an explicit construction of ON-OFF privacy schemes for N=2 sources together with an optimality proof under the Markov request model and finite lookahead window ω. No load-bearing step reduces by definition, by fitted-parameter renaming, or by self-citation chain to the target result itself; the derivation is a self-contained mathematical construction and proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the Markov chain model for requests and the assumption of positive lookahead window ω; no free parameters or invented entities are visible in the abstract.

axioms (2)

domain assumption User requests follow a Markov chain
Stated as the model for correlated behavior over time.
domain assumption User knows future requests within a window of size ω > 0
Used to construct privacy-preserving queries.

pith-pipeline@v0.9.0 · 5701 in / 1006 out tokens · 21744 ms · 2026-05-24T19:49:41.081523+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We model the user’s requests by a Markov chain... π(xt) := min_ut p(xt|ut)... 1/Rt ≥ 2 − ∑ xt π(xt)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The query Qt is encoded from Xt, Ut and St... w(qt|xt,ut) = π(xt)/p(xt|ut) or 1−π(xt)/p(xt|ut)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.