Abstract
Publishing the opening and closing counts of a conserved inventory reveals the aggregate number of withdrawals. We study a mechanism that protects individual withdrawals by carrying out additional ones while keeping every published count exact. In a two-tray catering model, a steward replenishes the service tray and serves doughnuts from reserve to a separate standby roster. We give a capped additive mechanism that minimizes both the required roster and each upper tail of the number of standby servings. At and , if all twelve employees decline seconds, the steward must serve all twelve standby diners with probability at least 0.995905 at the minimum reserve capacity. Sampling the indicator of actual standby service at rate raises the exact failure parameter of the mechanism to .
CCS Concepts• Security and privacy → Privacy-preserving protocols.
Keywordsdifferential privacy, cover traffic, count queries, inventory reconciliation
Reference Format:
Lenora S. Valech. 2026. Cover Traffic Under Exact Stock Reconciliation. Preprint, November 20, 2026.
1Introduction
An inventory report can disclose a private action even if the report contains no individual records. In a closed stock, anyone who knows the opening and closing counts can determine the number of withdrawals. At a catered office handoff, that number can disclose who took a second serving. Refilling the serving tray moves stock between compartments. An auditor who counts both compartments sees the same withdrawals as before.
We study a service in which the first group has already received one doughnut per person. It is then offered seconds in private. The office requires a full tray for the next group and an exact public reconciliation of the service and reserve trays. Every doughnut missing at reconciliation must have been served. The steward can meet both conditions by serving reserve doughnuts to a separate group of standby diners. A standby serving and an employee’s second serving then have the same effect on the aggregate account. The amount of cover needed is greatest when the first group declines seconds.
The mechanism is related to fixed-size cover traffic. Here the items carrying cover are charged to the same physical stock as the genuine traffic. The office must have stock to restore the serving tray and people to take the additional servings. We derive separate lower bounds on these two resources, give a mechanism that attains both, and calculate the effect of inspecting the standby serving record. All released stock counts remain exact.
2Setting
2.1Service and reconciliation
A batch starts with doughnuts in a service tray and in a reserve. Each of eligible employees makes a private choice about taking one additional doughnut from the service tray. The roster and both opening counts are public. The steward observes the choices, and is the number of second servings. We assume a separate group of standby diners. Each of them is available for one serving from the reserve during the reconciliation interval. Treating a serving as indivisible rules out counting a shared doughnut as more than one transaction.
The steward replaces exactly units in the service tray and sends reserve units to standby diners. The office publishes the closing counts of both trays. They are verified by direct inspection. Write for the closing reserve count and for the total number of servings made during the batch. Then
The public view is equivalent to . Feasibility requires and . A full service tray is required on every input. This requires even when the office has no privacy requirement. Any additional reserve above is permitted.
Figure 1 shows a batch with four second servings and five standby servings. The count of nine missing doughnuts agrees with both the closing inventory and the actual number served.
2.2Privacy objective
Two inputs are adjacent if one employee changes their second-serving choice. We require -differential privacy for the public view [4, 5]. Set , with and . For every integer event and ordered pair of adjacent inputs ,
The steward and the batch interval are trusted. The audit releases stock counts and the fixed roster size. Which standby diners are served, when they are served, and the resulting serving receipts are outside the initial view. We analyze an audit of those receipts in Section 5.
We assess the number of standby servings and the minimum standby roster that supports the guarantee. We compare mechanisms at every input, without a distribution over employee choices. An additional reserve doughnut and an additional standby diner are separate resources. A surplus in one cannot make up a shortage in the other.
3Minimum Cover Requirement
3.1A bound on published totals
Fix an input with . Change refusals into second servings one at a time until the true number of seconds reaches . The event has probability zero at that endpoint because . Let and be the probability of this event at two successive inputs along the path, starting from the lower true count. Privacy gives . Applying privacy to the complement in the reverse direction gives . Define
Since is nondecreasing, iterating backwards gives . The argument accommodates mechanisms that use the full employee vector. Thresholds below have probability zero by conservation. For we use the upper bound 1, which also applies to offices with additional reserve stock.
3.2A matching mechanism
For , is the cumulative distribution function (CDF) of a nonnegative integer . Each iteration increases by at least unless it ends at 1. Draw independently of the choices and set
For , set . The steward samples the target before serving the standby group.
Theorem 1 (Minimum standby service). For any fixed employee input, attains the largest feasible probability of at every threshold under -privacy and with unconstrained standby staffing. Consequently minimizes every upper-tail probability of the standby serving count and the expected value of any nondecreasing loss on that count.
Proof. First suppose . Write for , taking zero mass outside the support. The successive ratios for with are nonincreasing. Each ratio is a secant slope of the concave map on . The intervals are ordered, and the ratio just beyond the last positive mass is zero.
Let be the law of and that of . The terms are positive only on a lower interval, by the ratio ordering and the zero left endpoint of . The reverse differences are positive only on an upper interval. The maximal event differences are therefore attained by a prefix and a suffix. For a prefix ending at , the difference is . For a suffix beginning at , the reverse difference is . The recurrence supplies both inequalities. Thus the additive law is private before clipping, and clipping at preserves privacy.
For , the resulting CDF equals . It is one at and above , so it attains all the bounds. If , the recurrence stays at zero. The constant output is private and again attains all bounds.∎
The implementation needs at most CDF terms. A uniform draw on selects the first CDF term above it, with remaining probability assigned to . For rational and , the finite set of terms can be represented exactly using a common integer denominator.
3.3Staffing and stock
Let be the least index with , or infinity when . Among offices with , the minimum standby roster is
The mechanism suffices since and . For necessity consider a batch in which all employees decline. If , then always, in contradiction to . Thus a larger reserve cannot reduce staffing. Conversely, a larger standby group cannot make up a reserve shortage when all employees take seconds. For the unique feasible private total of smallest magnitude is , and the standby service must supply one serving for each refusal.
At and , . With , while the first branch of governs the update, . That branch ceases to govern when the preceding CDF exceeds . For , and the first branch still governs . If every employee declines seconds, at least of public reconciliations must record 12 or more servings. With the minimum stock, this is exactly the probability that all twelve standby diners must be served.
4Finite Evaluation
4.1Baselines and checks
We used three baselines. Fixed total serves enough standby diners to bring the public total to in every batch. Uniform uses the optimal law at . For the reciprocal integer values of considered here, its pre-clipping noise is uniform on the integers 0 through . Shifted geometric adapts a standard conservative count release [2]. The truncated law with center gives mass proportional to for . Its exact before clipping is the endpoint mass. We mix the two adjacent integer centers whose endpoint masses bracket the target . The resulting average of the two privacy bounds equals the requested budget. This avoids a stricter baseline arising solely from integer rounding of .
For each tray and mechanism we enumerated the release distribution at all true counts. For neighboring laws , the largest forward privacy difference is . We computed both directions. Separately, we enumerated every subset of possible outputs for tray sizes 1 through 7, with and . The evaluation uses exact rational arithmetic and has no sampling error.
4.2Staffing in the absence of demand
Table 1 reports the workload on a batch in which all employees decline. With 12 employees and , the optimum saves 0.0082 expected servings relative to a fixed total, and the roster stays at 12. Increasing the tray to 24 at the same privacy setting leaves a requirement for 24 standby diners even though only 18.41 are served in expectation. The budget-matched geometric mixture matches the optimum at the tighter setting to the precision shown. At the optimal recurrence uses about 0.0049 fewer servings.
| Capacity | Fixed total | Uniform | Shifted geometric | Optimal | |
|---|---|---|---|---|---|
| 12 | 12.0000 / 12 | 10.7812 / 12 | 4.5508 / 10 | 4.5459 / 10 | |
| 12 | 12.0000 / 12 | 11.9999 / 12 | 11.9918 / 12 | 11.9918 / 12 | |
| 24 | 24.0000 / 24 | 19.3125 / 24 | 4.5508 / 10 | 4.5459 / 10 | |
| 24 | 24.0000 / 24 | 23.9997 / 24 | 18.4123 / 24 | 18.4123 / 24 | |
| 36 | 36.0000 / 36 | 25.5938 / 36 | 4.5508 / 10 | 4.5459 / 10 | |
| 36 | 36.0000 / 36 | 35.9993 / 36 | 18.4271 / 36 | 18.4271 / 36 |
Figure 2 gives the probability of accounting for 24 servings as the true number of second servings varies. Under the tighter budget, that total is reported in 1.49% of completely abstinent batches. When 23 employees take seconds, the office serves a standby diner with probability to avoid recording 23. The number served on standby can differ across these two cases even when both public audits agree.
Figure 3 shows how the minimum roster changes with and . At and , tightening from to increases the required roster from 14 to 22. At , the standby roster reaches the size of the employee roster. The procurement requirement stays at 36 throughout.
5Auditing the Standby Record
With the minimum reserve , an accurate public statement of whether any standby diner was served destroys privacy. At the public pair consisting of and the standby indicator is always . At the only feasible pairs are and . The event then requires . The same argument holds at any reserve capacity for the optimal mechanism, which always has .
An office might disclose the standby indicator in a random sample of batches. Suppose it independently chooses each batch with probability and publishes a separate erasure symbol in unsampled batches. Under the optimal mechanism the exact new failure parameter at the same is
For the upper bound, restrict an arbitrary event to sampled and unsampled outcomes. The sampled branch has a maximal privacy difference of at most 1, and the unsampled branch inherits . For equality, order the adjacent pair from to . Include all sampled observations possible at , which are disjoint from those at , and the unsampled observation , which occurs with probability only at the first input. The calculation also holds when . We verified it on the small-tray grid above at by enumerating the joint observations.
Even a one-percent sampling rate therefore imposes a failure parameter of at least 0.01. Schedules that publish the size of the fixed standby roster are compatible with the original guarantee. Payroll entries that distinguish actual standby service from attendance are a different release. Keeping the closing counts exact leaves no uncertainty about total consumption to absorb that disclosure.
6Related Work and Scope
Fixed-rate anonymous communication uses dummy transmissions to make observed traffic less dependent on actual demand. Loopix uses cover packets at clients and service providers [7]. Our setting has a fixed interval and a public volume rather than a packet trace. Generating the volume requires both stock and a recipient for each cover serving. The signed count mechanisms in [6] allow outputs on either side of the truth, whereas an audited serving total cannot fall below the number already served. Case, Honaker, and Movahedi study nonnegative noise for conservative releases [2]. Xiao et al. treat positive bounded noise subject to general moment and support constraints [8]. Our threshold bound starts at the neighboring count where the event first becomes physically impossible. Its binary-event inequalities also arise in differentially private testing [1, 3].
The evaluation concerns counts and staffing in a single batch. It does not model diner availability or cover-service duration. The private interval must be long enough for any staffing realization, and an observer who sees its duration has a larger transcript unless the duration is fixed. Multiple batches involving the same employee require a joint privacy analysis. Stock reconciliation certifies that the servings occurred. Whether the standby roster actually reports for duty is an operational assumption.
7Conclusion
A truthful, public inventory can conceal individual demand if part of the demand is assigned by the mechanism. In the minimum-stock office with pure differential privacy, declining a second serving sends one doughnut to the standby roster. The public account records the same number of servings on a day when every employee declines as on a day when every employee accepts.
References
- [1]Jordan Awan and Aleksandra Slavković. 2018. Differentially Private Uniformly Most Powerful Tests for Binomial Data. Advances in Neural Information Processing Systems 31. https://proceedings.neurips.cc/paper/2018/hash/296472c9542ad4d4788d543508116cbc-Abstract.html
- [2]Benjamin M. Case, James Honaker, and Mahnush Movahedi. 2021. The Privacy-preserving Padding Problem: Non-negative Mechanisms for Conservative Answers with Differential Privacy. arXiv:2110.08177.
- [3]Jinshuo Dong, Aaron Roth, and Weijie J. Su. 2022. Gaussian Differential Privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology 84 , 1 (2022), 3–37. https://doi.org/10.1111/rssb.12454
- [4]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Theory of Cryptography Conference. 265–284. https://doi.org/10.1007/11681878_14
- [5]Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science 9 , 3–4 (2014), 211–407. https://doi.org/10.1561/0400000042
- [6]Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. 2012. Universally Utility-Maximizing Privacy Mechanisms. SIAM Journal on Computing 41 , 6 (2012), 1673–1693. https://doi.org/10.1137/09076828X
- [7]Ania M. Piotrowska, Jamie Hayes, Tariq Elahi, Sebastian Meiser, and George Danezis. 2017. The Loopix Anonymity System. In 26th USENIX Security Symposium. 1199–1216.
- [8]Hanshen Xiao, Jun Wan, Elaine Shi, and Srinivas Devadas. 2025. One-Sided Bounded Noise: Theory, Optimization Algorithms and Applications. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 4214–4228. https://doi.org/10.1145/3719027.3765110