Paper 2022/702

Kevlar: Transparent, Efficient, Polynomial Commitment Scheme with Logarithmic Verification and Communication Costs on Efficient Groups

Abstract

We introduce a new efficient, transparent setup, polynomial commitment scheme that runs on efficient groups with logarithmic verifier and communication costs. Existing group based polynomial commitment schemes must run on costly groups such as class groups with unknown order or pairing based groups to achieve transparency (no trusted setup), making them slow in practice, and non-group based schemes such as Reed-Soloman based schemes has its own set of pros and cons compared to group based schemes. We offer the first group based polynomial commitment scheme that does not rely on expensive pairing based groups or class groups with unknown order to achieve transparency while still providing logarithmic verifier and communication costs. While the asymptotic performance of our protocol is comparable to the current state of art, its concrete verifier and communication costs are about one order of magnitude more efficient than the current state of art schemes. The asymptotic costs of our new transparent scheme is dominated by $3n \,\mathbb{G}$ exponential prover cost, 3 log $n \, \mathbb{G}$ exponential verifier cost and 3 log $n \, \mathbb{G}$ communication cost. Running with one thread and evaluating a polynomial of $n=2^{20}$ degree terms, the verifier cost of our protocol is $\approx 2.5 ms$, and the communication cost is $\approx 2 KB$, giving approximately 11X and 9X improvement over the current state of art.

Note: While there is only one author for the paper, the key concepts of this has already been reviewed by 3 peers. While this is the first release of the paper, we expect immediate practical benefits to zero knowledge protocol implementations in the blockchain world.