CS Paper Radar

Trust a Few: The Weakest Assumptions a Protocol Needs

Bhumika Mittal, Aalok Thakkar

cs.CR ·submitted 2026-10-07 09:25 UTC · v2
unusual

Abstract

Protocol verifiers check whether a protocol meets a security goal under stated trust assumptions, such as that a key is never leaked, a value is fresh, or a channel is authentic. They do not say which of those assumptions the goal needs. Rowe, Guttman and Liskov asked for the weakest assumptions under which a protocol achieves a goal and left the question open. We answer it for assumptions about keys, values and channels. Call a run that violates the goal an attack, and the assumptions that would rule it out its stopping set. The least a protocol must trust to meet a goal is exactly the set of minimal ways to stop all of its minimal attacks. Several such sets may exist. The answer becomes unique once either/or assumptions are allowed, and it is a single set exactly when every minimal attack is stopped by a single assumption. A Galois connection between assumptions and goals explains why: a goal may end in "or", but its hypothesis may not. The same structure gives the trust needed by a conjunction of goals and an exact condition under which composed protocols need no extra trust. To compute the answer, a loop asks a verifier whether a candidate suffices, records what stops each attack it reports, and recomputes the candidates. Deciding whether some trust of at most k assumptions suffices is NP-hard. With a bounded analyser of our own and with CPSA, the loop finds the weakest trust for 18 goals over ten protocols and their variants, and on each it agrees with evaluating every trust using the same verifier. The answers include an assumption that our model of the adopted fix of Kerberos PKINIT states but the client's authentication of the server does not need, and channel assumptions under which Needham-Schroeder meets its goal in a bounded model.

Closest papers

Nearest neighbours by meaning across the whole index.

Defining Purpose-Limited Secrets

cs.CR ·2026-10-07 ·Bhumika Mittal, Aalok Thakkar
similarity 0.52
Abstract

A cryptographic secret is issued for a purpose but grants a capability, and the capability is usually larger. Deployed systems state the purpose in policy and enforce only the capability. We make the purpose a property of the secret. A mechanism sees operations, not reasons, so a scheme enforces an admissible set $A(P)$ of operations that stands in for a declared intended use $I$; whether $I$ captures the human purpose is a modeling obligation that marks where policy takes over. Against the same $I$ we define three regimes: under confinement an operation outside the intended use is infeasible, under mediation a trusted component refuses it, and under accountability use beyond a stated bound is possible but attributed to the holder. The confinement games, for unpredictability and indistinguishability, coincide with the key-query forms of functional-signature unforgeability and constrained-PRF pseudorandomness and correspond to simulation-secure functional encryption within its feasibility boundary; stated against $I$, they also register a predicate that permits too much. A payment token uses all three regimes on one secret: it pays one capped charge at one merchant, can be narrowed but not widened, is checked by the merchant, and identifies the withdrawing account if spent twice. Attenuation unforgeability reduces to unforgeable signatures and a collision-resistant hash without random oracles; traceability and non-frameability hold under discrete log and unforgeable signatures in the random-oracle model. We present this framework as a common specification against which existing primitives are stated and compared.

0.25

Trust-Gated Capability Control: Breaking the Trust-Vulnerability Paradox in Multi-Agent LLM Systems

cs.GT cs.MA ·2026-10-04 ·Mehedi Hasan Nipu, Chinmoy Mitra, Tarannum Ahmed Nowshin, Israt Moyeen Noumi
theory similarity 0.51
Abstract

Layered trust models for multi-agent LLM systems remain largely conceptual: they name which dimensions of trust matter but not how layers combine, how their importance is set at runtime, or how trust should govern agent actions. This gap matters because higher inter-agent trust raises task success while also enlarging exposure to exploitation, a tension formalized as the Trust-Vulnerability Paradox. We make a five-layer trust stack operational through three contributions. First, a cross-layer synergy operator propagates prerequisite-layer deficits into de- pendent layers, feeding a generalized-mean composite trust that recovers the weakest-link rule as a limiting case, with provable bounds. Second, per-layer importance weights are grounded in observed failures via a no-regret online estimator that tracks which layer is currently most responsible for harm. Third, Trust- Gated Capability Control issues short-lived, revocable capability grants only when composite trust and the relevant prerequisite layers clear capability-specific thresholds. We prove this mechanism breaks the paradox: a stealthy compromise that inflates behavioral trust while degrading a prerequisite layer cannot escalate privilege, and give a closed-form, provably conservative trust fixed point with a bounded-latency revocation guarantee. A numerical study with a sleeper adversary confirms the predictions: composite-trust bounds hold across 20,000 random draws, the analytic fixed point matches simulation within 0.007, and a compromised prerequisite layer triggers automatic revocation within a few interactions.

0.12

Who Can Make the Action Happen? An Authority-Decomposition Framework for High-Risk Automated Systems

cs.CR ·2026-08-19 ·Mengting Wu, Lin Wang, Yong Zhang
similarity 0.51
Abstract · 62 pages, 4 figures; includes an ancillary technical supplement. Non-peer-reviewed preprint for scholarly feedback

High-risk automated systems distribute control across services, credentials, protected components, and lifecycle mechanisms. Labels such as authorized, approved, privileged, or protected therefore do not answer a basic causal question: which actors can actually make a consequential action occur? This paper provides an action-relative method for deriving which trust-domain coalitions are sufficient to cause protected execution, defined as the occurrence of a designated protected state transition. The framework models components, powers, resources, boundaries, and alternative realization structures; includes update, recovery, override, disablement, and alternative invocation; and separates causal control over execution from control over the authoritative account of an operation. It derives inclusion-minimal sufficient coalitions and tests whether claimed execution boundaries remain independent of designated upstream domains. Cross-domain analytical cases illustrate the method. In a split-control, release-intended, open-state, source-bounded Havenlon protocol model, the ordinary witness requires five trust domains, while certificate replacement yields a three-domain inclusion-minimal known requirement set among source-enumerated protocol witnesses; the Linux domain remains insufficient for the complete transition. Deployed global non-bypassability and boundary-bound veto coverage remain unresolved. The framework is a conceptual and analytical tool. It does not certify implementations, establish deployment security, guarantee complete discovery of hidden powers, or define evidence-verification semantics.

0.24

Self-evolving network verifiers

cs.NI cs.AI ·2026-08-11 ·Ioannis Protogeros, Tibor Schneider, Laurent Vanbever
position similarity 0.51
Abstract · 8 pages, 5 figures

Symbolic network verifiers can reason about correctness across vast spaces of routing inputs and failures, but only for the protocols and features an expert has encoded by hand. Creating and maintaining a faithful model of the control plane is both difficult and never-ending, since no written source specifies perfectly what a network does: vendor implementations deviate from the RFCs, and behaviour shifts with releases. The burden of constant upkeep ultimately keeps verification out of many networks that need it. We argue that the model should instead evolve automatically to faithfully capture the actual network behaviour. To achieve that, we leverage the only source that specifies it unambiguously: the router software itself. In a counterexample-guided loop, a coding agent proposes extensions to the verifier's symbolic encoding, while a trusted oracle (e.g., emulated routers) supplies the ground-truth routing state. The agent iteratively refines the network model using each disagreement with the oracle. As early evidence, a prototype of this system taught a 3,000-line SMT-based verifier three features it did not support: OSPF areas, BGP route reflection, and L3VPN over EVPN, converging autonomously on models that match the oracle, even noticing vendor-specific behaviour. Automating model growth shifts the hard problem from writing verification systems to systematically testing them; we propose a research agenda for trusting and harnessing automatically evolved verifiers.

0.10

Verification with Transfer: Exact Information Frontiers and Their Price in Calls

cs.LG cs.CRcs.ITstat.ML ·2026-10-08 ·Hazar Yueksel
similarity 0.50
Abstract · 46 pages, of which 8 pages main text. The Lean 4 formalization is in the ancillary files

A verifier that accepts or rejects whole answers reveals little: under a flat prior over $k$-bit answers, zero error needs $2^k-1$ verifications. The usual remedy is to solve related source tasks, either all first, as a curriculum does, or interleaved with verification. We price this remedy in information and in calls. With an exact verifier, the least causal information that any interleaving of source calls and $n$ verifications needs to succeed with probability $s$ is a list rate-distortion function, attained by one observation before any verification. It lower-bounds the expected number of binary source calls, which designed sources meet within $1+\log_25$ calls for unique answers and within a logarithmic term in general, where no additive constant suffices. With an exact verifier and fixed sources, moving every call before the first verification preserves all hard caps on calls, although interleaving can save unboundedly many expected calls; under a noisy verifier, source-first protocols can lose unbounded factors in information and in error. For linear banks over $\mathbb{F}_2$, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time $2^{O(h^2)}\operatorname{poly}(J,k+h)$ for $J$ sources and nuisance dimension $h$. In these banks, for zero error under a hard cap, the calls beyond the rounded-up information price are exactly those spent on nuisance. Every numbered result apart from two clauses about the planner is machine-checked in Lean 4, assuming two published results. Used as a ruler, the frontier shows a small transformer using all delivered bits at latent dimension $5$ and none at $11$ within fixed training budgets; in a test with predictions recorded before training, low XOR degree of the target bits did not suffice for their use.

0.22

Rational Dolev--Yao Attackers: Decidable Incentive-Aware Verification of Security Protocols in Strategic Logic

cs.CR cs.GT ·2026-08-24 ·Ioana Boureanu, R. Ramanujam
theory similarity 0.50
Abstract

Symbolic protocol verification models the network attacker as a Dolev--Yao (DY) intruder, which does everything its knowledge permits, whether or not it serves any purpose; real adversaries instead maximise utility, attacking only when the payoff is positive. We introduce a rational Dolev--Yao attacker, a DY intruder whose actions carry costs and whose security-violating goals carry rewards, and call a protocol rationally secure when no intruder strategy achieves a violation with strictly positive utility, expressed in a weighted fragment of ATL (WATL). We prove this decidable for a bounded rational DY intruder over a finite cost-annotated concurrent game structure, characterise its complexity, and show it strictly refines DY security: some protocols are DY-insecure yet rationally secure, separated by a computable threshold. We illustrate the framework on two contrasting use-cases: an authenticated payment under session uncertainty, where a rational intruder must strategise across indistinguishable sessions and its imperfect information strictly raises the attack cost a designer must price against; and ThreeBallot, a cryptography-free scheme where we pinpoint the bribe-to-benefit ratio below which no rational coercer attacks.

0.16

TrustShiftProbe: Characterizing, Benchmarking, and Defending Staged Trust Attacks on MCP Servers

cs.CR cs.AI ·2026-08-24 ·Mehrdad Rostamzadeh, Sidhant Narula, Mohammad Ghasemigol, Daniel Takabi
similarity 0.50
Abstract

The Model Context Protocol (MCP) has emerged as the standard layer connecting Large Language Model agents to external tool backends. This openness introduces a severe server-side threat we term TrustShift: a compromised MCP server behaves benignly during an initial conditioning phase, building operational reliance and suppressing agent skepticism, before switching to an adversarial payload once an interaction threshold is reached. The evasion is temporal, not syntactic: benign at deploy time, the server's defection is invisible to predeployment static analysis, which sees only the honest phase. Switched payloads range from overt structural violations to schema-valid manipulations, the latter preserving outer protocol compliance to evade runtime middleware filters. Crucially, TrustShift originates in the server-controlled tool channel, not user prompts (unlike indirect prompt injection) or the transport (unlike man-in-the-middle): the adversary is the trusted server endpoint itself. We introduce TrustShiftProbe, an evaluation and defense framework with four contributions: (1) a stateful temporal threat model of the agent-server lifecycle as a benign conditioning phase followed by an adversarial defection at a trust horizon; (2) a language-agnostic attack engine that instantiates each variant as a compromised MCP server across four production domains; (3) SHIELD, a multi-tier, zero-oracle runtime defense at the MCP transport boundary that audits server payloads against behavioral baselines learned during clean trust windows; and (4) a taxonomy of nine TrustShift variants spanning three execution mechanisms (structural violation, semantic corruption, scope expansion) and three adversarial objectives (disruption, exfiltration, and their combination). Across frontier proprietary and open-weight models, TrustShift attacks achieve a 69.5% mean attack success rate that SHIELD mitigates to 42.7%.

0.41

Runtime Assurance Under Measurement Attack: Necessary and Sufficient Observability Conditions for Learned Control in Radio Access Networks

eess.SP cs.CR ·2026-09-25 ·Yasser Al Eryani
similarity 0.49
Abstract · 17 pages, 6 figures, 9 tables

Runtime assurance pairs a verified fallback with an untrusted controller and a switching monitor, and is the leading route to admitting learned policies into safety-relevant network control. Its guarantee rests on a condition it assumes rather than requires: that the monitor's estimation error is zero, or at worst stochastic with a characterisable rate. In mobile networks many measurements originate at untrusted endpoints, where the error is neither. We state this assurance precondition and prove it: at zero measurement noise the guarantee survives an adversary controlling $q$ channels if and only if the plant is $2q$-sparse observable with respect to the safety-relevant output. This is functional observability over attack supports, strictly weaker than full-state observability: on our topology a per-cell outage condition doubles the budget and one stated over total offered load triples it. The converse is a constructive attack making a safe and an unsafe trajectory observationally identical; it defeats every monitor on those channels, not one detector, at any noise level. As the trust split is static and known before deployment, confining the adversary to one family yields a confinement threshold, above which trusted channels alone resolve the state and all untrusted channels may be corrupt at once. Three uninfluenceable counters cross it here, lifting the budget from two to six and making placement the dominant lever. Below the precondition the monitor faces a frontier, not a dichotomy; a set-valued monitor is optimal and carries sufficiency into non-zero noise at the residual test's false-rejection rate. An adversary reaching the trigger radius owns the switch regardless. The same argument bounds any monitor reading agent messages rather than measurements. A rank test decides the budget and identification does not preserve it, so a published budget must name its margin floor.

0.20