Paper 2026/2398

Note on Extractability of PST Polynomial Commitment Scheme

Abstract

A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.