CS Paper Radar

Scaling Zero Knowledge UNSAT Verification via Normalized Chaining

Ashwin Karthikeyan, Ethan Kharitonov, Kuldeep S. Meel, Anwar Hithnawi

cs.CR cs.LO ·submitted 2026-09-16 19:28 UTC · v1

Abstract

Proofs of UNSAT are a standard primitive in formal verification and software assurance. In many real-world settings, the proof itself encodes proprietary or security-sensitive information, making public disclosure undesirable. Zero-knowledge certification of UNSAT addresses this tension: it enables a prover to convince a verifier that no satisfying assignment exists, without revealing anything about the underlying proof beyond its validity. Luo et al. recently introduced ZkUnsat, a protocol that achieves this goal by proving the validity of a weakened resolution proof in zero knowledge. ZkUnsat demonstrates the feasibility of zero-knowledge certification; however, its scalability to larger, real-world instances is constrained by substantial prover memory overhead, limiting its real-world applicability. Motivated by advances in UNSAT proof formats such as LRAT, which enable efficient plain-text verification, we present a preprocessing technique that improves the efficiency of ZkUnsat without introducing additional leakage. Our approach normalizes the proof so that each derived clause is justified by a resolution chain of fixed public length k. This eliminates chain-length leakage and reduces prover memory usage. With k = 16, our method certifies roughly 62% more instances than baseline ZkUnsat on the SAT 2002 competition benchmarks. Furthermore, for an equivalent number of certified instances, the memory footprint drops to under 25% of that required by the baseline.

Closest papers

Nearest neighbours by meaning across the whole index.

Bits Under ZK-LLM: Evaluating Zero-Knowledge-Friendly Quantization for Verifiable Private LLM Inference

cs.AI ·2026-09-29 ·Taeung Yoon, Yupeng Zhang, Xiaojing Liao
similarity 0.71
Abstract · 22 pages, 5 figures

Zero-knowledge proofs are emerging as a promising approach for enabling private, verifiable LLM governance and auditing, where regulators, users, and auditors need to verify claims about training-data usage or LLM inference-time behavior, while model providers must protect proprietary model parameters. However, despite the growing interest in ZK-LLMs, the understanding of ZK-friendly quantization remains limited. This gap matters because in the ZK setting, quantization directly shapes the arithmetic structure, constraint complexity, and proving cost of ZK inference. ZK protocols operate over finite fields and incur costs that depend heavily on the number and type of arithmetic operations, nonlinearities, and lookup constraints. Understanding ZK-friendly quantization is therefore essential for making ZK-LLMs practical. In this work, we present the first systematic study of ZK-friendly quantization for LLMs. We first formalize the definition of ZK-friendly quantization, capturing the properties required for ZK proof generation. We then evaluate nine language models, including Qwen2.5-14B and the mixture-of-experts model Qwen3-30B-A3B, across a broad design space of weight, activation, and nonlinear lookup table precision. Our results show that activation precision is substantially more sensitive than weight precision, while nonlinear lookup approximations can become the dominant source of utility degradation. Also, we identify RMSNorm inverse-square-root lookups as a recurring bottleneck in several large models and recover near-baseline utility by selectively increasing precision only at the bottleneck. Finally, we show that reducing bit-width or lookup-table size does not necessarily yield proportional end-to-end proving savings, showing that conventional low-bit quantization heuristics do not directly translate to ZK proving efficiency and motivating operator-aware precision selection.

0.21

Can Verifiable PIR Match the Online Efficiency of SimplePIR?

cs.CR ·2026-11-17 ·Xinxuan Zhang, Ruida Wang, Zirui Wang, Yuming Guo, Jikang Bai +3 more
top venue similarity 0.68
Abstract · Accepted for publication at the 2027 IEEE Symposium on Security and Privacy (IEEE S&P 2027)

Verifiable Private Information Retrieval (vPIR) ensures that a malicious server cannot return tampered database records, but it traditionally incurs significant overhead compared to classical PIR.Recent advancements, notably VeriSimplePIR, approach the online efficiency of SimplePIR by introducing a proof preprocessing phase and requiring only lightweight client-side online verification. However, this scheme relies on an additional Short Integer Solution (SIS) assumption and SIS-based commitments, which only support relaxed range proofs. Consequently, these schemes are forced to adopt significantly weaker parameter choices, resulting in additional online overhead. In this paper, we propose a novel vPIR protocol that employs a newly designed error-correcting code-based commitment scheme as the database digest. This approach (i)supports efficient proofs of linear relations, (ii) achieves precise range proofs and (iii) eliminates the reliance on the SIS assumption. Thus, our scheme successfully adopts parameter choices identical to those of SimplePIR. As a result, our vPIR protocol is the first to achieve exactly the same online communication and server computation costs as SimplePIR, while keeping online client computation nearly identical. Additionally, compared to VeriSimplePIR,our protocol reduces online communication and client-side computation by approximately 20%, and decreases online server-side computation by over 35%.

0.47

Incrementally Verifiable Oracle Aided Computation

cs.CR ·2026-11-10 ·Shafi Goldwasser, Yael Kalai
theory similarity 0.68
Abstract

Incrementally verifiable computation (IVC) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. Standard IVC schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. We construct IVC schemes for oracle-aided computations under the LWE assumption by first constructing SNARGs, and then extending them to IVC. We consider the following two settings, where below, k is the security parameter, n is the input length, and T, S, and Q are the time, space, and oracle-query bounds. 1. Robust computations: For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an eps-fraction of incorrect oracle answers, we construct privately verifiable SNARGs and IVC. Public parameters, private verification keys, and proofs have length poly(k ,S, log T,1/eps), and verification uses O(k/eps) oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable SNARGs and IVCs with public parameters of length o(n), and o(Q) verifier oracle queries. 2. Signed oracles: For oracles that digitally sign their query-answer pairs, we construct publicly verifiable SNARGs and IVC without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length poly(k,S,log T). For deterministic computations with oracle query and answer lengths poly(k,log T), we remove the dependence on S, obtaining public parameter and proof lengths poly(k,log T). All our constructions have adaptive completeness and soundness.

0.28

Performance Bottlenecks in Computing ZK Proofs on a GPU

cs.CR ·2026-11-06 ·Victor Carolino, Caleb Geren, Michael Kaufman, Maximilian Nussbaum, William Scott +1 more
similarity 0.68
Abstract · 8 pages

Zero-knowledge proofs allow one party to prove the correctness of a statement or execution of a computation while revealing no more than the statement of correctness itself. Recent use cases, such as AI datasets, suggest the need for faster proof generation over increasingly large constraint sets. This paper explores efforts in optimizing zero-knowledge proof generation, specifically PlonK, using GPUs, for applications that are not amenable to solution via incrementally verifiable computing (IVC). Our intention with this work is to improve ZK performance by introducing fundamental changes in the low-level architectural structure of proof generation. These changes affect performance curves for most current proof generation algorithms. In particular, this paper explores the trade-offs between increased parallelization on GPUs and the resultant memory management problems that occur due to this parallelization. We implement a parallelized PlonK in order to analyze these trade-offs and make arguments concerning the nature of data flows within the proving protocol. Our results lead us to consider multi-GPU environments to maximize performance for large circuit sizes. Such environments introduce issues of communication, efficient hardware management, data partition, and data transfers. This paper further discusses the use cases that motivate multi-GPU implementations, their cost models, and the use of remote direct memory access (RDMA) for data transfer among GPUs.

0.29

VerfGraph: Efficient Zero-Knowledge Verifiable Graph Query Evaluation System

cs.CR ·2026-11-03 ·Tianyi Ma, Yuncong Zhang, Yuanzhuo Yu, Boshi Yuan, Shi-Feng Sun
benchmark similarity 0.67
Abstract · 13 pages, 3 figures, 7 tables

Graph databases are often used to manage relationship-rich data, whose graph structure and attributes may be sensitive. In many applications, a database owner or a service provider evaluates queries over a private graph for a client. Because the graph cannot be fully disclosed and independently re-executing the query may be impractical, the client cannot directly verify the returned result. This creates a need for verifiable graph query evaluation that preserves data confidentiality. We present VerfGraph, a zero-knowledge system for verifiable graph query evaluation, which enables a client to verify that the query result was correctly computed over a committed graph data, without revealing private graph records or intermediate query values beyond the public inputs and what is implied by the query result. Building on the expansion-centric model introduced by the state-of-the-art zero-knowledge verifiable graph query evaluation system ZKGraph (ICDE'26), VerfGraph achieves more efficient and expressive zero-knowledge verifiable graph query evaluation by advancing design in two key ways. First, we propose novel operator-proof methods for core expansion and shortest-path operations that reduce costly sorting and comparison checks and eliminate edge canonicalization for bidirectional expansion. Furthermore, we introduce correctness proofs for count and weighted shortest-path operators, broadening the class of graph queries that can be verified. We evaluate VerfGraph using the LDBC Social Network Benchmark. Compared with ZKGraph on complex IC queries, VerfGraph achieves $33.9\times$-$59.7\times$ speedups in proof generation and reduces peak prover memory by factors of $4.5\times$-$6.6\times$, while maintaining millisecond-level verification and producing sub-MB proofs.

0.27

Apply All, Prove Once: Embedding Parameterized Lemmas in DRAT

cs.LO ·2026-11-17 ·Randal E. Bryant, Zachary Battleman, Marijn J. H. Heule
similarity 0.66
Abstract

The deletion-resolution-asymmetric-tautology (DRAT) proof format is widely used to express unsatisfiability proofs of Boolean formulas. Our DRATL format extends DRAT with parameterized lemmas, allowing a single proof to succinctly capture the common case where multiple instances of a pattern occur in a formula, differing in the identities and phases of the variables. Proofs expressed in DRATL can be hierarchical, with the proof of one lemma containing instantiations of others. Our elaborator program expands a DRATL proof containing multiple, nested lemmas into a standard DRAT proof. Most significantly, the elaboration yields compact proofs, where a single sequencing of the proof steps for each lemma covers all of its instantiations. Several case studies demonstrate that lemmas can provide a powerful method to generate short proofs for challenging problems.

0.30

Can AI Oversight Be Zero Knowledge?

cs.AI cs.CCcs.CR ·2026-10-01 ·Alessandro Chiesa, Ziyi Guan, Burcu Yildiz
theory similarity 0.66
Abstract

AI systems increasingly produce outputs from confidential data, such as a fitness-for-duty assessment from medical records or the predicted properties of a drug candidate from its secret structure. It is important to verify that such outputs are correct without revealing the underlying data. A recent line of work studies verification of AI outputs via interactive proofs and debate for oracle-aided computation, where correctness may depend on an oracle such as human judgment, a physical experiment, or the web. These works focus on verification by a verifier that runs much faster than the computation. However, such efficient verification is impossible for general oracle-aided computation, and these works therefore rely on additional assumptions. We focus instead on privacy: allowing the verifier to run in time polynomial in the computation, we ask whether interactive arguments for oracle-aided computation can be zero knowledge, so that the verifier learns nothing about the confidential data beyond the correctness of the output. We prove that, in general, they cannot. In the random oracle model, there are no zero-knowledge proofs for all oracle-aided computations, even if both the prover and the verifier are allowed to run much longer than the computation itself. The impossibility extends to debate, a canonical model for scalable oversight. On the positive side, we show that if the oracle attaches a cryptographic signature to each of its answers, then every oracle-aided computation can be verified in zero knowledge with an efficient prover and verifier, assuming only collision-resistant hash functions. Beyond privacy, this also gives an alternative approach to scalable oversight that relies neither on an honest opponent, as in debate, nor on the robustness of the computation, as in prior single-prover protocols.

0.19

A Multi-Prover Interactive Protocol for Certification of Resolution Refutations

cs.LO ·2026-11-10 ·Philipp Czerner, Adrian Krauss, Josia Pietsch, Javier Esparza
similarity 0.66
Abstract · 33 pages, 7 figures, extended version to CSL 2027 version

A resolution refutation of a SAT-formula $\varphi$ is an independently checkable certificate proving that $\varphi$ is unsatisfiable. However, the refutations of $\varphi$ can be exponentially larger than $\varphi$. So, a verifier needs worst-case exponential time in the size of $\varphi$ to check their correctness. We present ResCertify, an interactive probabilistic protocol in which the verifier interacts with multiple independent, untrusted provers (MIP) to check the refutation with very low probability of error. The verifier runs in linear time in the size of $\varphi$. The provers require time $\mathcal{O}(n \cdot |Φ|)$, where $Φ$ is the resolution refutation and $n$ is the number of variables of $\varphi$. If they can be trusted to act as a multilinear oracle on certain queries, a single prover suffices, and the runtime can be improved to $\mathcal{O}(|Φ|)$. Finally, while the focus of our work is theoretical, we also report on a proof-of-concept implementation of ResCertify.

0.40