Welcome to the resource topic for 2023/1710
Title:
Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies
Authors: Mingjie Chen, Yi-Fu Lai, Abel Laval, Laurane Marco, Christophe Petit
Abstract: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 (JACM’91), 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 (Eurocrypt’22). 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 consider three representations: arithmetic circuits, rank-1 constraint systems and branching programs.
This work gives the first attempt at constructing a post-quantum generic proof system from isogeny assumptions (the group action DDH problem).
Though the resulting proof systems are linear in the circuit size, they possess interesting features such as non-interactivity, statistical zero-knowledge, and online-extractability.
ePrint: https://eprint.iacr.org/2023/1710
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .