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 $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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2021
Keywords
zero knowledgepublic-key cryptography
Contact author(s)
jlee @ nanotronics co
History
2021-11-18: revised
2020-10-14: received
See all versions
Short URL
https://ia.cr/2020/1274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1274,
      author = {Jonathan Lee},
      title = {Dory: Efficient, Transparent arguments for Generalised Inner Products and Polynomial Commitments},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1274},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1274}},
      url = {https://eprint.iacr.org/2020/1274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.