Summary
Protecting privacy when releasing sequences of integer data is tricky because each number reveals some information about previous ones. The authors study a way to release these integers with controlled privacy loss using a rational-feedback mechanism that observes all outputs. They show exact mathematical laws and hierarchies that measure privacy loss and error, and provide efficient algorithms to approximate the best tradeoffs between privacy, error, and randomness needed. Their work includes formal verification for correctness and illustrates how structured data matrices can reduce error and randomness while simpler feedback models keep fewer noise bits.
What this means in practice
- •For data privacy engineers: Design privacy mechanisms for releasing integer data with explicit error and randomness tradeoffs guaranteed by finite laws.
- •For cryptographic protocol developers: Use exact privacy bounds and hierarchies to calibrate randomized integer releases for secure multiparty computations under strict participation rules.
A theory result. No direct application yet.
Authors
Ganxuan Yang, Siqi Wen, Shuyan Yu, Jidong Yuan
Abstract
Hidden randomized rounding couples the privacy loss of successive integer releases. We study a rational-feedback mechanism under predictable signed-unit participation and full observation of every physical output. A preparation's lifetime connects three results. First, preserving complete carries until an observed echo synchronizes the worlds gives exact finite-law point compilation, with support-width exponent $3C-2$ at every fixed budget $C\ge2$. Second, releasing commitments earlier gives a monotone hierarchy whose exact endpoint, strict gaps and numerical brackets quantify calibration loss. At one fixed discrete Gaussian, a loss allowance of 0.09 requires all four commitments. Third, legal regeneration yields an unrestricted KL rate with a square-root testing remainder and a complete asymptotic frontier under joint physical-time and participation constraints. At fixed rational parameters, finite-window occupation programs approximate that frontier to error $2^{-b}$ in polynomial bit time in $b$. Verified countable-transcript semantics and independently checked finite certificates support these analyses. A matched static workload illustrates the resulting design tradeoff: a structured finite integer matrix improves error and fresh randomness, while the scalar feedback instance retains fewer noise-state and source-table bits.