Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes
This addresses privacy-preserving multi-party computation for Boolean aggregation, though it exposes a fundamental tension between security hardness and practical DP guarantees.
The paper tackles private Boolean summation across multiple clients by introducing PolyVeil, a protocol that encodes private bits as permutation matrices in the Birkhoff polytope, achieving perfect simulation-based security for the server and #P-hard inference for the aggregator. It develops finite-sample DP analysis with explicit constants, showing non-vacuous DP guarantees only when the private signal is undetectable in the full variant, while the compressed variant achieves non-vacuous ε at moderate SNR.
We introduce PolyVeil, a protocol for private Boolean summation across $k$ clients that encodes private bits as permutation matrices in the Birkhoff polytope. A two-layer architecture gives the server perfect simulation-based security (statistical distance zero) while a separate aggregator faces \#P-hard likelihood inference via the permanent and mixed discriminant. Two variants (full and compressed) differ in what the aggregator observes. We develop a finite-sample $(\varepsilon,δ)$-DP analysis with explicit constants. In the full variant, where the aggregator sees a doubly stochastic matrix per client, the log-Lipschitz constant grows as $n^4 K_t$ and a signal-to-noise analysis shows the DP guarantee is non-vacuous only when the private signal is undetectable. In the compressed variant, where the aggregator sees a single scalar, the univariate density ratio yields non-vacuous $\varepsilon$ at moderate SNR, with the optimal decoy count balancing CLT accuracy against noise concentration. This exposes a fundamental tension. \#P-hardness requires the full matrix view (Birkhoff structure visible), while non-vacuous DP requires the scalar view (low dimensionality). Whether both hold simultaneously in one variant remains open. The protocol needs no PKI, has $O(k)$ communication, and outputs exact aggregates.