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

Praneeth Vepakomma

cs.CRMar 24, 2026

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

Authors: Praneeth Vepakomma

Organizations: Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · Massachusetts Institute of Technology (MIT)

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: The two-layer PolyVeil protocol. Each client encodes its private bit vector as a masked doubly stochastic matrix $D_{t}$ and sends it (or the scalar $f_{t}$ ) to the aggregator, and the noise $\eta_{t}$ to a separate noise aggregator. The two aggregators do not communicate (dashed line). The server receives only the aggregate scalars $F$ and $H$ , from which it recovers $S$ exactly. The server has information-theoretic security (its view depends only on $S$ ). The aggregator faces #P-hard inference (it sees $D_{t}$ but cannot efficiently extract $M_{t}$ ).

D_{t}\;=\;\alpha^{*}\,M_{t}\;+\;\sum_{i=1}^{K_{t}}\alpha_{t,i}\,P_{t,i}.

(3)

Algorithm 1 PolyVeil

Panel of Figure 2 — Figure 2: Structure of the simulation proof for the server’s information-theoretic security (Theorem 6.2 ). Left: the real protocol execution with actual private inputs. Right: the simulator, which knows only the aggregate $S$ (not individual $\mathbf{b}_{t}$ ) and fabricates a view with identical distribution. The equivalence $\equiv$ means identical distributions, holding against computationally unbounded adversaries. The dashed box states the key structural property that makes the proof work.

Panel of Figure 3 — Figure 3: The density derivation: from the aggregator’s inference problem to the key formula. The aggregator’s MAP estimator requires evaluating $\nu(R^{\prime})$ (Steps 1–2). The density marginalizes over all $((2n)!)^{K}$ permutation tuples (Step 3), but most contribute zero — only tuples in $\mathrm{Supp}(R^{\prime})^{K}$ survive (Step 4). The resulting formula (Step 5) is a sum of polytope volumes over valid tuples, raising two questions answered in Figure 4 .

Panel of Figure 4 — Figure 4: The two branches of the #P-hardness argument, continuing from the density formula in Figure 3 . Left branch (Question a): the number of valid tuples equals the permanent of the support matrix $A(R^{\prime})$ , which counts perfect matchings in a bipartite graph; computing this is #P-complete (Valiant, 1979). Right branch (Question b): each valid tuple’s contribution is a polytope volume expressible as a mixed discriminant; computing this is #P-hard (Barvinok, 1997). Both branches converge: the density is a #P-hard number of individually #P-hard terms, with no cancellation.

Panel of Figure 5 — Figure 5: Non-interactive multi-statistic extraction. In the full two-layer protocol (Algorithm 3 ), each client transmits the masked matrix $D_{t}$ to the aggregator once. After clients go offline, the aggregator applies different extraction vectors to the stored matrices to compute multiple aggregate statistics, each recovered exactly by the server via noise cancellation. No additional client communication is required for new queries. Additive secret sharing requires a new round of client participation for each statistic.

Figure 6: Privacy–utility trade-offs in the compressed two-layer protocol (

n=100

\alpha^{*}=1/(4n)

\delta=10^{-6}

). (a) DP parameter

\varepsilon

vs. number of decoys

K_{t}

, showing a U-shaped curve with minimum

\varepsilon\approx 13

K_{t}=9

. (b) Signal-to-noise ratio vs.

K_{t}

; at the optimal

K_{t}

the SNR is

\approx 1

, meaning the signal is comparable to noise. (c) The parametric trade-off

\varepsilon

vs. SNR; better privacy (smaller

\varepsilon

) requires operating near SNR

\approx 1

, while higher SNR rapidly worsens

\varepsilon

. (d) Normalized MMSE vs.

K_{t}

; at the DP-optimal

K_{t}=9

the aggregator reduces its prior uncertainty by only

0.3\%

Secure Multi-Party Computation

Secure multi-party computation lets organizations jointly analyze private data without revealing their inputs to one another.

See all 20 papers

Differentially Private Verification of Distribution Properties
Apr 12, 2026Elbert Du, Cynthia Dwork, Pranay Tankala +1Differential Privacy Communication Complexity
Harvard University · Rutgers University
Giskard : Byzantine Robust and Private Aggregation for Large-Scale Decentralized Learning
Jun 17, 2026Ousmane Touat, César Sabater, Mohamed Maouche +1Secure Multi-Party Computation Communication-Efficient Distributed Training
INSA Lyon, LIRIS, CNRS, Villeurbanne, France · INRIA, INSA Lyon, Villeurbanne, France
TAPAS: Efficient Two-Server Asymmetric Private Aggregation Beyond Prio(+)
Mar 20, 2026Harish Karthikeyan, Antigoni PolychroniadouSecure Aggregation Secure Multi-Party Computation
JPMorgan AI Research, JPMorgan AlgoCRYPT CoE

Apr 12, 2026J/K move · Enter open · S save

Differentially Private Verification of Distribution Properties

Elbert Du, Cynthia Dwork, Pranay Tankala, Linjun Zhang

Harvard University · Rutgers University

Differential Privacy Communication Complexity

Open paper AskPDF arXiv

A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerful, knowledgeable, but untrusted prover. In this work, we initiate the study of differentially private distribution property verification. After all, if we do not trust the prover to help us with verification, why should we trust it with our sensitive sample? We map a landscape of differentially private verification of properties of distributions. In the non-private case it is known that one-round private-coin protocols can have substantially lower complexity than public-coin (AM) protocols. In contrast, the possibility for improvement in differentially private interactive proofs depends on the privacy parameter regime and model. Drawing on connections between privacy and replicability and privacy amplification techniques in the literature we show: 1. There exists a reduction from any one-round

(\varepsilon,δ)

-differentially private private-coin protocol to a differentially private AM protocol for the parameter regime

\varepsilon = O(1/\sqrt{s})

and

δ= O(1/s^{5/2})

with the same privacy and sample and communication complexities. In the local model, this is relaxed to

\varepsilon = O(1/\sqrt{\log s})

2. However, when the privacy guarantee is very relaxed (

\varepsilon \in Ω(\log s)

), private coins indeed reduce sample and communication complexities. We also obtain a computationally efficient Merlin-Arthur proof for privately testing whether samples are drawn from a product distribution and prove that its sample complexity is optimal up to a

polylog N

factor by reducing uniformity testing to independence testing with Boolean attributes and appealing to known lower bounds on sample complexity for private uniformity testing.

Abstract

Secure Multi-Party Computation

Explore similar work

Differentially Private Verification of Distribution Properties

Giskard : Byzantine Robust and Private Aggregation for Large-Scale Decentralized Learning

TAPAS: Efficient Two-Server Asymmetric Private Aggregation Beyond Prio(+)