Paper 2020/1274

Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments

Jonathan Lee

Abstract

This paper presents Dory, a transparent setup, public-coin interactive argument for proving correctness of an inner-pairing product between committed vectors of elements of the two source groups. For an inner product of length $n$, proofs are $6\log n$ target group elements, $1$ element of each source group and $3$ scalars. Verifier work is dominated by an $O(\log n)$ multi-exponentiation in the target group. Security is reduced to the symmetric external Diffie Hellman assumption in the standard model. We also show an argument reducing a batch of two such instances to one, requiring $O(n^{1/2})$ work on the Prover and $O(1)$ communication. We apply Dory to build a multivariate polynomial commitment scheme via the Fiat-Shamir transform. For $$ the product of one plus the degree in each variable, Prover work to compute a commitment is dominated by a multi-exponentiation in one source group of size $$. Prover work to show that a commitment to an evaluation is correct is $$ in general and $$ for univariate or multilinear polynomials, whilst communication complexity and Verifier work are both $$. Using batching, the Verifier can validate $$ polynomial evaluations for polynomials of size at most $$ with $$ group operations and $$ field operations.