Two round ZKIP of knowledge for SAT and its applications

Abstract

This paper proposes the optimal 4-move ZKIP (Zero-Knowledge Interactive Proof systems) of knowledge for SAT and its application. Using the trapdoor bit commitment scheme and the WI(Witness Indistingushable) and the WH(Witness Hiding), it is shown that as compared with 6-move ZKIP for SAT, the proposed ZKIP is 4-move ZKIP for SAT and under claw-free pairs of functions the proposed ZKIP is also 4-move ZKIP. The proposed scheme is more efficient at the points of computational complexity and communication complexity.