This paper develops the composition theory for adversarial aggregation channels (AACs) — the framework that unifies impossibility theorems across social choice, computability, mechanism design, and quantum information under a single conservation identity. While prior work treats individual AAC channels, this paper asks what happens when such channels compose, providing the AAC analogue of Shannon's classical composition calculus for cascade, parallel, and network topologies. For separable adversaries, four main results are established. The Cascade Composition Theorem decomposes total adversarial capacity across a series composition as A_casc = A₁ + A_{2|1} − L, where L ≥ 0 is a data-processing loss arising from the Dobrushin contraction coefficient, and the cascade aliasing set is shown to be monotone non-decreasing — cascading can only increase impossibility. The Parallel Composition Theorem establishes a maximum law for robust discriminability under independent observation. The Cascade Conservation Identity shows that the enrichment–corruption duality telescopes through cascade stages with an inter-stage adversarial synergy correction term. The Cascade Second Law proves that under the institutional Markov property, Shannon entropy of the true state is non-decreasing through cascade stages, with strict increase wherever self-referential closure occurs. The paper then extends the theory to correlated adversaries — multi-stage actors who can communicate and coordinate across institutional stages. A communication-constrained adversary model is introduced in which inter-stage correlation is mediated by a shared signal of bounded entropy R, interpolating between the separable and fully collusive regimes. The Correlated Adversary Cascade Theorem shows that correlated randomized adversaries can destroy discriminability that no single deterministic strategy can, via a cancellation mechanism impossible under independent randomization. The collusion premium Π(R) ≥ 0 measures the additional adversarial capacity gained from inter-stage communication and is bounded above by min{R, D^rob_casc}. The collusion-distortion function — the adversarial analogue of Shannon's rate-distortion function — is introduced with a Lagrangian dual shown to be automatically convex, and strong duality is established away from finitely many phase-transition rates. The Binary Degeneracy Theorem proves that adversarial cancellation is a strictly higher-dimensional phenomenon: the collusion premium vanishes identically for binary signal spaces and is generically positive for |S| ≥ 3. For J-stage cascades, a multipartite collusion decomposition via inclusion-exclusion is derived with three-body corrections that are non-zero only when the adversarial communication graph contains cycles; when the topology is a tree, the pairwise decomposition is exact. This connects the AAC framework to the game-theoretic literature on communication equilibria (Forges, Barany, Myerson), with the collusion premium providing a quantitative bridge between mechanism design and information-theoretic impossibility. All results are verified against Shannon's classical composition theory as a consistency check, reducing to standard results in the non-adversarial limit.
This paper develops the composition theory for adversarial aggregation channels (AACs) — the framework that unifies impossibility theorems across social choice, computability, mechanism design, and quantum information under a single conservation identity. While prior work treats individual AAC channels, this paper asks what happens when such channels compose, providing the AAC analogue of Shannon's classical composition calculus for cascade, parallel, and network topologies. For separable adversaries, four main results are established. The Cascade Composition Theorem decomposes total adversarial capacity across a series composition as A_casc = A₁ + A_{2|1} − L, where L ≥ 0 is a data-processing loss arising from the Dobrushin contraction coefficient, and the cascade aliasing set is shown to be monotone non-decreasing — cascading can only increase impossibility. The Parallel Composition Theorem establishes a maximum law for robust discriminability under independent observation. The Cascade Conservation Identity shows that the enrichment–corruption duality telescopes through cascade stages with an inter-stage adversarial synergy correction term. The Cascade Second Law proves that under the institutional Markov property, Shannon entropy of the true state is non-decreasing through cascade stages, with strict increase wherever self-referential closure occurs. The paper then extends the theory to correlated adversaries — multi-stage actors who can communicate and coordinate across institutional stages. A communication-constrained adversary model is introduced in which inter-stage correlation is mediated by a shared signal of bounded entropy R, interpolating between the separable and fully collusive regimes. The Correlated Adversary Cascade Theorem shows that correlated randomized adversaries can destroy discriminability that no single deterministic strategy can, via a cancellation mechanism impossible under independent randomization. The collusion premium Π(R) ≥ 0 measures the additional adversarial capacity gained from inter-stage communication and is bounded above by min{R, D^rob_casc}. The collusion-distortion function — the adversarial analogue of Shannon's rate-distortion function — is introduced with a Lagrangian dual shown to be automatically convex, and strong duality is established away from finitely many phase-transition rates. The Binary Degeneracy Theorem proves that adversarial cancellation is a strictly higher-dimensional phenomenon: the collusion premium vanishes identically for binary signal spaces and is generically positive for |S| ≥ 3. For J-stage cascades, a multipartite collusion decomposition via inclusion-exclusion is derived with three-body corrections that are non-zero only when the adversarial communication graph contains cycles; when the topology is a tree, the pairwise decomposition is exact. This connects the AAC framework to the game-theoretic literature on communication equilibria (Forges, Barany, Myerson), with the collusion premium providing a quantitative bridge between mechanism design and information-theoretic impossibility. All results are verified against Shannon's classical composition theory as a consistency check, reducing to standard results in the non-adversarial limit.
This paper proves that the Adversarial Aggregation Channel (AAC) conservation identity Δ = 𝒜_V + D^rob_V is the unique quantitative extension of Arrow's decisive-coalition framework. The result is established in two stages. Stage 1 (Classical Forcing): Five axioms — Operational Discriminability, Adversarial Corruption, Data Processing, Exact Bookkeeping, and Boolean Recovery — jointly determine the AAC. A Categorical Uniqueness Theorem shows that the two-term decomposition is the unique exact decomposition whose terms are natural transformations in the category of adversarial channels (AdChan); any finer decomposition requires a non-natural selection rule on the adversary's action space. Stage 2 (Quantum Forcing): The five axioms extend to quantum channels by replacing total variation with trace distance (forced by the Helstrom bound) and classical adversaries with CPTP maps. The quantum conservation identity is categorically forced by the same argument; the no-cloning theorem is derived as the quantum Self-Referential Closure (SRC) condition. The full forcing chain is: Arrow → qualitative AAC → quantitative AAC → quantum AAC → no-cloning as SRC. The five axioms are independent. The categorical uniqueness theorem and quantum forcing are new results.
We introduce the notion of empirical coordination for quantum correlations. Quantum mechanics enables the calculation of probabilities for experimental outcomes, emphasizing statistical averages rather than detailed descriptions of individual events. Empirical coordination is thus a natural framework for quantum systems. Focusing on the cascade network, the optimal coordination rates are established, indicating the minimal resources required to simulate, on average, a quantum state. As we consider a network with classical communication links, superposition cannot be maintained, hence the quantum correlations are separable (i.e., a convex combination of product states). This precludes entanglement. Providing the users with shared randomness, before communication begins, does not affect the optimal rates for empirical coordination. We begin with a rate characterization for a basic two-node network, and then generalize to a cascade network. The special case of a network with an isolated node is considered as well. The results can be further generalized to other networks as our analysis includes a generic achievability scheme. The optimal rate formula involves optimization over a collection of state extensions. This is a unique feature of the quantum setting, as the classical parallel does not include optimization. As demonstrated through examples, the performance depends heavily on the choice of decomposition. We further discuss the consequences of our results for quantum cooperative games.
Collusion-free (CF) and collusion-preserving (CP) protocols enrich the standard security offered by multi-party computation (MPC), to tackle settings where subliminal communication is undesirable. However, all existing solutions make arguably unrealistic assumptions on setups, such as physical presence of the parties, access to physical envelopes, or extreme isolation, where the only means of communication is a star-topology network. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic scenarios. Motivated also by the increasing interest in using hardware tokens for cryptographic applications, in this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the state of the art, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving (in short, CP) secure as long as no parties abort. In the case of an aborting adversary, our protocol still achieves standard (G)UC security with identifiable (and unanimous) abort. Leveraging the above identifiability property, we augment our protocol with a penalization scheme which ensures that it is not profitable to abort, thereby obtaining CP security against incentive-driven attackers. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest. Similar to existing CP/CF solutions, our protocol preserves, as a fallback, security against monolithic adversaries, even when the setup (i.e., the hardware tokens) is compromised or corrupted. In addition, our fallback solution achieves identifiable and unanimous abort, which we prove are impossible in previous CP solutions.
The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. To address this challenge, we investigate three topics in our study. In the first part, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Owing to this result, in the second part, we study algorithms for non-convex optimization of a class of functions we call Lipschitz-like functions. This class includes entropic quantities, and hence these results may be of independent interest in information theory. Subsequently, in the third part, we show that one can use these techniques to compute the sum capacity of an arbitrary two-sender MACs to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.
The classical capacity of a noisy optical channel is the maximum rate at which information can be transmitted reliably, given a constraint on the mean input energy. For the ubiquitous bosonic Gaussian channels, which include standard models of loss and noise in fibre and free-space optical links, determining this rate requires addressing whether entanglement between channel uses or non-Gaussian signals can outperform Gaussian encodings. More precisely, the question is whether the energy-constrained Holevo information is additive across arbitrarily many channel uses and coincides with its Gaussian counterpart. We answer these fundamental questions in the affirmative for every single-mode bosonic Gaussian channel at every input energy. Namely, we prove that independently prepared Gaussian states with Gaussian-distributed random displacements achieve the capacity, including in the low-energy regime where squeezing the signals competes with encoding information in their displacement. Our proof connects an entanglement inequality to a sharp, additive lower bound on output entropy. We then characterise communication above capacity: under a strict total photon-number cutoff, the probability of correct decoding decreases exponentially with the number of channel uses, and we derive explicit bounds on the decay exponent. When only the mean photon number is constrained, a simple energy-rescaling formula determines exactly the entire asymptotic rate--error trade-off: the capacity at mean photon number N and allowed average decoding error ε equals the vanishing-error capacity at mean photon number N/(1−ε). Together, these results identify the ultimate limits of classical communication for some of the most fundamental models of optical communication.
This paper asks a question the quantum information literature has not addressed: what happens to the rest of the world when quantum coordination activates? When two parties coordinate using shared entanglement, the standard analysis stops at their joint measurement outcomes. This paper goes further — it formalizes what a third-party observer, one completely excluded from the quantum state, experiences in the downstream environment. The answer: environmental consequences that no classical physics can explain, and in the strongest case, consequences that are identical to what the observer would experience if the parties had secretly communicated. The paper introduces the excluded observer interface model, defines environmental divergence as an operational measure, and proves a leakage-performance separation theorem: quantum coordination simultaneously exceeds the classical performance ceiling while leaking zero information about local conditions to the excluded observer — breaking the classical Pareto frontier between coordination performance and operational security. Demonstrated across the CHSH game (Δ_TV = 0.104, distinguishable from communication) and the Mermin-Peres Magic Square game (Δ_TV = 0.111, indistinguishable from communication, ε = 0). This is Paper 1 in a four-paper series: Paper 1 (this paper) — Existence. Proves the excluded observer's environment diverges from classical baselines. Paper 2 — Structure. Extends the framework into complex-valued information geometry, demonstrating that the excluded observer's information space acquires a CP¹ structure and that complex phase tracking becomes operationally necessary for predictive consistency in multi-outcome environments. Zenodo DOI 10.5281/zenodo.18944106. Paper 3 — Detection. Shifts the observer partition inward, deriving a sequential detection architecture for the coordinating party to detect marginal bias using only local statistics. Proves the protocol is information-theoretically optimal (saturates the Shannon capacity bound). Zenodo DOI 10.5281/zenodo.19056735. Paper 4 — Action. Derives the organizational decision-theoretic consequences: optimal hierarchy depth as a computable function of adversary coordination quality, decision window, and stakes magnitude. The result generalizes beyond quantum coordination to any scenario with external time pressure, communication friction, and unforeseen disruption. Zenodo DOI 10.5281/zenodo.19057065.