[2603.00381] Verifier-Bound Communication for LLM Agents: Certified Bounds on Covert Signaling

Computer Science > Cryptography and Security arXiv:2603.00381 (cs) [Submitted on 27 Feb 2026] Title:Verifier-Bound Communication for LLM Agents: Certified Bounds on Covert Signaling Authors:Om Tailor View a PDF of the paper titled Verifier-Bound Communication for LLM Agents: Certified Bounds on Covert Signaling, by Om Tailor View PDF HTML (experimental) Abstract:Colluding language-model agents can hide coordination in messages that remain policy-compliant at the surface level. We present CLBC, a protocol where generation and admission are separated: a message is admitted to transcript state only if a small verifier accepts a proof-bound envelope under a pinned predicate $\Pi$. The predicate binds policy hash, public randomness schedule, transcript chaining, latent schema constraints, canonical metadata/tool fields, and deterministic rejection codes. We show how this protocol yields an upper bound on transcript leakage in terms of latent leakage plus explicit residual channels, derive adaptive composition guarantees, and state a semantic lower bound when policy-valid alternatives remain choosable. We report extensive empirically grounded evidence: aggregate evaluation satisfies all prespecified thresholds; strict lane decoder advantage is bounded at 0.0000 with MI proxy 0.0636; adaptive-colluder stress tests remain below attacker thresholds; and baseline separation shows large gaps between reject-by-default semantics and audit-only controls. We further quantify operational ...