Double-Efficient ZkSNARKs Without Trusted Setup

Explore a groundbreaking zero-knowledge argument for NP in this IEEE Symposium on Security & Privacy presentation. Delve into the world of doubly-efficient zkSNARKs without trusted setup, offering low communication complexity and concrete costs for both prover and verifier. Discover how this novel approach, based on standard cryptographic assumptions, achieves communication proportional to d log G plus the square root of witness size. Learn about the prover's linear runtime and verifier's sub-linear runtime for batched or data-parallel statements. Examine a new commitment scheme for multilinear polynomials that allows for reduced witness-related communication. Understand the application of the Fiat-Shamir heuristic to create Hyrax, a zkSNARK in the random oracle model. Compare Hyrax's performance against five state-of-the-art baseline systems, revealing its advantages in proof size and computational efficiency. Gain insights into zkSNARK comparisons, cryptographic assumptions, efficiency metrics, and the design space of general-purpose proof systems. Explore proof machinery, commitment properties, interactive proofs, and various mathematical concepts crucial to understanding this innovative approach to zero-knowledge arguments.