Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time

István András Seres; Péter Burcsi

Paper 2023/670

Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time

István András Seres

, Eötvös Loránd University

Péter Burcsi

, Eötvös Loránd University

Abstract

Polynomial commitment schemes are fundamental building blocks in numerous cryptographic protocols such as verifiable secret sharing, zero-knowledge succinct non-interactive arguments, and many more. The most efficient polynomial commitment schemes rely on a trusted setup which is undesirable in trust-minimized applications, e.g., cryptocurrencies. However, transparent polynomial commitment schemes are inefficient (polylogarithmic opening proofs and/or verification time) compared to their trusted counterparts. It has been an open problem to devise a transparent, succinct polynomial commitment scheme or prove an impossibility result in the transparent setting. In this work, for the first time, we create a transparent, constant-size polynomial commitment scheme called Behemoth with constant-size opening proofs and a constant-time verifier. The downside of Behemoth is that it employs a cubic prover in the degree of the committed polynomial. We prove the security of our scheme in the generic group model and discuss parameter settings in which it remains practical even for the prover.

Note: Improved readability of proofs and made many corrections.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Polynomial Commitment Schemes KZG RSA class groups
Contact author(s): seresistvanandras @ gmail com
bupe @ inf elte hu
History: 2023-10-15: last of 2 revisions; 2023-05-11: received; See all versions
Short URL: https://ia.cr/2023/670
License: CC BY

BibTeX

@misc{cryptoeprint:2023/670,
      author = {István András Seres and Péter Burcsi},
      title = {Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time},
      howpublished = {Cryptology ePrint Archive, Paper 2023/670},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/670}},
      url = {https://eprint.iacr.org/2023/670}
}