We present a communication-efficient zero-knowledge proof of knowledge for the factorization of Blum integers, a special class of integers of the form n = p q , where p and q are distinct prime numbers satisfying p ≡ q ≡ 3 mod 4 and p ≃ q ≃ n . Existing protocols for proving such statements often incur significant communication costs, especially when demonstrating that p and q are of nearly equal size. We leverage the MPC-in-the-head paradigm, a cryptographic technique that transforms secure multi-party computation protocols into efficient zero-knowledge proof systems. In our protocol, the prover uses additive sharing of p and q over the integers. This approach simplifies proving the size relationship p ≃ q ≃ n and the congruence p ≡ q ≡ 3 mod 4 without requiring costly range proofs. To verify the primality of p and q , we employ the Boneh-Franklin biprimality test. Our protocol achieves a significant reduction in communication complexity. For a 2048-bit integer n and 128-bit security, we construct a proof as small as 12.3 KB, with prover and verifier computational costs comparable to existing protocols that require over 131 KB.
This is the NIST Threshold Call, calling for public submissions of multi-party threshold schemes, and other related crypto-systems, to support the United States’ National Institute of Standards and Technology (NIST) in gathering a public body of reference materials unadvanced cryptography. In a threshold scheme, a reference cryptographic primitive (e.g., signing, encryption, decryption, key generation) is computed in a distributed manner, while its private/secret key is or becomes secret-shared across various parties. The threshold schemes submitted in reply to this call will be interchangeable with a reference no threshold primitive of interest, in the sense that their outputs can be used interchangeably in a subsequent operation. The primitives of interest are organized into various categories, across two classes: Class N, for selected NIST-specified primitives; and Class S, for special primitives that are not specified by NIST but are threshold friendly or have useful functional features. The scope of Class S also includes fully homomorphic encryption, zero-knowledge proofs, and auxiliary gadgets. This document specifies submission phases, and the requirements for submitting a package, including a technical specification, a reference implementation, and a report on experimental evaluation. A subsequent phase of public analysis will support the elaboration of a characterization report, which may help assess new interests beyond the cryptographic techniques currently standardized by NIST, and may include recommendations for future processes.
Md. Sameeruddin Khan, Tom Chen, Mithileysh Sathiyanarayanan, Mohammed Mujeerulla · 5 authors
The Internet of Things (IoT) model is presented in this paper with multi-layer security based on the Lenstra-Lenstra-Lovasz (LLL) algorithm. End nodes for the Internet of Things include inexpensive gadgets like the Raspberry Pi and Arduino boards. It is not practical to run rigorous algorithms on them, as opposed to computer systems. Therefore, a cryptography procedure is required that could function on this IOT equipment. Bitcoins and Ethereum are examples of cryptocurrency and Ripple employs techniques such as elliptic curve digital signature, Elliptic-Curve Diffie-Hellman (ECDH), and algorithm to sign any cryptocurrency on SECP256k1 elliptic curves transactions. By using Lenstra-Lenstra-Lovasz on a real-world Bitcoin blockchain and applying it to multiple dimensions, such as nonce leakage and weak nonces across several elliptic curves with different bit sizes on a Raspberry Pi, we can demonstrate the security of elliptic curve cryptosystems. Public key encryption techniques are seriously threatened by the development of quantum computing. Therefore, employing lattice encryption with Nth Degree Truncated Polynomial Ring Units (NTRU-NTH) on the Bitcoin blockchain will increase the resistance of Bitcoin blocks to quantum computing assaults. The execution time taken on SECP256k1 is 131.7 Milli seconds comparatively faster than NIST-224P and NIST-384P.
Zero-knowledge proof (ZKP) is an important cryptographic tool that sees wide applications in real-world scenarios where privacy must be protected, including privacy-preserving blockchains and zero-knowledge machine learning. Existing ZKP acceleration approaches using GPUs, FPGAs, and ASICs focus only on classic protocols that rely on expensive elliptic curve arithmetics. Emerging ZKP protocols based on hash functions can greatly reduce the algorithmic complexity, but they also introduce much more diverse computation kernels that cannot be efficiently handled by a single accelerator chip if dedicated units for each kernel are used. Our approach is to leverage a unified hardware architecture that is able to efficiently support the common primitives in ZKP, and then use smart mapping strategies to flexibly map various kernels to such hardware while ensuring high resource utilization. We design UniZK as such a ZKP accelerator, with a systolic-array-based hardware architecture enhanced with extra local links and a new vector processing mode. We propose novel mapping strategies to support diverse kernels including number theoretic transforms, hash functions, and general polynomial computations. UniZK provides 97x and 46x speedups on average compared to the CPU and GPU implementations of the same protocols, and is also 840x faster than previous ZKP accelerators using different protocols.
Zero-knowledge proofs (ZKPs) are widely applied in digital economies, such as cryptocurrencies and smart contracts, for establishing trust and privacy between untrusted parties. Classical ZKPs rely on computational assumptions and are vulnerable to quantum attacks. While a recent advance suggests quantum-sound symmetric relativistic ZKPs for the graph three-coloring problem without computational assumptions, the high round complexity, which leads to unachievable runtime and overall randomness cost, renders them impractical for real-life deployment. To overcome this, we develop an efficient asymmetric relativistic ZKP protocol using relativistic bit commitments, and prove its quantum soundness by relating it to the nonlocal Clauser-Horne-Shimony-Holt (CHSH) game. Our protocol achieves a linear relationship between the round complexity and the number of edges, and thus significantly improves practical feasibility. In addition, we implement a proof-of-principle experiment which completes all interactive rounds in about 0.22 seconds and requires an overall randomness cost of 430.81 MB. Our work illustrates the powerful potential of integrating special relativity with quantum theory in trustless cryptography, paving the way for robust applications against quantum attacks in distrustful Internet environments. Zero-knowledge proofs can protect privacy online, but almost all current methods are vulnerable to quantum attacks. Here, the authors report an efficient relativistic protocol and experiment that resists quantum attacks and greatly reduces runtime, randomness cost and communication rounds.
Collision-resistant cryptographic hash functions (CRHs) are crucial for security, particularly for message authentication in Zero-knowledge Proof (ZKP) applications. However, traditional CRHs like SHA-2 or SHA-3, while optimized for CPUs, generate large circuits, rendering them inefficient in the ZK domain. Conversely, ZK-friendly hashes are designed for circuit efficiency but struggle on conventional hardware, often orders of magnitude slower than standard hashes due to their reliance on expensive finite field arithmetic. To bridge this performance gap, we present HashEmAll, a novel collection of FPGA-based realizations for three prominent ZK-friendly hashes: Griffin, Rescue-Prime, and Reinforced Concrete. Each offers distinct optimization profiles, with both area-optimized and latency-optimized variants available, allowing users to tailor hardware selection to specific application constraints regarding resource utilization and performance. Our extensive evaluation shows that latency-optimized HashEmAll designs outperform CPU implementations by at least $10 \times$, with the leading design achieving a $23 \times$ speedup. These gains are coupled with lower power consumption and compatibility with accessible FPGAs. Importantly, the highly parallel and pipelined architecture of HashEmAll enables significantly better practical scaling than CPU-based approaches towards building real-world ZKP applications, such as data commitments with Merkle Trees, by mitigating the hashing bottleneck for large trees. This highlights the suitability of HashEmAll for real-world ZKP applications involving large-scale data authentication. We also highlight the ability to translate the HashEmAll methodology to various ZK-friendly hash functions and different field sizes.
Delaram Kahrobaei, Ludovic Perret, Martina Vigorito
Abstract Bidoux and Gaborit introduced a new general technique to improve zero-knowledge ( ZK ) proof-of-knowledge ( PoK ) schemes for a large set of well-known post-quantum hard computational problems such as the syndrome decoding, the permuted kernel, the rank syndrome decoding, and the multivariate quadratic ( MQ ) problems. In particular, the authors’ idea in the study of Bidoux and Gaborit was to use the structure of these problems in the multi-instance setting to minimize the communication complexity of the resulting ZK PoK schemes. The security of the new schemes is then related to new hard problems. In this article, we focus on the new multivariate-based ZK PoK and the corresponding new underlying problem: the so-called <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} . We present a new efficient probabilistic algorithm for solving the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} which is polynomial-time if <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>m</m:mi> <m:mo>−</m:mo> <m:mi>n</m:mi> <m:mo>∈</m:mo> <m:mi>O</m:mi> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:math> m-n\in O\left(1) . We also present experimental results showing that the algorithm is efficient in practice.
At a time when post-quantum cryptography is more and more present in the cryptographic landscape, it is of great interest to find new hard problems on which we can rely. Here, we present a new problem, the vector space factorization problem, and use it to build a signature scheme. The idea of factorizing subspaces of a finite field is used in rank metric codes, most notably in the decoding of LRPCs. In this context, one of the subspaces is known to factorize. Factorizing without the knowledge of both subspaces appears in the signature scheme Murave, in which the rank support basis decomposition problem is introduced from a coding theory in rank metric point of view. In Bro's thesis, the SquareSpace problem is introduced, where one wants to find the 'square root' of a subspace. We generalize here this problem into the vector space factorization problem, which is the same as the rank support basis decomposition problem introduced in Murave, the difference being we do not look at it from a coding theory point of view, but really from a vector subspace one. We use it here to build a zero-knowledge proof of knowledge. The scheme uses the MPCitH paradigm, and especially the TCitH framework, which is an efficient way to build ZK proofs. We study the difficulty of solving the vector space factorization problem by detailing the combinatorial attacks on the problem, analyzing their complexity, and describing an algebraic model to solve the problem. We then explain the MPC protocol used to build the signature scheme. Finally, this construction allows us to obtain sizes of signature of 8.9 to 10.9 kB for the first security level defined by NIST, which is reasonable as MPC-in-the-Head signatures typically range from 2.5 kB for an MQ instance to 14 kB for lattice-based instances.
The number theoretic transform (NTT) provides a practical and efficient technique to perform multiplication of very large degree polynomials typically found in fully homomorphic encryption (FHE), lattice-based cryptography, and non-interactive succinct zero-knowledge proof systems such as zk-SNARK. In this paper, we focus on this aspect and present two robust algorithms for efficient NTT using readily available GPU cards as hardware accelerators. These algorithms are based on the radix-2 Cooley-Tukey (CT) and 4-Step techniques, which are rooted in classical FFT research. To this end, our algorithms leverage novel strategy to optimize memory access patterns adaptive to input size, which often is very large. Our approach: i) reduces and optimizes the number of accesses required for global memory for thread synchronization on the GPU device, and ii) systematically improves and enhances the use of spatial locality. We achieve this effect by carefully controlling parameters such as the number of kernels, thread block size and shape, and thread layout, which directly impact overall NTT performance. The proposed optimizations enable our NTT implementation to handle very large polynomial sizes up to 228, which are usually a limiting factor in existing approaches, and achieve remarkable performance. To the best of our knowledge, our proposed technique is unique and provides a recipe for selecting suitable configurable parameter combinations to achieve top performance for a given polynomial degree. Furthermore, we perform thorough experiments and empirically assess the performance of our proposed algorithms on three mainstream commercial GPU cards by NVIDIA. Finally, we demonstrate that our algorithms compare favorably and outperform an existing commercial-grade open-source implementation in this arena.
Joel Poncha Lemayian, Ghyslain Gagnon, Kaiwen Zhang, Pascal Giard
ABSTRACT Cryptocurrency blockchain networks safeguard digital assets using cryptographic keys, with wallets playing a critical role in generating, storing, and managing these keys. Wallets, typically categorized as hot and cold, offer varying degrees of security and convenience. However, they are generally software‐based applications running on microcontrollers. Consequently, they are vulnerable to malware and side‐channel attacks, allowing perpetrators to extract private keys by targeting critical algorithms, such as ECC, which processes private keys to generate public keys and authorize transactions. To address these issues, this work presents EthVault, the first hardware architecture for an Ethereum hierarchically deterministic cold wallet, featuring hardware implementations of key algorithms for secure key generation. Also, an ECC architecture resilient to side‐channel and timing attacks is proposed. Moreover, an architecture of the child key derivation function, a fundamental component of cryptocurrency wallets, is proposed. The design minimizes resource usage, meeting market demand for small, portable cryptocurrency wallets. FPGA implementation results validate the feasibility of the proposed approach. The ECC architecture exhibits uniform execution behavior across varying inputs, while the complete design utilizes only 27%, 7%, and 6% of LUTs, registers, and RAM blocks, respectively, on a Xilinx Zynq UltraScale+ FPGA.
Traditional identity authentication algorithms that rely on centralized trust authorities and plaintext identity verification often suffer from privacy leakage, key misuse, and single-point-of-failure risks. This study proposes a lightweight, privacy-preserving authentication algorithm based on elliptic curve and zero-knowledge proofs to address these issues. The proposed scheme introduces a random challenge and an anonymous verification mechanism during the authentication process to ensure both identity privacy and authentication security. While maintaining high levels of security and verifiability, the algorithm effectively reduces computational complexity and communication overhead. Experimental results demonstrate that the proposed method significantly outperforms traditional RSA and ECDSA in terms of authentication delay, communication cost, and security robustness. This approach is practical and scalable, offering a promising solution for secure authentication in environments with limited resource.
With the rapid development of the digital economy and the Internet of Things, identity authentication in resource-constrained environments faces challenges such as low efficiency and inadequate privacy protection. Addressing the high computational and communication overhead of traditional RSA and ECC authentication mechanisms, this study proposes an efficient identity authentication mechanism (AC-ZKP) based on algebraic curves and non-interactive zero-knowledge proofs (NIZK). This mechanism leverages algebraic curve group operations to achieve lightweight key management and employs zero-knowledge proofs to ensure information concealment and anti-forgery during identity verification. The paper conducts a systematic study across four dimensions: system modeling, algorithm design, security analysis, and performance evaluation. Experimental results demonstrate that while maintaining 128-bit security strength, the AC-ZKP mechanism reduces authentication latency by approximately 44% and communication overhead by about 40%. It also exhibits strong scalability and resistance to attacks, significantly outperforming traditional ECC schemes. These findings provide a viable solution for lightweight, high-security identity authentication in IoT, edge computing, and cross-border data exchange environments.
Zero-Knowledge Proofs (ZKPs) are public key cryptosystem that enables to demonstrate that a statement which is known by them is correct without revealing the same to the verifier. ZKPs have moved in modern cryptographic systems, blockchain applications, decentralized finance (DeFi) and identity authentication systems. This paper explores the evolution of ZKPs and their significance as in secure and privacy preserving. We classify ZKPs into two groups namely interactive and non-interactive, discussing prominent protocols such as zk-SNARKs, zk-STARKs, Bulletproofs, PLONK, and Halo2. Each approach has advantages as efficiency, proof size, and computational overhead. The study further examines the multitude of applications of ZKPs, as privacy-enhanced blockchain transactions, zero-knowledge rollups for scalability, decentralized identity management, secure voting mechanisms, and regulatorycompliant financial systems. With advantages, possible limitations in scalability, lack of standardization, and vulnerabilities to emerging quantum computing threats. Due to the restrictions, hardware acceleration through GPUs and others, presents promising solutions, while new protocols such as PLONK and Halo2 seek to optimize performance to earlier developed solutions. Finally, we discuss the future trajectory of ZKPs. This review aims to provide an understanding of the current state of ZKP research, its applications, and the key challenges that need to be addressed to facilitate broader adoption.
Katharina Koschatko, Reinhard Lüftenegger, Christian Rechberger
Gröbner basis cryptanalysis of hash functions and ciphers, and their underlying permutations, has seen renewed interest recently. Anemoi (Crypto’23) is a permutation-based hash function that is efficient for a variety of arithmetizations used in zero-knowledge proofs. In this paper, exploring both theoretical bounds as well as experimental validation, we present new complexity estimates for Gröbner basis attacks on the Anemoi permutation over prime fields.We cast our findings in what we call the six worlds of Gröbner basis cryptanalysis. As an example, keeping the same security arguments of the design, we conclude that at least 41 instead of 37 rounds would need to be used for 256-bit security, whereby our suggestion does not yet include a security margin.
Open access
Polynomial and algebraic computation
Cryptography and Residue Arithmetic
Mathematics, Computing, and Information Processing
Shahzad Ahmad Butt, Benjamin Reynolds, V. Ramamurthy, Xiao Xiao · 8 authors
Zero-Knowledge Proofs (ZKPs) have emerged as an important cryptographic technique allowing one party (prover) to prove the correctness of a statement to some other party (verifier) and nothing else. ZKPs give rise to user's privacy in many applications such as blockchains, digital voting, and machine learning. Traditionally, ZKPs suffered from poor scalability but recently, a sub-class of ZKPs known as Zero-knowledge Succinct Non-interactive ARgument of Knowledges (zk-SNARKs) have addressed this challenge. They are getting significant attention and are being implemented by many public libraries. In this paper, we present a novel scalable architecture that is suitable for accelerating the zk-SNARK prover compute on FPGAs. We focus on the multi-scalar multiplication (MSM) that accounts for the majority of computation time spent in zk-SNARK systems. The MSM calculations extensive rely on modular arithmetic so highly optimized Intel IP Libraries for modular arithmetic are used. The proposed architecture exploits the parallelism inherent to MSM and is implemented using the Intel OneAPI framework for FPGAs. Our implementation runs 110x-150x faster compared to reference software library, uses a generic curve form in Jacobian coordinates and is the first to report FPGA hardware acceleration results for BLS12-381 and BN128 family of elliptic curves.
Zero-knowledge proof (ZKP) is an attractive cryptographic paradigm that allows a party to prove the correctness of a given statement without revealing any additional information. It offers both computation integrity and privacy, witnessing many celebrated deployments, such as computation outsourcing and cryptocurrencies. Recent general-purpose ZKP schemes, e.g., zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK), suffer from time-consuming proof generation, which is mainly bottlenecked by the large-scale number theoretic transformation (NTT) and multi-scalar point multiplication (MSM). To boost its wide application, great interest has been shown in expediting the proof generation on various platforms like GPU, FPGA and ASIC.So far as we know, current works on the hardware designs for ZKP employ two separated data-paths for NTT and MSM, overlooking the potential of resource reusage. In this work, we particularly explore the feasibility and profit of implementing both NTT and MSM with a unified and high-performance hardware architecture. For the crucial operator design, we propose a dual-precision, load-balanced and fully-pipelined Montgomery multiplier (LBFP MM) by introducing the new mixed-radix technique and improving the prior quotient-decoupled strategy. Collectively, we also integrate orthogonal ideas to further enhance the performance of LBFP MM, including the customized constant multiplication, truncated LSB/MSB multiplication/addition and Karatsuba technique. On top of that, we present the unified, scalable and highperformance hardware architecture that conducts both NTT and MSM in a versatile pipelined execution mechanism, intensively sharing the common computation and memory resource. The proposed accelerator manages to overlap the on-chip memory computation with off-chip memory access, considerably reducing the overall cycle counts for NTT and MSM.We showcase the implementation of modular multiplier and overall architecture on the BLS12-381 elliptic curve for zk-SNARK. Extensive experiments are carried out under TSMC 28nm synthesis and similar simulation set, which demonstrate impressive improvements: (1) the proposed LBFP MM obtains 1.8x speed-up and 1.3x less area cost versus the state-of-the-art design; (2) the unified accelerator achieves 12.1x and 5.8x acceleration for NTT and MSM while also consumes 4.3x lower overall on-chip area overhead, when compared to the most related and advanced work PipeZK.
Pedro García-Cereijo, Gabriel Fernández-Blanco, Paula Fraga‐Lamas, Tiago M. Fernández‐Caramés
The deterministic nature of blockchains presents a significant challenge to pseudo-random number generation. Conventional seed-based random number generation methods may not be suitable for deterministic environments as they may be predictable and susceptible to attacks. To address this challenge, this paper proposes the integration of a pseudo-random number generation oracle for the nodes of an Ethereum network. Such an oracle acts as an external provider of pseudo-random numbers, generating random data by using the Fortuna algorithm, which can be used by smart contracts and decentralized applications on the blockchain. However, the integration of an oracle raises additional security and reliability concerns as it relies on a central node that impairs the decentralization of the blockchain and depends on the ability of the oracle to provide unpredictable and non-tampered pseudo-random numbers. The presented implementation can be used in different sectors, such as games of chance, random selection and other scenarios where randomness is essential to guarantee fairness and security. Thus, the integration of a pseudo-random number generation oracle into a Ethereum network can significantly improve the functionality and security of such decentralized applications. In order to show the performance of the proposed system, a comparison is presented that evaluates the security improvements with respect to traditional randomization methods within smart contracts.
Relevance: Starting with the invention of the Internet, the world began to change rapidly, and the pace of change is increasing, so the problem of data storage and processing is becoming more and more relevant. The ZK-STARK protocol is a new cryptographic zero-knowledge proof protocol that is not yet widely used in practice and allows you to check a message or a transaction on the blockchain network for authenticity without reproducing it completely. At the moment, gaps and problems related to this protocol are identified: computational complexity, possible poor compatibility with other protocols, and resistance to attacks from quantum computers. Therefore, the paper aims to supplement the coverage of the problem associated with computational complexity and to propose solutions to this problem. Purpose: on the basis of the theoretical implementation of the first stage named Arithmetization of the ZK-STARK protocol, to test its software implementation in order to provide recommendations on its most computationally efficient version. Research methods: mathematical statements on interpolation theory, group theory, number theory; information on Fibonacci numbers; information on the Euler function; generating element of a group; cyclic groups; Lagrange interpolation polynomial and the sequence of calculations of Arithmetization; Visual Studio 2022 programming environment, C++ programming language, NTL library, Microsoft Excel. Results of work: The result of the work is the theoretical implementation of the first stage of the ZK-STARK protocol and the effectiveness testing of the first stage, and providing recommendations for its most effective version. Conclusion: Testing has shown that the practical implementation of the Arithmetization based on the inverse fast Fourier transform has a time complexity , that is in times less than the time complexity of the Arithmetization based on inverse matrices method and Gaussian method for interpolation, that speeds up the work of Arithmetization of the ZK-STARK protocol.
Open access
Cybersecurity and Information Systems
Advanced Computational Techniques in Science and Engineering
Collision-resistant, cryptographic hash (CRH) functions have long been an integral part of providing security and privacy in modern systems. Certain constructions of zero-knowledge proof (ZKP) protocols aim to utilize CRH functions to perform cryptographic hashing. Standard CRH functions, such as SHA2, are inefficient when employed in the ZKP domain, thus calling for ZK-friendly hashes, which are CRH functions built with ZKP efficiency in mind. The most mature ZK-friendly hash, MiMC, presents a block cipher and hash function with a simple algebraic structure that is well-suited, due to its achieved security and low complexity, for ZKP applications. Although ZK-friendly hashes have improved the performance of ZKP generation in software, the underlying computation of ZKPs, including CRH functions, must be optimized on hardware to enable practical applications. The challenge we address in this work is determining how to efficiently incorporate ZK-friendly hash functions, such as MiMC, into hardware accelerators, thus enabling more practical applications. In this work, we introduce AMAZE, a highly hardware-optimized open-source framework for computing the MiMC block cipher and hash function. Our solution has been primarily directed at resource-constrained edge devices; consequently, we provide several implementations of MiMC with varying power, resource, and latency profiles. Our extensive evaluations show that the AMAZE-powered implementation of MiMC outperforms standard CPU implementations by more than 13$\times$. In all settings, AMAZE enables efficient ZK-friendly hashing on resource-constrained devices. Finally, we highlight AMAZE's underlying open-source arithmetic backend as part of our end-to-end design, thus allowing developers to utilize the AMAZE framework for custom ZKP applications.
Xudong Zhu, Haoqi He, Zhengbang Yang, Yi Deng · 6 authors
Zero-knowledge proof (ZKP) is a cryptographic primitive that enables a prover to convince a verifier that a statement is true, without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities, its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been widely deployed in various privacypreserving applications such as cryptocurrencies and verifiable computation. Although state-of-the-art zkSNARKs are highly efficient for the verifier, the computational overhead for the prover is still orders of magnitude too high to warrant use in many applications. This overhead arises from several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and especially the multi-scalar multiplication (MSM) which constitutes the largest proportion. Therefore, further efficiency improvements are needed.In this paper, we focus on comprehensive optimization of running time and storage space required by the MSM algorithm on GPUs. Specifically, we propose a novel, modular and adaptive parameter configuration technique—elastic MSM to enable us to adjust the scale of MSM according to our own wishes by performing a corresponding amount of preprocessing. This technique enables us to fully unleash the potential of various efficient parallel MSM algorithms. We have implemented and tested elastic MSM over three prevailing parallel Pippenger algorithms on GPUs. Across various preprocessing space limitations (across various MSM scales), our constructions achieve up to about 1.90×, 1.08× and 1.36× (2.58×, 1.39× and 1.91×) speedup versus three state-of-the-art parallel Pippenger algorithms on GPUs, respectively.From another perspective, elastic MSM could also be regarded as a preprocessing technique over the well-known Pippenger algorithm, which is modular and could be used to accelerate almost all the most advanced parallel Pippenger algorithms on GPUs. Meanwhile, elastic MSM provides an adaptive trade-off between the running time and the extra storage space needed by parallel Pippenger algorithms on GPUs. This is the first preprocessing technique to retain the improved MSM computation brought by preprocessing under varying storage space limitations. Specifically, across various preprocessing space limitations (across various MSM scales), our constructions achieve up to about 192× and 223× (159× and 174×) speedup versus two state-ofthe- art preprocessing parallel Pippenger algorithms on GPUs, respectively.