CS Paper Radar

SRE: Accelerating Zero-Knowledge Proofs via Scalar Redundancy Elimination in Multi-Scalar Multiplication

Jonathan Ku, Guanglei Zhou, Jiawen Wu, Junyao Zhang, Haoxuan Shan, Changchun Zhou, JV Rajendran, Yiran Chen, Hai Li

cs.CR ·submitted 2026-10-20 01:00 UTC · v1

Abstract

Multi-Scalar Multiplication (MSM) is a fundamental cryptographic operation used in Elliptic Curve Cryptography (ECC) across a wide range of applications. Its computation involves intensive elliptic curve point additions (PADD). MSM plays a critical role in cryptographic primitives such as polynomial commitments and zero-knowledge proofs (ZKPs), where it often becomes the runtime bottleneck. Consequently, optimizing MSM is an active area of research focused on reducing computational complexity and accelerating performance. The current state-of-the-art algorithm for large-scale MSM is Pippenger's bucket method, which consists of three main steps: point merging, bucket aggregation, and window aggregation. Among these, the point merging step is the primary performance bottleneck. Our work targets this major computational bottleneck. To reduce operations for practical applications, we propose a novel Scalar Redundancy Elimination (SRE) algorithm with three approaches: a vanilla array-based approach, a list-based greedy approach, and a list-based exhaustive approach, all incorporating an early stopping technique. Depending on the use case, these strategies can be integrated into our modified MSM algorithm, which is based on Pippenger's bucket method. As a result, our proposed MSM algorithm, enhanced with the SRE technique, incurs less than $3\%$ additional search time, while reducing the number of operations by $25\%$, leading to a $30\%$ speedup in runtime compared to the standard Pippenger's bucket method. This translates to a $10 \sim 20\%$ runtime reduction in various ZKP systems that rely heavily on MSM.

Closest papers

Nearest neighbours by meaning across the whole index.

Locus: A Framework for Exploring and Optimizing Point Addition Hardware for Zero-Knowledge Proofs

cs.AR cs.CR ·2026-09-16 ·Gaurav Kuwar, Alhad Daftardar, Jianqiao Mo, Siddharth Garg, Brandon Reagen
publishedcode/data similarity 0.72
Abstract · 9 pages, 10 figures, 9 tables. Accepted at the IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2026)

Zero-Knowledge Proofs (ZKPs) are critical for privacy-preserving and verifiable computation, but their cryptographic primitives impose high computational overheads. One such primitive is point addition (PADD) on elliptic curves. Several prior works have implemented PADDs in hardware, but only for a few specific elliptic curves and design points, leaving a large design space unexplored, and lacking systematic guidance on hardware design trade-offs. To address this gap, we present Locus, a framework dedicated to optimizing and exploring point addition hardware. Given the parameters of any elliptic curve in a supported equation form, Locus automatically generates ASIC and FPGA implementations of PADD, enabling systematic exploration of the PADD design space. Using Locus, we conduct the first comprehensive hardware-focused study of PADD designs, exploring trade-offs over 1,000 design points. On a 12nm technology node, our framework produces PADD designs that yield a $2.71\times$ geomean speedup and $3.11\times$ geomean area reduction compared to prior ASICs, $34.67\times$ geomean speedup over CPU, and $3.15\times$ geomean speedup on end-to-end proof generation when integrated into a prior ZKP accelerator at iso-area. Locus is available at https://github.com/cryptolets/cryptolets/tree/locus.

0.58

ZKPU: Zero-Knowledge Processing Unit for Heterogeneous Workloads

cs.AR ·2026-10-20 ·Jonathan Ku, Changchun Zhou, Jiawen Wu, Sangouk Jeon, Cong Guo +6 more
similarity 0.63
Abstract

Zero-knowledge proofs (ZKPs) have become a fundamental building block for privacy-preserving computation, blockchain systems, and verifiable machine learning. Modern ZKP protocols span two distinct families: curve-based protocols, which rely on large finite-field arithmetic, and hash-based protocols, which operate over native 64-bit fields. Existing hardware accelerators are specialized for one protocol family because they are built on operand-scanning Montgomery multiplication, resulting in fixed-width datapaths, poor utilization across heterogeneous operand widths, and limited scalability. This paper presents \emph{ZKPU}, a Zero-Knowledge Processing Unit for heterogeneous ZKP workloads. ZKPU introduces a new compute paradigm by co-designing finely integrated product scanning (FIPS) Montgomery multiplication with a reconfigurable Twin Systolic Fabric (TSF), enabling modular multiplication at arbitrary widths in 64-bit increments. Combined with a fine-grained Deque buffer, on-chip twiddle-factor generator, and memory-efficient MSM preprocessing strategy, ZKPU provides a unified architecture for both curve-based and hash-based protocols. Evaluation using Groth16 and Plonky2 shows that ZKPU achieves up to $144\times$ speedup for NTT, $13.6\times$ for MSM, and approximately $7.2\times$ end-to-end application speedup over state-of-the-art accelerators, while being the first architecture to efficiently support both protocol families on a single reconfigurable hardware platform.

0.27

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

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

cs.CR cs.IT ·2026-10-20 ·Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik, Han Mao Kiah
similarity 0.58
Abstract

At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.

0.22

Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

cs.CR ·2026-11-12 ·Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães +1 more
publishedhot direction similarity 0.57
Abstract · Full version of a paper accepted at ASIACRYPT 2026. 92 pages

An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring $R_q = \mathbb{Z}_q[Y]/(Y^N+1)$, and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large $O(N)$ overhead in range proofs, and the lack of an explicit method for efficient -- sublinear in circuit size -- verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for $R_q$ that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the $O(N)$ overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.

0.70

Shedding Light on Complex Bitcoin Mixer Transactions: 67-Fold Reduction in Unclassified Cases

cs.CR ·2026-08-22 ·Nikolay Larionov, Yekaterina Smolenkova, Yury Yanovich
code/data similarity 0.57
Abstract

Bitcoin's Unspent Transaction Output (UTXO) model enables public analysis of fund flows, but users often merge transactions into Shared Send Mixers (SSMs) to obscure these flows. Untangling SSMs to recover original subtransactions is an NP-complete problem. While a practical untangling algorithm exists, it fails to classify 1.4% of SSM transactions due to computational time limits. This paper introduces four novel heuristics that exploit structural weaknesses in real-world SSM transactions to resolve these timeout cases: preemptive grouping, connectable singleton, ambiguous pairing, and knapsack fallback. We provide theoretical proofs validating each heuristic and integrate them into an optimized pipeline. Applied to timeout transactions, our approach classifies 98.5% of previously unresolved cases, reducing the overall unclassified transaction rate from 1.4% to 0.021% of all SSM transactions. Our open-source implementation and comprehensive evaluation on the complete Bitcoin blockchain demonstrate that the heuristics effectively untangle previously intractable transactions, enabling more accurate flow analysis and deeper structural insights into cryptocurrency transaction patterns.

0.46

Exposing SIMD Parallelism in SQIsign: An AVX-512 Implementation

cs.CR ·2026-08-14 ·Weize Wang, Chutong Wang, Yu Wu, Qifan Xue, Jieyu Zheng +1 more
similarity 0.56
Abstract

Modern isogeny-based cryptosystems spend much of their running time in finite-field, elliptic-curve, and higher-dimensional isogeny arithmetic. Exploiting SIMD parallelism is nontrivial: routines such as Montgomery ladders contain loop-carried dependencies, while point, pairing, and theta-coordinate formulas expose only irregular fine-grained parallelism. We show that substantial SIMD parallelism can be recovered by reorganizing the arithmetic dependency graphs of higher-level primitives rather than vectorizing field multiplication in isolation. We develop an end-to-end AVX-512IFMA implementation of SQIsign in which data remain in a radix-$2^{51}$ vector representation across most of the curve-side computation. Our redesign includes projective xDBLADD schedules, batched point doubling in several coordinate systems, a vectorized biscalar ladder, fused cubical-arithmetic pairing steps, and batched one- and two-dimensional isogeny evaluation. Relative to the reference C implementation, we achieve end-to-end speedups of $1.76\times$, $1.71\times$, and $3.18\times$ for key generation, signing, and verification at NIST level~I; combined with Qlapoti, key-generation and signing speedups rise to $2.90\times$ and $2.69\times$. We further apply the same backend and methodology to CORAL, a recent isogeny group action for post-quantum non-interactive key exchange based on two-dimensional $2$-isogenies. Across five parameter sets, this yields $1.28$--$1.40\times$ speedups for key generation and $1.92$--$2.46\times$ for shared-key computation. These results provide cross-scheme evidence that algorithm-level SIMD scheduling is a reusable optimization dimension for higher-dimensional isogeny cryptography.

0.04

TRACE: Traversal and Reasoning Algebraic Computing Engine for Formal Hardware Verification

cs.AR ·2026-08-17 ·Jan Kleinekathöfer, Lennart Weingarten, Kamalika Datta, Rolf Drechsler
hot direction similarity 0.55
Abstract

Modern hardware verification of complex circuits relies heavily on the efficiency of formal methods. For complex arithmetic circuits in particular Symbolic Computer Algebra (SCA) engines which represent pseudo-boolean functions using polynomials are crucial. As circuit complexity grows in the age of AI, verification of arithmetic primitives, including Multiplication, Addition, Multiply-Accumulate (MAC), becomes a computational bottleneck. To address this, we introduce TRACE (Traversal and Reasoning Algebraic Computing Engine), a highly efficient framework designed to investigate the intersection of traversal strategies and proof efficiency. Unlike existing SCA tools which are mainly limited to multipliers, TRACE offers a flexible framework for researchers to analyze memory usage and verification time across a wide range of arithmetic circuits (adder, multiplier and MAC). To overcome the state-explosion problem inherent in polynomial expansion, the engine incorporates advanced reduction techniques, including optimized traversal strategies, conflict removal, and polarity-based optimization for compact symbolic representations. Our experimental results show that for optimized MAC, for the first time, TRACE was able to verify previously unverifiable circuits

0.35