Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs). Experimental results show that MSMAC achieves up to 328X and 1.96X speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79X. On 4 FPGAs, MSMAC performs 1,261X faster than a single CPU core.
Hao Zhou, Changxu Liu, Lan Yang, Li Shang · 5 authors
Recently, there has been increased emphasis on privacy-preserving computation technologies, such as homomorphic encryption (HE) and zero-knowledge proof (ZKP). Modular multiplication is a critical component for both HE and ZKP. Variable bit-width is a must for many applications of privacy-preserving computation, due to variable bit-width requirements for different cryptography schemes. However, the majority of modular multipliers that support variable bit-width configurations exhibit relatively low throughput. This work presents a fully pipelined Montgomery modular multiplier with variable bit-width support. Truncated multipliers are introduced to reduce the resources of modular multipliers in our approach. In order to meet different bit-width requirements, the proposed modular multiplier can be dynamically reconfigured. The proposed design can support widely used bit-width configurations, specifically, 384-bit, 256-bit, and 128-bit. 256-bit and 128-bit modes support parallel computation of 2 and 6 sets of operands, respectively. Compared with existing variable bit-width modular multipliers, the proposed reconfigurable modular multiplier significantly improves the throughputs with even lower resources.
Zero-knowledge proof is a cryptographic primitive that allows for the validation of statements without disclosing any sensitive information, foundational in applications like verifiable outsourcing and digital currency. However, the extensive proof generation time limits its widespread adoption. Even with GPU acceleration, proof generation can still take minutes, with Multi-Scalar Multiplication (MSM) accounting for about 78.2% of the workload. To address this, we present DistMSM, a novel MSM algorithm tailored for distributed multi-GPU systems. At the algorithmic level, DistMSM adapts Pippenger's algorithm for multi-GPU setups, effectively identifying and addressing bottlenecks that emerge during scaling. At the GPU kernel level, DistMSM introduces an elliptic curve arithmetic kernel tailored for contemporary GPU architectures. It optimizes register pressure with two innovative techniques and leverages tensor cores for specific big integer multiplications. Compared to state-of-the-art MSM implementations, DistMSM offers an average 6.39× speedup across various elliptic curves and GPU counts. An MSM task that previously took seconds on a single GPU can now be completed in mere tens of milliseconds. It showcases the substantial potential and efficiency of distributed multi-GPU systems in ZKP acceleration.
Biscuit is a recent multivariate signature scheme based on the MPC-in-the-Head paradigm. It has been submitted to the NIST competition for additional signature schemes. Signatures are derived from a zero-knowledge proof of knowledge of the solution of a structured polynomial system. This extra structure enables efficient proofs and compact signatures. This short note demonstrates that it also makes these polynomial systems easier to solve than random ones. As a consequence, the original parameters of Biscuit failed to meet the required security levels and had to be upgraded.
Jonathan Ku, Junyao Zhang, Haoxuan Shan, Saichand Samudrala · 9 authors
Elliptic curve cryptography (ECC) is widely used in security applications such as public key cryptography (PKC) and zero-knowledge proofs (ZKP). ECC is composed of modular arithmetic, where modular multiplication takes most of the processing time. Computational complexity and memory constraints of ECC limit the performance. Therefore, hardware acceleration on ECC is an active field of research. Processing-in-memory (PIM) is a promising approach to tackle this problem. In this work, we design ModSRAM, the first 8T SRAM PIM architecture to compute large-number modular multiplication efficiently. In addition, we propose R4CSA-LUT, a new algorithm that reduces the cycles for an interleaved algorithm and eliminates carry propagation for addition based on look-up tables (LUT). ModSRAM is co-designed with R4CSA-LUT to support modular multiplication and data reuse in memory with 52% cycle reduction compared to prior works with only 32% area overhead.
Ruben De Smet, Robrecht Blancquaert, Tom Godden, Kris Steenhaut · 5 authors
Elliptic curve cryptography is a widely deployed technology for securing digital communication. It is the basis of many cryptographic primitives such as key agreement protocols, digital signatures, and zero-knowledge proofs. Fast elliptic curve cryptography relies on heavily optimised modular arithmetic operations, which are often tailored to specific micro-architectures. In this article, we study and evaluate optimisations of the popular elliptic curve Curve25519 for ARM processors. We specifically target the ARM NEON single instruction, multiple data (SIMD) architecture, which is a popular architecture for modern smartphones. We introduce a novel representation for 128-bit NEON SIMD vectors, optimised for SIMD parallelisation, to accelerate elliptic curve operations significantly. Leveraging this representation, we implement an extended twisted Edwards curve Curve25519 back-end within the popular Rust library "curve25519-dalek". We extensively evaluate our implementation across multiple ARM devices using both cryptographic benchmarks and the benchmark suite available for the Signal protocol. Our findings demonstrate a substantial back-end speed-up of at least 20% for ARM NEON, along with a noteworthy speed improvement of at least 15% for benchmarked Signal functions.
Nicholas Brandt, Dennis Hofheinz, Michael Klooß, Michael Reichle
We construct the first blind signature scheme that achieves all of the following properties simultaneously: – it is tightly secure under a standard (i.e., non-interactive, non-q-type) computational assumption, – it does not require pairings, – it does not rely on generic, non-black-box techniques (like generic NIZK proofs). The third property enables a reasonably efficient solution, and in fact signatures in our scheme comprise 10 group elements and 29 Zp-elements. Our scheme starts from a pairing-based non-blind signature scheme (Abe et al., JoC 2023), and uses recent techniques of Chairattana-Apirom, Tessaro, and Zhu (CRYPTO 2024) to replace the pairings used in this scheme with non-interactive zero-knowledge proofs in the random oracle model. This conversion is not generic or straightforward (also because the mentioned previous works have converted only significantly simpler signature schemes), and we are required to improve upon and innovate existing techniques in several places. As an interesting side note, and unlike previous works, our techniques only require a non-programmable random oracle, and our signature scheme achieves predicate blindness (which means that the user can prove state ments about the signed message during the signing process).
Threshold signatures, notably ECDSA, are fundamental for securing decentralized applications.Their non-linear structure poses challenges in distributed signing, often tackled by pairwise multiplicative-to-additive share conversion, leading to O(n) communication and O(n 2 ) verification costs for each of n signers.Moreover, most schemes lack robustness, necessitating a complete restart upon fault.A pioneering work by Wong et al. (NDSS '23) still requires rolling back to the preceding round to resume signing after another round to convince all other signers.We revisit secure multiparty computation from threshold linearly homomorphic encryption (LHE).Realizing its public verifiability and fault recovery, we encompass two technical contributions to Castagnos-Laguillaumie LHE (CT-RSA '15): a 2-round robust distributed key generation (DKG) protocol in the dishonest majority setting and an accompanying zero-knowledge proof allowing extraction in an unknown-order group.We extend the DKG with dual-code-based verification (ACNS '17), upgrading its O(tn 2 )-cost private verifiability to an O(n 2 ) public one.Built on our DKG, we present the first threshold ECDSA protocol with O(1) communication and O(n) verification perparty costs while matching the lowest round complexity of nonrobust schemes (CCS '20).Empirically, we halve the computation and communication costs of the signing phase compared to stateof-the-art robust threshold ECDSA (NDSS '23).We also illustrate the versatility of our techniques with an improved threshold extension (IEEE S&P '23) of BBS+ signatures (IEEE Syst.J. '13).
Lennart Braun, Guilhem Castagnos, Ivan Damgård, Fabien Laguillaumie · 7 authors
We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO ‘23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.
Zero-knowledge proof (ZKP) systems have surged attention and held a fundamental role in contemporary cryptography. Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) protocols dominate the ZKP usage, implemented through arithmetic circuit programming paradigm. However, underconstrained or overconstrained circuits may lead to bugs. The former refers to circuits that lack the necessary constraints, resulting in unexpected solutions and causing the verifier to accept a bogus witness, and the latter refers to circuits that are constrained excessively, resulting in lacking necessary solutions and causing the verifier to accept no witness. This article introduces a novel approach for pinpointing two distinct types of bugs in ZKP circuits. The method involves encoding the arithmetic circuit constraints to polynomial equation systems and solving them over finite fields by the computer algebra system . The classification of verification results is refined, greatly enhancing the expressive power of the system. A tool, AC 4 , is proposed to represent the implementation of the method. Experiments show that AC 4 demonstrates an increase in the solved rate, showing a 36.7% improvement over Picus and CIVER, and a slight improvement over halo2-analyzer, a checker for halo2 circuits. Within a solvable range, the checking time has also exhibited noticeable improvement, demonstrating a magnitude increase compared to previous efforts.
Background. To ensure the protection of the biometric access control system used in unsecured communication channels, it is necessary to exclude the storage and transfer, transfer of biometric data as well as sequences generated on their basis. The paper proposes a cryptographic protocol of two-factor authentication with the zero-knowledge over the extended field GF(2m) on elliptic curves using biometric data and the private key of the user. Objective. The aim of the article is to develop a cryptographic protocol for zero-knowledge two-factor authentication based on elliptic curves using biometric data and the user’s private key, which allows increasing cryptographic strength and reducing the duration of the authentication process. Methods. The process of implementing zero-knowledge proof protocols is as follows: one user (proofer) can convince another user (verifier) that he has some secret without disclosing the secret itself. Results. A cryptographic protocol for two-factor authentication with zero-knowledge over the extended field GF(2m) of elliptic curves using user biometric data is proposed, which significantly reduces the size of the protocol parameters and increases cryptographic strength (computational complexity of the breaking). There is no leakage of private key information and biometric data of the user during the execution of the zero-knowledge proof protocol. Conclusions. The implementation of a cryptographic protocol with zero-knowledge proof two-factor authentication based on elliptic curves allows significantly reducing the size of protocol parameters and increasing the cryptographic strength (computational complexity of the breaking).
Ірина Стрелковська, Олексій Онацький, Лариса Григорівна Йона
Background. To ensure the protection of the biometric access control system used in unsecured communication channels, it is necessary to exclude the storage and transfer, transfer of biometric data as well as sequences generated on their basis. The paper proposes a cryptographic protocol of two-factor authentication with the zero-knowledge over the extended field GF(2m) on elliptic curves using biometric data and the private key of the user. Objective. The aim of the article is to develop a cryptographic protocol for zero-knowledge two-factor authentication based on elliptic curves using biometric data and the user’s private key, which allows increasing cryptographic strength and reducing the duration of the authentication process. Methods. The process of implementing zero-knowledge proof protocols is as follows: one user (proofer) can convince another user (verifier) that he has some secret without disclosing the secret itself. Results. A cryptographic protocol for two-factor authentication with zero-knowledge over the extended field GF(2m) of elliptic curves using user biometric data is proposed, which significantly reduces the size of the protocol parameters and increases cryptographic strength (computational complexity of the breaking). There is no leakage of private key information and biometric data of the user during the execution of the zero-knowledge proof protocol. Conclusions. The implementation of a cryptographic protocol with zero-knowledge proof two-factor authentication based on elliptic curves allows significantly reducing the size of protocol parameters and increasing the cryptographic strength (computational complexity of the breaking).
Protecting the privacy of blockchain transactions is extremely important for users. Stealth address protocols (SAP) allow users to receive assets via stealth addresses that they do not associate with their stealth meta-addresses. SAP can be generated using different cryptographic approaches. DKSAP uses an elliptic curve multiplication and hashing of the resulting shared secret. Another approach is to use a elliptic curve pairing. This paper presents four SA protocols that use elliptic curve pairing as a cryptographic solution. ECPDKSAPs are pairing-based protocols that include viewing key and spending key, while ECPSKSAP is a pairing-based protocol that uses a single key with which spending and the viewing key are derived. We find that ECPDKSAPs give significantly better results than DKSAP with the view tag. The best results are achieved with Protocol 3 (Elliptic Curve Pairing Dual Key Stealth Address Protocol), which is Ethereum-friendly. ECPSKSAP is significantly slower, but it provides an interesting theoretical result as it uses only one private key.