Paper 2026/284

Knowledge Soundness of Polynomial Commitments in the Algebraic Group Model Does Not Guarantee Extractability

Abstract

The Algebraic Group Model (AGM) has become a standard framework for analyzing the knowledge soundness of group-based polynomial commitment schemes. In this work, we formally establish inherent limitations of this methodology. We isolate a structural property satisfied by essentially all practical group-based polynomial commitments, which we term AGM-clarity. We prove that for AGM-clear schemes, evaluation binding implies knowledge soundness in the AGM. This collapse reveals that the AGM definition of knowledge soundness does not capture a distinct security property, but is merely a structural consequence of evaluation binding. To precisely characterize the guarantees on extractability provided by the AGM, we introduce Weak Interpolation Knowledge Soundness (WIKS) in the standard model, which is an extreme relaxation of extractability. We show that WIKS is implied by standard evaluation binding and prove that, for AGM-clear schemes, knowledge soundness in the AGM is equivalent to WIKS. We further reformulate WIKS as Correct-Interpolation Binding and use this binding-style characterization to establish that, for binding polynomial commitments, special soundness is strictly stronger than WIKS. Together, these results calibrate AGM knowledge soundness for practical polynomial commitment schemes against two standard-model notions: for AGM-clear schemes, it is already implied by evaluation binding, while for binding schemes, it remains strictly weaker than special soundness. In particular, AGM proofs of knowledge soundness do not certify "knowledge" in the sense of immediate extractability.

Note: Added a separation between AGM knowledge soundness and computational special soundness for polynomial commitments, using a separation of Külaots et al. (EUROCRYPT 2026), along with minor editorial improvements.