## CryptoDB

### Paper: DAG-$\Sigma$: A DAG-based Sigma Protocol for Relations in CNF

Authors: Gongxian Zeng , Peng Cheng Laboratory Junzuo Lai , Jinan University Zhengan Huang , Peng Cheng Laboratory Yu Wang , Peng Cheng Laboratory Zhiming Zheng , Beihang University Search ePrint Search Google Slides ASIACRYPT 2022 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-$\Sigmaup$ protocol) for $k$-CNF relations, by turning these relations into directed acyclic graphs (DAGs). Our DAG-$\Sigmaup$ protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.'s general method.
##### BibTeX
@inproceedings{asiacrypt-2022-32504,
title={DAG-$\Sigma$: A DAG-based Sigma Protocol for Relations in CNF},
publisher={Springer-Verlag},
author={Gongxian Zeng and Junzuo Lai and Zhengan Huang and Yu Wang and Zhiming Zheng},
year=2022
}