TY - GEN
T1 - DAG- Σ
T2 - 28th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2022
AU - Zeng, Gongxian
AU - Lai, Junzuo
AU - Huang, Zhengan
AU - Wang, Yu
AU - Zheng, Zhiming
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - At CRYPTO 1994, Cramer, Damgå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- Σ protocol) for k-CNF relations (in the discrete logarithm setting), by converting these relations to directed acyclic graphs (DAGs). Our DAG- Σ protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.’s general method.
AB - At CRYPTO 1994, Cramer, Damgå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- Σ protocol) for k-CNF relations (in the discrete logarithm setting), by converting these relations to directed acyclic graphs (DAGs). Our DAG- Σ protocol achieves less communication cost and smaller computational overhead compared with Cramer et al.’s general method.
KW - Conjunctive normal form
KW - Directed acyclic graph
KW - Disjunctive normal form
KW - Proof of partial knowledge
KW - Sigma protocol
UR - https://www.scopus.com/pages/publications/85148022333
U2 - 10.1007/978-3-031-22966-4_12
DO - 10.1007/978-3-031-22966-4_12
M3 - 会议稿件
AN - SCOPUS:85148022333
SN - 9783031229657
T3 - Lecture Notes in Computer Science
SP - 340
EP - 370
BT - Advances in Cryptology – ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Agrawal, Shweta
A2 - Lin, Dongdai
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 5 December 2022 through 9 December 2022
ER -