Welcome to Pulse Check by @HouseofZK, your trusted source for the latest developments, insights, and analysis in the zero-knowledge field. Each edition of this report examines the cutting-edge advancements shaping the industry, with this particular edition focusing on the standout research papers introduced into the Cryptology ePrint Archive throughout July and August 2024, with highlights including optimizations to sum-check proving, succinct non-subsequence arguments, simplified constructions for designated-verifier zk-SNARKs, enhancing recursive zkVMs with lower prover costs, and much more.
Succinct Non-Subsequence Arguments, by San Ling, Khai Hanh Tang, Khu Vu, Huaxiong Wang and Yingfei Yan: Cryptology ePrint
This work introduces the first succinct non-subsequence argument, a cryptographic technique for proving that one sequence is not a subsequence of another. This concept has applications across several fields, including DNA sequence analysis, blockchains, and natural language processing. The authors leverage the sumcheck protocol in combination with multivariate polynomial commitment schemes (PCSs) to achieve efficient proof generation. Their construction results in a succinct proof system where prover time is linear in the size of the sequences, and verification time is sublinear. These advances improve the efficiency of proving non-subsequence relationships, expanding potential applications for cryptographic verification in complex computational tasks.
Designated-Verifier zk-SNARKs Made Easy by Chen Li and Fangguo Zhang: Cryptology ePrint
This paper by Chen Li and Fangguo Zhang simplifies the construction of designated-verifier zk-SNARKs, a proof system where only the verifier with a specific secret can verify the proof. The approach leverages the efficiency of Fiat-Shamir transformations and improves security guarantees for applications such as secure auditing or identity verification where privacy is critical. The paper introduces optimizations that reduce proof size and complexity, making it easier to implement zk-SNARKs in real-world systems.
LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems by Dan Boneh and Binyi Chen: Cryptology ePrint
LatticeFold introduces a novel folding protocol built on lattice-based cryptography, specifically leveraging the Module SIS problem. This new approach is designed to offer post-quantum security for recursive SNARKs, unlike many existing schemes that rely on traditional homomorphic commitment schemes vulnerable to quantum attacks.
LatticeFold is highly versatile, supporting both low-degree relations like R1CS and high-degree relations such as CCS. The folding protocol ensures that witnesses maintain a low norm across multiple rounds of folding, which is critical for efficient performance. Additionally, by operating over smaller fields (e.g., 64-bit fields), LatticeFold provides performance comparable to state-of-the-art pre-quantum folding schemes like Hypernova while offering future-proof, post-quantum security.
This protocol’s design also allows for integration with existing optimizations used in fully homomorphic encryption (FHE) and lattice signature schemes, benefiting from potential software and hardware accelerations in those fields.
TaSSLE: Lasso For The Commitment-phobic by Daniel Dore: Cryptology ePrint
TaSSLE is a novel lookup argument designed to minimize commitment costs in decomposable tables, a challenge in cryptographic proofs. It extends the Lasso technique, allowing large table lookups without the need for full table commitments. This is particularly relevant for applications such as zero-knowledge virtual machines (zkVMs). TaSSLE can be integrated with existing lookup arguments to reduce overhead, providing a more efficient proof system. Its applications are broad, including new strategies for scalable zkVM designs.
More Optimizations to Sum-Check Proving by Quang Dao and Justin Thaler: Cryptology ePrint
Quang Dao and Justin Thaler's paper focuses on improving the efficiency of the sum-check protocol, a critical component in several SNARK constructions. The protocol is often applied to a polynomial of the form g(x)=eq(w,x)⋅p(x)g(x) = \text{eq}(w, x) \cdot p(x)g(x)=eq(w,x)⋅p(x), where p(x)p(x)p(x) is a product of multilinear polynomials. Their optimization significantly reduces the number of field multiplications required during the prover step, particularly improving efficiency when working over large prime-order fields.
Their work builds upon previous optimizations from researchers such as Gruen and further introduces methods that can speed up the prover by 25% in typical use cases. This improvement is particularly impactful in binary tower fields, where further computational savings are realized, making this approach useful for various SNARK-based applications.
Jolt-b: Recursion Friendly Jolt With Basefold Commitment by Hang Su, Qi Yang, Zhenfei Zhang: Cryptology ePrint
Jolt-b extends the Jolt zkVM by introducing a recursion-friendly feature using the Basefold commitment scheme. This extension allows the zkVM to achieve recursive proof generation while maintaining efficiency. Compared to other recursion-friendly variants like Zeromorph and HyperKZG, Jolt-b demonstrates significant speed improvements, offering a 1.24x and 1.52x faster prover time, respectively.
By leveraging the Basefold scheme and operating over the Goldilocks field, Jolt-b achieves recursion compatibility with lower prover costs, opening up new possibilities for large-scale zkVM deployments where recursion is crucial for scalability and performance.
AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities by Vlasis Koutsos, Sankarshan Damle, Dimitrios Papadopoulos, Sujit Gujar and Dimitris Chatzopoulos: Cryptology ePrint
AVeCQ introduces a modular framework for anonymous verifiable crowdsourcing, addressing challenges like worker anonymity while maintaining verifiable worker qualities. This system is designed for crowdsourcing environments where task requesters need reliable input while ensuring that workers' privacy and anonymity are protected. AVeCQ leverages cryptographic primitives to ensure that workers' submissions are unlinkable across tasks, promoting user privacy.
The system outperforms current state-of-the-art solutions in tasks like image annotation and average review, with significant speed improvements (up to 40%) while maintaining verification and blockchain transaction integrity. AVeCQ is particularly suited for decentralized platforms, and it demonstrates notable efficiency gains when prototyped over Ethereum.
VerITAS: Verifying Image Transformations at Scale by Trisha Datta, Binyi Chen and Dan Boneh: Cryptology ePrint
VerITAS is a system designed to verify transformations applied to large-scale images, specifically addressing image provenance. The system is significant in contexts like news media, where verifying the authenticity of edited images is crucial. Using zk-SNARKs, VerITAS allows users to prove that specific edits were made to a signed image without revealing the original content.
VerITAS supports image sizes up to 90 MB, handling large datasets more efficiently than prior work. For low-powered devices, like cameras, VerITAS generates proofs in under an hour, while on more capable systems, the process takes less than five minutes. Verification takes only two seconds in a browser. The system broadens the applications of zk-SNARKs, enabling scalable proof systems for verifying transformations of private data.
A Crack in the Firmament: Restoring Soundness of the Orion Proof System and More by Thomas den Hollander and Daniel Slamanig: Cryptology ePrint
This paper addresses a critical flaw in the Orion proof system, a post-quantum zero-knowledge argument system with linear prover time. Orion, while being efficient, was found to have soundness vulnerabilities under certain conditions. The authors present a solution to restore soundness in the Orion system and provide additional improvements that enhance its robustness against quantum attacks.
Their approach reinforces the zero-knowledge properties while maintaining efficiency, improving the proof system's practical use for large computations. They also introduce optimizations that reduce proof size and verification complexity, making Orion more scalable and better suited for real-world applications.
On the Concrete Security of Non-interactive FRI by Alexander R. Block and Pratyush Ranjan Tiwari: Cryptology ePrint
This paper provides a thorough security analysis of Non-Interactive FRI (Fast Reed-Solomon Interactive Oracle Proof), a protocol commonly used as the backbone for many efficient SNARK systems. The authors examine the Fiat-Shamir transformation for FRI, a critical step for ensuring its security in non-interactive settings. Their analysis highlights the importance of selecting the right parameters to optimize security without compromising on performance.
The results underscore FRI's security in real-world deployments where it secures millions of dollars in transactions, and the work contributes to building stronger confidence in FRI-based cryptographic protocols.
Trust Nobody: Privacy-Preserving Proofs for Edited Photos with Your Laptop by Pierpaolo Della Monica, Ivan Visconti, Andrea Vitaletti and Marco Zecchini: Cryptology ePrint
This paper introduces a system that enables users to prove that a digital image has undergone specific, authorized edits - such as cropping or resizing - without revealing the original image. The approach is designed to run efficiently on a standard laptop, even for high-resolution images. The privacy-preserving proof system ensures that confidential images can remain private while still providing verifiable guarantees about the transformations applied. This makes it particularly valuable for journalism, legal evidence, or digital content verification.
Garuda and Pari: Faster and Smaller SNARKs via Equifficient Polynomial Commitments, by Michel Dellepere, Pratyush Mishra and Alireza Shirzad: Cryptology ePrint
This research presents two new SNARK constructions: Pari and Garuda, which address the dual challenges of reducing proof size and speeding up proof generation. Pari stands out with the smallest known SNARK proof size - just 160 bytes using the BLS12-381 curve - beating existing schemes like Groth16 and Polymath. Garuda focuses on improving proof generation time, introducing support for arbitrary custom gates and free linear gates, significantly reducing prover-time costs. Both systems rely on the innovative "equifficient" polynomial commitment schemes, enforcing consistent polynomial representation across different bases. These advances position both Pari and Garuda at the cutting edge of SNARK performance.
Improved Polynomial Division in Cryptography, by Kostas Kryptos Chalkias, Charanjit Jutla, Jonas Lindstrom, Varun Madathil and Arnab Roy: Cryptology ePrint
This work addresses a key efficiency challenge in cryptographic systems, particularly in SNARKs and polynomial commitments like Groth16 and KZG. Polynomial division, a core operation in these systems, typically requires O(nlogn)O(n \log n)O(nlogn) time using Fast Fourier Transforms (FFTs). The authors propose a unified approach that improves upon existing methods for polynomial division, offering significant speedups in computation.
Their method introduces novel conjugate representations and leverages l'Hôpital's rule to handle edge cases in division, providing more efficient implementations of these cryptographic protocols. Benchmarks show a 2x speedup for KZG commitments and a modest 2-3% improvement for Groth16 proofs compared to existing implementations, while also allowing support for larger circuits without increasing group sizes. These advancements are applicable to a wide range of cryptographic protocols, making polynomial division more scalable and efficient.
zk-Promises: Making Zero-Knowledge Objects Accept the Call for Banning and Reputation: by Maurice Shih, Michael Rosenberg, Hari Kailad and Ian Miers: Cryptology ePrint
zk-Promises is a privacy-preserving framework designed to handle anonymous state updates while ensuring accountability. It allows asynchronous operations such as banning, reputation docking, or state changes, crucial for applications like forums or access-controlled environments. The framework enables interactions with private client states stored in zk-objects, with updates secured by zkSNARKs to ensure integrity and confidentiality. zk-Promises supports features like asynchronous reputation updates and reputation-dependent rate limiting, which help protect against attacks like Sybil. Its innovative approach balances privacy and accountability in decentralized systems, making it a practical solution for complex access control and reputation management.
Efficient Zero-Knowledge Arguments for Paillier Cryptosystem, by Borui GONG, Wang Fat Lau, Man Ho Au, Rupeng Yang, Haiyang Xue and Lichun Li: Cryptology ePrint
This paper presents a novel zero-knowledge argument system tailored to the Paillier cryptosystem, focusing on improving efficiency in proof size, verification costs, and supporting batch proof generation and verification. Unlike traditional systems that suffer from large proof sizes and linear verification times, this approach achieves sublinear proof size and significantly reduces the computational overhead, particularly when handling large numbers of Paillier ciphertexts. The paper reports substantial performance improvements, such as a 17-fold reduction in proof size and a 3x speed-up in verification times in certain batch scenarios. This makes it particularly well-suited for data-heavy applications like analytics.
Mova: Nova Folding Without Committing to Error Terms, by Nikolaos Dimitriou, Albert Garreta, Ignacio Manzur and Ilia Vlasov: Cryptology ePrint
Mova is an improvement over Nova's folding scheme, particularly in the sphere of R1CS (Rank-1 Constraint System) proofs. The main innovation is that Mova eliminates the need to commit to error and cross terms, typically required in Nova, by using Multilinear Extension (MLE) evaluations instead. This results in Mova’s prover being 5-10 times faster than Nova and slightly faster than Hypernova under reasonable parameters, while maintaining similar verifier costs but with fewer communication rounds. Mova's design is well-suited for use cases like incremental verifiable computation (IVC) and proof-carrying data (PCD), which benefit from its efficient folding operations. It also introduces a new language for describing folding schemes, offering insights into how to further optimize prover performance and reduce computational overheads.
Proximity Gaps in Interleaved Codes, by Benjamin E. Diamond and Angus Gruen: Cryptology ePrint
This paper investigates the concept of proximity gaps in the context of linear error-correcting codes, particularly interleaved codes. A proximity gap occurs when each affine line of words in a code either contains words that are close to the code or none at all. The authors extend this concept to interleaved codes, demonstrating that codes with proximity gaps in their unique decoding radius retain this property even when interleaved. This result is particularly relevant to Reed-Solomon codes, where proximity gaps play an important role in error correction and data recovery. Their findings have applications in coding theory and cryptography, providing more efficient error correction techniques for certain classes of codes.
Safe Curves for Elliptic-Curve Cryptography, by Daniel J. Bernstein and Tanja Lange: Cryptology ePrint
The paper by Daniel J. Bernstein and Tanja Lange provides a comprehensive survey on the selection of elliptic curves that are secure for cryptographic use. The authors discuss not only the mathematical security concerns such as discrete logarithm attacks but also the practical pitfalls that can arise during implementation. They emphasize the importance of choosing curves that are resistant to a broad spectrum of attacks, including those that exploit side-channel vulnerabilities. The paper forms part of a larger effort to standardize "safe curves" that provide strong security assurances in public-key cryptography applications.
Hekaton: Horizontally-Scalable zkSNARKs via Proof Aggregation by Michael Rosenberg, Tushar Mopuri, Hossein Hafezi, Ian Miers and Pratyush Mishra: Cryptology ePrint
Hekaton introduces a novel framework for horizontally scaling zkSNARKs by breaking large computations into smaller chunks, allowing them to be processed in parallel across multiple nodes. This "distribute-and-aggregate" approach enables faster and more efficient zkSNARK generation for large-scale applications, addressing the traditional performance bottlenecks of zkSNARKs in terms of time and space complexity.
The key innovation in Hekaton is its ability to aggregate these chunk proofs into a single, succinct proof, while ensuring that shared data between chunks is efficiently handled. The system demonstrates strong scalability, achieving linear performance improvements as the number of nodes increases. Notably, Hekaton can process computations involving 2352^{35}235 gates in under an hour, making it faster than previous zkSNARK solutions.
Hekaton's application in real-world scenarios, such as verifiable key directories and RAM computation proofs, shows significant efficiency gains, enabling zkSNARKs to handle more practical, large-scale workloads.
HyperPianist: Pianist with Linear-Time Prover via Fully Distributed HyperPlonk, by Chongrong Li, Yun Li, Pengfei Zhu, Wenjie Qu and Jiaheng Zhang: Cryptology ePrint
HyperPianist builds on the scalability and efficiency challenges faced by SNARK-based proof systems, specifically focusing on large circuit computations. It improves upon previous systems like Pianist by distributing the proof generation process across multiple machines, significantly reducing prover time. HyperPianist leverages the HyperPlonk framework and enhances it with linear-time prover complexity, and logarithmic communication costs. The system is designed to handle large-scale applications by distributing computation and minimizing overhead during the proof generation process. The system's improvements make it particularly useful for scenarios requiring extensive computations, while also providing a more efficient lookup argument method via the integration of Lasso, a lookup argument protocol.
Stackproofs: Private Proofs of Stack and Contract Execution Using Protogalaxy, by Liam Eagen, Ariel Gabizon, Marek Sefranek, Patrick Towa and Zachary J. Williamson: Cryptology ePrint
"Stackproofs" presents a new approach for creating private proofs of contract execution, building on the zk-SNARK framework used in the Aztec protocol. The authors propose a model called "Repeated Computation with Global state" (RCG), which extends the concept of Incrementally Verifiable Computation (IVC) by allowing for global consistency checks across computations while maintaining space efficiency. This construction offers enhanced privacy and efficiency for smart contract systems. The use of Protogalaxy enables more streamlined proof generation, which can improve performance in private blockchain environments.
Non-Interactive Zero-Knowledge from LPN and MQ, by Quang Dao, Aayush Jain and Zhengzhong Jin: Cryptology ePrint
This research introduces the first non-interactive zero-knowledge (NIZK) arguments based on post-quantum assumptions, specifically Learning Parity with Noise (LPN) and Multivariate Quadratic (MQ) equations. Unlike previous constructions relying on Learning with Errors (LWE), this work leverages the hardness of random under-determined MQ equations and introduces new cryptographic tools such as correlation-intractable hash functions and lossy public-key encryption schemes. This approach could expand the applications of MQ-based assumptions in advanced cryptographic proof systems, particularly in post-quantum security contexts.
We endeavor to keep you up-to-date with the biggest developments in ZK, and you can stay connected with @HouseofZK by exploring our in-depth articles, detailed project reports, and be the first to know about our upcoming events and podcast releases.
We hope you’ve found this edition of Pulse Check useful, and thank you for being part of our journey. We’ve checked the pulse, and we definitively declare that ZK is very much alive!
Your feedback is essential for the growth and relevance of our reports, and we encourage readers to suggest topics and projects for future editions, or to directly contribute their insights and articles.
This information was curated by the House of ZK team - if you see any errors or believe there are important updates missing, please email contact@hozk.io with your feedback.
