Sumcheck-Based zkSNARKs are Non-malleable

Abstract

Simulation extractability ensures that any adversary who produces a valid proof must possess a corresponding witness, even after seeing simulated proofs for potentially false statements. This property is vital for preventing malleability attacks and is therefore essential for securely deploying zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) in distributed systems. While prior work, particularly the frameworks by Faonio et al. (CCS’24, TCC’23) and Kohlweiss et al. (TCC’23), has established simulation extractability for a wide class of pairing-based zkSNARKs using the KZG univariate polynomial commitment scheme (Kate et al., Asiacrypt’10), we initiate a systematic study of simulation extractability for zkSNARKs based on the celebrated sumcheck protocol and the PST multivariate polynomial commitment scheme (Papamanthou et al., TCC’13). PST cannot be simulation extractable, due to its linear homomorphism, however, we show that it satisfies a refined notion of controlled malleability similar to the notion of Chase et al. (EUROCRYPT’12), which informally captures that linear homomorphism is essentially the only admissible malleability. We demonstrate that our notion of controlled malleability suffices to ensure security within the widely adopted design paradigm of compiling polynomial interactive oracle proofs into zkSNARKs, covering several state-of-the-art schemes such as HyperPlonk (EUROCRYPT’23), Spartan (CRYPTO’20) and Libra (CRYPTO’19).