Perfect Zero-Knowledge Argument of Knowledge with Negligible Error Probability in Two-Round for NP from Any One-Way Permutation

Abstract

Based on the interactive proof of Hamiltonian Cycle (HC) of large directed graph, which is a $\Sigma$-protocol, we construct a perfectly hiding and computationally binding trapdoor commitment in 2-round from any one-way permutation. Then, based on this trapdoor commitment, we construct perfect zero-knowledge argument of knowledge with negligible error probability in 2-round for $\mathcal{NP}$, assuming only the existence of a one-way permutation.