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