# Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

arXiv: https://arxiv.org/abs/2603.22808 · HTML: https://mlsanity.com/paper/2603.22808/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 21 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Builds on (most cited first, 3 of 3)

- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [InstaHide: Instance-hiding Schemes for Private Distributed Learning](https://mlsanity.com/paper/2010.02772/) (2020)
- [The Privacy Blanket of the Shuffle Model](https://mlsanity.com/paper/1903.02837/) (2019)

## Abstract (arXiv)

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 n4 Kt 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.