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

1. Problem Statement

The paper addresses the Private Multi-Party Boolean Sum problem. In this scenario, $k$ clients each hold a private binary bitstream of length $n$. A server wishes to compute the total number of ones across all $kn$ bits (the grand sum $S$) without learning any individual client's bitstream, partial sums, or specific bit counts.

Existing solutions face significant trade-offs:

• Secure Multi-Party Computation (MPC): High communication/computation costs scaling with circuit complexity.
• Homomorphic Encryption (HE): High per-operation costs and reliance on public-key infrastructure.
• Differential Privacy (DP): Sacrifices accuracy for privacy by adding statistical noise, resulting in approximate rather than exact results.

The paper proposes a new paradigm called Combinatorial Privacy, which aims to achieve exact aggregation with information-theoretic security for the main server and computational security for an aggregator, without requiring public-key infrastructure.

2. Methodology: The PolyVeil Protocol

The core innovation is encoding private binary data as permutation matrices and hiding them within the Birkhoff polytope (the set of doubly stochastic matrices).

A. Mathematical Foundation

• Encoding: Each client $t$ encodes their bitstream $b_t$ into a block-diagonal permutation matrix $M_t$ of size $2n \times 2n$. Each bit $b_{t,j}$ corresponds to a $2 \times 2$ block: Identity ($I_2$) for 0 and Swap ($J_2$) for 1.
• Masking: The client creates a masked matrix $D_t$ by taking a convex combination of their private matrix $M_t$ and $K_t$ random "decoy" permutation matrices $P_{t,i}$:
  $$D_t = \alpha^* M_t + \sum_{i=1}^{K_t} \alpha_{t,i} P_{t,i}$$
  Here, $\alpha^* \in (0,1)$ is a public scaling factor, and $\sum \alpha_{t,i} = 1 - \alpha^*$. By the Birkhoff-von Neumann theorem, $D_t$ is a doubly stochastic matrix.
• Algebraic Extraction: The protocol uses specific selection vectors $w$ and $y$ such that $w^T M_t y = s_t$ (the count of ones in the bitstream). Due to linearity, the server can compute a scalar $f_t = w^T D_t y = \alpha^* s_t + \eta_t$, where $\eta_t$ is a noise term derived from the decoys.

B. The Two-Layer Architecture

The paper identifies a fatal vulnerability in naive implementations (the De-Shuffling Attack) and proposes a corrected Two-Layer Protocol:

1. Layer 1: Information-Theoretic Security (The Server)

   • The server receives only aggregate scalars: $F = \sum f_t$ and $H = \sum \eta_t$ (the latter obtained via a trusted shuffler or separate noise aggregator).
   • The server computes $S = (F - H) / \alpha^*$.
   • Security: The server's view is identically distributed for any two inputs with the same aggregate sum $S$. This provides perfect simulation-based security (statistical distance zero), meaning the server learns nothing about individual inputs, even with infinite computational power.

2. Layer 2: Computational Security (The Aggregator)

   • A separate entity (the Aggregator) receives the full masked matrices $D_t$ but not the noise values $\eta_t$.
   • To learn $s_t$, the aggregator must invert the masking: recover $M_t$ from $D_t$.
   • Security: This requires evaluating the probability density of a random doubly stochastic matrix at a specific point. The paper proves that computing this density (and thus the likelihood of a candidate permutation) is #P-hard, reducing to the computation of the Permanent of a matrix and the Mixed Discriminant. This creates a computational barrier for polynomial-time adversaries.

C. Variants

• Full Variant: The aggregator sees the full matrix $D_t$. Security relies on #P-hardness.
• Compressed Variant: Clients compute $f_t$ locally and send only the scalar to the aggregator. This reduces communication to $O(k)$ and allows for a rigorous $(\epsilon, \delta)$-Differential Privacy (DP) analysis, though the Birkhoff structure is less critical here.

3. Key Contributions

1. Combinatorial Privacy Paradigm: Introduces a new privacy model distinct from number-theoretic hardness (MPC/HE) and statistical noise (DP), leveraging the combinatorial structure of the Birkhoff polytope.
2. De-Shuffling Attack Analysis: Rigorously proves that naive protocols where the server sees identity-linked scalars and shuffled noise are insecure. The integrality constraint of bit counts allows a semi-honest server to uniquely reconstruct all individual data with probability 1.
3. Two-Layer Protocol Design: Proposes a novel architecture separating the "information" (matrices) from the "noise" (scalars) to ensure no single entity can compromise privacy.
4. Computational Hardness Proof: Demonstrates that likelihood-based inference for the aggregator is #P-hard, providing a strong computational barrier against polynomial-time attacks.
5. Finite-Sample DP Analysis: Provides explicit constants for $(\epsilon, \delta)$-DP guarantees for the aggregator in the compressed variant, analyzing the trade-off between the number of decoys, signal-to-noise ratio (SNR), and privacy parameters.

4. Results and Findings

• Correctness: The protocol outputs the exact grand sum $S$ with zero error, as the noise terms cancel out algebraically during aggregation.
• Server Security: The server achieves unconditional security. Its view is statistically indistinguishable for any two input sets yielding the same sum.
• Aggregator Security:
  • Full Protocol: The aggregator faces a #P-hard problem. While the signal is visible (detectable by an unbounded adversary), it is computationally intractable to decode efficiently.
  • Compressed Protocol: The aggregator sees only a scalar $f_t = \alpha^* s_t + \eta_t$. The paper derives a non-vacuous $(\epsilon, \delta)$-DP guarantee.
• The "Vacuous" DP Tension:
  • The paper reveals a fundamental tension:
    • To achieve non-vacuous DP (meaningful $\epsilon$), the signal-to-noise ratio must be low, making the signal undetectable. In this regime, the Birkhoff structure is irrelevant; simple Gaussian noise would suffice.
    • To utilize the #P-hardness of the Birkhoff structure, the signal must be visible (moderate $\alpha^*$). However, in this regime, the DP guarantee becomes vacuous (extremely large $\epsilon$) because the signal is detectable.
  • Conclusion: No single variant currently achieves both non-vacuous DP and #P-hardness simultaneously. The two security layers operate at different scales of the parameter $\alpha^*$.

5. Significance

• Exact Aggregation: Unlike Differential Privacy, PolyVeil provides exact results, which is crucial for applications like epidemiological surveillance or precise federated analytics where noise is unacceptable.
• No Public Key Infrastructure: The protocol does not require complex key management or public-key cryptography, relying instead on symmetric operations and a trusted shuffler.
• Communication Efficiency: The compressed variant achieves $O(k)$ communication complexity, independent of the bitstream length $n$, making it highly scalable.
• New Security Paradigm: It shifts the security foundation from "hard to factor" or "hard to learn with errors" to "hard to decompose a polytope," opening a new avenue for privacy-preserving computation based on combinatorial geometry.

6. Open Questions

The paper identifies the central open problem as closing the gap between the DP regime (where the signal is invisible) and the #P-hardness regime (where the signal is visible but hard to decode). Proving that a single protocol variant can offer both non-vacuous differential privacy and computational hardness against all polynomial-time attacks remains an unsolved challenge. Additionally, extending the security proofs to the malicious model (where clients may deviate from the protocol) is a future direction.