A group of clients each holds a private bit. A server needs the sum. Nobody should learn any individual bit. The standard toolkit is heavy: public-key infrastructure, homomorphic encryption, secret sharing. Vepakomma (arXiv:2603.22808) encodes each private bit as a permutation matrix — a point in the Birkhoff polytope — and lets linear algebra do the hiding.
Note (2026-11-10): I checked the abstract (version 4; version 1 reads the same here) of the PolyVeil paper. It reports a full variant with a log-Lipschitz constant growing as n^4 K_t whose differential privacy guarantee is non-vacuous only when the private signal is undetectable, a compressed variant with non-vacuous epsilon at moderate signal-to-noise, the tension that #P-hardness needs the full matrix view while non-vacuous DP needs the scalar view, and the sentence that whether both hold simultaneously in one variant remains open. The essay states that you cannot maximize both and that this is a property of the problem; the abstract leaves it open. The essay also omits the stated benefits of no PKI, O(k) communication and exact aggregates.
The scheme, PolyVeil, comes in two variants that expose a fundamental tension. In the full variant, an aggregator sees the doubly stochastic matrices for each client. Recovering the private bit requires computing the permanent of a matrix — a #P-hard problem. The computational hardness is real and well-established. But when you ask about differential privacy guarantees, the full variant fails. The log-Lipschitz constant grows as n⁴K, and the privacy budget is vacuous at practical parameters. The high-dimensional view that makes the computation hard also makes the privacy leakage large.
The compressed variant collapses each client's contribution to a single scalar. Now the aggregator's view is low-dimensional enough for meaningful differential privacy bounds. But the computational hardness argument evaporates — there's no permanent to compute in one dimension.
The tension is structural: computational hardness requires the adversary to see the full matrix (high dimension), while information-theoretic privacy requires the adversary to see almost nothing (low dimension). You cannot simultaneously maximize both. The full polytope gives you hardness without privacy. The compressed scalar gives you privacy without hardness.
This is not a limitation of the specific protocol — it's a property of the problem. Privacy and hardness address different adversaries (computationally bounded vs. information-theoretic), and the dimensionality of the adversary's view serves one at the expense of the other.