Paper 2022/1569

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

Gongxian Zeng, Peng Cheng Laboratory
Junzuo Lai, College of Information Science and Technology, Jinan University
Zhengan Huang, Peng Cheng Laboratory
Yu Wang, Peng Cheng Laboratory
Zhiming Zheng, Institute of Artificial Intelligence, LMIB, NLSDE, Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Beihang University
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2022
Keywords
Sigma protocol Proof of partial knowledge Conjunctive normal form Directed acyclic graph Disjunctive normal form
Contact author(s)
gxzeng @ cs hku hk
laijunzuo @ gmail com
zhahuang sjtu @ gmail com
wangy12 @ pcl ac cn
zzheng @ pku edu cn
History
2022-11-11: approved
2022-11-11: received
See all versions
Short URL
https://ia.cr/2022/1569
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1569,
      author = {Gongxian Zeng and Junzuo Lai and Zhengan Huang and Yu Wang and Zhiming Zheng},
      title = {DAG-$\Sigma$: A DAG-based Sigma Protocol for Relations in CNF},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1569},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1569}},
      url = {https://eprint.iacr.org/2022/1569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.