Search: “verifiable-computation”

Smart search ranks by meaning as well as keywords (one row per story, last 45 days).

Towards Tackling Application Logic Flaws through Autonomous Formal-Logic Modeling and Automated Reasoning

LL-Verifier combines LLMs with logic model checking to automatically discover logic flaws, uncovering vulnerabilities in 27 IoT access-control protocols.

Researchers present LL-Verifier, a framework that uses LLMs to autonomously convert natural-language protocol descriptions and security goals into formal logic models in a new logic language built on Maude, then applies logic model checking for exhaustive verification. The framework targets application-logic flaws that are tied to business semantics and hard to scale with manual analysis. Evaluation on 27 access-control protocols of widely used IoT devices uncovered a range of sophisticated logic vulnerabilities with security and privacy implications.

arXiv cs.CR·Sep 9, 17:58 UTC · 6d agoResearch1

42

Scaling Verification of Cryptographic Software with Aeneas, Rust, and Lean

Microsoft SymCrypt implementations of SHA-3 and ML-KEM verified in Lean via Aeneas-extracted Rust models, with AI agents writing proofs.

The paper develops a methodology for verifying production Rust cryptographic code by using Aeneas to extract pure models into Lean, avoiding low-level pointer and aliasing reasoning. Applied to Microsoft's SymCrypt, it verifies SHA-3 and ML-KEM implementations ported from C to Rust and extends SymCrypt with FrodoKEM, ML-DSA, and HPKE. A 237 KLOC Lean development establishes safety, panic-freedom, and functional correctness of 16.7 KLOC of Rust supporting post-quantum cipher suites on x86-64 and ARM. AI agents autonomously write formal proofs verified by the Lean kernel, and evaluation shows verified Rust meets SymCrypt's performance and portability requirements.

arXiv cs.CR·Sep 14, 14:32 UTC · 1d agoResearch1

42

AI models' written reasoning steps correspond to distinct internal patterns, a new study finds

KAIST and Naver AI Lab researchers show LLM reasoning steps like extraction and computation map to distinct activation patterns, strongest in middle layers.

Researchers at KAIST and Naver AI Lab defined eight recurring reasoning operations, including extraction, decomposition, formula recall, deduction, and computation, and showed they correspond to separable activation patterns in Qwen2.5-7B, Qwen3-8B, and Gemma4-31B on math tasks, with GPT-5 labeling solution segments. The separation peaks in middle layers, holds even when a computation step produces a wrong answer, and goes beyond surface-level token choice. Findings replicated on Llama-3-8B, and classifiers trained on Qwen3-8B transferred to GPQA-Diamond and MATH-500. The authors note that using internal states for error detection or mid-generation steering remains future work.

The Decoder·Sep 12, 13:39 UTC · 3d agoAI research2

42

Understanding the Usability of Cryptographic Verification Tools

Survey of Tamarin and ProVerif users reveals usability barriers: debugging non-termination, model validation, and opaque proof failures hinder cryptographic protocol verification.

The paper presents an exploratory human-centered survey of researchers, graduate students, and practitioners with hands-on experience using Tamarin, ProVerif, and related cryptographic protocol verification tools. Findings reveal usability barriers across the verification workflow, including difficulties debugging non-termination and performance issues plus the lack of systematic methods for validating formal models against real protocols. When proofs fail without concrete attacks, users commonly simplify models, add helper lemmas, and revisit modeling abstractions. Participants called for actionable diagnostics, clearer explanations of results, visualization, and automation for recurring proof tasks.

arXiv cs.CR·Sep 14, 20:40 UTC · 1d agoResearch

20

Maverick: Private and Verifiable LLM Inference Made Practical via Matrix-Vector Multiplication Delegation

Maverick protocol delivers private and verifiable LLM inference via matrix-vector multiplication delegation, achieving up to 45x throughput gains over local inference on Qwen3-4B.

Maverick introduces an information-theoretically sound protocol for delegating matrix-vector multiplication with transparent preprocessing, efficient batch verification, and virtually no server overhead, combined with LPN-based pseudorandom masking for input privacy. It addresses privacy and correctness concerns when users delegate open-weight LLM inference to third-party providers. An end-to-end prototype evaluated on Qwen3-4B achieved throughput gains over local inference of up to 45x with precomputed privacy masks and 44x for verification-only workloads, with a CPU server using up to 128 threads.

arXiv cs.CR·Sep 9, 14:53 UTC · 6d agoResearch1

40

Sound Debloating of Redundant Checks in Zero-Knowledge Machine-Learning Circuits

Automated framework soundly removes up to 48.7% of redundant constraints in ezkl and zkml ZK-ML circuits, cutting prover time by up to 72.8%.

The framework uses whole-circuit abstract interpretation and a provenance graph to verify that each removed redundant check (range proofs, sign lookups, bit decompositions) remains entailed by the rest of the circuit, provably preserving soundness. It was evaluated on MLP, CNN, RNN, and transformer circuits generated by ezkl and zkml, with up to 25.3 million constraints. It removes up to 48.7% of constraints and reduces prover time by up to 72.8% without weakening security. Under-constrained circuits in deployed ZK systems have previously enabled attackers to forge transactions and bypass verification.

arXiv cs.CR·Sep 9, 13:27 UTC · 6d agoResearch1

35

Scores Alone Do Not Prove Discovery: The Discovery Certification Protocol for Auditing AI Research Agents

Researchers introduce the Discovery Certification Protocol, an auditable test framework that verifies whether AI research agents' claimed discoveries are genuine.

The Discovery Certification Protocol (DCP) converts AI research agents' discovery claims into executable recovery and feedback tests organized as gated audits. Controlled audits in SQLite optimization and virtual catalyst control produced zero recoveries in 96 episodes, with an upper bound of 0.0468. A deterministic, LLM-free verifier reproduces audit decisions from frozen evidence, giving AI research a common evidence language for outcomes, alternative routes, and feedback effects.

Hugging Face daily papers·Sep 6, 20:00 UTC · 9d agoAI research

30

Fresh-Challenge VDF Attestations for Model-Relative Response Latency

Fresh-Challenge VDF Attestations bind verifiable delay functions to unpredictable public challenges, yielding succinct evidence of model-relative response latency.

The paper specifies FCLA, a protocol composition that binds a VDF to an unpredictable public challenge, a message, and independently auditable release/receipt records. Under explicit assumptions about VDF sequentiality and a calibrated bound on an adversary's sequential evaluation rate, an accepted transcript is inconsistent with post-challenge generation. A benchmark of the public reference implementation confirms the expected evaluation-versus-verification separation on one documented machine. The contribution is a protocol design analysis, not a new VDF construction.

arXiv cs.CR·Sep 11, 11:25 UTC · 4d agoResearch

15

CertiFlash: A Formal Verification Framework for Flash Translation Layers in Computational Solid State Drives

CertiFlash provides machine-checked formal verification of SSD flash translation layers, proving isolation, integrity, and ownership invariants to prevent tenant data leaks.

CertiFlash is an open-source formal verification framework for Flash Translation Layers (FTL) in computational SSDs, mechanized in the Rocq proof assistant. It shows that a faulty FTL can corrupt device state at five surfaces (e.g., leaking data between tenants or dropping integrity tags), demonstrated on a DaisyPlus OpenSSD. Designers prove once that every operation of a general FTL model preserves a global invariant covering mapping, isolation, integrity, ownership, and allocation; new designs need only discharge five hypotheses. Across four case studies, added effort was 27-3,231 lines against a 16,489-line framework.

arXiv cs.CR·Sep 9, 15:44 UTC · 6d agoResearch1

25

Stealing AI Reasoning Traces

Researchers demonstrate a decryption jailbreak that extracts encrypted reasoning traces from Anthropic, OpenAI, and Google LLM APIs via weaker sibling models.

The paper exploits the fact that encrypted chain-of-thought blocks returned by LLM providers are interchangeable across sessions, users, and models within a provider's ecosystem. Injecting an encrypted trace into a weaker, less-safeguarded model from the same provider forces it to output the trace in plaintext, bypassing anti-distillation mechanisms. Decoding 315,320 reasoning blocks scraped from public repositories recovered 367 PII artifacts and 182 credentials, showing large-scale private data leakage. The flaw also enables hidden hazardous information disclosure and invisible prompt injections embedded in encrypted blocks; mitigations were proposed after responsible disclosure.

Schneier on Security·Sep 8, 10:20 UTC · 7d agoAI safety & security

58

Observational Indistinguishability and Integrity Blind Regions in Hybrid Quantum-Classical Workflows

Framework formalizes integrity blind regions in hybrid quantum-classical workflows, validated across 3,600 label interventions with conformal detection rules.

The paper presents a claim-relative evidence and reference framework for integrity of hybrid quantum-classical workflows, distinguishing structural blind regions caused by observational indistinguishability from finite-batch statistical misses. Experiments over 3,600 label interventions show exact label-path invariance for feature and prediction views. The geometry-aligned construction detects 343 of 2,700 conclusion-changing interventions using the conformal rule and 1,183 of 2,700 with the uncorrected union, with executed conformal clean false-action rates of 0.048-0.059.

arXiv cs.CR·Sep 15, 13:16 UTC · 18h agoResearch

12

OPEN-1B: A Fully Auditable Training Run

Open-1B releases a 1B-parameter model with bitwise-reproducible training, letting independent auditors verify every step of the run on commodity hardware.

The paper introduces a 'fully auditable' tier of model transparency: every training operation is reproducible with bitwise certainty on heterogeneous commodity hardware by imposing definite ordering on GPU kernel reductions, data batch ordering, and collective communication. Because replaying a full run on one machine is infeasible, a collective verification scheme lets many independent auditors certify individual steps covering the whole run. The authors release Open-1B with its full pretraining dataset, every intermediate checkpoint, the training codebase, and an audit harness. This rules out undisclosed data, injected biases, or backdoors that proof-of-learning or proof-of-training-data techniques cannot exclude.

arXiv cs.AI / cs.LG / cs.CL·Sep 15, 16:23 UTC · 15h agoAI research

58

Scalable Composition of Byzantine Agreements under Reorder Attacks

Researchers present the first adversary model combining party corruption with channel reordering attacks, establishing tight security thresholds for composed Byzantine agreement protocols.

The paper presents the first adversary model combining party corruption with adversarial channel attacks that reorder messages across multiple Byzantine agreement executions. It proves impossibility results for authenticated BA under parallel composition when n ≤ 3t or n ≤ 2c + 2t + 1, with matching possibility results when n > max{3t, 2c + 2t + 1}. The authors provide general black-box compilers plus erasure-correcting-code variants that achieve constant multiplicative communication overhead for long messages.

arXiv cs.CR·Sep 9, 02:35 UTC · 7d agoResearch

25

Beyond Solver Verdicts: Generative Reward Models for Autoformalization

Researchers introduce Generative Verification (GenV), a generative reward model achieving 0.961 AUROC in detecting unfaithful autoformalization that preserves solver verdicts.

The paper formalizes Verdict-Preserving-Unfaithfulness (VPU), a failure mode in neurosymbolic autoformalization where an incorrect encoding executes successfully and matches the expected solver verdict, and proves verdict-only verification is bounded to chance-level detection. The proposed Generative Verification (GenV) distills an offline Z3-equivalence oracle into a reference-free, continuous reference-equivalence score within the language model's vocabulary space. The oracle-mined verifier (GenV+HN) achieves 0.961 AUROC, generalizes zero-shot across unseen translators and formal styles, and yields an 11.3-point downstream accuracy gain in agentic test-time compute allocation. Mechanistic analysis with decision-projected logit lenses and sparse autoencoders shows the generative readout extracts precise spatial error coordinates without explicit localization training.

Hugging Face daily papers·Sep 9, 20:00 UTC · 6d agoAI research1

35

Access Control as Verified Parse Constraints

Researchers verify a class of EverParse validators that correctly enforce access-control policies, deploying a machine-checked enforcement gate on seL4.

The paper targets enforcement-code bugs in commercial security gateways by proving that forward-only, backtrack-free EverParse validators are verified recognizers for a bounded finite-state class that includes access-control decision functions with fixed-offset fields and bounded disjunction. Encoding a bounded policy language into a fixed-size byte buffer allows an SMT solver to verify the enforcement code once, covering all byte values, policies, requests, and sessions. Editing rule content over a fixed endpoint set requires no new proof, while adding endpoints reruns the toolchain. A deployment on the seL4 microkernel ensures every request passes through the gate and unverified components cannot corrupt the enforcement chain.

arXiv cs.CR·Sep 11, 06:33 UTC · 5d agoResearch

28

Certifying Adversarial Robustness of Quantum Classifiers under Known-Readout Query Access

Framework certifies adversarial robustness of quantum classifiers using only measurement statistics and finite-shot outcomes, demonstrated on IBM Quantum hardware.

The paper introduces a measurement-only certification framework for adversarial robustness of quantum classifiers under known-readout query access, requiring no tomography, parameters, or gradients. It returns a lower bound ruling out untargeted errors within a radius and an attack-independent upper bound witnessing an adversarial state, both estimable with finite-sample guarantees. Evaluations show the lower bound tracks exact optima on tractable instances while the upper bound stays informative when standard attacks fail. The method was validated on IBM Quantum hardware using 40 executions of two 8-qubit quantum neural networks.

arXiv cs.CR·Sep 10, 14:45 UTC · 5d agoResearch

27

Atlas: Efficient Verifiable Semantic Search

Atlas delivers zero-knowledge proofs for HNSW semantic search, verifying RAG retrieval in under a second on SIFT1M and 2.0 seconds at 100M vectors.

Atlas lets a search provider prove that a query was answered correctly against a committed HNSW index without revealing the index, addressing provider deviations like truncation or bias. It combines offline preprocessing, a fixed-size-state restructuring of HNSW with a correctness proof, and timestep-tagged batching of per-step arguments. The system proves queries in under a second on SIFT1M and 2.0 seconds at 100 million vectors while preserving plaintext HNSW recall, and proven retrieval maintains end-to-end RAG answer quality at lower cost than prior verifiable retrieval systems.

arXiv cs.CR·Sep 10, 17:30 UTC · 5d agoResearch1

40

Implementing a White-Box Undetectable Backdoor for Random Fourier Features

Researchers implement Goldwasser's CLWE-based undetectable backdoor for Random Fourier Features models in numpy/scipy, confirming practical realizability with no detectable differences from clean models.

The paper provides an end-to-end implementation of the Goldwasser et al. white-box undetectable backdoor for models trained with the Random Fourier Features algorithm, using only numpy and scipy. It derives two samplers for the core GP_d(b_k) distribution: a rejection-sampling proxy and an exact closed-form sampler verified against its analytic form. Statistical indistinguishability tests covering weight-space and functional black-box comparisons found no detectable difference between backdoored and clean models across sparsity ratios. The underlying lattice hardness reduction was not reproduced, and the work demonstrates the threat is realizable with commodity scientific-computing tools rather than specialized cryptographic infrastructure.

arXiv cs.CR·Sep 14, 22:18 UTC · 1d agoResearch

50

Guppy: Efficient Light Clients via Recursive Zero-Knowledge Proofs

Guppy lets blockchain light clients verify full state via recursive zero-knowledge proofs without validators maintaining state commitments, processing thousands of updates per second.

Guppy is a light-client protocol in which validators commit only to state updates while an off-chain, untrusted service secured by recursive zero-knowledge proofs maintains a verifiable Merkle tree over the full state. A hash-chain commitment moves validator signature verification out of the proving circuit, and a parallel recursive proving pipeline keeps latency growth logarithmic with throughput. A Plonky2-based implementation maintains a tree of size 2^30 while processing thousands of updates per second, adding only 2-4 seconds of latency without increasing block-construction complexity.

arXiv cs.CR·Sep 7, 20:41 UTC · 8d agoResearch

22

Do AI Coding Assistants Check Before They Install? A Pre-Registered Demand-Side Audit of Trust Signals in the Research Software Supply Chain

Pre-registered audit finds AI coding assistants verified provenance signals in only 9 of 1,920 trials before installing research software packages.

The study tested whether AI coding assistants check machine-readable trust signals such as SBOMs, signed releases, and provenance attestations before installing six open-source research software projects spanning HPC and quantum computing. Three models under two operating modes produced 1,920 registered trials scored from container logs. Provenance signals were opened in only 9 of 1,920 trials (0.5%) and zero of 384 control trials, with no trial running a verification command. The authors conclude publishing signals is insufficient and verification must be built into the program running the assistant.

arXiv cs.AI / cs.LG / cs.CL·Sep 7, 16:55 UTC · 8d agoAI safety & security

48

ResidualAuth: What Authorization State Must Language Agents Preserve under Revocable Delegation?

Formalizes residual authorization state language agents must preserve under revocable delegation; token-budget summaries mostly fail while hard gates stop unauthorized effects.

The paper shows two authorization histories with identical current permissions can require opposite decisions after the same direct-edge revocation, formalizing the needed information as residual authorization state. Exponentially many future-distinct states can share one transitive closure, with exact or tight asymptotic bounds on the state an exact monitor requires. Across four open-weight models, fixed 256-token summaries solved at most 2 of 16 paired episodes while authenticated current-query reads solved 15-16 of 16. A hard effect gate reduced eight observed unauthorized effects to zero without changing preceding attempts.

arXiv cs.CR·Sep 8, 00:05 UTC · 8d agoResearch

27

SCHERI: Provably Secure Speculation Under the Constant-Time Policy for CHERI (Extended Version)

Researchers formally prove existing CHERI speculation proposals leak secrets and present SCHERI, a processor design with end-to-end Spectre-resistant constant-time guarantees.

The paper builds a formal framework reasoning jointly about capability safety, speculative execution, and information-flow security on CHERI architectures. It demonstrates that existing secure-speculation proposals fail to preserve constant-time confidentiality guarantees and can transiently leak isolated secrets. The authors present SCHERI, a new processor design formally proven to provide end-to-end secure speculation for the constant-time policy, resilient to Spectre attacks.

arXiv cs.CR·Sep 15, 16:33 UTC · 15h agoResearch

45

You've Got a BUD in Me: Authenticated Reads from Per-Block Write Logs

Researchers propose BUD, per-block write-log digests enabling blockchain validators to serve historical membership and exclusion proofs far cheaper than state-wide tries.

The paper introduces Block Update Digests (BUD), which authenticate each block's write log with predecessor pointers, plus a SuperBUD and exponential hierarchy to turn long unchanged intervals into short proofs. Soundness against adversarial provers and up to f Byzantine validators is proven under archive, attestation, and committee evidence assumptions. Benchmarks show a 50x state-size increase raises the base-BUD path only 1.24x versus 3.1x for in-memory and 69.5x for disk-backed Merkle Patricia tries, with read payloads below 800 bytes and p99 warm verification at 146 microseconds.

arXiv cs.CR·Sep 10, 08:46 UTC · 5d agoResearch

14

Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale

Researchers certify a dependency-preserving upper bound of 2^-164.81 on honest decapsulation failure for ML-KEM-768 within an explicit ROM/CBD abstraction.

The paper models ML-KEM-768's domain-separated public-matrix streams as independent uniform ring elements and secret polynomials as CBD2 primitives, explicitly not claiming an information-theoretic result about the fixed SHAKE instantiation in FIPS 203. It preserves dependencies from the public matrix and both ciphertext-compression terms, using a graph-coupled reference, a proper-ideal bivariate Fourier transport, and a 256-coordinate union bound. The certified bound is Pr[K' != K] <= 2^-164.81, with the exponent 164.8107162... exceeding the 164.81 threshold by only about 0.0007162 bits; 164.82 is not certified. The bound applies to messages fixed independently of the randomness under honest encryption and decapsulation, and is not an exact DFR, a fixed-SHAKE equivalence, or a new IND-CCA reduction.

arXiv cs.CR·Sep 9, 10:13 UTC · 6d agoResearch1

30

Beyond the Turing threshold: Productive grammars generate essentially undecidable languages

A theoretical paper designs formal grammars that emulate Post's productive sets, generating languages that are provably beyond Turing decidability.

The paper elaborates on Emil Post's productive sets, which are not even semi-computable, and builds formal grammars that emulate their construction over natural numbers. The resulting languages are shown to be essentially undecidable, placing them beyond Turing decidability. This is pure computability and formal language theory with limited direct security relevance.

arXiv cs.CR·Sep 10, 11:20 UTC · 5d agoResearch1

10

A Note on Sphere Packing Bounds for Tuple Lattice Sieving

Proves upper bounds on k-irreducible unit vector set rates, yielding nearly tight asymptotics relevant to tuple lattice sieving in cryptanalysis.

The paper bounds the maximal asymptotic rate of k-irreducible sets of unit vectors via spherical code packing bounds. It shows R_k is sandwiched between (1/2 - o(1)) log2(k)/k and (1 + o(1)) log2(k)/k for large k. These almost-tight bounds inform subexponential complexity analyses of tuple lattice sieving, which underpins security estimates for lattice-based cryptography.

arXiv cs.CR·Sep 8, 03:20 UTC · 8d agoResearch

15

GAUGE: A Formal Framework for Measuring Cryptographic Security under Heterogeneous Adversary Cost Models

GAUGE frames cryptographic security as profiles over adversary cost models, certifying a ranking reversal between ML-KEM-512 and AES-128 from a 4–5% memory pricing shift.

GAUGE represents cryptographic security as a function over admissible adversary cost models (a security profile), proves profiles are piecewise-linear and concave, and establishes a rating trilemma when two profiles cross. A polynomial-time linear-programming procedure certifies whether the ranking of two schemes is robust, reverses under admissible models, or is genuinely incomparable. Applied to NIST post-quantum standards, the framework certifies a ML-KEM-512 versus AES-128 ranking reversal from a 4–5% shift in memory pricing and measures lattice-sieving cost drift of 9.79 bits per year over eight years. A hybrid X25519 + ML-KEM-768 handshake reduces combined-break probability twenty-fold at a 2.3 kilobyte cost.

arXiv cs.CR·Sep 15, 14:55 UTC · 16h agoResearch

48

Forgetting Without Restarting: Execution-State Unlearning for Stateful LLM Agents

Researchers propose provenance-guided selective replay letting LLM agents forget revoked information without restarts, matching full reset behavior.

The paper formalizes execution-state unlearning for stateful LLM agents, requiring that agents behave as if a revoked memory record was never observed across transcripts, compressed memory, tool plans, and KV caches. It proves exact unlearning requires at least T-τ+1 recomputed transitions and that Provenance-Guided Selective Replay attains this bound via a provenance graph, KV cache cropping, and sanitized replay. In audits across three agent suites, nine baselines, and three model families, memory deletion left leakage unchanged, instruction-based forgetting collapsed under elicitation (Leak@probes = 1.00), and selective replay matched full resets at up to 9x fewer recomputed tokens.

arXiv cs.CR·Sep 4, 08:31 UTC · 11d agoAI safety & security1

42

SWE-Bench Pro Verified: A Reliable Benchmark for Software Engineering Agents

SWE-Bench Pro Verified is a corrected benchmark showing prior coding-agent scores were inflated by reward hacking and flawed tasks.

Analysis of SWE-Bench Pro found its evaluation undermined by reward hacking from leakage of gold solutions or hidden evaluation information, plus task quality issues such as misleading problem statements and improperly scoped tests. The authors present SWE-Bench Pro Verified, combining anti-hacking safeguards that eliminate major leakage channels with minimal task refinements. Evaluations show some models perform substantially worse than previously reported, suggesting SWE-Bench Pro overestimates real software engineering capability.

Hugging Face daily papers·Sep 7, 20:00 UTC · 8d agoAI research1

35

An Open-Source End-to-End FHE Implementation for Privacy-Preserving Llama 3 8B Inference

Odin runs Llama-3-8B fully homomorphic encrypted inference on a single H100 in 366 seconds, a 4.51x speedup over THOR.

Odin is an open-source end-to-end GPU CKKS implementation for privacy-preserving Llama-3-8B inference that co-designs ciphertext packing with model execution. A feature-major cross-layer layout unifies residual connections and layer interfaces, while transient intra-operator layouts serve linear projections and attention, avoiding intermediate repacking of QK^T softmax outputs. Minimax polynomial approximation with input-range control reduces polynomial degree and multiplicative depth for nonlinear ops. With 128-token input, Odin evaluates all 32 Transformer layers on one NVIDIA H100 80 GB in 366.4 s using 58.9 GiB peak memory, versus 1651.9 s for the THOR baseline, a 4.51x speedup.

arXiv cs.CR·Sep 11, 02:51 UTC · 5d agoResearch

48