**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 $n$ 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 $n$. Prover work to show that a commitment to an evaluation is correct is $O(n^{\log 8 / \log 25})$ in general and $O(n^{1/2})$ for univariate or multilinear polynomials, whilst communication complexity and Verifier work are both $O(\log n)$. Using batching, the Verifier can validate $\ell$ polynomial evaluations for polynomials of size at most $n$ with $O(\ell + \log n)$ group operations and $O(\ell \log n)$ field operations.

**Category / Keywords: **cryptographic protocols / zero knowledge, public-key cryptography

**Date: **received 12 Oct 2020

**Contact author: **jlee at nanotronics co

**Available format(s): **PDF | BibTeX Citation

**Version: **20201014:182037 (All versions of this report)

**Short URL: **ia.cr/2020/1274

[ Cryptology ePrint archive ]