CS Paper Radar

Provisional Reachability: Containing Agents by Making Every Crossing Revocable

Yoshiaki Takashita

cs.CR cs.NI ·submitted 2026-09-18 16:14 UTC · v1
unusual

Abstract

A companion paper found that what a defender must block over time has units: bits per period [Takashita, 2026a]. This paper sets it. Hold every crossing in escrow for one period, audit each held item independently with probability r, and revoke the window if any audit catches something. An adversary crossing k times, each carrying c bits, expects kc(1-r)^k, maximised at k* = 1/ln(1/(1-r)), a bound of L(r) ~ c/(er) per window. The bound is a supremum over the adversary's choice, so the scheme may be public; simulation matches it to 7.7 standard errors. It is a rate, not a total: escrow alone still lets the secret assemble in every run. But if the secret decays at a fraction mu of held bits per period, holdings converge to g/mu at any horizon, so an L-bit secret is unreachable once mu > g/L -- an error threshold in Eigen's sense, sharp where the closed form puts it (100% of runs assemble at 0.9mu*, 0% at 2mu*, over 20,000 windows). Deception that needs the adversary to reason badly fails: a surface whose names lie left accuracy at 18 of 18, and 100% at three reader strengths. Withholding reference works, and differently: no reader would commit at all. Keying the entry points hides 0.10 bits of what a module does; keying the denotation hides 2.64 of 3.00 at chance accuracy, while 100% of readers still call it ordinary Python. Variance must be removed from the audit rate, where loot is convex in r, and added to the activation budget, where survival is multiplicative: extinction 70% to 100% at a fixed mean. End to end the stack takes the leak from 100,000 to 59 bits, a factor of 1,704, leaving 12% of legitimate work standing; keying the window to the caller restores that to 100% at no cost in leakage, at the price of a bound that is per principal. Of 65 read-only tools, escrow leaves 2,400 bits per call: a factor of 10, not infinity.

Comment
35 pages. Companion papers: arXiv:2609.18145, arXiv:2609.19720. Code and records included as ancillary files

Closest papers

Nearest neighbours by meaning across the whole index.

When One Leak Pays Forever: Context Binding and the Price of Deterring Collusion

cs.GT cs.CRecon.TH ·2026-09-29 ·Tingyi Lin, Shawn Yu, Ruoran Lai, Huanxi Zhang
published similarity 0.62
Abstract · Accepted at NeurIPS 2026

A coalition that deviates once can profit many times when what it sells keeps working. In a threshold-encrypted mempool, a leading defense against maximal extractable value (MEV), a quorum of the decryption committee that sells its decryption capability to a front-runner exposes every later block that the capability still decrypts. We ask how large a penalty, such as slashable stake, deters this kind of collusion. In our repeated game, a single leak by any coalition in a monotone family of authorized coalitions (for example, any $k$ of the $n$ committee members) unlocks a set of future rounds, costs a one-time penalty, and ends the coalition's participation. We show that every dynamic deviation reduces to choosing a leak time, so deterrence holds if and only if each coalition's penalty covers the largest discounted value that a single leak reaches. Without discounting, over $T$ rounds of unit value full reuse needs a penalty of $T$ while binding each leak to its own round needs $1$, so no penalty that is constant in the horizon deters unbounded reuse; a reuse window of $w$ rounds costs at most $w$ times the largest per-round value. The cheapest profile of per-party stakes that deters every coalition solves a covering linear program. For blockchain design, per-epoch keys cut the required stake from the value of a key's lifetime to the value of one epoch; we calibrate the gap on Ethereum front-running data and place Ferveo and Shutter in the model. The analysis extends to sealed-bid auctions, multi-authority voting, and federated learning under a shared key.

0.29

Clean Sheets and Checkpoints: Evidence Complexity for Certifying Sequential Agent Risk

cs.LG cs.AI ·2026-10-29 ·Rohith Yanambaka Venkata, Don McBride, Tiago Sequeira, Md. Al Amin
similarity 0.58
Abstract · 26 pages, 3 figures, 3 tables

Dangerous-capability evaluations often test an AI agent from prepared states at ordered milestones. A clean sheet records no successes. What it certifies about a campaign of $B$ attempts depends on what a failed attempt erases. We model the task as a chain of $k$ milestones divided into checkpoint segments and ask how many zero audit responses certify, at level $α$, a completion probability of at most $ε$. For segments chosen before the audit, counting possible completion windows gives a certificate for any specified budget. The bound also covers adaptive deployment processes that follow the chain's transitions, provided their success probabilities after every complete history are capped by the corresponding audit success probabilities. The audit does not test this transport assumption. In rare-risk phase interiors, each segment is either rarely completed within the budget (active) or nearly always completed (free). The minimum expected number of zero responses is asymptotic to $\log(1/α)\,(B^a/(a!\,ε))^{1/K_A}$, where the $a$ active segments contain $K_A$ milestones and are those at least as long as a budget-dependent threshold. The certificate attains this constant. Every asymptotically optimal evaluator must divide its expected response count equally among active milestones in the limit, with a vanishing share elsewhere. Where a single segment passes from active to free, each of its milestones receives a smaller limiting share than an active milestone; a crossover-aware certificate attains the optimal constant. For selected segments with known or unqueried prefix steps, counting failed cycles can sharpen the certificate.

0.29

How Much Must a Private Mempool Hide? Exact Leakage Thresholds for Sandwich Attacks

cs.GT cs.CRq-fin.TR ·2026-09-25 ·Tingyi Lin, Jiazhuo Li, Ruoran Lai
publishedtheory similarity 0.58
Abstract · Accepted at NeurIPS 2026

Private and encrypted mempools hide pending transactions to stop sandwich attacks and other forms of maximal extractable value (MEV), but what they hide is rarely everything: a transaction's pair, direction, and a coarse range for its size can still leak. How much leakage makes sandwiching pay? We answer exactly for a fee-free constant-product automated market maker, the pricing rule behind Uniswap v2. Traders observe an interval containing the victim's size and bid in a first-price auction for the right to sandwich it, and the winning front-run must keep the victim's trade executable at every size in the interval. The answer turns on the smallest size consistent with the leak. It alone determines the feasible front-runs, the largest feasible front-run is optimal for pointwise, expected, and worst-case profit alike, and the guaranteed profit has a closed form. When execution is costly, a privacy layer that wants to rule out sandwiches profitable at every consistent size may therefore reveal anything about the size except a lower bound above an explicit threshold; the upper end of the range is irrelevant. With two or more symmetric traders, every pure-strategy perfect Bayesian equilibrium of the auction hands the entire expected net rent to the auctioneer. If the direction is hidden too, no non-contingent first leg front-runs both possible directions, while post-trade arbitrage can survive even perfect pre-trade hiding.

0.41

Blindfold: Keeping the Audit Coin Secret from LLM Agents

cs.CR cs.AIcs.LG ·2026-10-27 ·Wei Zhu, Meiyun Zuo, Huiping Sun
similarity 0.57
Abstract

Audit-based certification bounds the violation rate of an LLM agent by auditing a random fraction $\varepsilon$ of actions and reweighting the audited labels; its validity is meant to rest only on the defender's audit coin. We show that it also rests on a confidentiality property: the coin must not interfere with the agent's view before the action commits, at a time the agent chooses. We call this pre-commit noninterference (PNI) and measure its violation by $D_{\mathrm{A}}$, the total-variation distance between the agent's views under the two coin values. PNI is necessary and sufficient for an unbiased certificate against adaptive agents, the worst-case bias is $(1-\varepsilon)D_{\mathrm{A}}$, and no procedure that sees only audited labels can pay less. Leakage composes across steps, a resource shared across episodes opens a channel of computable size, and raising the audit rate cannot restore validity. On a monitor we built, a silent audit changes no output but adds latency that tool timestamps expose, and the agent can enlarge it. A real LLM agent follows an injection that names a visible audit notice (generic, tool, and timing clauses have no effect); over that channel the plain certificate fails on measured labels and, by a post-hoc analysis, in a live run on a pre-registered schedule, while a silent audit restores it. A fresh coin per audited call closes the timing channel; padding only narrows it.

0.31

When the Agent Edits Its Own Limits: Evaluating a Write-Time Floor Against Prompt Prohibitions

cs.LG ·2026-10-05 ·Sajib Hossain, Moeen Uddin Mahmud
benchmark similarity 0.56
Abstract · 10 pages, 1 figure, 4 tables. Longer study: arXiv:2610.06274

Many agent runtimes give the agent a tool for editing its own configuration. Some settings grant abilities, such as enabling a tool. Others set the agent's limits: where it may write, who may message it, which address it listens on, how callers authenticate, and the gate that blocks risky writes. We measure how often models widen those limits while handling ordinary requests, and how well two kinds of defence hold: a prohibition in the system prompt, in three wordings, and a check at the point of writing that we call a containment floor. Every case records whether a protected write was attempted and whether it was saved, read from the tool's arguments and from the file rather than from the model's reply. With no defence, a frontier model saved a protected value on 25 of 72 requests, often when the request never named the field. A prompt that listed the protected field names stopped every request that used those names and did not reduce writes on requests that only described the goal; a prompt that described the forbidden effects did the reverse. With the floor, 0 of 167 protected writes were saved while 65 were attempted. A single-pass pilot on two further models shows the same pattern. We draw four lessons for evaluating agent safeguards: count attempts beside outcomes, test a prompt defence with requests written in a different vocabulary from the prompt, check that a zero means the safeguard fired, and log what the harness sends to the model, because a request-ordering defect in our own runtime was invisible in the transcripts and was found again, independently, by a later benchmark.

0.25

Leakage-Resilient Computation via Matrix Refreshing

cs.CR ·2026-11-03 ·Stefan Dziembowski, Sebastian Faust
theory similarity 0.56
Abstract

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

0.20

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

On the Relative Security of Prompt Injection: Mechanised Definitions, Defences and Verdicts for LLM Agents

cs.CR cs.AI ·2026-11-08 ·Brijesh Dongol
theory similarity 0.55
Abstract

An LLM agent that reads untrusted content, such as an email or a web page, may follow instructions hidden in it. Noninterference is too strong for such agents, since a useful agent lets untrusted content influence what it does and may disclose the user's data by design, and declassification needs a release policy written for each task. We instead state security relative to a reference agent, which runs the same plan under the same runtime monitor with a model that never obeys untrusted content. An agent is relatively secure if every leak it has is a leak the reference already has. Our framework, PlanTERS, instantiates relative security, a notion from speculative execution, with a small agent language in which the attacker chooses how the model follows instructions, a composition with runtime monitors, and attacker models that differ in what they observe. A fence theorem shows that revoking injectable tools at the first untrusted read, and never granting them back, makes every plan relatively secure at the event level on finite runs, for every model behaviour in which each injection is a single call and the model obeys on a schedule fixed in advance; with a fairness condition, this extends to possibly infinite runs. We prove or refute relative security for agents with fences, budgets, approvals, loops and dual LLMs, in Isabelle/HOL.

0.16