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

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.

Available format(s)
Cryptographic protocols
Publication info
Polynomial Commitment SchemesKZGRSAclass groups
Contact author(s)
seresistvanandras @ gmail com
bupe @ inf elte hu
2023-10-15: last of 2 revisions
2023-05-11: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.