CS Paper Radar

Verifiable Random Sampling of Private Data Without a Trusted Single Party

Muhammed Karamuk, Mikołaj Glinka, Ruben Wolff

cs.CR cs.AI ·submitted 2026-11-16 15:09 UTC · v1

Abstract

Problem: When a party supports claims about a private dataset by disclosing a sample, auditors cannot tell whether it was drawn at random or "cherry-picked" to hide flaws in the rest of the data. Solution: The data holder commits to the hashes of every item in its dataset and registers the commitment with independent servers. Selection then waits on a decentralized randomness beacon: a network that jointly emits a fresh random value every few seconds, outside the control of the data holder and the auditors. The value emitted two beacon rounds after the commitment picks the sample. Each server returns a signed receipt, so anyone can later check that the revealed sample is exactly the one that value prescribes. Selection from the committed set stays unbiased as long as the beacon's threshold holds and one required server is honest, and a pre-agreed name, checked with the servers, stops repeated or abandoned draws. We call this protocol NoCherry. Applications: Any audit that spot-checks a private corpus: private AI benchmarks and held-out test sets, dataset quality claims, code and security audits, test-fairness review, vulnerability handling, and compliance sampling. Auditors need not trust the data holder to hand over a representative sample of the committed data, since the protocol proves it, and data holders need not expose their entire dataset.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

ClaimReceipt: Verifying Evidence Sufficiency and Coverage in Agent Evaluations

cs.AI cs.CRcs.MA ·2026-09-02 ·Peiying Zhu, Sidi Chang
similarity 0.63
Abstract · Submitted to Who Verifies the Agents? Toward Reliable Agent Development (NeurIPS 2026 workshop). 8 pages, 1 figure, 7 tables

Agent evaluations face two distinct evidentiary questions: whether a reported claim is recomputable from retained evidence (sufficiency), and whether the retained records cover the committed experiment set (coverage). Generic logs and hash-linked transcripts answer neither reliably. We introduce ClaimReceipt, a claim-relative receipt specification and selective verifier that binds typed transaction evidence to a signed experiment manifest and returns PASS, INVALID, or INCONCLUSIVE per claim. We freeze the specification before implementation (SHA-256 18d109...b81). On 1,392 historical buyer--seller records, a CR-2 verifier reproduces all five manually labeled audit verdicts, exactly replays 600 deterministic and 792 post-generation records, makes every one of 13 declared field groups non-redundant under tested ablations, and returns the expected result on 11/11 semantic faults with 0/8 false positives. We then run a separate prospective CR-3 epoch: 30 assignments are committed before inference, terminal receipts are signed and chained, and private evidence is encrypted for an auditor. Complete evidence yields coverage and accounting PASS; withholding one terminal receipt returns INCONCLUSIVE_COVERAGE, while withholding all private openings preserves coverage and protocol verification but makes economic claims inconclusive, exactly matching a preregistered prediction. Receipt instrumentation adds 0.021% of model-inference time and 9.9 KB per transaction. A specification-legibility probe indicates that our own frozen specification is not yet unambiguous to an independent reader. Claim verification therefore requires both claim-sufficient evidence and a committed universe against which omissions become visible.

0.38

Certified Corruption Budgets: Anytime-Valid Leaderboard Claims under Adaptive Rigging

cs.CR cs.AIstat.ME ·2026-10-06 ·Hamed Khosravi, Xiaoming Huo
benchmark similarity 0.63
Abstract

Public leaderboards for AI models are read continuously, and attackers can see every published standing. Vote rigging, selective disclosure of private variants, and benchmark contamination can each move a ranking. Existing guarantees assume genuine records or bound the corruption per step, which an attacker who corrupts in bursts evades. We introduce the certified corruption budget, a tolerance $\widehat{B}_t$ computed after $t$ records and published with each pairwise claim. With probability at least $1-α$, simultaneously at all times, the claim is correct or more than $\widehat{B}_t$ records were corrupted. It holds against attackers who watch every certificate, with no bound on their budget. Forged records and records altered once seen require different certificates: the certificate for forgeries fails, with probability approaching one, against an attacker who flips votes it has seen, while one that charges roughly twice as much per record remains valid, with constant bets even against attackers who see the future, and no smaller charge is valid at every level. The certified budget grows nearly as fast as any valid method allows: with a win fraction $\frac{1}{2}+δ$, each new record adds close to $2δ$ to the number of forged records the claim can withstand ($δ$ flipped). Publishing the best of $V$ private variants costs only an amount growing like $\log V$. In replays on 1.8 million Chatbot Arena votes, a few hundred rigged votes make standard confidence intervals certify false orderings, while ours stays valid. On real votes, our certificate shows that clearly separated models withstand about 2,000 forged votes.

0.36

The Acknowledgment Point Is the System: Durable Policy-Decision Receipts for AI Audit Evidence

cs.CR cs.AI ·2026-08-17 ·Neeraj Kumar Singh Beshane
code/data similarity 0.62
Abstract · 6 pages, 4 figures, 2 tables. Code and release artifacts: https://github.com/neerazz/RuntimeGuard-AI/releases/tag/v2.0.0

An AI audit record is useful only if its durability and trust boundary are explicit. Returning a guarded decision before any durable write minimizes latency, but it cannot guarantee that evidence survives an immediate crash. We rebuild RuntimeGuard-AI around this constraint. The resulting research prototype binds each deterministic policy decision to the exact policy source, commits a privacy-minimizing record at a caller-selected synchronization boundary, and returns an Ed25519-signed receipt that states whether that boundary completed. After restart, the engine validates framed records, manifests, shard placement, sequence continuity, and replay identity. A separate attestation path groups committed records into chained, signed Merkle epochs that an auditor verifies with an externally obtained key. On an Apple M4 Pro at four worker threads and 2,048-byte prompts, buffered signed evidence reaches 27,193 requests/s with 141.9 microseconds median latency. Per-record data and full synchronization reduce throughput to approximately 242 requests/s and raise median latency to 16.0 ms. Sealing a 100,000-record signed epoch takes 97.0 ms. The result is a measured durability-latency trade-off, not a "free" asynchronous audit path. The prototype does not prove model execution, prevent a compromised signer from forking history, or establish legal conformity.

0.45

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

Canaries in the Bank: Auditing User-Level Privacy in Private Evolution

cs.CR cs.AIcs.LG ·2026-09-11 ·Sai Aparna Aketi, Enayat Ullah, Shripad Gade
similarity 0.61
Abstract · 14 pages

Private Evolution (PE) generates high-fidelity synthetic data in federated settings without exposing users' raw data. It aggregates clipped user votes over a shared candidate bank into a differentially private histogram, with noise calibrated to the worst-case user contribution. However, it is unclear whether an adversary can realize this worst-case privacy loss while following the PE protocol. We introduce a protocol-aware empirical audit in which the server commits to a single shared candidate bank and replaces roughly 1% of its entries with probes derived from a known, non-private canary. We evaluate eight attacks, including an unchanged-bank baseline, exact copies, plausible paraphrases, and high-entropy synthetic nonces. Experiments on Yelp and Sentiment140 show that natural-text attacks remain substantially below the theoretical DP bound, while nonce-based attacks yield considerably stronger bounds and come closest to the mechanism's privacy ceiling. These results quantify the gap between formal worst-case privacy and leakage achievable through protocol-valid candidate-bank manipulation.

0.19

Sealed bets on emerging research topics: a protocol for judging early detection, applied to a detector and to eight research funders

cs.DL ·2026-10-25 ·Sébastien Gracia
benchmark similarity 0.60
Abstract · 37 pages, 4 figures, 19 tables. OpenTimestamps proofs and position fingerprints: doi:10.5281/zenodo.23641352

Tools that claim to detect emerging research topics are rarely judged on their own lists. Our main contribution is a protocol that makes such judgement possible. A bet freezes four things before its verdict can be known: the date of the photograph, the population of candidates, the verdict rule, and the comparison with chance drawn among the same candidates. The list has a fixed length, is read on two axes (champions and failures) against a computed ceiling, and is sealed by cryptographic fingerprint; sealing proves that a list existed at a date, not that it is right. A topic is a champion if its yearly volume of records triples within three years and reaches 100, a failure if it falls by 30%. We apply the protocol to one detector on PubMed/MEDLINE, in three separate blocks. On a retrospective benchmark (2017-2022), chance among the candidates yields 26.7 champions and 15.1 failures out of 120 slots; the detector yields 85 and 3, and under nine pre-registered variants of the verdict rule its champions stay between 2.5 and 5.0 times chance, with no more failures. The detector was developed with these verdicts known, and its specification is not published. Prospective validation rests on six sealed bets, judged in early 2029 and early 2030; only bets 5 and 6 test exactly the instrument of the benchmark. A secondary, exploratory study applies the same judge to eight research funders: under exact name matching, which may disadvantage grant texts, the detector's lists are more concentrated in future champions than the twenty topics named in the most grants of each funder (70.8% against 20.8% to 35.8%, chance 22.3%). We document data defects, negative results and the limits of each comparison.

0.31

ReplayAudit: Auditing Outsourced LLM Fine-Tuning via Sealed Records and Selective Replay

cs.CR cs.LG ·2026-11-06 ·Yihan Xia, Wenxin Xu, Taotao Wang
similarity 0.60
Abstract · 23 pages, 5 figures

Auditing outsourced LLM fine-tuning requires checking an untrusted provider's training while controlling verification cost. Uniform sampling ignores training-time signals, while checking a suspicious record can require replaying several preceding steps. We present ReplayAudit, a telemetry-guided auditing system that seals training records before challenges and independently replays sampled intervals from sealed checkpoints. Loss changes and parameter-update norms guide stratified random sampling; replay determines whether the selected computation agrees with its records. We relate sampling probabilities to replay work and evaluate the system on real LoRA training. A 7B BF16 prototype rejects a false update-norm report during a random audit; targeted checks also reject false loss reports and skipped updates. We calibrate sampling budgets offline to at least a 90% probability of directly selecting an injected step. For two learning-rate deviation settings, executing these budgets on the same honest 1.5B trajectory reduces median complete-audit wall time by 49% and 67% relative to uniform sampling. When skipped updates evade the high-anomaly stratum, the corresponding audit instead costs 38% more. These results show how deviation capture and actual replay work jointly determine the cost of telemetry-guided auditing.

0.33

PCM: A Proof-Carrying Message Protocol for Verifiable Multi-Agent Communication

cs.CE cs.AIcs.CRcs.MA ·2026-10-29 ·Bravish Ghosh
benchmarktheorycode/data similarity 0.60
Abstract · 50 pages, 9 figures, 15 tables. Specification, conformance vectors, verifier and benchmark: https://github.com/Cygnux-Labs/PCM-protocol

When one AI agent tells another that "the tests passed" or "a person approved this refund", the receiver has only the sender's word. A2A and MCP authenticate the channel, but the sender is the party in doubt, so a prompt-injected agent can launder fabricated facts and authority through a multi-agent system. We present Proof-Carrying Messages (PCM), a protocol in which each claim carries evidence: records from an append-only Merkle log that the agent cannot write, with inclusion proofs, signed by an attesting signer the agent cannot control. Receivers check messages offline and give each claim a three-valued result: proven, unproven or failed. A claim that rests only on the agent's own report is never proven. Authority travels as grant chains rooted in a recorded human approval, and the chains can only narrow. We specify four claim types, a typed caveat algebra, replay rules that survive restarts, and strict readings that make independent verifiers agree, and we prove the resulting security properties. On a pre-specified benchmark of 926 messages from real runs, 712 of them lies in 16 classes, PCM accepts 10 lies, all of them stale evidence (1.4%, 95% CI 0.8-2.6%). Plain A2A accepts all 712, and models of six deployed protocols (A2A with signed Agent Cards, uAgents, RFC 9421, SCITT, AP2, Verifiable Intent) accept 504-712. Two independent verifiers agree on all 926 verdicts, and verification takes about 1 ms.

0.23