Chen, MingjieLai, Yi FuLaval, AbelMarco, LauranePetit, Christophe2025-01-262025-01-262025-01-25202410.1007/978-3-031-56232-7_112-s2.0-85190704657https://infoscience.epfl.ch/handle/20.500.14299/245067Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments. In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt’22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs.falsecommitmentsgeneric zero-knowledge proof of knowledgegroup actionisogeny-based cryptographypost-quantum cryptographytext::conference output::conference proceedings::conference paper