On the Security of KZG Commitment for VSS
Open Access
- 15 November 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 2561-2575
Abstract
The constant-sized polynomial commitment scheme by Kate, Zaverucha, and Goldberg (Asiscrypt 2010), also known as the KZG commitment, is an essential component in designing bandwidth-efficient verifiable secret-sharing (VSS) protocols. We point out, however, that the KZG commitment is missing two important properties that are crucial for VSS protocols. First, the KZG commitment has not been proven to be degree binding in the standard adversary model without idealized group assumptions. In other words, the committed polynomial is not guaranteed to have the claimed degree, which is supposed to be the reconstruction threshold of VSS. Without this property, shareholders in VSS may end up reconstructing different secrets depending on which shares are used. Second, the KZG commitment does not support polynomials with different degrees at once with a single setup. If the reconstruction threshold of the underlying VSS protocol changes, the protocol must redo the setup, which involves an expensive multi-party computation known as the powers of tau setup. In this work, we augment the KZG commitment to address both of these limitations. Our scheme is degree-binding in the standard model under the strong Diffie-Hellman (SDH) assumption. It supports any degree 0 < d ≤ m under a powers-of-tau common reference string with m+ 1 group elements generated by a one-time setup.Keywords
Funding Information
- National Science Foundation (2240976)
This publication has 29 references indexed in Scilit:
- Constant-Size Commitments to Polynomials and Their Applications2010
- On expected constant-round protocols for Byzantine agreementJournal of Computer and System Sciences, 2009
- Perfectly-Secure MPC with Linear Communication Complexity2008
- Scalable and Unconditionally Secure Multiparty Computation2007
- Robust Multiparty Computation with Linear Communication Complexity2006
- Short Signatures from the Weil Pairing2001
- Secure Distributed Key Generation for Discrete-Log Based Cryptosystems1999
- Efficient dispersal of information for security, load balancing, and fault toleranceJournal of the ACM, 1989
- Authenticated Algorithms for Byzantine AgreementSIAM Journal on Computing, 1983
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960