Welcome to the resource topic for 2022/1569
Title:
DAG-\Sigma: A DAG-based Sigma Protocol for Relations in CNF
Authors: Gongxian Zeng, Junzuo Lai, Zhengan Huang, Yu Wang, Zhiming Zheng
Abstract:At CRYPTO 1994, Cramer, Damg{\aa}rd and Schoenmakers proposed a general method to construct proofs of knowledge (PoKs), especially for k-out-of-n partial knowledge, of which relations can be expressed in disjunctive normal form (DNF). Since then, proofs of k-out-of-n partial knowledge have attracted much attention and some efficient constructions have been proposed. However, many practical scenarios require efficient PoK protocols for partial knowledge in other forms.
In this paper, we mainly focus on PoK protocols for k-conjunctive normal form (k-CNF) relations, which have n statements and can be expressed as follows: (i) k statements constitute a clause via OR'' operations, and (ii) the relation consists of multiple clauses via AND’’ operations. We propose an alternative Sigma protocol (called DAG-\Sigma protocol) for k-CNF relations (in the discrete logarithm setting), by converting these relations to directed acyclic graphs (DAGs). Our DAG-\Sigma protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.'s general method.
ePrint: https://eprint.iacr.org/2022/1569
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 .