https://crypto.iacr.org/2024/program.php
Aug 19-22
BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes
How to Prove Statements Obliviously?
Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
Greyhound: Fast Polynomial Commitments from Lattices
Concretely Efficient Lattice-based Polynomial Commitment from Standard Assumptions
Adaptively Secure Zero Knowledge SNARKs for UP
Adaptive Security in SNARGs via iO and Lossy Functions
Zero-knowledge IOPs Approaching Witness Length
FRIDA: Data Availability Sampling from FRI
STIR: Reed–Solomon Proximity Testing with Fewer Queries
Aggregating Falcon Signatures With LaBRADOR
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
More Efficient Zero-Knowledge Protocols over via Galois Rings
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions
Resettable Statistical Zero-Knowledge for NP
Non-Interactive Zero-Knowledge from LPN and MQ
Polymath: Groth16 Is Not The Limit
Field-Agnostic SNARKs from Expand-Accumulate Codes
Mangrove: A Scalable Framework for Folding-based SNARKs
HyperNova: Recursive arguments for customizable constraint systems
BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes
Hadas Zeilberger and Binyi Chen and Ben Fisch
https://eprint.iacr.org/2023/1705
This works introduces BaseFold, a new field-agnostic Polynomial Commitment Scheme (PCS) for multilinear polynomials that has verifier costs and prover time. An important application of a multilinear PCS is constructing Succinct Non-interactive Arguments (SNARKs) from multilinear polynomial interactive oracle proofs (PIOPs). Furthermore, field-agnosticism is a major boon to SNARK efficiency in applications that require (or benefit from) a certain field choice.
Our inspiration for BaseFold is the Fast Reed-Solomon Interactive-Oracle Proof of Proximity (FRI IOPP), which leverages two properties of Reed-Solomon (RS) codes defined over FFT-Friendly fields: encoding time, and a second property that we call foldability. We first introduce a generalization of the FRI IOPP that works over any foldable linear code in linear time. Second, we construct a new family of linear codes which we call random foldable codes, that are a special type of punctured Reed-Muller codes, and prove tight bounds on their minimum distance. Unlike RS codes, our new codes are foldable and have encoding time over any sufficiently large field. Finally, we construct a new multilinear PCS by carefully interleaving our IOPP with the classical sumcheck protocol, which also gives a new multilinear PCS from FRI.
BaseFold is 2-3 times faster than prior multilinear PCS constructions from FRI when defined over the same finite field. More significantly, using Hyperplonk (Eurocrypt, 2022) as a multilinear PIOP backend for apples-to-apples comparison, we show that BaseFold results in a SNARK that has better concrete efficiency across a range of field choices than with any prior multilinear PCS in the literature. Hyperplonk with Basefold has a proof size that is more than 10 times smaller than Hyperplonk with Brakedown and its verifier is over 30 times faster for circuits with more than gates. Compared to FRI, Hyperplonk with Basefold retains efficiency over any sufficiently large field. For illustration, with BaseFold we can prove ECDSA signature verification over the secp256k1 curve more than 20 times faster than Hyperplonk with FRI and the verifier is also twice as fast. Proofs of signature verification have many useful applications, including offloading blockchain transactions and enabling anonymous credentials over the web.
How to Prove Statements Obliviously?
Sanjam Garg and Aarushi Goel and Mingyuan Wang
https://eprint.iacr.org/2023/1609
Cryptographic applications often require proving statements about hidden secrets satisfying certain circuit relations. Moreover, these proofs must often be generated obliviously, i.e., without knowledge of the secret. This work presents a new technique called --- FRI on hidden values --- for efficiently proving such statements. This technique enables a polynomial commitment scheme for values hidden inside linearly homomorphic primitives, such as linearly homomorphic encryption, linearly homomorphic commitment, group exponentiation, fully homomorphic encryption, etc. Building on this technique, we obtain the following results.
An efficient SNARK for proving the honest evaluation of FHE ciphertexts. This allows for an efficiently verifiable private delegation of computation, where the client only needs to perform logarithmic many FHE computations to verify the correctness of the computation. An efficient approach for privately delegating the computation of zkSNARKs to a single untrusted server, without requiring the server to make any non-black-box use of cryptography. All prior works require multiple servers and the assumption that some subset of the servers are honest. A weighted threshold signature scheme that does not require any setup. In particular, parties may sample their own keys independently, and no distributed key generation (DKG) protocol is needed. Furthermore, the efficiency of our scheme is completely independent of the weights. Prior to this work, there were no known black-box feasibility results for any of these applications. We also investigate the use of this approach in the context of public proof aggregation. These are only a few representative applications that we explore in this paper. We expect our techniques to be widely applicable in many other scenarios.
Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
Valerio Cini and Giulio Malavolta and Ngoc Khanh Nguyen and Hoeteck Wee
https://eprint.iacr.org/2024/281
Polynomial commitment scheme allows a prover to commit to a polynomial of degree , and later prove that the committed function was correctly evaluated at a specified point ; in other words for public . Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree ) - with the latter being efficiently verifiable, and (ii) no pre-processing step is allowed.
Surprisingly, as far as plausibly quantum-safe polynomial commitments are concerned, the currently most efficient constructions only rely on weak cryptographic assumptions, such as security of hash functions. Indeed, despite making use of the underlying algebraic structure, prior lattice-based polynomial commitments still seem to be much behind the hash-based ones. Moreover, security of the aforementioned lattice constructions against quantum adversaries was never formally discussed.
In this work, we bridge the gap and propose the first (asymptotically and concretely) efficient lattice-based polynomial commitment with transparent setup and post-quantum security. Our interactive variant relies on the standard (Module-)SIS problem, and can be made non-interactive in the random oracle model using Fiat-Shamir transformation. In addition, we equip the scheme with a knowledge soundness proof against quantum adversaries which can be of independent interest. In terms of concrete efficiency, for our scheme yields proofs of size X smaller than the hash-based commitment (Block et al., Asiacrypt 2023), and X smaller than the very recent lattice-based construction by Albrecht et al. (Eprint 2023/1469).
Greyhound: Fast Polynomial Commitments from Lattices
Ngoc Khanh Nguyen and Gregor Seiler
https://link.springer.com/chapter/10.1007/978-3-031-68403-6_8
In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple -protocol for proving evaluations for polynomials of bounded degree with verifier time complexity . By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in ) that admits a sublinear verifier runtime. To highlight practicality of Greyhound, we provide implementation details including concrete sizes and runtimes. Notably, for large polynomials of degree at most , the scheme produces evaluation proofs of size 93KB, which is 8000X smaller than the recent lattice-based construction by Albrecht et al. (EUROCRYPT 2024), and three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023).
Concretely Efficient Lattice-based Polynomial Commitment from Standard Assumptions
Intak Hwang and Jinyeong Seo and Yongsoo Song
https://eprint.iacr.org/2024/306
Polynomial commitment is a crucial cryptographic primitive in constructing zkSNARKs. Most practical constructions to date are either vulnerable against quantum adversaries or lack homomorphic properties, which are essential for recursive proof composition and proof batching. Recently, lattice-based constructions have drawn attention for their potential to achieve all the desirable properties, though they often suffer from concrete inefficiency or rely on newly introduced assumptions requiring further cryptanalysis. In this paper, we propose a novel construction of a polynomial commitment scheme based on standard lattice-based assumptions. Our scheme achieves a square-root proof size and verification complexity, ensuring concrete efficiency in proof size, proof generation, and verification. Additionally, it features a transparent setup and publicly verifiability. When compared with Brakedown (CRYPTO 2023), a recent code-based construction, our scheme offers comparable performance across all metrics. Furthermore, its proof size is approximately 4.1 times smaller than SLAP (EUROCRYPT 2024), a recent lattice-based construction.
Adaptively Secure Zero Knowledge SNARKs for UP
Surya Mathialagan and Spencer Peters and Vinod Vaikuntanathan
https://eprint.iacr.org/2024/227
We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class in the reusable designated verifier model. is an expressive subclass of consisting of all languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm. Our main results are as follows.
A reusably and adaptively sound zero-knowledge (zk) dvSNARG for , from subexponential LWE and evasive LWE (a relatively new but popular variant of LWE). Our SNARGs achieve very short proofs of length bits for soundness error. A generic transformation that lifts any ``Sahai-Waters-like'' (zk) SNARG to an adaptively sound (zk) SNARG, in the designated-verifier setting. In particular, this shows that the Sahai-Waters SNARG for is adaptively sound in the designated verifier setting, assuming subexponential hardness of the underlying assumptions. The resulting SNARG proofs have length bits for soundness error. Our result sidesteps the Gentry-Wichs barrier for adaptive soundness by employing an exponential-time security reduction. A generic transformation that lifts any adaptively sound (zk) SNARG for to an adaptively sound (zk) SNARK for , while preserving zero-knowledge. The resulting SNARK achieves the strong notion of black-box extraction. There are barriers to achieving such SNARKs for all of from falsifiable assumptions, so our restriction to is, in a sense, necessary. Applying (3) to our SNARG for from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size These are the first SNARK constructions (even in the designated-verifier setting) for a non-trivial subset of from (sub-exponentially) falsifiable assumptions.
Adaptive Security in SNARGs via iO and Lossy Functions
Brent Waters and Mark Zhandry
https://eprint.iacr.org/2024/254
We construct an adaptively sound SNARGs in the plain model with CRS relying on the assumptions of (subexponential) indistinguishability obfuscation (iO), subexponential one-way functions and a notion of lossy functions we call length parameterized lossy functions. Length parameterized lossy functions take in separate security and input length parameters and have the property that the function image size in lossy mode depends only on the security parameter. We then show a novel way of constructing such functions from the Learning with Errors (LWE) assumption.
Our work provides an alternative path towards achieving adaptively secure SNARGs from the recent work of Waters and Wu. Their work required the use of (essentially) perfectly re-randomizable one way functions (in addition to obfuscation). Such functions are only currently known to be realizable from assumptions such as discrete log or factoring that are known to not hold in a quantum setting.
Zero-knowledge IOPs Approaching Witness Length
Noga Ron-Zewi and Mor Weiss
https://eprint.iacr.org/2024/816
Interactive Oracle Proofs (IOPs) allow a probabilistic verifier interacting with a prover to verify the validity of an NP statement while reading only few bits from the prover messages. IOPs generalize standard Probabilistically-Checkable Proofs (PCPs) to the interactive setting, and in the few years since their introduction have already exhibited major improvements in main parameters of interest (such as the proof length and prover and verifier running times), which in turn led to significant improvements in constructions of succinct arguments. Zero-Knowledge (ZK) IOPs additionally guarantee that the view of any query-bounded (possibly malicious) verifier can be efficiently simulated. ZK-IOPs are the main building block of succinct ZK arguments which use the underlying cryptographic object (e.g., a collision-resistant hash function) as a black box.
In this work, we construct the first ZK-IOPs approaching the witness length for a natural NP problem. More specifically, we design constant-query and constant-round IOPs for 3SAT in which the total communication is , where is the number of variables and is an arbitrarily small constant, and ZK holds against verifiers querying bits from the prover's messages, for a constant . This gives a ZK variant of a recent result of Ron-Zewi and Rothblum (FOCS 20), who construct (non-ZK) IOPs approaching the witness length for a large class of NP languages. Previous constructions of ZK-IOPs incurred an (unspecified) large constant multiplicative overhead in the proof length, even when restricting to ZK against the honest verifier. We obtain our ZK-IOPs by improving the two main building blocks underlying most ZK-IOP constructions, namely ZK codes and ZK-IOPs for sumcheck. More specifically, we give the first ZK-IOPs for sumcheck that achieve both sublinear communication for sumchecking a general tensor code, and a ZK guarantee. We also show a strong ZK preservation property for tensors of ZK codes, which extends a recent result of Bootle, Chiesa, and Liu (EC 22). Given the central role of these objects in designing ZK-IOPs, these results might be of independent interest.
FRIDA: Data Availability Sampling from FRI
Mathias Hall-Andersen and Mark Simkin and Benedikt Wagner
https://eprint.iacr.org/2024/248
As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain. Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents. As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available.
Data availability sampling, introduced by Bassam et al., is a process that allows light nodes to check the availability of data without download it. In a recent effort, Hall-Andersen, Simkin, and Wagner have introduced formal definitions and analyzed several constructions. While their work thoroughly lays the formal foundations for data availability sampling, the constructions are either prohibitively expensive, use a trusted setup, or have a download complexity for light clients scales with a square root of the data size.
In this work, we make a significant step forward by proposing an efficient data availability sampling scheme without a trusted setup and only polylogarithmic overhead. To this end, we find a novel connection with interactive oracle proofs of proximity (IOPPs). Specifically, we prove that any IOPP meeting an additional consistency criterion can be turned into an erasure code commitment, and then, leveraging a compiler due to Hall-Andersen, Simkin, and Wagner, into a data availability sampling scheme. This new connection enables data availability to benefit from future results on IOPPs. We then show that the widely used FRI IOPP satisfies our consistency criterion and demonstrate that the resulting data availability sampling scheme outperforms the state-of-the-art asymptotically and concretely in multiple parameters.
STIR: Reed–Solomon Proximity Testing with Fewer Queries
Gal Arnon and Alessandro Chiesa and Giacomo Fenzi and Eylon Yogev
https://eprint.iacr.org/2024/390
We present STIR (Shift To Improve Rate), a concretely efficient interactive oracle proof of proximity (IOPP) for Reed--Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. Roughly, in order to achieve bits of security, STIR has query complexity , while the popular FRI protocol (including variants based on conjectured security assumptions) has query complexity . STIR relies on a new technique for recursively reducing the degree of the function being tested while simultaneously improving the rate. We provide an implementation of STIR compiled to a SNARK. Compared to FRI, our implementation achieves an improvement in argument size that ranges from to depending on the chosen parameters. For example, in order to achieve 128 bits of security for degree and rate , STIR has argument size ~KiB, compared to ~KiB for FRI.
Aggregating Falcon Signatures With LaBRADOR
Marius A. Aardal and Diego F. Aranha and Katharina Boudgoust and Sebastian Kolby and Akira Takahashi
https://eprint.iacr.org/2024/311
Several prior works have suggested to use non-interactive arguments of knowledge with short proofs to aggregate signatures of Falcon, which is part of the first post-quantum signatures selected for standardization by NIST. Especially LaBRADOR, based on standard structured lattice assumptions and published at CRYPTO’23, seems promising to realize this task. However, no prior work has tackled this idea in a rigorous way.
In this paper, we thoroughly prove how to aggregate Falcon signatures using LaBRADOR. First, we improve LaBRADOR by moving from a low-splitting to a high-splitting ring, allowing for faster computations. This modification leads to some additional technical challenges for proving the knowledge soundness of LaBRADOR. Moreover, we provide the first complete knowledge soundness analysis for the non-interactive version of LaBRADOR. Here, the multi-round and recursive nature of LaBRADOR requires a complex and thorough analysis. For this purpose, we introduce the notion of predicate special soundness (PSS). This is a general framework for evaluating the knowledge error of complex Fiat-Shamir arguments of knowledge protocols in a modular fashion, which we believe to be of independent interest. Lastly, we explain the exact steps to take in order to adapt the LaBRADOR proof system for aggregating Falcon signatures and provide concrete estimates for proof sizes. Additionally, we formalize the folklore approach of obtaining aggregate signatures from the class of hash-then-sign signatures through arguments of knowledge.
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
https://eprint.iacr.org/2024/868
We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other symmetric-key-based post-quantum signature schemes that support stateless many-time signing. Notably, the performance of Loquat remains practical even when employing algebraic hash functions. Our Python-based implementations of Loquat demonstrate a signature size of 46KB, with a signing time of 5.04 seconds and a verification time of merely 0.21 seconds. Instantiating the random oracle with an algebraic hash function results in the R1CS constraints for signature verification being about 148K, 7 to 175 times smaller than those required for state-of-the-art MPC-in-the-head-based signatures and 3 to 9 times less than those for SPHINCS+ [Bernstein et al. CCS’19]. We explore two applications of Loquat. First, we incorporate it into the ID-based ring signature scheme [Buser et al. ACNS’22], achieving a significant reduction in signature size from 1.9 MB to 0.9 MB with stateless signing and practical master key generation. Our second application presents a SNARK-based aggregate signature scheme. We use the implementations of Aurora [Ben-Sasson et al. EC’19] and Fractal [Chiesa et al. EC’20] to benchmark our aggregate signature’s performance. Our findings show that aggregating 32 Loquat signatures using Aurora results in a proving time of about 7 minutes, a verification time of 66 seconds, and an aggregate signature size of 197 KB. Furthermore, by leveraging the recursive proof composition feature of Fractal, we achieve an aggregate signature with a constant size of 145 KB, illustrating Loquat’s potential for scalability in cryptographic applications.
More Efficient Zero-Knowledge Protocols over via Galois Rings
Fuchun Lin and Chaoping Xing and Yizhou Yao
https://eprint.iacr.org/2023/150
A recent line of works on zero-knowledge (ZK) protocols with a vector oblivious linear function evaluation (VOLE)-based offline phase provides a new paradigm for scalable ZK protocols featuring fast proving and small prover memory. Very recently, Baum et al. (Crypto'23) proposed the VOLE-in-the-head technique, allowing such protocols to become publicly verifiable. Many practically efficient protocols for proving circuit satisfiability over any Galois field are implemented, while protocols over rings are significantly lagging behind, with only a proof-of-concept pioneering work called Appenzeller to Brie (CCS'21) and a first proposal called Mozarella (Crypto'22). The ring or , though highly important (it captures computation in real-life programming and the computer architectures such as CPU words), presents non-trivial difficulties because, for example, unlike Galois fields , the fraction of units in is .
In this work, we first construct ZK protocols over a high degree Galois ring extension of (fraction of units close to ) and then convert them to efficiently using amortization techniques. Our results greatly change the landscape of ZK protocols over~.
We propose a competing ZK protocol that has many advantages over the state-of-the-art Mozarella. We remove the undesirable dependence of communication complexity on the security parameter, and achieve communication complexity strictly linear in the circuit size. Furthermore, our protocol has better concrete efficiency. For bits soundness on circuits over and , we offer -- improvements in communication. Inspired by the recently proposed interactive message authentication code technique (Weng et al., CCS'22), we construct a constant round ZK protocol over with sublinear (in the circuit size) communication complexity, which was previously achieved only over fields. We show that the pseudorandom correlation generator approach can be adapted to efficiently implement VOLE over Galois rings, with analysis of the hardness of underlying LPN assumptions over Galois rings. We adapt the VOLE-in-the-head technique to make it work for , yielding publicly verifiable non-interactive ZK protocols over which preserve most of the efficiency metrics of the VOLE-based ZK protocols.
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions
Noga Amit and Guy N. Rothblum
https://eprint.iacr.org/2024/850
What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations.
In this work we ask: what other tasks have efficient argument systems based only on one-way functions? We show two positive results:
First, we construct a new argument system for batch-verification of statements ( statements with a unique witness) for witness relations that are verifiable in depth . Taking to be the length of a single witness, the communication complexity is , where is an arbitrarily small constant. In particular, the communication is quasi-linear in the length of a single witness, so long as . The number of rounds is constant and the honest prover runs in polynomial time given witnesses for all inputs' membership in the language.
Our second result is a constant-round doubly-efficient argument system for languages in P that are computable by bounded-space Turing machines. For this class of computations, we obtain an exponential improvement in the trade-off between the number of rounds and the (exponent of the) communication complexity, compared to known unconditionally sound protocols [Reingold, Rothblum and Rothblum, STOC 2016].
Resettable Statistical Zero-Knowledge for NP
Susumu Kiyoshima
https://link.springer.com/chapter/10.1007/978-3-031-68400-5_9
Resettable statistical zero-knowledge [Garg--Ostrovsky--Visconti--Wadia, TCC 2012] is a strong privacy notion that guarantees statistical zero-knowledge even when the prover uses the same randomness in multiple proofs.
In this paper, we show an equivalence of resettable statistical zero-knowledge arguments for NP and witness encryption schemes for NP.
Positive result: For any NP language L, a resettable statistical zero-knowledge argument for L can be constructed from a witness encryption scheme for L under the assumption of the existence of one-way functions. Negative result: The existence of even resettable statistical witness-indistinguishable arguments for NP imply the existence of witness encryption schemes for NP under the assumption of the existence of one-way functions. The positive result is obtained by naturally extending existing techniques (and is likely to be already well-known among experts). The negative result is our main technical contribution. To explore workarounds for the negative result, we also consider resettable security in a model where the honest party's randomness is only reused with fixed inputs. We show that resettable statistically hiding commitment schemes are impossible even in this model.
Non-Interactive Zero-Knowledge from LPN and MQ
Quang Dao, Aayush Jain & Zhengzhong Jin
https://link.springer.com/chapter/10.1007/978-3-031-68400-5_10
We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random underdetermined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and Jain (ePrint 2024), together with exponentially-hard MQ.
The main technical ingredient of our construction is an extremely natural (but only in hindsight!) construction of correlation-intractable (CI) hash functions from MQ, for a NIZK-friendly sub-class of constant-degree polynomials that we call concatenated constant-degree polynomials. Under exponential security, this hash function also satisfies the stronger notion of approximate CI for concatenated constant-degree polynomials. The NIZK construction then follows from a prior blueprint of Brakerski-Koppula-Mour (CRYPTO 2020). In addition, we also show how to construct (approximate) CI hashing for degree- polynomials from the (exponential) hardness of solving random degree- equations, a natural generalization of MQ. To realize NIZK with statistical zero-knowledge, we design a lossy public-key encryption scheme with approximate linear decryption and inverse-polynomial decryption error from Dense-Sparse LPN. These constructions may be of independent interest.
Our work therefore gives a new way to leverage MQ with uniformly random equations, which has found little cryptographic applications to date. Indeed, most applications in the context of encryption and signature schemes make use of structured variants of MQ, where the polynomials are not truly random but posses a hidden planted structure. We believe that the MQ assumption may plausibly find future use in the designing other advanced proof systems.
Polymath: Groth16 Is Not The Limit
Helger Lipmaa
https://link.springer.com/chapter/10.1007/978-3-031-68403-6_6
Shortening the argument of the Groth16 zk-SNARK for R1CS (three group elements or 1536 / 3072 bits over the BLS12381/BLS24-509 curves) is a long-standing open problem. We propose a zk-SNARK Polymath for the Square Arithmetic Programming constraint system using the KZG polynomial commitment scheme. Polymath has a shorter argument (1408 / 1792 bits over the same curves) than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security future applications. We also handle public inputs in a simple way. We optimized Polymath's prover through an exhaustive parameter search. Polymath's prover does not output elements, aiding in batch verification, SNARK aggregation, and recursion. Combined with a linear-time prover zk-SNARK, like in zkBridge or Testudo, Polymath maintains linear-time proving.
Field-Agnostic SNARKs from Expand-Accumulate Codes
Alexander R. Block, Zhiyong Fang, Jonathan Katz, Justin Thaler, Hendrik Waldner & Yupeng Zhang
https://link.springer.com/chapter/10.1007/978-3-031-68403-6_9
In recent years, efficient realizations of succinct non-interactive arguments of knowledge (SNARK) have gained popularity due to their practical applications in various domains. Among existing schemes, those based on error-correcting codes are of particular interest because of their good concrete efficiency, transparent setup and plausible post-quantum security. However, many existing code-based SNARKs suffer from the disadvantage that they only work on specific finite fields due to the use of the Reed-Solomon code and the fast Fourier transform algorithm.
In this work, we construct a code-based SNARK that does not rely on specific underlying fields; i.e., it is field-agnostic. Our construction follows the framework of Brakedown (CRYPTO '23) and builds a polynomial commitment scheme (and hence a SNARK) by utilizing a new family of linear codes built from the recent expand-accumulate codes (CRYPTO '22). Our work generalizes these codes to operate over any finite field, and our main technical contribution is showing that, with high probability, these codes have constant rate and constant relative distance on any field, solving an open problem left in the previous paper.
These properties are crucial to build efficient SNARKs. To prove a statement of size , the prover time of our SNARK is , and the proof size is . We demonstrate the concrete efficiency of our scheme empirically in the experiments. When proving the ECDSA verification on curve secp256k1, it only takes 0.23s to generate the proof, 2 orders of magnitude faster than SNARKs that are not field-agnostic. Comparing to Brakedown which is also field-agnostic, our proof size is 1.9--3.3 smaller due to the good distance of the error-correcting code, while introducing only a small overhead of 1.2 on the prover time.
Mangrove: A Scalable Framework for Folding-based SNARKs
Wilson Nguyen and Trisha Datta and Binyi Chen and Nirvan Tyagi and Dan Boneh
https://eprint.iacr.org/2024/416
We present a framework for building efficient folding-based SNARKs. First we develop a new "uniformizing" compiler for NP statements that converts any poly-time computation to a sequence of identical simple steps. The resulting uniform computation is especially well-suited to be processed by a folding-based IVC scheme. Second, we develop two optimizations to folding-based IVC. The first reduces the recursive overhead of the IVC by restructuring the relation to which folding is applied. The second employs a "commit-and-fold'' strategy to further simplify the relation. Together, these optimizations result in a folding based SNARK that has a number of attractive features. First, the scheme uses a constant-size transparent common reference string (CRS). Second, the prover has (i) low memory footprint, (ii) makes only two passes over the data, (iii) is highly parallelizable, and (iv) is concretely efficient. Microbenchmarks indicate that proving time is competitive with leading monolithic SNARKs, and significantly faster than other streaming SNARKs. For () gates, the Mangrove prover is estimated to take minutes ( hours) with peak memory usage approximately MB ( MB) on a laptop.
HyperNova: Recursive arguments for customizable constraint systems
Abhiram Kothapalli and Srinath Setty
https://eprint.iacr.org/2023/573
We introduce HyperNova, a new recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023/552), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. HyperNova makes four contributions, each resolving a major problem in the area of recursive arguments. First, it provides a folding scheme for CCS where the prover’s cryptographic cost is a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme. The folding scheme can fold multiple instances at once, making it easier to build generalizations of IVC such as PCD. Second, when proving program executions on stateful machines (e.g., EVM, RISC-V), the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step (“a la carte” cost profile). Third, we show how to achieve zero-knowledge for “free” and without the need to employ zero-knowledge SNARKs. Fourth, we show how to efficiently instantiate HyperNova over a cycle of elliptic curves. For this, we provide a general technique, which we refer to as CycleFold, that applies to all modern folding-scheme-based recursive arguments.
