Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits Based on Isogenies
Zero-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.
2-s2.0-85190704657
University of Birmingham
The University of Auckland
Université Libre de Bruxelles
École Polytechnique Fédérale de Lausanne
University of Birmingham
2024
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 14459 LNCS
1611-3349
0302-9743
221
243
REVIEWED
EPFL
| Event name | Event acronym | Event place | Event date |
Goa, India | 2023-12-10 - 2023-12-13 | ||